Python optimise-t-il la récursivité de la queue?

206

J'ai le morceau de code suivant qui échoue avec l'erreur suivante:

RuntimeError: profondeur de récursivité maximale dépassée

J'ai essayé de réécrire ceci pour permettre l'optimisation de la récursivité de queue (TCO). Je pense que ce code aurait dû réussir si un TCO avait eu lieu.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Dois-je conclure que Python ne fait aucun type de TCO, ou dois-je simplement le définir différemment?

Jordan Mack
la source
11
@Wessie TCO tient compte de la dynamique ou de la statique du langage. Lua, par exemple, le fait aussi. Il vous suffit de reconnaître les appels de queue (assez simples, à la fois au niveau AST et au niveau du bytecode), puis de réutiliser le cadre de pile actuel au lieu d'en créer un nouveau (également simple, en fait encore plus simple dans les interprètes que dans le code natif) .
11
Oh, un mot: vous parlez exclusivement de récursivité de queue, mais utilisez l'acronyme "TCO", qui signifie optimisation d' appel de queue et s'applique à toute instance de return func(...)(explicitement ou implicitement), qu'elle soit récursive ou non. TCO est un sur-ensemble approprié de TRE, et plus utile (par exemple, il rend possible le style de passage de continuation, ce que TRE ne peut pas), et pas beaucoup plus difficile à mettre en œuvre.
1
Voici une façon hackée de l'implémenter - un décorateur utilisant la levée d'exceptions pour jeter les cadres d'exécution: metapython.blogspot.com.br/2010/11/…
jsbueno
2
Si vous vous limitez à la récursivité de queue, je ne pense pas qu'un traçage correct soit super utile. Vous avez un appel vers foode l'intérieur un appel vers foode l'intérieur vers foode l'intérieur un appel vers foo... Je ne pense pas que des informations utiles seraient perdues en perdant cela.
Kevin
1
J'ai récemment entendu parler de la noix de coco, mais je ne l'ai pas encore essayé. Cela vaut la peine d'y jeter un coup d'œil. Il est supposé avoir une optimisation de récursivité de queue.
Alexey

Réponses:

216

Non, et ce ne sera jamais le cas puisque Guido van Rossum préfère pouvoir avoir des retraits corrects:

Élimination de la récursivité de la queue (2009-04-22)

Derniers mots sur les appels de queue (2009-04-27)

Vous pouvez éliminer manuellement la récursivité avec une transformation comme celle-ci:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500
John La Rooy
la source
12
Ou si vous allez le transformer comme ça - juste from operator import add; reduce(add, xrange(n + 1), csum):?
Jon Clements
38
@JonClements, qui fonctionne dans cet exemple particulier. La transformation en boucle while fonctionne pour la récursivité de queue dans les cas généraux.
John La Rooy
25
+1 Pour être la bonne réponse, mais cela semble être une décision de conception incroyablement osée. Les raisons invoquées semblent se résumer à "c'est difficile à faire étant donné la façon dont le python est interprété et je n'aime pas ça quand même!"
Basic
12
@jwg Alors ... Quoi? Vous devez écrire une langue avant de pouvoir commenter les mauvaises décisions de conception? Cela semble à peine logique ou pratique. Je suppose de votre commentaire que vous n'avez aucune opinion sur les fonctionnalités (ou leur absence) dans une langue jamais écrite?
Basic
2
@Basic Non, mais vous devez lire l'article sur lequel vous commentez. Il semble très fortement que vous ne l'ayez pas lu, vu comment cela se résume à vous. (Vous devrez peut-être lire les deux articles liés, malheureusement, car certains arguments sont répartis sur les deux.) Cela n'a presque rien à voir avec l'implémentation du langage, mais tout à voir avec la sémantique voulue.
Veky
179

J'ai publié un module effectuant l'optimisation des appels de queue (gérant à la fois le style de récursion de queue et de passage de continuation): https://github.com/baruchel/tco

Optimisation de la récursivité de queue en Python

