English Version

S'il fallait donner un point commun à l'ensemble des LISPs qui hantent les tréfonds des internets, ce sont les méthodes suivantes: cons, car, cdr et list. Ces méthodes permettent de construire et de manipuler des listes chainées.

(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)

Ces listes sont au coeur du langage, elles lui offrent sa souplesse et son élégance.

Mais, cette représentation présente quelques particularités. Par exemple, si l'on utilise l'instruction «push» dans Common Lisp, la nouvelle valeur est rajoutée en tête de la liste.

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

Pour un utilisateur de Python, cette façon de faire est très surprenante. En effet, notons deux choses que les Lispiens considèrent on ne peut plus normal, mais qui laisse les Pythonistes quelque peu perplexe.

D'abord, l'instruction push qui ajoute la valeur en tête de la liste. La raison en est simple, il est beaucoup plus efficace de construire une nouvelle cellule qui pointe sur la première cellule de cette liste. Ajouter en queue, impose de parcourir toute la liste pour déterminer où accrocher les wagons.

Le second point, plus anecdotique, est que la variable modifiée est le dernier argument de l'instruction. Ceux qui ont conçu Common Lisp ont considéré la façon dont l'expression se lit en anglais pour fournir une syntaxe. On pousse un élément dans une liste.

La deuxième contrainte qui découle du choix d'une liste chainée est que l'on ne peut sauter directement à une cellule particulière. Il nous faut traverser la liste, en décomptant soigneusement chaque cellule, pour aboutir à la bonne.

Common Lisp offre bien l'instruction: «nth nb», mais en réalité elle ne fait que cacher un parcours de liste borné par un compteur.

Je prends évidemment Python comme exemple car c'est aujourd'hui l'un des langages les mieux connus. Python est l'un des premiers langages a avoir systématisé l'utilisation des tableaux dynamiques. Or, il est intéressant de noter qu'il y a une similitude, dont je doute fortement qu'elle soit accidentelle, entre les deux langages. En effet, LISP et Python partagent beaucoup de points communs, si l'on met de côté des formalismes très différents. Les variables y sont déclarées à la volée en leur assignant une valeur, et les listes ou les tableaux y jouent un très grand rôle.

Les instructions car et cdr qui permettent de récupérer le premier élément d'une liste ou la suite d'une liste sont présents dans Python sous une forme très simples.

Il suffit de comparer:

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

avec:

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

Je ne voudrais pas m'attirer d'ennuis, mais je soupçonne fortement Monsieur Van Rossum d'avoir tiré une certaine inspiration du langage LISP. Certains argueront qu'il n'existe pas des milliers de façon d'accéder aux éléments des listes. Certes, mais la souplesse de Python dans ce domaine le rapproche et même, osons le dire, dépasse LISP dans sa facilité à manipuler des listes, même si celles-ci sont sous la forme d'un tableau.

C'est là où les Lispiens vont faire remarquer une chose tout à fait fondamentale: A la différence de Python, le cdr de LISP ne fait que renvoyer un pointeur sur la cellule suivante par rapport à la racine.

Autrement dit, un cdr ne crée par une nouvelle liste, il pointe simplement sur l'élément suivant, alors que Python lui va créer une nouvelle liste à chaque fois. Dans le cas de Common Lisp, il faut demander expressément au langage de dupliquer cette liste avec la fonction «copy-list».

Dans ce cas, Common Lisp offre une plus grande souplesse que Python en permettant la duplication ou non de la liste principale.

A priori, chaque approche offre ses avantages et ses inconvénients.

Alors comment LispE peut-il offrir une combinaison des deux approches?

Permettre tout à la fois un accès direct aux éléments à la façon de Python tout en gardant la possibilité d'accéder à des sous-chaines sans duplication inutile.

La réponse est très simple...

Nous avons construit LispE autour d'un tableau dynamique à la Python... Mais avec un petit plus pour conserver la souplesse de LISP...

Si l'on regarde le diagramme au-dessus, on voit immédiatement qu'une liste en LispE est en fait composée de deux classes distinctes.

Voici le code C++ correspondant (très simplifié):

class ARRAY {
   //Un tableau dynamique
   vector<Element*> table;

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

class LIST {
    ARRAY* array;
    int decalage;

