I find myself working with DSLs quite a bit, and thus I write a few parsers. Some languages are better than others for parsers and pattern matching is a technique that makes writing parsers a true joy. I will not go over the basics of pattern matching here, rather show how F#’s active patterns can be used to take pattern matching to the next level.

The traditional steps of a “parser” are roughly lexical analysis (tokenizer), syntactic analysis (parser) and then evaluator (interpreter). In this post we’ll focus on the parsing step of a simple DSL. A parser typically consume a list of tokens and produces an Abstract Syntax Tree (AST), ready to be passed on the evaluator/interpreter.

If you give someone Fortran, he has Fortran.

If you give someone Lisp, he has any language he pleases.

– Guy Steele

Replace Fortran with whatever language you are currently using, and the quote still holds true today. Lisp has been around for a long time, and it’s built-in flexibility is still unmatched by other languages. In this post we will look at key Lisp concepts such as code-is-data and powerful macro semantics.

I recently looked into Tail Call Optimisation/Elimination (TCO) and the implications for 3 modern languages, namely F#, Clojure and Scala. In this post I share my findings. If you’re new to the subject or just looking into some of these languages I hope this post can be of some use to you. I will mix code snippets in the 3 languages freely (and without warning! :)

TCO is a well documented topic in books and articles about functional programming, and the TCO in .NET and the lack thereof in the JVM has been debated “to death” on various programmers’ boards. I don’t intend to add any fuel to the fire here, rather some background and practical implications.

This article serves as a follow-up to my previous post on symbolic execution, which can be found here. In this article, we will delve deeper into the details of KLEE and LLVM, discussing a potential practical application for a symbolic executor. We will also address some limitations and drawbacks associated with this approach.

If you’re interested in the changes we made for KLEE and LLVM, you can find them on GitHub.

One limitation of symbolic execution, as well as dynamic code analysis in general, is that the code under analysis needs to be buildable and linkable. Consequently, it is more challenging to analyze subsystems or code snippets compared to using a lint tool. Another complication arises from the fact that the symbolic executor’s virtual machine must also comprehend and model the system calls used by the code. This makes the tool OS-dependent, as it requires emulating all calls that “escape” the executor. Cadar, Dunbar, and Engler explain how this can be achieved for Linux by analyzing GNU coreutils in [1].

GNU and Richard Stallman were a real catalyst for the open source movement and its crown jewel: the Linux kernel. Not only did Mr. Torvalds’ early Linux releases had nearly 100% GNU “user-land”, he also decided to release it under the GNU Public License (GPL). GNU and Stallman are forever linked with the birth and popularization of open source, and innovated both technically and legally by turning copyright laws on their head with the copyleft licenses. The Free Software Foundation, the custodians of the GPL, is a constant source of spicy statements about the state of the software industry.

When people think about .NET development, they think of C#. Sure there are other languages (VB, ASP.NET etc) but .NET and C# are very tightly linked (just drop an .NET assembly in reflector for technical proof). If you’re writing a new Windows application (and it’s not a high performant game), chances are you are reading WPF books right now.

One of the promises of .NET when it was released was “the great language independent” runtime, making all these languages interoperate in joyful bliss. Technically this still holds, but in practice it’s all about C#.

Given the fact that I worship at the SICP altar, it should come as no surprise that I follow the recipe outlined in chapter 4 of said book; implementing a Scheme interpreter in every language I am trying to learn. Over the years it has turned out to be a very useful exercise, since the problem is just “big enough” to force me to drill into what the languages have to offer.

A while back, I had the opportunity to collaborate with my colleague, Philippe Gabriel, on a research project focused on automating defect finding and enhancing overall test coverage. Our primary concern at the time was null pointer dereferences, which had the potential to cause system-wide crashes. In our quest, we explored various strategies and tools, both free and commercial. However, what truly captured our interest was a fascinating area of research called “Symbolic execution.” Imagine having a tool that could automatically identify critical bugs in your source code with minimal or no false positives, while also generating input stimuli to trigger those bugs.

Having gained experience through numerous software projects and collaborations with diverse individuals, I’ve observed a recurring issue: a lack of understanding regarding the nature and process of software development. Surprisingly, even among developers, there persists a belief that seniority alone enables one to design and plan a problem, leaving less experienced developers to implement it. Some individuals still equate software development to assembly line production in the automotive industry.

In chapter 1 of “Structure and Interpretation of Computer Programs” SICP, Abelsson and Sussman describe a concept they call the “sorcerer’s spirit”

Let’s begin with an inspiring quote from my favorite book on computer programming, “Structure and Interpretations of Computer Programs” (SICP) by Abelson and Sussman.

Underlying our approach to this subject (computer programming) is our conviction that “computer science” is not a science and that its significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology – the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of “what is”. Computation provides a framework for dealing precisely with notions of “how to”.

Read more...