Skip to content

6.16 Pourquoi Lisp (brouillon)

Claude Roux edited this page Oct 24, 2022 · 1 revision

Pourquoi Lisp?

Lisp est un cas à part dans l'histoire des langages de programmation. Contrairement à certaines idées reçues, les langages de programmation ont souvent une vie longue, très longue. Ainsi, Fortran ou Cobol sont toujours utilisés, alors qu'ils ont été créés dans les années 50. Lisp n'échappe pas à cette règle, ancien mais toujours présent. Sauf que personne n'a jamais décidé de réimplanter son Fortran ou son Cobol dans son coin. Alors que, lorsque l'on se rend sur la page Wikipédia consacrée à Lisp, on découvre des dizaines d'implantation différente. Des dizaines.

Pourquoi cet engouement? Comment se fait-il qu'un langage né à la fin des années 50 continue d'attirer des aficionados prêts à réimplanter leur propre interprétation du langage. Un peu comme ces films de fan qui pullulent sur Youtube, qui revisitent les personnages de la Guerre des Etoiles pour leur propre bonheur. 70 ans après, on continue de revisiter Lisp et de proposer de nouvelles versions.

Tout d'abord, débarrassons nous de l'éléphant dans notre magasin de porcelaine. La raison première, c'est que faire un interpréteur Lisp est facile. Très facile.

Evidemment, la qualité scientifique d'un argument de ce genre laisse généralement de marbre le moindre théoricien un peu branché dans le domaine. Pourquoi facile? Que signifie facile dans ce contexte?

Parenthèses

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, il faut l'avouer. Mais comme le font souvent remarquer les programmeurs Lisp, c'est un peu une illusion:

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

Notation Préfixée

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.

Mais, je m'emballe. Revenons un peu en arrière.

Fabriquer des langages

Je fabrique des interpréteurs depuis des années, depuis ma thèse de doctorat plus exactement. J'en ai même fait mon métier d'une certain façon.
Le sujet de ma thèse portait sur la meilleure façon de compiler et d'exécuter des grammaires pour analyser des langues vivantes telles que le français ou l'anglais. Je finis par être engagé par un des laboratoires de Xerox, à Grenoble, où le prototype en C++ que j'avais écrit pour ma thèse se transforma en un outil à la fois très riche et très puissant: le Xerox Incremental Parser ou XIP.

XIP offrait près d'une dizaine de types différents de règle pour analyser des problèmes aussi divers que la désambiguïsation des catégories syntaxiques que la construction des dépendances via un moteur d'inférence.

//Règle syntaxique

2> NP -> (det+[prep:~]),(coord+[first:~,last:~]),num+,
        (punct+[first:~,form:fcm]),(punct+[first:~,form:fquotes]),
        adv,(AP+[first:~]),
//Règle de dépendance:

