Version française

Lisp is not dead. For a language born at the end of the 50's, this is a happy but also very surprising fact. The success of Clojure or the remarkable resistance of Common Lisp represent a kind of anomaly in a world dominated by javascript and Python... By the way, javascript is in fact a Lisp in disguise.

Well, Lisp is not dead, and since the proof has to be in the pudding, we will show how our own LispE interpreter was implemented.

But the question can be asked, how does a prefixed language, drowned in parentheses, still attract so much interest?

Lisp is not only one of the oldest languages still in use, but also one of the very first functional languages ever invented.

Lisp is homoiconic. That is, the language is stored in the form of lists, which are also a basic data structure of the language. This makes the language extraordinarily malleable, as this example shows.

Finally, there are few programming languages as easy to implement as Lisp.

There are two very paradoxical reasons for this.

Let's take an aspect of the language that often stings the eyes of newbies: the infamous parentheses that the language seems to abuse. Yes, Lisp uses these parentheses heavily and they sometimes make the language a bit obscure. But as Lisp programmers often point out, this is a bit of an illusion:

(sin 10); Lisp
sin(10); Other language

Before we embark on yet another defense of the language along the lines of: parentheses in Lisp are great, but only insiders can understand them. Let's notice a second element that often confuses those who learn the language: in Lisp everything is prefixed.

Here we have the two most common complaints: parentheses and prefixed notation. And to top it all off, we also have our answer to what makes building a Lisp interpreter a bit of an easy ride. Well, compared to other languages, that is.

So here is this strange paradox which makes the highly parenthetized prefixed form of Lisp both the reason for rejecting the language but also for its simplicity to create interpreters to run it.

And all this is based on a fundamental notion in compilation theory: the abstract syntax tree.

One of the most important steps, when compiling a sequence of instructions in a language like Python or C++, is to reduce everything to trees.

The reason for this is very simple, a tree is the best way to express the relationships that the different objects have with each other in a program:

toto=10 + a-20

Generally, a compiler or interpreter takes the above expression and puts it through a series of transformations:

• tokenization
• reorganization in the form of a tree via a formal grammar (BNF)

Tokenization as its name indicates consists in cutting the string into as many autonomous units (tokens):

toto=10 + a-20 # becomes: toto,=,10,+,a,-,20

This operation in Lisp is even easier than in a language like Python. Indeed, in most languages, tokenisation is done along the operators, spaces are rarely enough.

In Lisp, tokenisation is reduced to identifying parentheses and spaces.

(setq toto (- (+ 10 a) 20)); becomes (,setq,toto,(,-,(,+,10,a,),20,),) 

But above all, the fundamental difference is the construction of the tree. If we take our Python expression, the corresponding tree is as follows:

                 =
               /   \
             toto   -
                   / \
                  +  20
                 / \
                10  a

This is the result of applying a grammar that might look like this:

assignment :: name = expression|variable
expression :: value|variable operator variable|expression

We will now perform a prefixed walk:

= toto - + 10 a 20

We will add parentheses to this prefixed walk, as follows, each non-terminal subtree will be injected between parentheses:

(=)
(= toto)
(= toto (-))
(= toto (- (+)))
(= toto (- (+ 10)))
(= toto (- (+ 10 a)))
(= toto (- (+ 10 a) 20))

So, this parenthetical representation is in every way similar to Lisp. And this is not by chance.

McCarthy's initial project consisted in integrating into Fortran symbolic expressions strongly inspired by Church's lambda-calculus theory: the M-expressions. However, it soon turned out that the intermediate step called S-expressions was much simpler to implement.

If we add that the construction and application of grammars to reconstruct such a tree is far from trivial, we quickly understand how much the Lisp expressions avoid to a designer all the heavy architecture of traditional languages.

Finally, let's add that the systematic prefixed representation for operators and functions also greatly simplifies code compilation.

Remember for example that in Python, calling a function or writing a mathematical expression obey different rules. We are so used to manipulating these expressions, that we forget that this difference in syntax has a cost:

toto = 10 + a - 20
titi = sin(a)

Indeed, we need different entry points in our grammar to understand each of these expressions.

If we compare these expressions to Lisp:

(setq toto (- (+ 10 a) 20))
(setq titi (sin a))

You can immediately see the difference, in Lisp everything is a function, including operators. Thus, the compilation of numerical expressions or function calls is unified in the same formalism.

In a way, Lisp forces the user to do some of the compilation work, where other languages apply heavy grammars to build these S-expressions. But, it also removes many ambiguities that sometimes lead to bugs.

Just compare:

toto = 10 - 2 * 10

with the unambiguous form:

