2.4 Attraper une récursion terminale
De nombreuses personnes se demandent souvent pourquoi en 2021, on continue à s'intéresser au langage Lisp. Après tout, voilà un langage né à la fin des années 50, dont la syntaxe n'a quasiment pas bougé depuis cette époque.
Or certains esprits chagrins s'évertuent de le maintenir en vie envers et contre tout. C'est plein de parenthèses dans tous les sens, avec des contraintes illisibles sur la position des opérateurs et des fonctions. Et si cela ne suffisait pas, il a ses adorateurs, ses fans absolus prêts à tout pour évangéliser les masses d'incrédules.
Ils sont convaincus que l'on doit abjurer Python, Java ou C++ pour suivre les voies sacrées de Clojure, Scheme ou Common Lisp.
Mais pourquoi un langage aussi étrangement archaïque continue d'attirer certains programmeurs?
Tout d'abord, Lisp est peut-être le langage le plus simple à implémenter. En effet, Lisp est d'une régularité tout à fait remarquable, puisque les opérateurs et les appels de fonction ont exactement la même syntaxe préfixée.
Comparons le code Python suivant:
def test(x):
y = 9*x/2+3*x
return y
print(test(10))avec le code Lisp suivant:
(defun tst(x):
(+ (* 9 (/ x 2)) (* 3 x))
)
A première vue, le code Python semble tout à fait lisible.
Pourtant, du fait des règles de précédence des opérateurs, cette expression se révèle beaucoup plus compliquée à interpréter que prévu.
Essayez de calculer 10 de tête, vous verrez que la tâche n'a rien d'aisée.
La version Lisp qui semble au premier coup d'oeil plus lourde et compliquée, ne présente en revanche aucune ambiguïté. Certes, elle est largement alourdie par des parenthèses, mais l'ordre d'exécution est tout à fait évident.
De fait, s'il fallait donner une interprétation préalable à cette expression, il y a de forte chance pour que ça ressemble à ça:
Les parenthèses n'apparaissent-elles pas désormais comme une solution élégante pour transcrire cet arbre sous une forme textuelle?
Soyons d'ailleurs honnête, personne n'écrierait une expression Python aussi ambiguë, un informaticien consciencieux implémenterait cette expression sous la forme suivante:
def test(x):
y = (9*(x/2))+(3*x)
return yIl rajouterait les fameuses parenthèses dans son expression pour la rendre explicite...
Ce qui rend Lisp très intéressant, c'est que la syntaxe du langage se confond avec son Arbre Syntaxique Abstrait... D'une certaine manière Ce Que Vous Voyez, C'est Ce Qui s'Exécute...
Rappelons quand même que lorsque l'on compile une expression Python, on passe nécessairement par une phase intermédiaire qui s'appelle justement l'Arbre Syntaxique Abstrait (ou Arbre de la Syntaxe Abstraite, selon la traduction directe dans Wikipedia).
La compilation d'un programme Lisp se réduit à une première phase de découpage en segments (tokens). Ensuite, il suffit d'effectuer un parcours séquentiel de cette liste, puis de partir en récursion à chaque parenthèse ouvrante et d'en sortir à chaque parenthèse fermante. Ainsi, à chaque point de récursion, on peut intercepter la compilation d'une expression pour l'interpréter ou la modifier localement au besoin.
Dans LispE, cela permet en particulier d'appliquer les macros ou de composer les expressions à base de map, filter ou autre takewhile.
Nous allons aussi y brancher le mécanisme de détection des récursions terminales...
Sous ce terme barbare se cache en fait un mécanisme extrêmement efficace pour transformer une récursion en une itération. Plus exactement, dans une telle fonction, le dernier appel coïncide avec l'obtention du résultat. Pour mieux comprendre ce que cette définition cache, il suffit d'examiner le code suivant:
# Oui, c'est du Python, l'idée, c'est de montrer que ce problème est universel
def fact(x):
if x == 1:
return 1
else:
return x * fact(x - 1)La version ci-dessus est non terminale. Il faut dépiler l'ensemble des appels avant d'obtenir le résultat.
Pour transformer ce code en une version terminale, il suffit de rajouter un paramètre à la fonction. Le but ici est que la fin du calcul doit coïncider avec le dernier appel de la fonction:
def fact(x,y):
if x == 1:
return y
else:
return fact(x - 1, x*y)
# Le premier appel est:
fact(3,1)Comme on le voit sur cette version, les calculs intermédiaires sont effectués au fur et a mesure de la récursion.
Lorsque x == 1, y contient déjà notre résultat.
Le code Python ci-dessus peut être simplement traduit en LispE sous la forme suivante:
(defun fact(x y)
(if (eq x 1)
y
(fact (- x 1) (* x y))
)
)
L'objectif est de faire en sorte que LispE lui reconnaisse une certaine qualité terminale.
La question que l'on se pose immédiatement est la suivante: comment identifier une récursion terminale?
Grâce au passage du témoin...
Tout d'abord, rappelons que la construction de l'Arbre Syntaxique Abstrait est le résultat d'une récursion non terminale. On descend en récursion à chaque parenthèse ouvrante et on remonte à chaque parenthèse fermante. Chaque appel renvoie une sous-liste que l'on range au retour de récursion dans la liste courante. Une fois l'ensemble des instructions analysées, cette liste courante est à son tour renvoyée à l'étage supérieur.
Le truc est le suivant: Si une fonction ne comprend qu'un seul bloc d'instructions, nous allons marquer la tête de ce bloc comme candidat possible pour une récursion terminale.
(defun fact(x y)
(if (eq x 1) ; <--- ce if est marqué comme potentiellement terminal
y
(fact (- x 1) (* x y))
)
)
L'astuce ici est très simple. Au moment de l'exécution du if, il suffit de transmettre le témoin à l'appel sélectionné. Chaque instruction va donc systématiquement recevoir cette marque à chaque appel.
(defun fact(x y)
(if (eq x 1) ; le if transmet sa marque à la prochaine instruction à être exécutée
y
(fact (- x 1) (* x y)) ; <-- on marque donc cette instruction
)
)
- S'il s'agit d'un appel récursif, il sera traité comme appel terminal...
- S'il s'agit d'un autre if, il recevra la marque à son tour.
- S'il s'agit d'une tout autre instruction, l'effet de cette marque sera sans effet.
Dans LispE, un appel identifié comme terminal recevra un traitement particulier. Ainsi, au lieu de rajouter une nouvelle zone d'arguments dans la pile d'exécution, comme lors d'un appel normal, on réutilise la zone courante pour écraser les arguments locaux avec leurs nouvelles valeurs. Puis on revient de récursion, sans exécuter le corps de la fonction, en renvoyant une valeur particulière: _TERMINAL.
Autrement dit, lorsqu'une récursion terminale est détectée:
- On met à jour la pile d'arguments
- On retourne la valeur _TERMINAL
// fonction_appelante est initialisée au premier appel
if (fonction_appelante == this && isTerminal())
update_stack();
return _TERMINAL;
}
Tout cela est bel et bien beau. Mais comment s'effectue l'exécution complète de la fonction?
En effet, si l'appel à la fonction consiste à simplement mettre à jour la pile, il faut bien que l'ensemble soit exécuté jusqu'à ce que le résultat soit obtenu...
La solution est toute bête... Il suffit de considérer chaque appel comme potentiellement terminal et d'effectuer une boucle à chaque appel de fonction. Si l'appel n'est pas terminal, cette boucle n'aura d'autre incidence qu'un test supplémentaire...
do {
element = eval(code_fonction);
}
while (element == _TERMINAL);
A chaque appel du code de la fonction, on reçoit une valeur en retour.
- Si cette valeur est _TERMINAL, cela signifie que la pile a été mise à jour et qu'une nouvelle itération est nécessaire
- Sinon, il s'agit d'une valeur de retour d'une fonction, et on sort immédiatement de la boucle
Ainsi, l'exécution d'une fonction peut se résumer au code suivant:
if (fonction_appelante == this && isTerminal()) {
update_stack();
return _TERMINAL;
}
create_new_stack();
update_stack();
fonction_appelante = this;
do {
element = eval(code_fonction);
}
while (element == _TERMINAL);Ce qui rend ce code très simple, c'est que la décision d'entrer en récursion terminale est purement locale. Elle n'implique aucune compilation particulière du code, aucune analyse complexe pour trouver exactement où ces appels vont avoir lieu. La mécanique en jeu implique seulement de marquer les lieux potentiels d'exécution terminale et de laisser l'interpréteur décider dynamiquement si ces appels pourront s'effectuer.
L'ensemble requiert moins de 20 lignes de code sur les 40.000 qui composent l'interpréteur, un coût mineur pour un mécanisme qui permet d'éviter de faire exploser la pile lors de calculs complexes.
Voici un dernier exemple où plus de 2.000.000 d'appels récursifs sont exécutés:
; Ça marche aussi pour les lambdas...
(
(lambda (x y)
(if (eq x 0)
(* 2 y)
(self (- x 1) (+ y 2))
)
)
2000000 1
)