    //La liste de base
    LIST() {
      decalage = 0;
      array = new ARRAY;
    } 

    //Chaque fois que l'on accède à un élément, on rajoute le décalage
    Element* operator[](int pos) {
      return array->at(decalage + pos);
    }
};

Que se passe-t-il quand on demande le cdr d'une liste?

C'est très simple, on crée un objet de type LIST qui va partager le même array, mais avec un décalage incrémenté de 1...

    //Le constructeur appelé en cas de cdr
    LIST(LIST* l) {
       //on partage le même tableau
       array = l->array;
       //mais on décale désormais de 1
       decalage = l->decalage + 1;
    }

    //On appelle notre méthode cdr qui va appeler le constructeur ci-dessus
    Element* cdr() {
      return new LIST(this);
    }

Par conséquent, le cdr va certes créer un nouvel élément de type LIST, mais sans dupliquer le tableau lui-même (array). On conserve donc tout à la fois la souplesse de Python, array est un tableau dynamique, tout en offrant la souplesse de LISP quand on effectue un cdr.

On garde de plus la possibilité d'un accès direct à un élément du tableau via nth.

En fait, comparé à une liste chainée qui généralement contient 3 pointeurs, l'un vers la valeur, l'autre vers la cellule suivante et le dernier vers la cellule précédente, le coût mémoire est très raisonnable.

Un parcours de liste se résume désormais à itérer sur un tableau avec un index. Si les fonctions traditionnelles sont maintenues, leur implantation en revanche est transformée. Alors que pour des raisons d'efficacité, Common Lisp ajoute les éléments en tête, ici, l'ajout le plus efficace se fait en queue. En revanche, l'ajout en tête est certes permis, mais il impose de déplacer les éléments à droite pour libérer la première case.

Enfin, j'ai eu il y a peu une discussion avec quelqu'un qui affirmait que le portage de certaines instructions du langage APL en LispE était une hérésie. Or, si ces instructions ne sont pas adaptées à des listes chainées, elles s'appliquent évidemment à des tableaux. Et c'est là, où le côté hybride de cette structure devient vraiment intéressant (voir: APL).

Voici par exemple comment on peut appliquer le produit interne dans LispE pour calculer la multiplication de deux matrices:

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

; ce qui donne:

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

Le dernier point sur lequel LispE diffère de Common Lisp est le choix délibéré de placer la variable de réception en 2ième position systématiquement, après l'opérateur ou le nom de fonction.

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

Ce choix vient de ce que la syntaxe de LispE, à l'instar de tous les LISP, peut se comprendre comme une forme d'Arbre de la Syntaxe Abstraite.

         push
        /   \
       r   quote
              \
               e

Les parenthèses permettent alors d'exprimer les différents niveaux de cet arbre.

L'autre raison est un peu plus subtile. Prenons l'exemple équivalent en Python: r.append("e"). L'arbre correspondant est:

        append
        /   \
       r    "e"

De fait, le choix de placer systématiquement en deuxième position la variable à modifier vient aussi du fait que l'on peut considérer push non comme une fonction, mais comme une méthode attachée à la liste r.

Autrement dit, alors que LispE est un langage fonctionnel, le choix de placer la variable de réception en 2ième position obéit à une sorte de philosophie OOP sous-jacente. Les fonctions peuvent être réinterprétées comme des méthodes associées à des types particuliers.

(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

Ainsi, on normalise systématiquement la position des arguments de façon à renforcer le lien entre la variable et la méthode qui la modifie. Cette syntaxe a aussi comme avantage de faciliter la transition entre un langage comme Python et LispE. Il suffit de placer en tête ce qui en Python est considérée comme une méthode.

On peut trouver ce choix quelque peu trivial, mais comme nous l'avons montré dans le blog sur la transpilation, cette disposition des arguments facilite aussi l'utilisation de LispE comme interpréteur de nouveaux langages.

Ainsi, le langage a été conçu pour faciliter le passage à un langage fonctionnel très riche compatible aussi bien avec un environnement C++, Python ou WASM, avec des performances très au-delà de Python.

Les choix que nous avons fait ont été à la fois motivé pour des raisons de flexibilité et de performance, mais aussi avec l'idée de normaliser certains aspects du langage pour offrir une plate-forme plus simple à utiliser pour des gens issus du sérail des langages impératifs.