English Version

Lisp n'est pas mort. Pour un langage né à la fin des années 50, c'est là un constat réjouissant mais aussi très surprenant. Le succès de Clojure ou la résistance remarquable de Common Lisp représentent une forme d'anomalie dans un monde dominé par javascript et Python... D'ailleurs en passant, javascript est en fait un Lisp déguisé.

Bon reprenons, Lisp n'est pas mort, d'ailleurs le but de ce blog, c'est de montrer comment l'interpréteur LispE a été implanté.

Mais la question peut se poser, comment un langage préfixé, noyé dans les parenthèses continue-t-il d'attirer autant d'intérêt?

Lisp est non seulement l'un des plus anciens langages encore en activité, mais aussi l'un des tout premiers langages fonctionnels jamais inventés.

Lisp est homoiconique. Autrement dit, le langage est enregistré sous la forme de listes, qui sont aussi une structure de données de base du langage. Ce qui rend le langage extraordinairement malléable, comme le montre cet exemple.

Enfin, il y a peu de langages de programmation aussi simple à implanter que Lisp.

Il y a deux raisons très paradoxales à cela.

Prenons un aspect du langage qui pique souvent les yeux des néophytes: les infâmes parenthèses dont le langage semble abuser. Oui, Lisp utilise ces parenthèses massivement et elles rendent parfois le langage un peu obscure. Mais comme le font souvent remarquer les programmeurs Lisp, c'est un peu une illusion:

(sin 10) ; Lisp
sin(10) ; Autre langage

Avant de nous embarquer dans une énième défense du langage sur le mode: les parenthèses dans Lisp c'est génial, mais bon seuls les initiés peuvent comprendre. Remarquons un deuxième élément qui souvent trouble ceux qui apprennent le langage: en Lisp tout est préfixé.

Voilà, nous avons là les deux complaintes les plus courantes: parenthèses et notation préfixée. Et comble de paradoxe, nous avons aussi notre réponse sur ce qui fait de la construction d'un interpréteur Lisp, une petite ballade de santé. Enfin comparé à d'autres langages s'entend.

Voilà donc cet étrange paradoxe qui fait de la forme préfixée hautement parenthétisée de Lisp à la fois la raison d'un rejet du langage mais aussi de sa simplicité à créer des interpréteurs pour l'exécuter.

Et tout cela repose sur une notion fondamentale en théorie de la compilation: l'arbre de la syntaxe abstraite.

L'une des étapes les plus importantes, lorsque l'on compile une suite d'instructions dans un langage comme Python ou C++, c'est de tout ramener à des arbres.

La raison en est fort simple, un arbre permet d'exprimer au mieux les relations que les différents objets entretiennent les uns avec les autres au sein d'un programme:

toto=10 + a-20

Généralement, un compilateur ou un interpréteur prend l'expression ci-dessus et lui fait subir une suite de transformation:

• la segmentation (tokenization)
• la réorganisation sous la forme d'un arbre via une grammaire formelle (BNF)

La segmentation comme son nom l'indique consiste à découper la chaine en autant d'unités autonomes:

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

Cette opération en Lisp est encore plus facile que dans un langage comme Python. En effet, dans la plupart des langages, la segmentation s'effectue le long des opérateurs, les espaces sont rarement suffisants.

En Lisp, la segmentation se réduit à identifier les parenthèses et les espaces.

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

Mais surtout, la différence fondamentale, c'est la construction de l'arbre. Si l'on reprend notre expression Python, l'arbre correspondant est le suivant:

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

C'est le résultat de l'application d'une grammaire qui pourrait ressembler à cela:

assignement :: nom = expression|variable
expression :: valeur|variable opérateur variable|expression

Nous allons maintenant effectuer une marche préfixée:

= toto - + 10 a 20

Nous allons rajouter des parenthèses dans cette marche préfixée, de la façon suivante, chaque sous-arbre non terminal sera injecté entre parenthèses:

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

Voilà, cette représentation parenthétisée est en tout point semblable à du Lisp. Et cela ne doit rien au hasard.

