Est-ce un moyen générique de convertir une procédure récursive en récursivité de queue?

13

Il semble que j'ai trouvé un moyen générique de convertir toute procédure récursive en récursion de queue:

  1. Définissez une sous-procédure d'assistance avec un paramètre "résultat" supplémentaire.
  2. Appliquez ce qui serait appliqué à la valeur de retour de la procédure à ce paramètre.
  3. Appelez cette procédure d'assistance pour commencer. La valeur initiale du paramètre "result" est la valeur du point de sortie du processus récursif, de sorte que le processus itératif résultant commence à partir de l'endroit où le processus récursif commence à diminuer.

Par exemple, voici la procédure récursive d'origine à convertir ( exercice SICP 1.17 ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Voici la procédure convertie et récursive de queue ( exercice SICP 1.18 ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Quelqu'un peut-il prouver ou infirmer cela?

nalzok
la source
1
O(Journaln)
Deuxième réflexion: choisir bd'être une puissance de 2 montre que le réglage initial productà 0 n'est pas tout à fait correct; mais le changer en 1 ne fonctionne pas quand bc'est étrange. Peut-être avez-vous besoin de 2 paramètres d'accumulateur différents?
j_random_hacker
3
Vous n'avez pas vraiment défini de transformation d'une définition récursive non-queue, l'ajout d'un paramètre de résultat et son utilisation pour l'accumulation est assez vague et ne se généralise guère aux cas plus complexes, par exemple les traversées d'arbres, où vous avez deux appels récursifs. Une idée plus précise de "continuation" existe cependant, dans laquelle vous effectuez une partie du travail, puis laissez une fonction de "continuation" prendre le relais, recevant en paramètre le travail que vous avez effectué jusqu'à présent. Il est appelé style de passage de continuation (cps), voir en.wikipedia.org/wiki/Continuation-passing_style .
Ariel
4
Ces diapositives fsl.cs.illinois.edu/images/d/d5/CS422-Fall-2006-13.pdf contiennent une description de la transformation cps, dans laquelle vous prenez une expression arbitraire (éventuellement avec des définitions de fonction avec des appels non-tail) et le transformer en une expression équivalente avec seulement des appels de queue.
Ariel
@j_random_hacker Oui, je peux voir que ma procédure "convertie" est en fait fausse ...
nalzok

Réponses:

12

Votre description de votre algorithme est vraiment trop vague pour l'évaluer à ce stade. Mais, voici quelques éléments à considérer.

CPS

En fait, il existe un moyen de transformer n'importe quel code en un formulaire qui n'utilise que des appels de queue. Il s'agit de la transformation CPS. CPS ( Continuation-Passing Style ) est une forme d'expression de code en passant à chaque fonction une continuation. Une continuation est une notion abstraite représentant "le reste d'un calcul". Dans le code exprimé sous forme CPS, la façon naturelle de réifier une continuation est comme une fonction qui accepte une valeur. Dans CPS, au lieu d'une fonction renvoyant une valeur, il applique à la place la fonction représentant la continuation en cours au "retourné" par la fonction.

Par exemple, considérez la fonction suivante:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Cela pourrait être exprimé en CPS comme suit:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

C'est moche et souvent lent, mais cela présente certains avantages:

  • La transformation peut être complètement automatisée. Il n'est donc pas nécessaire d'écrire (ou de voir) le code sous forme CPS.
  • Combiné avec le thunking et le trampoline , il peut être utilisé pour fournir une optimisation des appels de queue dans des langues qui ne fournissent pas d'optimisation des appels de queue. (L'optimisation de l'appel de queue des fonctions directement récursives de la queue peut être réalisée par d'autres moyens, tels que la conversion de l'appel récursif en boucle. Mais la récursivité indirecte n'est pas aussi triviale à convertir de cette manière.)
  • Avec CPS, les continuations deviennent des objets de première classe. Étant donné que les continuations sont l'essence du contrôle, cela permet à pratiquement n'importe quel opérateur de contrôle d'être implémenté comme une bibliothèque sans nécessiter de prise en charge particulière de la langue. Par exemple, goto, exceptions et threading coopératif peuvent tous être modélisés à l'aide de continuations.

TCO

Il me semble que la seule raison de se préoccuper de la récursivité de queue (ou des appels de queue en général) est à des fins d'optimisation de l'appel de queue (TCO). Donc, je pense qu'une meilleure question à poser est "ma transformation donne-t-elle un code qui soit optimisé par l'appel de queue?".

Si nous considérons une fois de plus CPS, l'une de ses caractéristiques est que le code exprimé en CPS consiste uniquement en appels de queue. Puisque tout est un appel de queue, nous n'avons pas besoin d'enregistrer un point de retour dans la pile. Donc, tout le code sous forme CPS doit être optimisé pour les appels de queue, non?

Enfin, pas tout à fait. Vous voyez, alors qu'il peut sembler que nous avons éliminé la pile, tout ce que nous avons fait est simplement de changer la façon dont nous la représentons. La pile fait maintenant partie de la fermeture représentant une continuation. Donc, CPS ne fait pas comme par magie tous nos appels de code optimisés.

Donc, si CPS ne peut pas tout faire TCO, y a-t-il une transformation spécifiquement pour la récursivité directe qui le peut? Non, pas en général. Certaines récursions sont linéaires, mais d'autres ne le sont pas. Les récursions non linéaires (par exemple, arborescentes) doivent simplement maintenir un état variable quelque part.

Nathan Davis
la source
c'est un peu déroutant quand dans la sous-section " TCO ", quand vous dites "tail-call optimisé" vous voulez dire "avec une utilisation constante de la mémoire". Le fait que l'utilisation dynamique de la mémoire ne soit pas constante n'annule pas le fait que les appels sont en effet en queue et qu'il n'y a pas de croissance illimitée dans l' utilisation de la pile . Le SICP appelle de tels calculs «itératifs», donc dire «bien que ce soit le TCO, ça ne le rend toujours pas itératif» aurait pu être une meilleure formulation (pour moi).
Will Ness
@WillNess Nous avons encore une pile d'appels, elle est simplement représentée différemment. La structure ne change pas simplement parce que nous utilisons le tas plutôt que la pile matérielle . Après tout, il existe de nombreuses structures de données basées sur la mémoire de tas dynamique qui ont «pile» dans leur nom.
Nathan Davis
le seul point ici est que certaines langues ont des limites câblées à l'utilisation de la pile d'appels.
Will Ness