1> if (SUBJ(#2,#1) & COORDITEMS[sc](#2,#3))     SUBJ(#3,#1)

Comme on peut le voir sur l'échantillon au-dessus, transformer ces règles en code exécutable n'avait rien de trivial.

Pour donner un ordre de grandeur, la grammaire de l'anglais comprenait près de 60.000 règles. XIP pouvait ainsi analyser des textes dans cette langue à une vitesse de l'ordre de 3000 mots/s sur une machine moyenne de 2005. Le système était conçu sous la forme de grammaires noyaux que l'on pouvait raffiner à volonté, en rajoutant des fichiers de règle supplémentaires. Celles-ci étaient organisées en couche qui définissaient leur ordre d'exécution. On pouvait ainsi facilement adapter une grammaire à un domaine nouveau en rajoutant des lexiques spécialisés ou en injectant de nouvelles couches à des endroits stratégiques pour identifier certaines expressions particulières. Une sorte de « fine-tuning » avant l'heure.

Aujourd'hui, les méthodes plus modernes à base d'apprentissage profond, ont rendu ces approches largement obsolètes, mais il faut noter que notre système resta opérationnel pendant près de 17 ans, de 1999 à 2017. Il fut utilisé, par exemple, dans la track 5 de SemEval 2016, une campagne d'évaluation des méthodes d'analyse de sentiments, où notre système obtint d'ailleurs la première place (voir: Feedbacked Ensemble Modelling on Syntactico-Semantic Knowledge for Aspect Based Sentiment Analysis).

Je vous parle de Lisp et je dérive sur un moteur de règles syntaxiques. Vous vous demandez certainement où je veux en venir.

Routines programmatiques

En fait, les linguistes qui utilisaient XIP se heurtaient souvent à des problèmes qui ne pouvaient se résoudre qu'avec de la programmation traditionnelle. L'exemple le plus simple est le besoin de conserver la trace de certaines informations découvertes dans une phrase précédente. Je commençais alors à rajouter la notion de variables, puis de boucles dans le moteur. J'aboutis alors à une horrible mixture que personne n'arrivait à comprendre ou à utiliser.

Puis je décidais de coupler XIP avec Python. Il devenait alors possible d'exécuter dans une règle un appel à des fonctions Python. Malheureusement, si le besoin était là, les grammaires devenaient extrêmement compliquées à débogguer. A cela se rajoutait un problème récurrent particulièrement frustrant à corriger: les textes que nous analysions mélangeaient souvent différents encodages. Les corpus étaient très souvent construits en mélangeant des textes en UTF-8 avec des textes en LATIN 2.

Le résultat était catastrophique. En particulier, Python 2 plantait régulièrement sur des chaines aux encodages mélangés.

KiF

Je finis par développer mon propre langage de programmation, totalement intégrée dans XIP: KiF. Au début, le langage ressemblait à un Python fortement typé, avec une emphase particulière sur la tolérance aux encodages mélangés.

Soyons honnête, la solution choisie est généralement rejetée par les puristes. Elle consiste à considérer l'UTF-8 comme l'encodage par défaut d'un texte, et à traiter les caractères n'obéissant pas à cet encodage comme des caractères LATIN que l'on va tenter de convertir en UTF-8. A cet effet, on fournit à la fonction de conversion un paramètre supplémentaire qui est le numéro de la table d'encodage Latin dont on se sert pour effectuer cette conversion. Par défaut, on utilise la table Latin 2 qui couvre la majorité des langues européennes occidentales, qui constituaient à l'époque, le gros des corpus que l'on traitait.

C'est une façon assez rustique de résoudre ce problème, mais cela marche remarquablement bien.

Couplage

L'avantage d'une intégration très étroite de KiF avec XIP était la possibilité d'accéder à tout moment à la structure linguistique en cours, de façon à pouvoir intercaler des analyses autres que linguistique. Je m'autorisais aussi à en faire un langage autonome, dont le descendant (Tamgu(탐구)) me sert toujours régulièrement pour nettoyer des textes et du code.

En 2017, lorsque mon laboratoire fut racheté par Naver, je décidais d'en profiter pour remettre à plat la façon dont j'avais écrit le code de KiF à l'origine. Car, autant l'avouer, le code avait fini par devenir incompréhensible à force de corrections et de rustines. Aujourd'hui, le langage s'appelle Tamgu(탐구) et il est disponible en libre accès.

Tout cela pour dire, que cette mise à plat eut aussi comme conséquence une réflexion sur la façon dont un interpréteur peut être construit.

Compilation du Lisp

Nous avons parlé plus haut de cet étrange paradoxe que la forme préfixée hautement parenthétisée de Lisp est à la fois la raison d'un rejet du langage mais aussi de sa simplicité à créer des interpréteurs pour l'exécuter.

Pour mieux comprendre ce que l'on veut dire par là, nous allons introduire une notion fondamentale en théorie de la compilation: l'arbre de la syntaxe abstraite.

L'Arbre de la Syntaxe Abstraite (Abstract Syntax Tree ou AST)

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, comme le montre l'exemple ci-dessus. 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, c'est à dire par la gauche de notre arbre:

= 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 symbolique 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.

Préfixe

Enfin, ajoutons que la représentation préfixée systématique pour les opérateurs et les fonctions simplifient 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 qu'il accomplit lui-même dans d'autres langages. 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))

Uniformité de la syntaxe

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 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 un langage simple et populaire. Rappelons que la plupart de ces remarques pourraient s'appliquer à des langages comme C++ ou Java.