Le projet initial de McCarthy consistait à intégrer dans Fortran des expressions symboliques inspirées fortement de la théorie du lambda-calcul de Church: les M-expressions. Or, il s'avéra rapidement que l'étape intermédiaire appelé S-expressions était beaucoup plus simple à mettre en oeuvre.

Si l'on rajoute que la fabrication et l'application de grammaires pour reconstruire un tel arbre est loin d'être trivial, on comprend vite à quel point les expressions Lisp évitent à un concepteur toute la lourde architecture des langages traditionnelles.

Enfin, ajoutons que la représentation préfixée systématique pour les opérateurs et les fonctions simplifie aussi grandement la compilation du code.

Rappelons par exemple que dans Python, l'appel à une fonction ou l'écriture d'une expression mathématique obéissent à des règles différentes. Nous avons une telle habitude de manipuler ces expressions, que nous oublions que cette différence de syntaxe a un coût:

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

En effet, il nous faut disposer de points d'entrée différents dans notre grammaire pour appréhender chacune de ces expressions.

Si l'on compare ces expressions à Lisp:

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

On voit immédiatement la différence, en Lisp tout est fonction, y compris les opérateurs. Ainsi, la compilation des expressions numériques ou des appels de fonction est unifiée dans un même formalisme.

D'une certaine manière, Lisp impose à l'utilisateur d'effectuer une partie du travail de compilation, là où les autres langages appliquent de lourdes grammaires pour construire ces S-expressions. Mais, il permet aussi de s'abstraire de certaines ambiguïtés qui parfois conduisent à des bogues.

Il suffit de comparer:

toto = 10 - 2 * 10

avec la forme non ambigue:

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

L'autre avantage de Lisp, c'est qu'il n'est nul besoin de s'inventer des styles de programmation différents pour intégrer de nouvelles fonctionnalités.

Python en offre des exemples particulièrement frappants:

fruits = ["pomme", "poire", "banane", "fraise"]
v = [x for x in fruits if "a" in x]

Notons que nous avons choisi Python comme langage de comparaison, parce qu'il a l'avantage d'être simple et populaire. Rappelons que la plupart de ces remarques pourraient s'appliquer à des langages comme C++ ou Java.

Lisp grâce à son uniformité syntaxique, n'a pas besoin de réinventer la roue pour implanter l'exemple ci-dessus:

Voici comment on pourrait traduire cette expression en LispE:

