6.19 LispE isn't exactly your granny's Lisp

If there's one thing all the LISPs haunting 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)

Linked lists

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

Head

But there are a few peculiarities to this representation. For example, if you use the "push" instruction in Common Lisp, the new value is added to the head of the list.

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

I can already hear the teeth grinding together of the distinguished Lispians who see this as nothing more than a very normal and honest thing to do. And I owe them this reply: "You're right". If the language was designed that way, it's up to the user to make a minimum effort to get used to it.

On the other hand, for a Python user, this way of doing things is very surprising. Indeed, let's note two little things that may offend the delicate soul of Pythonians, even if in the eyes of Lispians any user of another language and python in particular is a brute whose thick mind cannot conceive the surreal beauty of delicately intertwined parentheses.

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.

Direct access

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.

Once again, a Lispian proud of his art won't mind. But for people used to cruder languages, the first attempts may not be optimal.

Let's take a random example: Python

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.

Python: the panacea?

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.

Combine the two?

So how can LispE offer a combination of both approaches?

Allowing Python-style direct access to elements while retaining the ability to access sub-chains 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 a shift 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
       shift = l->shift + 1;
    }

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