Version française

If there's one thing all the LISPs lurking in the net have in common, it's the following methods: cons, car, cdr and list. These methods allow you to construct and manipulate linked lists.

(cons 'a '(b c)) ; (a b c)
(list 'a 'e '(f g)) ; (a e (f g))
(car '(a b c)) ; a
(cdr '(a b c)) ; '(b c)

These lists are at the heart of the language, giving it its flexibility and elegance.

However, this representation has a few quirks. For example, if you use the "push" instruction in Common Lisp, the new value is added at the head of the list.

(setq r '(A B C D))
(push 'v r) ; (V A B C D)

For a Python user, this way of doing things is very surprising. Indeed, let's note two things that Lispians find pretty normal but makes the transition to this language quite complicated for a Pythonista.

First, the push instruction, which adds the value at the head of the list. The reason is simple: it's much more efficient to build a new cell that points to the first cell in the list. Adding the value at the end of the list means you have to go through the whole list to find out where to hang the cars.

The second, more anecdotal point is that the modified variable is the last argument of the instruction. Those who designed Common Lisp considered the way the expression reads in English to provide a syntax. We push an element into a list.

The second constraint arising from the choice of a linked list is that we can't jump directly to a particular cell. We have to traverse the list, carefully counting down each cell, to get to the right one.

Common Lisp does offer the instruction: "nth nb", but in reality it merely hides a list traversal bounded by a counter.

I'm obviously using Python as an example, because it's one of the best-known languages today. Python was one of the first languages to systematize the use of dynamic arrays. Now, it's interesting to note that there's a similarity between the two languages, which I doubt is accidental. Indeed, LISP and Python share many points in common, if we set aside their very different formalisms. Variables are declared on the fly by assigning them a value, and lists and arrays play a major role.

The car and cdr instructions, which retrieve the first element of a list or the continuation of a list, are present in Python in a very simple form.

Just compare:

(setq l '(1 2 3))
(car l) ; 1
(cdr l) ; (2 3)

with:

l = [1,2,3]
l[0] # 1
l[1:] # [2,3]

I don't want to get into trouble, but I strongly suspect that Mr. Van Rossum drew some inspiration from the LISP language.

Some will argue that there aren't a thousand ways of accessing list elements. True, but Python's flexibility in this area brings it close to, and even, dare we say, surpasses LISP in its ease of manipulating lists, even if these are in the form of an array.

This is where Lispians will point out something quite fundamental: unlike Python, LISP's cdr simply returns a pointer to the next cell relative to the root.

In other words, a cdr doesn't create a new list, it simply points to the next element, whereas Python will create a new list each time. In the case of Common Lisp, you must explicitly ask the language to duplicate this list with the copy-list function.

In this case, Common Lisp offers greater flexibility than Python by allowing the main list to be duplicated or not.

In principle, each approach has its advantages and disadvantages.

So how can LispE offer a combination of both approaches?

Allowing Python-style direct access to elements while retaining the ability to access sub-lists without unnecessary duplication.

The answer is quite simple...

We've built LispE around a Python-style dynamic array... But with a little extra to keep LISP's flexibility...

If we look at the diagram above, we can immediately see that a LispE list is in fact made up of two distinct classes.

Here's the corresponding C++ code (much simplified):

class ARRAY {
   //A dynamic array
   vector<Element*> table;

   Element* at(int pos) {
     return table[pos];
   }
}

class LIST {
    ARRAY* array;
    int offset;

    //The basic list
    LIST() {
      offset = 0;
      array = new ARRAY;
    } 

    //Each time an element is accessed, the offset is added
    Element* operator[](int pos) {
      return array->at(offset + pos);
    }
};

What happens when we request the cdr of a list?

It's very simple: we create an object of type LIST which will share the same array, but with an offset incremented by 1...

    //The constructor called in case of cdr
    LIST(LIST* l) {
       //share the same array
       array = l->array;
       // but now shifted by 1
       offset = l->offset + 1;
    }

    //Call our cdr method, which will call the above constructor
    Element* cdr() {
      return new LIST(this);
    }

Consequently, the cdr will create a new LIST element, but without duplicating the array itself. This retains both the flexibility of Python - array is a dynamic array - and the flexibility of LISP when performing a cdr.

We also retain the possibility of direct access to an element of the array via nth.

In fact, compared with a linked list, which generally contains 3 pointers, one to the value, one to the next cell and one to the previous cell, the memory cost is very reasonable.

List traversal now boils down to iterating over an array with an index. While the traditional functions have been retained, their implementation has been transformed. Whereas, for reasons of efficiency, Common Lisp adds elements at the head, here the most efficient addition is at the tail. On the other hand, adding elements at the head is permitted, but requires moving the elements to the right to free up the first square.

Finally, I recently had a discussion with someone who claimed that porting certain APL instructions to LispE was heresy. While these instructions are not suitable for linked lists, they are obviously applicable to arrays. And this is where the hybrid aspect of this structure becomes really interesting (see: APL).

For example, here's how to apply the inner product in LispE to calculate the multiplication of two matrices:

(. '((1 2) (5 4) (3 0)) '+ '* '((6 2 3 4) (7 0 1 8)))

which gives:

((20 2 5 20) (58 10 19 52) (18 6 9 12))

The final point on which LispE differs from Common Lisp is the deliberate choice to place the receiving variable in the 2nd position, after the operator or function name.

(setq r '(a b c d))
(push r 'e)

This is because LispE syntax, like all LISPs, can be understood as a form of Abstract Syntax Tree.

        push
        /  \
       r   quote
              \
               e

The brackets are then used to express the different levels of this tree.

The other reason is a little more subtle. Take the equivalent example in Python: r.append("e"). The corresponding tree is:

       append
        /  \
       r   "e"

In fact, the choice of systematically placing the variable to be modified in the second position also stems from the fact that push can be considered not as a function, but as a method attached to the r list.

In other words, while LispE is a functional language, the choice to place the recipient variable in the 2nd position obeys a kind of underlying OOP philosophy. Functions can be reinterpreted as methods associated with particular types.

(setq r '(1 2 3 4 5))

(push r 'v) ; (1 2 3 4 5 v)
(extract r 1 3) ; gives (2 3)
(pop r 1) ; gives (1 3 4 5 v)

(setq s "abcdef")
(find s "bc") ; gives 1

In this way, the position of the arguments is systematically normalized to reinforce the link between the variable and the method modifying it. This syntax also has the advantage of easing the transition between a language like Python to LispE. All you have to do is place at the top what in Python is considered a method.

You may find this choice somewhat trivial, but as we showed in the blog on transpilation, this arrangement of arguments also makes it easier to use LispE as an interpreter for new languages.

As such, LispE has been designed to facilitate the transition to a very rich functional language compatible with either a C++, Python or WASM environment, with performance well ahead of Python.

The choices we made were motivated both by reasons of flexibility and performance, but also by the idea of standardizing certain aspects of the language to offer an easier-to-use platform for people with a background in imperative languages.