Lisp de par son approche systématique sur la position des opérateurs et la forme de son code permet de rajouter autant de sucre syntaxique désiré sans jamais devoir transformer la grammaire du langage.

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.

Lisp est mon guide

Avec les années, l'idée d'une représentation unifiée des opérateurs et des fonctions s'est imposée à moi comme une évidence. Vous voudrez bien excuser ici un esprit médiocre qui vous transmet ce qu'il a péniblement appris après des années de travail. En effet, rien de ce que je vais décrire ici n'est en soi particulièrement original ou nouveau.

Mais, en revanche, l'approche que je propose, qui se sert de Lisp comme modèle, a l'avantage d'être particulièrement simple et adaptée à la réalisation d'interpréteurs.

La Programmation Orientée Objet est-elle soluble dans Lisp?

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.

Quel est donc ce lien mystérieux qui existe entre Lisp et OOP?

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 grand théorème que Turing avait démontré lorsqu'il avait expliqué que sa machine et le lambda-calcul de Alonzo Church était équivalent.

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 retranscrire sous une forme impérative.

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

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

Autrement dit, on peut utiliser par exemple une représentation objet C++ pour implémenter des concepts propres à Lisp.

La liste

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 noeud 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, une classe Fonction ou une classe Entier, nous pourrons allègrement enregistrer dans la même structure des opérateurs, des fonctions 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.

La fonction Eval

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->relache()
   v = e->Eval();
}

return v;

Remarquons la méthode relache 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 de cette valeur est basée sur l'utilisation d'un compteur de référence. Lorsque celui-ci a la valeur 0, relache nettoie cette valeur.

Architecture à la Lisp

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 relache 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.

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->relache();
}

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.

Immuabilité

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.

Threads

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.

Dans le cas de notre version de Lisp: LispE

De plus, dans le cas de LispE, par défaut tout appel à une fonction implique la duplication des ses arguments. Enfin, les threads n'ont pas accès aux variables globales, tout cela permet d'éviter les problèmes d'accès concurrents aux variables. Il existe cependant, des mécanismes très simples pour accéder à des variables communes, mais ces mécanismes doivent être explicitement mis en place pour que ce partage puisse avoir lieu.

LispE: C++ s'inspire de Lisp pour implanter un Lisp

LispE dont le code est d'ailleurs dans le GitHub qui héberge ce blog, représente l'aboutissement de cette réflexion selon un mécanisme de mise en abyme dont j'avoue être assez friand.

Nous utilisons ainsi la philosophie de Lisp en C++ pour implanter un interpréteur Lisp.

Nous retrouvons bien une classe mère pour l'ensemble de notre code: Element. La classe la plus importante est List qui permet à la fois de gérer des listes d'éléments mais aussi des listes d'instructions. Chaque classe peut surcharger sa méthode eval ce qui permet d'associer à des objets particuliers des comportements spécifiques.

Différentes classes

Dans un Lisp, les objets de base se résument finalement à très peu de chose:

  • Des atomes
  • Des nombres
  • Des chaines de caractères
  • Des listes

Evidemment, nous avons rajouté des conteneurs supplémentaires comme par exemple des dictionnaires et des ensembles (sets). Nos nombres ont été sub-divisés entre flottants et entiers, de même que les listes comprennent des versions spécifiques pour manipuler uniquement des nombres ou des chaines de caractères.

Chacun de ces objets est défini par une classe dérivée de Element qui lui est propre. La majorité de ces classes partagent une méthode eval commune qui ne fait que renvoyer l'objet lui-même.

List

Cette classe est sans doute la plus importante, car c'est à elle que revient la tâche d'exécuter une suite d'instructions. En effet, lorsque l'on reçoit comme instruction Lisp: (+ 10 20), notre interpréteur va la compiler sous la forme suivante:

List: vector[Operator(+), Integer(10), Integer(20)] 

La méthode eval de cette classe se sert du premier élément, ici Operator(+), une classe dérivée de la classe Atom, d'ailleurs, pour effectuer l'exécution de cette opération.

Indexation des méthodes sur le premier élément d'une liste