Il a souvent été affirmé que la récursivité de la queue ne convenait pas à la méthode de codage Pythonic et que l'on ne devrait pas se soucier de la façon de l'intégrer dans une boucle. Je ne veux pas contester ce point de vue; parfois cependant j'aime essayer ou implémenter de nouvelles idées en tant que fonctions récursives de queue plutôt qu'avec des boucles pour diverses raisons (se concentrer sur l'idée plutôt que sur le processus, avoir vingt fonctions courtes sur mon écran en même temps plutôt que seulement trois "Pythonic" fonctions, travailler dans une session interactive plutôt que de modifier mon code, etc.).

L'optimisation de la récursivité de queue en Python est en fait assez simple. Bien qu'il soit dit impossible ou très délicat, je pense qu'il peut être atteint avec des solutions élégantes, courtes et générales; Je pense même que la plupart de ces solutions n'utilisent pas les fonctionnalités Python autrement qu'elles ne le devraient. Des expressions lambda propres fonctionnant avec des boucles très standard conduisent à des outils rapides, efficaces et entièrement utilisables pour implémenter l'optimisation de récursivité de queue.

Pour plus de commodité, j'ai écrit un petit module implémentant une telle optimisation de deux manières différentes. Je voudrais discuter ici de mes deux fonctions principales.

La voie propre: modifier le combinateur Y

Le combinateur Y est bien connu; il permet d'utiliser les fonctions lambda de manière récursive, mais il ne permet pas à lui seul d'incorporer des appels récursifs dans une boucle. Le calcul lambda à lui seul ne peut pas faire une telle chose. Un léger changement dans le combinateur Y peut cependant protéger l'appel récursif à évaluer réellement. L'évaluation peut ainsi être retardée.

Voici la célèbre expression du combinateur Y:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

Avec un très léger changement, j'ai pu obtenir:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Au lieu de s'appeler elle-même, la fonction f renvoie maintenant une fonction effectuant le même appel, mais puisqu'elle le renvoie, l'évaluation peut être effectuée plus tard de l'extérieur.

Mon code est:

def bet(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

La fonction peut être utilisée de la manière suivante; voici deux exemples avec les versions récursives de queue de factorielle et de Fibonacci:

>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

De toute évidence, la profondeur de récursivité n'est plus un problème:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

C'est bien sûr le seul véritable objectif de la fonction.

Une seule chose ne peut pas être faite avec cette optimisation: elle ne peut pas être utilisée avec une fonction récursive de queue évaluant une autre fonction (cela vient du fait que les objets retournés appelables sont tous traités comme des appels récursifs supplémentaires sans distinction). Comme je n'ai généralement pas besoin d'une telle fonctionnalité, je suis très satisfait du code ci-dessus. Cependant, afin de fournir un module plus général, j'ai réfléchi un peu plus afin de trouver une solution de contournement pour ce problème (voir la section suivante).

Concernant la rapidité de ce processus (qui n'est pas le vrai problème cependant), il se trouve être assez bon; Les fonctions récursives de queue sont même évaluées beaucoup plus rapidement qu'avec le code suivant à l'aide d'expressions plus simples:

def bet1(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

Je pense que l'évaluation d'une expression, même compliquée, est beaucoup plus rapide que l'évaluation de plusieurs expressions simples, ce qui est le cas dans cette deuxième version. Je n'ai pas gardé cette nouvelle fonction dans mon module, et je ne vois aucune circonstance où elle pourrait être utilisée plutôt que celle "officielle".

Style de passage de continuation avec exceptions

Voici une fonction plus générale; il est capable de gérer toutes les fonctions récursives de queue, y compris celles renvoyant d'autres fonctions. Les appels récursifs sont reconnus à partir d'autres valeurs de retour par l'utilisation d'exceptions. Cette solution est plus lente que la précédente; un code plus rapide pourrait probablement être écrit en utilisant des valeurs spéciales comme "drapeaux" détectés dans la boucle principale, mais je n'aime pas l'idée d'utiliser des valeurs spéciales ou des mots clés internes. Il y a une interprétation amusante de l'utilisation des exceptions: si Python n'aime pas les appels récursifs à la queue, une exception devrait être levée lorsqu'un appel récursif à la queue se produit, et la manière Pythonique sera de capturer l'exception afin de trouver des éléments propres solution, qui est en fait ce qui se passe ici ...

class _RecursiveCall(Exception):
  def __init__(self, *args):
    self.args = args
def _recursiveCallback(*args):
  raise _RecursiveCall(*args)
def bet0(func):
    def wrapper(*args):
        while True:
          try:
            return func(_recursiveCallback)(*args)
          except _RecursiveCall as e:
            args = e.args
    return wrapper

Maintenant, toutes les fonctions peuvent être utilisées. Dans l'exemple suivant, f(n)est évalué à la fonction d'identité pour toute valeur positive de n:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Bien sûr, on pourrait faire valoir que les exceptions ne sont pas destinées à être utilisées pour rediriger intentionnellement l'interprète (comme une sorte de gotodéclaration ou probablement plutôt une sorte de style de passage de continuation), ce que je dois admettre. Mais, encore une fois, je trouve drôle l'idée d'utiliser tryune seule ligne comme une returndéclaration: nous essayons de renvoyer quelque chose (comportement normal) mais nous ne pouvons pas le faire à cause d'un appel récursif (exception).

Réponse initiale (2013-08-29).

J'ai écrit un très petit plugin pour gérer la récursivité de la queue. Vous pouvez le trouver avec mes explications là-bas: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Il peut incorporer une fonction lambda écrite avec un style de récursivité de queue dans une autre fonction qui l'évaluera comme une boucle.

La caractéristique la plus intéressante de cette petite fonction, à mon humble avis, est que la fonction ne repose pas sur un hack de programmation sale mais sur un simple calcul lambda: le comportement de la fonction est changé en un autre lorsqu'elle est insérée dans une autre fonction lambda qui ressemble beaucoup au combinateur Y.

Thomas Baruchel
la source
Pourriez-vous, s'il vous plaît, fournir un exemple de définition d'une fonction (de préférence similaire à une définition normale) qui appelle en queue l'une des nombreuses autres fonctions en fonction d'une condition, en utilisant votre méthode? En outre, votre fonction d'emballage peut-ellebet0 peut-elle être utilisée comme décorateur pour les méthodes de classe?
Alexey
@Alexey Je ne suis pas sûr de pouvoir écrire du code dans un style bloc dans un commentaire, mais vous pouvez bien sûr utiliser la defsyntaxe pour vos fonctions, et en fait le dernier exemple ci-dessus repose sur une condition. Dans mon article baruchel.github.io/python/2015/11/07/… vous pouvez voir un paragraphe commençant par "Bien sûr, vous pourriez objecter que personne n'écrirait un tel code" où je donne un exemple avec la syntaxe de définition habituelle. Pour la deuxième partie de votre question, je dois y réfléchir un peu plus car je n'y ai pas consacré de temps depuis un moment. Cordialement.
Thomas Baruchel
Vous devez vous soucier de l'endroit où l'appel récursif se produit dans votre fonction même si vous utilisez une implémentation de langage non TCO. En effet, la partie de la fonction qui se produit après l'appel récursif est la partie qui doit être stockée sur la pile. Par conséquent, rendre votre fonction récursive à la queue minimise la quantité d'informations que vous devez stocker par appel récursif, ce qui vous donne plus d'espace pour disposer de grandes piles d'appels récursifs si vous en avez besoin.
josiah
21

Le mot de Guido est sur http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

J'ai récemment publié une entrée dans mon blog sur l'histoire de Python sur les origines des fonctionnalités de Python. Une remarque secondaire sur le fait de ne pas prendre en charge l'élimination de la récursivité de la queue (TRE) a immédiatement déclenché plusieurs commentaires sur le dommage que Python ne le fasse pas, y compris des liens vers des entrées de blog récentes par d'autres essayant de "prouver" que TRE peut être ajouté à Python. facilement. Alors laissez-moi défendre ma position (c'est-à-dire que je ne veux pas de TRE dans la langue). Si vous voulez une réponse courte, c'est tout simplement impythonique. Voici la longue réponse:

Jon Clements
la source
12
Et c'est là que réside le problème avec ce qu'on appelle BDsFL.
Adam Donahue
6
@AdamDonahue avez-vous été parfaitement satisfait de chaque décision prise par un comité? Au moins, vous obtenez une explication raisonnée et faisant autorité du BDFL.
Mark Ransom
2
Non, bien sûr que non, mais ils me paraissent plus impartiaux. Ceci d'un prescriptiviste, pas d'un descriptiviste. L'ironie.
Adam Donahue
6

CPython ne prend pas et ne soutiendra probablement jamais l'optimisation des appels de queue basée sur les déclarations de Guido van Rossum sur le sujet.

J'ai entendu des arguments selon lesquels cela rend le débogage plus difficile en raison de la façon dont il modifie la trace de la pile.

récursif
la source
18
@mux CPython est l'implémentation de référence du langage de programmation Python. Il existe d'autres implémentations (telles que PyPy, IronPython et Jython), qui implémentent le même langage mais diffèrent dans les détails d'implémentation. La distinction est utile ici car (en théorie) il est possible de créer une implémentation alternative de Python qui fait du TCO. Je ne suis au courant de personne qui y pense même, et l'utilité serait limitée car le code qui en dépendrait se briserait sur toutes les autres implémentations Python.
3

Essayez la mise en œuvre expérimentale du TCO de la macropie pour la taille.

Mark Lawrence
la source
2

Outre l'optimisation de la récursivité de la queue, vous pouvez définir manuellement la profondeur de récursivité en:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
zhenv5
la source
5
Pourquoi n'utilisez-vous pas simplement jQuery?
Jeremy Hert
5
Parce que ce aussi n'offre pas TCO? :-D stackoverflow.com/questions/3660577/…
Veky