(setq fruits '("pomme" "poire" "banane" "fraise"))
(setq v (filterlist (λ(x) (in x "a")) fruits))

Comme on le voit, la syntaxe reste la même.

D'ailleurs, si l'on reste dans le domaine de la légende, lorsque l'on demanda à des ingénieurs de produire, en quelques jours, un nouveau langage pour le Web, leur première version ressemblait à du Lisp. Mais, effrayé, on leur demanda de corriger leur copie, ce qui donna la version de javascript que l'on connait aujourd'hui.

L'intérêt du Lisp, c'est qu'il permet très facilement d'expérimenter avec de nouveaux opérateurs ou de nouvelles fonctionnalités sans devoir chaque fois réimplanter la grammaire du langage. Nombre de concepts en informatique, à commencer par la programmation objet, ont commencé avec des implantations en Lisp.

Comme je le disais précédemment, Lisp est une philosophie. C'est une façon de représenter et d'exécuter des programmes sous une forme intermédiaire entre l'homme et la machine. Les S-expressions offrent une façon très élégante de représenter dans une même syntaxe code et données.

Pourrait-on s'en inspirer dans d'autres langages?

Je programme en C++.

Je sais bien que le langage a une réputation sulfureuse et certains m'ont conseillé de passer à Rust. Mais, après 30 ans de pratique, j'estime avoir une certaine familiarité avec un langage dont les performances ne sont plus à démontrer.

Car évidemment, lorsque l'on réalise son propre interpréteur, on s'attend à une certaine efficacité aussi bien en terme de compilation que d'exécution. C++ permet à la fois de chatouiller le processeur au raz du métal tout en manipulant des abstractions de très haut niveau. Mais le prix à payer est parfois assez lourd, car le langage est tortueux et souvent piégeux, pour ne pas dire joueur.

Le but de ce blog est de montrer comment on peut construire un interpréteur Lisp en C++, qui s'inspire directement de la philosophie fonctionnelle de Lisp.

Une sorte de mise en abyme programmatique en quelque sorte...

Tout d'abord commençons par une banalité: que vous pratiquiez la programmation fonctionnelle ou tout autre forme de programmation, de toute façon au bout du compte, votre programme finira sous la forme d'un code machine avec pleins de jumps dans tous les coins.

Je sais, c'est triste mais c'est ainsi. C'est un peu comme voir un tableau d'un grand maitre de la Renaissance. De loin, ça a l'air lisse au poil de pinceau près, quand on se rapproche, on voit les coups de brosse.

Tout ce que vous pouvez programmer dans un langage généraliste donné, vous devez pouvoir le programmer dans un autre langage généraliste. C'est là la conclusion du fameux article de Turing où il explique que sa machine et le lambda-calcul de Alonzo Church sont équivalents.

Sans cette équivalence, les langages fonctionnels ne pourraient exister.

Ce qui ne signifie pas que ces langages ne sont pas intéressants, bien au contraire, ils permettent d'aboutir à des programmes d'une rare sobriété et d'une rare solidité. Mais fondamentalement, ils existent parce que l'on peut les compiler sous une forme impérative.

Mais à l'inverse, les concepts fonctionnels les plus puissants peuvent aussi être retranscrits dans des langages plus traditionnels:

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

Autrement dit, on peut concevoir une programmation en C++ qui s'inspire de Lisp.

Et ça a quelques avantages...

La représentation de base de Lisp, celle qui définit depuis toujours le langage et qui se cache au coeur même de son nom est la liste (LISP = LIST Processing).

Il existe de nombreuses façons de créer des listes en C++, mais pour l'instant nous allons nous contenter de la forme la plus simple qui soit: le vecteur.

Cependant, et c'est là évidemment qu'est le coeur de l'intrigue, un vecteur en C++ ne peut être déclaré que pour un type donné:

std::vector<Element*> elements;

Or une liste en Lisp peut conserver n'importe quel type d'éléments, aussi bien des valeurs, que des opérateurs ou des appels de fonction.

Pour que notre vecteur offre la même souplesse, les lecteurs aguerris auront immédiatement deviné qu'il suffit que tous les objets du langage dérivent de la classe Element.

Ainsi, si nous dérivons de Element, une classe Opérateur ou une classe Entier, nous pourrons allègrement enregistrer dans la même structure des opérateurs ou des entiers. Si de plus, la classe Liste, elle-même dérive de la classe Element, nous pourrons construire des représentations enchâssées sans la moindre limite.

Il manque juste un élément pour parachever notre description: chaque classe dérivée devra surcharger sa propre méthode Eval.

Dans le cas d'un entier ou d'une chaine de caractère, cette méthode renverra l'élément lui-même, pour une fonction ou un opérateur, leur méthode Eval effectuera l'exécution correspondante.

Voici, par exemple la boucle principale d'exécution d'un programme:

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

return v;

Remarquons la méthode release qui nettoie l'élément lorsque celui-ci n'est pas utilisé au sein d'une variable ou d'un conteneur. Le cycle de vie d'une structure de données est basée sur l'utilisation d'un compteur de référence. Lorsque ce dernier a la valeur 0, release nettoie cette structure.

Examinons de plus près cette fameuse fonction Eval:

On initialise d'abord v avec la valeur null_, une valeur constante qui ne peut être détruite. Ainsi, l'appel de release ici n'aura aucun effet sur cette variable à l'entrée de la boucle.

Puis on appelle la méthode Eval pour chacun des éléments du vecteur dont le résultat est rangé dans v.

Et c'est là où les choses deviennent intéressantes. Chaque valeur dans l'interpréteur est associée avec un compteur de référence qui s'accroit de 1 quand cette valeur est rangée dans une variable ou dans un conteneur. Quand une fonction est appelée qui renvoie un résultat, il peut se passer 2 choses:

• La valeur provient de l'application d'une fonction
• La valeur a été renvoyée par une variable ou un conteneur

Or si nous examinons attentivement la boucle, nous voyons que la valeur de v est systématiquement libérée à chaque itération, sauf pour la dernière instruction dans éléments. Pour les valeurs sauvegardées dans une variable ou un conteneur, l'appel de cette fonction n'a aucun impact. Pour les autres, elle les détruit ou les sauvegarde dans des pools de données.

Ce mode de fonctionnement s'inspire directement de la programmation fonctionnelle:

Chaque fonction renvoie une et une seule valeur dont le cycle de vie est décidé localement.

Si cette valeur n'est pas sauvegardée dans une variable ou dans un conteneur, elle sera libérée dans la boucle à l'itération suivante, sinon elle sera renvoyée.

En Lisp, c'est exactement ce que produit un appel de fonction:

; la dernière ligne renverra le calcul final
(defun calcul(x)
  (setq x (* x 2))
  (+ x 1)
)

Ce qui est fondamental dans cette approche, c'est que la gestion des valeurs renvoyées est purement locale, il n'y a aucun effet de bord. Plus exactement, si la valeur n'est sauvegardée dans aucune structure, sa libération dans cette boucle peut être effectuée sans problème, elle n'aura aucun impact ailleurs dans le code.

Organiser le code de cette façon permet de contrôler pas à pas le cycle de vie de toutes les structures de données en mémoire. Quand une valeur est importante, il suffit de la placer dans une variable ou un conteneur. Sinon, elle sera détruite à la sortie de la fonction qui l'aura créée.

Ainsi, dans l'exécution de: (* 10 (+ 20 1) (- 15 1)), les valeurs intermédiaires (+ 20 1) ou (- 15 1) seront utilisées par la multiplication mais détruites à la fin:

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

return new Entier(value);

La boucle ci-dessus par exemple effectue la multiplication des entiers présents dans elements. A chaque itération, si v provient d'un calcul intermédiaire, il pourra être détruit.

Ainsi, on s'assure bien qu'à chaque étape, rien ne traine dans l'espace mémoire. Remarquons d'ailleurs que le résultat final de cette boucle est un objet intermédiaire qui pourra lui aussi être détruit au niveau de l'appel de cette fonction.

L'autre aspect fondamental de cette architecture est que les objets, correspondant à des instructions, sont par définition immuables. Autrement dit, le même objet peut-être exécuté autant de fois que nécessaire sans qu'il ne soit jamais modifié.

Enfin, l'exécution de ces instructions se fait en dehors d'une machine virtuelle, puisque que chaque objet sait nécessairement comment s'exécuter.

Ainsi, on retrouve dans cette approche, les propriétés fondamentales de la programmation fonctionnelle.

• Tout est appel de fonction (ici ramené à un appel de Eval pour chaque objet)
• Immuabilité des objets
• Absence d'effets de bord.

Ce mécanisme permet en particulier de pouvoir très facilement créer des threads indépendants qui pourront exécuter les mêmes fonctions en parallèle. En effet, il suffit de lancer la fonction Eval sur un objet pour que celui-ci s'exécute.

Ceci est d'ailleurs la différence la plus importante avec les méthodes plus traditionnelles où les instructions sont traduites en pseudo-code et exécutées par une machine virtuelle. Python par exemple ne peut exécuter qu'une seule machine virtuelle à la fois, ce qui restreint d'autant la possibilité d'écrire des threads, puisqu'ils sont tous exécutés dans le même espace protégé par le fameux GIL (Global Interpreter Lock). Python peut exécuter des threads mais un à la fois.

A l'inverse, la programmation objet permet de simplifier grandement certains aspects parfois très complexes à maîtriser. Par exemple, l'addition d'objets de type différent est un problème assez épineux à gérer et Python n'échappe pas à la règle, il suffit de jeter un coup d'oeil sur l'implantation de __add__ pour s'en convaincre.

(+ 10 20 30) ; rend un entier
(+ 10.1 2.109) ; rend un flottant

Dans le cas qui nous intéresse, ce problème s'avère en fait très simple à résoudre.

La classe Element contient la liste des méthodes numériques de base du langage:

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

Il suffit donc pour les classes Entier, Flottant ou String de les surcharger pour avoir le comportement voulu.

Comme nous l'avons dit plus haut, notre implémentation va reposer sur l'utilisation d'un vecteur d'éléments. Ce vecteur d'éléments a la forme suivante:

std::vector<Elements*> liste;

Reprenons notre exemple: (+ 10 20 30), il pourrait être compilé sous la forme suivante:

liste: [Opérateur(+), Entier(10), Entier(20), Entier(30)]

Opérateur et Entier sont des instances de classes dérivant de: Element.

Surchargeons la méthode plus dans notre classe Entier:

class Entier : public Element {
public:
  long value;

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

  long commeEntier() {
     return value;
  }
};

La méthode plus permet de fixer le comportement de l'addition pour un type d'objet particulier. Il nous reste maintenant à définir l'opérateur + au sein d'une liste.

Cela nous donne la méthode: eval_plus ci-dessous:

   Element* List::eval_plus() {
        //On récupère le premier élément de notre liste d'instructions
        Element* r = liste[1]->Eval();
        Element* v;
        Element* inter;
        for (long i = 2; i < size(); i++) {
          v = liste[i]->Eval();
          inter = r->plus(v);
          v->release();
          if (r != inter) {
             r->release();
             r = inter;
          }
        }
        return r;
   }

Remarquons que la première donnée (en position 1) définira le type d'addition voulu. Ainsi, si la liste commence par un entier, le résultat sera une somme d'entiers en fin d'analyse. Dans le cas d'une chaine de caractères, il s'agira d'une concaténation.

Le premier élément de la liste (en position 0) est donc l'opérateur: Opérateur(+). Nous pouvons donc facilement imaginer un mécanisme, par exemple un switch/case qui nous permet de lancer cette méthode en particulier:

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

Ainsi, chaque fois que la méthode Eval sera exécutée depuis un objet Liste, nous pourrons exécuter la fonction placée en position 0 dans notre liste.

Et voici que l'ensemble du fonctionnement se dévoile. Si une instance dans la liste est une valeur atomique, Eval renverra l'instance elle-même. Si en revanche, il s'agit d'une liste, on appellera récursivement la méthode au-dessus qui renverra le résultat correspondant.

Cette représentation correspond point par point à notre liste en Lisp. Il suffit de lancer Eval depuis la racine de cette liste pour exécuter l'ensemble de notre programme.

Etendre le langage se résume à dériver la classe Element et à surcharger les méthodes nécessaires correspondantes. Ainsi, si l'on crée une classe Date, on pourra définir une addition ou une soustraction propre à la gestion des dates.

Tout d'abord, je tiens à souligner l'efficacité de l'interpréteur produit avec cette méthode, comme l'illustre cette expérience.

Certaines personnes pourraient se plaindre que Lisp est un langage de niche trop peu important pour faire l'effort de comprendre comment il a été implémenté. Cependant, ce qu'il faut retenir de cette présentation, c'est que si vous créez votre propre syntaxe et implémentez une grammaire pour la transformer en un arbre, vous pourrez utiliser le code C++ de l'interpréteur sous-jacent sans avoir besoin de le modifier vraiment. Nous avons, d'ailleurs, également implémenté un autre langage de programmation : TAMGU탐구, qui suit la même philosophie et met pourtant en œuvre un langage très similaire à Python.

Lisp peut sembler être un vieux langage issu des âges sombres de l'informatique, mais lorsque vous implémentez un interpréteur Lisp, ce que vous créez en réalité est un interpréteur universel, qui peut exécuter de nombreux langages de programmation dans le monde....

Tout ce dont vous avez besoin est un arbre...

Et ça, c'est vraiment cool...