Le fonctionnement de l'interpréteur est assez particulier. Chaque instruction et chaque type d'objets est associé avec un index unique dont la liste est conservée dans lispe_code.

On associe ensuite chacun de ces indexes avec une méthode dans la classe List qui correspond à son exécution:

    set_instruction(l_cons, "cons", P_THREE, &List::evall_cons);
  • l_cons provient de la liste de nos indexes dans lispe_code
  • "cons" est son nom tel qu'il apparait dans le langage, il s'agit forcément d'une chaine UTF-8
  • P_THREE est son arité
  • List::evall_cons est la méthode associée

LispE construit une table: evals dont la taille est fixée à l'avance par le nombre d'éléments dans lispe_code. Chaque position dans cette table correspond donc à l'une des valeurs dans cette enum. Ainsi à la position correspondant à l_cons, on placera un pointeur sur la méthode correspondante: List::evall_cons.

List::eval

La méthode eval se réduit alors à la ligne suivante:

//On exécute les méthodes via pointeur en C++ avec cette notation: this->*eval[..](lisp)

Element* List::eval(LispE* lisp) {
    return (this->*evals[liste[0]->label()])(lisp);
}

Si l'on examine l'ensemble des méthodes disponibles, on trouvera en particulier la ligne suivante:

set_instruction(l_plus, "+", P_ATLEASTTWO, &List::evall_plus);

Ainsi, si l'on reprend l'exemple: (+ 10 20), on peut facilement comprendre que la méthode label renverra comme valeur: l_plus, ce qui permettra d'exécuter: evall_plus.

Spécialisation

Pour les cas les plus fréquents, on peut aussi dériver une classe particulière dont la méthode eval remplacera l'indirection utilisée ici pour exécuter le code.

class List_plus : public List {
public:
  
   Element* eval(LispE* lisp);
};

Dans ce cas, eval effectuera directement l'addition. On effectue le remplacement de la liste régulière avec cette liste particulière à la compilation. Ainsi, notre liste aura en fait la forme suivante:

(* 10 (+ 20 30))

est compilée sous la forme:

List_multiply:[Operator(*), Integer(10), List_plus[Operator(+), Integer(20), Integer(30)]]

Un exemple de fonction: le et logique

Element* List::evall_and(LispE* lisp) {
    long listsize = liste.size();
    Element* second_element = null_;
    bool test = true;
        
    for (long i = 1; i < listsize && test; i++) {
        second_element->release();
        second_element = liste[i]->eval(lisp);
        test = second_element->Boolean();
    }
    second_element->release();
    return booleans_[test];
}

Si l'on regarde la ligne: second_element = liste[i]->eval(lisp);, on comprend mieux comment la spécialisation au-dessus va fonctionner. En effet, si liste[i] pointe sur un objet: List_plus, l'appel de sa méthode eval va immédiatement lancer la suite d'addition.

Si en revanche, il s'agit d'un objet List, on appellera la méthode eval de base et on passera par une indirection pour effectuer l'exécution.

On peut donc peaufiner notre interpréteur autant que l'on veut, en remplaçant à la compilation certains appels par des versions plus efficaces.

Conclusion

Cette stratégie d'écriture de programmes C++ n'a rien de bien original, mais elle permet d'opter pour des architectures où la gestion purement locale des données évite nombre de problèmes connus tels que les «fuites de mémoire» ainsi que certains effets de bord souvent incontrôlable en C++.

Enfin, cela permet de construire très facilement des interpréteurs plutôt efficaces que l'on peut très facilement étendre. Par exemple, dans le cas de LispE, la construction d'une bibliothèque externe s'effectue en dérivant simplement notre nouvel objet de la classe Element, intégrant de façon transparente son cycle de vie à l'interpréteur lui-même.

Si Lisp est un langage généraliste à l'image de C++ ou de Java, il est clair que l'on peut souvent ramener nombre d'algorithmes à cette stratégie d'écriture, permettant justement d'éviter les écueils propre à C++. Cela implique en revanche de penser les programmes différemment, ce qui est loin d'être toujours possible. Ce qui est dommage, quand on voit comment une approche fonctionnelle peut simplifier la programmation en C++.

Clone this wiki locally