(setq toto (- 10 (* 2 10))

The other advantage of Lisp is that there is no need to invent different programming styles to integrate new features.

Python offers particularly striking examples of this:

fruits = ["apple", "pear", "banana", "strawberry"]
v = [x for x in fruits if "a" in x]

Note that we have chosen Python as our comparison language, because it has the advantage of being simple and popular. Remember that most of these remarks could be applied to languages like C++ or Java.

Thanks to its syntactic uniformity, Lisp does not need to reinvent the wheel to implement the above example:

Here is how we could translate this expression into LispE:

(setq fruits '("apple" "pear" "banana" "strawberry"))
(setq v (filterlist (λ(x) (in x "a")) fruits))

As we can see, the syntax remains the same.

Moreover, if we stay in the realm of legend, when engineers were asked to produce, in a few days, a new language for the Web, their first version looked like Lisp. Which the managers disliked, so they were asked to correct their copy, which gave the version of javascript that we know today.

The interest of Lisp is that it makes it possible to experiment with new operators or new features without having to re-implement the language grammar each time. Many concepts in computer science, starting with object programming, started with implementations in Lisp.

As I said before, Lisp is a philosophy. It is a way of representing and executing programs in an intermediate form between man and machine. The S-expressions offer a very elegant way of representing code and data in the same syntax.

Could this be used in other languages?

I program in C++.

I know that the language has a bad reputation and some people advised me to switch to Rust. But, after 30 years of practice, I feel I have a certain familiarity with a language whose performances are no longer to be demonstrated.

Because of course, when you make your own interpreter, you expect a certain efficiency in terms of compilation and execution. C++ allows you to tickle the processor at the edge of the metal while manipulating very high level abstractions. But the price to pay is sometimes quite heavy, because the language is tortuous and often tricky, not to say deceitful.

The purpose of this blog is to show how one can build a Lisp interpreter in C++, which is directly inspired by the functional philosophy of Lisp.

It's like putting the code into a programmatic abyss in a way...

First of all, let's start with a banality: whether you practice functional programming or any other form of programming, your program will end up as machine code with lots of jumps in all corners.

I know, it's sad but that's the way it is. It's a bit like seeing a painting by a great Renaissance master. From a distance, it looks smooth and shiny, when you get closer, you see the brush strokes.

Anything you can program in one general purpose language, you must be able to program in another general purpose language. This is the conclusion of the famous Turing paper where he explains that his machine and Alonzo Church's lambda-calculus are equivalent.

Without this equivalence, functional languages could not exist.

This does not mean that these languages are useless, on the contrary, we can reach programs of a rare sobriety and solidity within this paradigm. But basically, they exist because they can be compiled in an imperative form.

But conversely, the most powerful functional concepts can also be transcribed into more traditional languages:

long factorial(long x) {
 if (x==1)
    return 1;
 else
    return x * factorial(x - 1);

In other words, we can design a C++ programming which is inspired by Lisp.

And it has some advantages...

The basic representation of Lisp, the one that has always defined the language and that lies at the heart of its name is the list (LISP = LIST Processing).

There are many ways to create lists in C++, but for now we will settle for the simplest form available: vector.

However, and this is obviously the heart of the matter, a vector in C++ can only be declared for a given type:

std::vector<Element*> elements;

However, a list in Lisp can hold any type of elements, including values, operators and function calls.

For our vector to offer the same flexibility, experienced readers will have immediately guessed that it is sufficient that all objects in the language derive from the Element class.

Thus, if we derive from Element, an Operator class or an Integer class, we will be able to store operators or integers in the same structure. If moreover, we derive the List class from Element, we can then build embedded representations without any limit.

There is just one missing element to complete our description: each derived class will have to override its own Eval method.

In the case of an integer or a string, this method will return the element itself, for a function or an operator, their Eval method will perform the corresponding execution.

Here is, for example, the main execution loop of a program:

Element* v = null_;
for (const auto& e : elements) {
   v->release()
   v = e->Eval();
}

return v;

Note the release method which cleans up the element when it is not used within a variable or a container. The life cycle of a data structure is based on the use of a reference counter. When this counter has the value 0, release cleans up this structure.

Let's take a closer look at this Eval function:

We first initialize v with the value null_, a constant value that cannot be destroyed. Thus, calling release here will have no effect on this variable at the entry of the loop.

Then we call the Eval method for each of the elements of the vector whose result is stored in v.

And this is where things get interesting. Each value in the interpreter is associated with a reference counter which increases by 1 when that value is stored in a variable or container. When a function is called that returns a result, two things can happen:

• The value comes from the application of a function
• The value was returned by a variable or a container

Now if we look closely at the loop, we see that the value of v is systematically released at each iteration, except for the last statement in elements. For values saved in a variable or a container, the call of this function has no impact. For the others, it destroys them or saves them in data pools.

This mode of operation is directly inspired by functional programming:

Each function returns one and only one value whose life cycle is decided locally.

If this value is not saved in a variable or in a container, it will be released in the loop at the next iteration, otherwise it will be returned.

Note that release means that the value is either destroyed or stored in a value pool for later reuse.

In Lisp, this is exactly what a function call does:

; the last line will return the final calculation
(defun calculus(x)
  (setq x (* x 2))
  (+ x 1)
)

What is fundamental in this approach is that the management of the returned values is purely local, there are no side effects. More exactly, if the value is not saved in any structure, its release in this loop can be done without any problem, it will have no impact elsewhere in the code.

Organizing the code in this way makes it possible to control step by step the life cycle of all data structures in memory. At each stage of the execution, data structures that are not stored in variables or containers can be safely released, even if the execution is done in a thread.

Thus, in the execution of: (* 10 (+ 20 1) (- 15 1)), the intermediate values (+ 20 1) or (- 15 1) will be used by the multiplication but released at the end:

long value = 1;
Element* v;
for (Element* e : elements) {
   v = e->Eval();
   value *= v->asNumber();
   v->release();
}

return new Integer(value);

The above loop for example performs the multiplication of the integers in elements. At each iteration, the v that come from an intermediate calculation, are released.

Thus, we make sure that at each step, nothing is left in the memory space. Note that the final result of this loop is an intermediate object which can also be destroyed when calling this function.

The other fundamental aspect of this architecture is that the objects, corresponding to instructions, are by definition immutable. In other words, the same object can be executed as many times as necessary without it ever being modified.

Finally, the execution of these instructions is done outside a virtual machine, since each object necessarily knows how to execute.

Thus, we find in this approach, the fundamental properties of functional programming.

• Everything is a function call (here reduced to an Eval call for each object)
• Immutability of objects
• No side effects.

This mechanism makes it very easy to create independent threads which can execute the same functions in parallel. In fact, you only need to launch the Eval function on an object for it to run.

This is the most important difference with more traditional methods where instructions are translated into pseudo-code and executed by a virtual machine. For example, Python can only execute one virtual machine at a time, which restricts the possibility of writing threads, since they are all executed in the same space protected by the famous GIL (Global Interpreter Lock). Python can execute threads but one at a time.

Note that in our case, threads arguments are always duplicated at launch, which removes any needs to protect data from concurrent access. However, we still provide a mechanism to make it possible to share some values across threads.

On the other hand, object programming simplifies a lot some aspects that are sometimes very complex to master. For example, the addition of objects of different types is a very difficult problem to manage and Python is no exception to the rule, just have a look at the implementation of __add__ to be convinced.

(+ 10 20 30) ; returns an integer
(+ 10.1 2.109) ; returns a float

In our case, this problem is actually very simple to solve.

The Element class contains the list of basic numerical methods of the language:

virtual Element* plus(Element* e);
virtual Element* minus(Element* e);
virtual Element* multiply(Element* e);
virtual Element* divide(Element* e);    

So for the Integer, Floating or String classes, you just have to overload them to get the desired behavior.

As we said before, our implementation is based on the use of a vector of elements. This element vector has the following form:

std::vector<Elements*> list;

Taking our example again: (+ 10 20 30), it could be compiled into the following form:

list: [Operator(+), Integer(10), Integer(20), Integer(30)]

Operator and Integer are instances of classes derived from: Element.

Let's override the plus method in our Index class:

class Integer : public Element {
public:
  long value;

  Element* plus(Element* e) {
     long v = value;
     v += e->asInteger();
     return new Integer(v);
  }

  long asInteger() {
     return value;
  }
};

The plus method makes it possible to set the behavior of the addition for a particular type of object. Now we have to define the + operator within a list.

This gives us the method: eval_plus below:

   Element* List::eval_plus() {
        //The element in position 0 is actually our "plus" operator.
        //We get the first element of our list of instructions at position 1
        Element* r = list[1]->Eval();
        Element* v;
        Element* inter;
        for (long i = 2; i < size(); i++) {
          v = list[i]->Eval();
          inter = r->plus(v);
          v->release();
          if (r != inter) {
             r->release();
             r = inter;
          }
        }
        return r;
   }

Note that the first data item (in position 1) will define the type of addition desired. Thus, if the list starts with an integer, the result will be a sum of integers at the end of the analysis. In the case of a string, it will be a concatenation.

The first element of the list (at position 0) is therefore the operator: Operator(+). So we can easily imagine a mechanism, for example a switch/case that makes it possible to launch this particular method:

Element* List::Eval() {
   switch (list[0]->label()) {
     case l_cons:
          return eval_cons();
     ...
     case l_plus:
        return eval_plus();
}

So, each time the Eval method is executed from a List object, we will be able to execute the function placed at position 0 in our list.

And here is where the whole operation is revealed. If an instance in the list is an atomic value, Eval will return the instance itself. If, on the other hand, it is a list, we will recursively call the method above which will return the corresponding result.

This representation corresponds point by point to our list in Lisp. We just have to launch Eval from the root of this list to execute our whole program.

Extending the language is simply a matter of deriving the Element class and overloading the corresponding necessary methods. Thus, if we create a Date class, we will be able to define an addition or a subtraction specific to date management.

First, I want to stress how efficient the interpreter produced with this method is, as illustrated with this experiment.

Some people might complain that Lisp is too much of a niche language to engage in the effort of understanding how it was implemented. However, what is really important in this article is that, if you create your own syntax and implement a grammar to turn it into a tree, you can use the underlying interpreter code in C++ without any real modification. In fact, we have also implemented another programming language: TAMGU탐구, which follows the same philosophy and still implements a language that is very similar to Python.

Lisp might sound like some old language lost in the dark age of computer science, but when you implement a Lisp interpreter, what you actually create is a universal interpreter, which can run many of the programming languages in the world...

All you need is a tree...

And that's very cool, indeed...