Qu'est-ce que l'élimination de la récursivité de la queue?

Question

Steve Yegge l'a mentionné dans un blog post et je n'ai aucune idée de ce que cela signifie, quelqu'un pourrait me remplir? Est-ce la même chose que tail call optimization?

Answer 1

L'élimination d'appel de queue est une optimisation qui économise pile espace. Elle remplace une fonction appel avec un goto. élimination récursive de la queue est la même chose, mais avec la contrainte supplémentaire que la fonction appelle lui-même.

en fait, si la dernière chose fonction A est return A(params...) alors vous pouvez éliminer l'allocation d'un cadre de pile et au lieu de définir les registres appropriés et sauter directement dans le corps de la fonction. Envisager une convention d'appel (imaginaire) qui passe tous les paramètres de la pile et renvoie la valeur dans un registre.

Certaines fonctions pourraient compiler jusqu'à (dans un langage d'assemblage imaginaire):

function: 
//Reading params B, C, & D off the stack 
pop B 
pop C 
pop D 
//Do something meaningful, including a base case return 
... 
//Pass new values for B, C, & D to a new invocation of function on the stack 
push D* 
push C* 
push B* 
call function 
ret 

Quelle que soit ce qui précède ne fait, il faut un nouveau cadre de pile entière pour chaque appel à la fonction. Cependant, puisque rien ne se produit après l'appel de la queue pour fonctionner, sauf un retour, nous pouvons optimiser ce cas en toute sécurité.

Entraînant:

function: 
//Reading params B, C, & D off the stack (but only on the first call) 
pop B 
pop C 
pop D 
function_tail_optimized: 
//Do something meaningful, including a base case return 
... 
//Instead of a new stack frame, load the new values directly into the registers 
load B, B* 
load C, C* 
load D, D* 
//Don't call, instead jump directly back into the function 
jump function_tail_optimized 

Le résultat final est une fonction équivalente qui permet d'économiser beaucoup d'espace de pile, en particulier pour les entrées qui donnent lieu à un grand nombre d'appels récursifs.

Il y a beaucoup d'imagination dans ma réponse, mais je pense que vous pouvez avoir l'idée.

Answer 2

de here:

» ... l'élimination de la récursion arrière est un cas particulier de l'élimination appel de queue dans lequel l'appel de la queue est un appel à la fonction elle-même Dans ce cas, le appel. peut être remplacé par un saut au début de la fonction après le déplacement des nouveaux arguments aux appropriés registres ou emplacements de la pile ... »

de Wikipedia:

» ... Quand une fonction est appelée, l'ordinateur doit « se souvenir » l'endroit où il a été appelé à partir, l'adresse de retour, afin qu'il puisse revenir à cet endroit avec le résultat une fois que la l'appel est terminé. Typiquement, ces informations sont sauvegardées sur la pile, une simple liste d'emplacements de retour dans l'ordre des heures auxquelles les emplacements d'appel qu'ils décrivent ont été atteints. Parfois, la dernière chose que fait une fonction après avoir terminé toutes les autres opérations est simplement d'appeler une fonction, éventuellement elle-même, et de renvoyer son résultat. Avec la récursion de queue, il n'est pas nécessaire de se souvenir de l'endroit d'où nous appelons - à la place, nous pouvons laisser la pile seule, et la nouvelle fonction appelée retournera son résultat directement à l'appelant d'origine. La conversion d'un appel vers une branche ou un saut dans un tel cas s'appelle une optimisation d'appel de fin. Notez que l'appel de queue ne doit pas apparaître lexicalement après toutes les autres instructions dans le code source; il est seulement important que son résultat soit immédiatement renvoyé, puisque la fonction appelante n'aura aucune chance de faire quoi que ce soit après l'appel si l'optimisation est effectuée .... "