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)These lists are at the heart of the language, giving it its flexibility and elegance.
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.
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.
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-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 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 chained 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 internal 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.