Ca c’est un titre qui en jette ! Faut dire que je tiens du maître Sokal himself.
Donc, vulgarisons un peu. Ca sera un article bien prise de tête. Lisez-le un dimanche soir quand vous ne captez pas arte (et si vous ne pigez rien, c’est pas grave, revenez dans un an, moi je le fais bien avec tous les articles d’Alex Martelli).
Un appel récursif, c’est une fonction qui s’appelle elle-même. Et en Python ça donne ça:
def fonction_recursive(): print "Je suis récursive, fuck yeah !" fonction_recursive() |
Et sa sortie va ressembler à ça:
>>> fonction_recursive() Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! Je suis récursive, fuck yeah ! [...] |
Un peu comme une boucle infinie:
while True: print "Je suis récursive, fuck yeah !" |
Car la fonction s’appelle elle même indéfiniement.
Les boucles infinies peuvent être utiles, mais en Python, les récursions infinies sont vachement craignos, parcequ’elles aboutissent toujours à ce message d’erreur:
RuntimeError: maximum recursion depth exceeded |
En effet, une boucle infinie est une sucession d’opération les une après les autres, mais une récursion infinie est une succession d’opérations les unes dans les autres. Et comme Python garde en mémoire une pile de chaque appel de fonction (c’est entre autre ce qui vous permet de voir le fameux stack trace quand il y a une erreur et remonter jusqu’à la source du plantage au moment d’une exception), il finit par remplir la pile, qui par défaut a une limite de 1000 entrées.
Du coup, en Python, quand on fait du récursif, on est obligé de faire une condition de sortie, du genre:
def fonction_recursive(count=0): if count > 100: return print "Je suis récursive, fuck yeah !" fonction_recursive(count + 1) |
Ce qui va ici limité le nombre d’appels récursifs à 100.
On ne va pas discuter de la pertinence de la récursivité, mais toujours est-il que Python est limité de ce côté, et c’est un choix délibéré.
Il est limité car dans d’autres langages, tels que Lisp et Erlang, on peut faire autant de récursion qu’on le souhaite, pourvu qu’on écrive la récursion d’une certaine façon. C’est ce qu’on appelle la TCO, Tail Call Optimisation: le pile d’appels est vidée au fur et à mesure et ne devient jamais pleine.
Comment ça s’utilise et pourquoi ça marche peut faire l’objet d’un article à lui tout seul, et ce n’est pas le but ici.
Le but de l’article est de répondre à une question que certains habitués de la récursion se posent: comment faire des state machines en Python ?
En effet, une manière très élégante de coder une state machine, ou automate fini, est justement d’utiliser une récusion infinie:
def etat3(a, b, c): print "Etat 3" print a, b, c etat1(a, b, c) def etat2(a, b, c): print "Etat 2" print a, b, c etat3(a, b, c) def etat1(a, b, c): print "Etat 3" print a, b, c etat2(a, b, c) etat1(1, 2, 3) |
Cela permet de faire transiter le code d’un état à un autre sans se soucier de stocker l’état courant, sans barder le programme de if/else, et le code est beaucoup plus élégant et simple à suivre (c’est un état qui change, c’est tout):
etat1 => etat2 => etat3 => etat1 => etat2 => etat3 => etc
Enfin plus simple, pourvu qu’on code proprement, car la récursion infinie, c’est au fond une forme ultime de goto (instruction qui par ailleurs est bannie de Python).
Mais, si vous l’avez remarqué, pour faire une state machine de cette manière, il nous faut des appels infinis (la state machine n’est pas sensée s’arrêter au bout de 1000 appels), et donc une TCO, ce que Python ne possède pas.
C’est évidement sans comptez notre Guido favoris qui nous a pondu la solution au problème, version Python:
def etat3(a, b, c): print "Etat 3" print a, b, c return etat1, [a, b, c] def etat2(a, b, c): print "Etat 2" print a, b, c return etat3, [a, b, c] def etat1(a, b, c): print "Etat 3" print a, b, c return etat2, [a, b, c] func, args = etat1, [1, 2, 3] while True: func, args = func(*args) |
Et voilà, nous avons le même effet (et les mêmes possibilités de sortie, condition, etc), mais en procédural plutôt qu’en purement fonctionnel. Toute l’astuce consiste à retourner le prochain état désiré au lieu de l’éxécuter, et de laisser la boucle principale se charger des appels.
Le bloc while est rarement utilisé en Python, à part justement pour des main loops (souvent infinies), et c’est probablement l’usage le plus pertinent que j’ai vu depuis longtemps.
J’aime
Super classe.
Il s’agit ni plus ni moins de faire du TCO à la main. ça marche mais c’est pas très convaincant. (On peut faire de même avec un décorateur qui explore les stackframes et fait ce qu’il faut).
( A noter aussi qu’il s’agit d’un limitation de l’interpréteur CPython, je ne suis pas sur que Pypy ou Jython aient les mêmes limitations. )
L’intégrer à l’interpréteur serait plus élégant mais Guido est contre malgré la démonstration que ce serait sans véritable inconvénient. Il est tétu le bougre. Il n’aime pas la programmation fonctionnelle et vu que la TCO favorise ce type de codage, ce n’est pas très étonnant.
La simplicité de l’interpréteur CPython est à la fois la meilleur chose et le plus grand frein (GIL, TCO), etc. Il suffit de voir LuaJit pour comprendre que d’autre choix sont possible…
Avec Stackless Python on peut faire un carton et franchir la barre des 1000 entrées ;)
Oui, c’est une forme de TCO à la main, avec une différence: python ne supprime pas d’entrées arbitrairement dans la stack, ce qui est fort chouette pour le débuggage.
Par ailleurs, je pense que l’entêtement de guido tient du fait qu’il veut garder le style de Python orientée d’une certaine façon. Il y a des tas d’autres très bons langages qui permettent de faire autrement, donc pour lui, il n’y a pas de raison de transformer Python en un de ses langages.
Je trouve que ça se tient: c’est une bonne chose qu’il y ai différents styles et différentes capacités pour chaque techno. Une techo fourre tout qui fait tout ce que font les autres ne marchent jamais.
Bon par contre, moins élégant que la version récursive, je veux bien. Mais quand même plus élégant qu’une exploration de stack frame hein :-) Explicit is better than implicit, tout ça.
@gael:
Ouai comme le précise LB, la limite est une question d’implémentation. Vous avez essayé Stackless ? Je n’ai aucun retour de mise en prod et je suis curieux d’avoir un feedback.
En fait j’avais pas réaliser que la TCO, c’est un peu comme VI/Emacs, tab/spaces, libre/proprio… C’est une grosse guerre de religion. Mais au final, ce qui est rassurant, c’est que généralement tous ceux qui sont assez barrés pour s’engager dans le débat sont en général de bons professionels. Le dev lambda (sans jeu de mot), il s’en branle.
Je le met là car on ne sait jamais:
Pour les fans de récursions.
Une petit lib sympas pour faire des states machines bien propres:
https://github.com/rbarrois/xworkflows
J’adore le titre du post…
Quoi, la machine a etat non recursive ? Oui, j’aime beaucoup aussi.
Direction illico dans mes bookmarks :-)
Merci pour l’article, j’avais utilisé ceci pour faire de la récursivité terminale en python: http://metapython.blogspot.be.
Usage à la fin pour la fonction factorielle:
@tailrecursivedef tail_fatorial (n, a=1):
if n == 1:
return a * 1
return tail_fatorial(n -1, n * a)