Appel de queue

En informatique , un appel de queue est un appel de sous- programme exécuté comme action finale d’une procédure. ^[1] Si la cible d’une queue est la même sous-routine, la sous-routine est dite récursive de queue , ce qui est un cas particulier de récursivité directe . La récursivité terminale (ou récursion terminale ) est particulièrement utile et souvent facile à gérer pour l’optimisation des implémentations.

Les appels de queue peuvent être implémentés sans ajouter de nouveau Cadre de pile à la pile d’appels . La majeure partie du cadre de la procédure actuelle n’est plus nécessaire et peut être remplacée par le cadre de l’appel de queue, modifié selon les besoins (similaire à la superposition pour les processus, mais pour les appels de fonction). Le programme peut alors sauter au sous-programme appelé. La production d’un tel code au lieu d’une séquence d’appel standard est appelée élimination de l’appel final ou optimisation de l’appel final . L’élimination des appels de queue permet aux appels de procédure en position de queue d’être implémentés aussi efficacement que les instructions goto , permettant ainsi une programmation structurée efficace . Dans les paroles deGuy L. Steele , “en général, les appels de procédure peuvent être utilement considérés comme des instructions GOTO qui transmettent également des paramètres et peuvent être codés de manière uniforme comme des instructions JUMP [de code machine].” ^[2]

Tous les langages de programmation ne nécessitent pas l’élimination des appels terminaux. Cependant, dans les langages de programmation fonctionnels , l’élimination des appels de queue est souvent garantie par la norme de langage , permettant à la récursivité de queue d’utiliser une quantité de mémoire similaire à celle d’une boucle équivalente . Le cas particulier des appels récursifs de queue, lorsqu’une fonction s’appelle elle-même, peut être plus propice à l’élimination des appels que les appels de queue généraux. Lorsque la sémantique du langage ne prend pas explicitement en charge les appels de queue généraux, un compilateur peut souvent encore optimiser les appels frères ou les appels de queue aux fonctions qui prennent et renvoient les mêmes types que l’appelant. ^[3]

La description

Lorsqu’une fonction est appelée, l’ordinateur doit “se souvenir” de l’endroit d’où il a été appelé, l’ adresse de retour , afin qu’il puisse revenir à cet endroit avec le résultat une fois l’appel terminé. En règle générale, ces informations sont enregistrées sur la pile d’appels , une simple liste d’emplacements de retour dans l’ordre des heures auxquelles les emplacements d’appel qu’ils décrivent ont été atteints. Pour les appels de queue, il n’est pas nécessaire de se souvenir de l’appelant – à la place, l’élimination des appels de queue n’apporte que les modifications minimales nécessaires au Cadre de pile avant de le transmettre, ^[4] et la fonction appelée de queue reviendra directement à l’ originalvotre interlocuteur. L’appel de queue n’a pas à apparaître lexicalement après toutes les autres déclarations dans le code source ; il est seulement important que la fonction appelante revienne immédiatement après l’appel de queue, renvoyant le résultat de l’appel de queue le cas échéant, puisque la fonction appelante est contournée lorsque l’optimisation est effectuée.

Pour les appels de fonction non récursifs, il s’agit généralement d’une optimisation qui ne fait gagner que peu de temps et d’espace, car il n’y a pas beaucoup de fonctions différentes disponibles à appeler. Cependant, lorsqu’il s’agit de fonctions récursives ou mutuellement récursives où la récursivité se produit via des appels de queue, l’espace de pile et le nombre de retours économisés peuvent devenir très importants, car une fonction peut s’appeler elle-même, directement ou indirectement, créant un nouveau Cadre de pile d’appels. chaque fois. L’élimination des appels de queue réduit souvent les exigences asymptotiques d’espace de pile de linéaire, ou O (n), à constant, ou O (1). L’élimination des appels de queue est donc requise par les définitions standard de certains langages de programmation, tels que Scheme , ^[5][6] et les langues de la famille ML entre autres. La définition du langage Scheme formalise exactement la notion intuitive de position de la queue, en spécifiant quelles formes syntaxiques permettent d’avoir des résultats dans le contexte de la queue. ^[7] Les implémentations permettant à un nombre illimité d’appels de queue d’être actifs au même moment, grâce à l’élimination des appels de queue, peuvent aussi être appelées ‘proprement récursives de queue’. ^[5]

Outre l’espace et l’efficacité d’exécution, l’élimination des appels de queue est importante dans l’ idiome de programmation fonctionnel connu sous le nom de style de passage de continuation (CPS), qui autrement manquerait rapidement d’espace de pile.

Forme syntaxique

Un appel de fin peut être situé juste avant la fin syntaxique d’une fonction :

fonction foo ( données ) { une ( données ); retourner b ( données ); }

Ici, les deux a(data)et b(data)sont des appels, mais bc’est la dernière chose que la procédure exécute avant de revenir et est donc en position de queue. Cependant, tous les appels de queue ne sont pas nécessairement situés à la fin syntaxique d’un sous-programme :

barre de fonction ( données ) { si ( a ( données ) ) { retour b ( données ); } retourne c ( données ); }

Ici, les deux appels à bet csont en position de queue. En effet, chacun d’eux se trouve respectivement à la fin de la branche if, même si le premier n’est pas syntaxiquement à la fin du barcorps de .

Dans ce code :

fonction foo1 ( données ) { renvoie une ( données ) + 1 ; } fonction foo2 ( données ) { var ret = a ( données ); retour ret ; } fonction foo3 ( données ) { var ret = a ( données ); retour ( ret == 0 ) ? 1 : ret ; }

l’appel à a(data)est en position terminale dans foo2, mais il n’est pas en position terminale ni dans foo1ni dans foo3, car le contrôle doit revenir à l’appelant pour lui permettre d’inspecter ou de modifier la valeur de retour avant de la renvoyer.

Exemples de programmes

Le programme suivant est un exemple dans Scheme : ^[8]

;; factorielle : nombre -> nombre ;; pour calculer le produit de tous les ;; positifs entiers inférieurs ou égaux à n. ( définir ( factorielle n ) ( si ( = n 0 ) 1 ( * n ( factorielle ( – n 1 )))))

Ceci n’est pas écrit dans un style récursif de queue, car la fonction de multiplication (“*”) est en position de queue. Cela peut être comparé à :

;; factorielle : nombre -> nombre ;; pour calculer le produit de tous les ;; positifs entiers inférieurs ou égaux à n. ( définir ( factoriel n ) ( fact-iter 1 n )) ( définir ( fact-iter product n ) ( if ( = n 0 ) product ( fact-iter ( * product n ) ( – n 1 ))))

Ce programme suppose une évaluation d’ordre applicatif . La procédure interne fact-iters’appelle elle-même en dernier dans le flux de contrôle. Cela permet à un interpréteur ou compilateur de réorganiser l’exécution qui ressemblerait normalement à ceci : ^[8]

appeler factorielle (4) appeler fact-iter (1 4) appeler fact-iter (4 3) appeler fact-iter (12 2) appeler fact-iter (24 1) retour 24 retour 24 retour 24 retour 24 retour 24

dans la variante la plus efficace , en termes d’espace et de temps :

appeler factorielle (4) appeler fact-iter (1 4) remplacer les arguments par (4 3) remplacer les arguments par (12 2) remplacer les arguments par (24 1) retour 24 retour 24

Cette réorganisation économise de l’espace car aucun état à l’exception de l’adresse de la fonction appelante n’a besoin d’être sauvegardé, que ce soit sur la pile ou sur le tas, et le Cadre de pile d’appel pour fact-iterest réutilisé pour le stockage des résultats intermédiaires. Cela signifie également que le programmeur n’a pas à s’inquiéter de manquer d’espace de pile ou de tas pour des récursions extrêmement profondes. Dans les implémentations typiques, la variante récursive de queue sera sensiblement plus rapide que l’autre variante, mais seulement d’un facteur constant.

Certains programmeurs travaillant dans des langages fonctionnels réécriront le code récursif pour qu’il soit récursif de queue afin qu’ils puissent tirer parti de cette fonctionnalité. Cela nécessite souvent l’ajout d’un argument “accumulateur” ( productdans l’exemple ci-dessus) à la fonction. Dans certains cas (tels que les listes de filtrage) et dans certains langages, la récursivité complète peut nécessiter l’écriture d’une fonction qui était auparavant purement fonctionnelle de sorte qu’elle mute les références stockées dans d’autres variables. ^{[ citation nécessaire ]}

Queue récursive modulo contre

La récursivité terminale modulo contre est une généralisation de l’optimisation par récursivité terminale introduite par David HD Warren ^[9] dans le cadre de la compilation de Prolog , vu comme un langage explicitement défini une fois . Il a été décrit (mais pas nommé) par Daniel P. Friedman et David S. Wise en 1974 ^[10] comme une technique de compilation LISP . Comme son nom l’indique, il s’applique lorsque la seule opération restant à effectuer après un appel récursif est d’ajouter une valeur connue devant la liste renvoyée (ou d’effectuer un nombre constant d’opérations simples de construction de données, en général). Cet appel serait donc untail call save for (” modulo “) ladite opération contre . Mais préfixer une valeur au début d’une liste à la sortie d’un appel récursif revient à ajouter cette valeur à la fin de la liste croissante à l’entrée de l’appel récursif, construisant ainsi la liste comme un effet secondaire , comme si dans un paramètre d’accumulateur implicite. Le fragment Prolog suivant illustre le concept :

Exemple de code

% Prolog, queue récursive modulo contre : partition ([], _ , [], []). partition ([ X | Xs ], Pivot , [ X | Rest ], Bigs ) :- X @< Pivot , !, partition ( Xs , Pivot , Rest , Bigs ). partition ([ X | Xs ], Pivot , Smalls , [ X | Rest]) :- partition ( Xs , Pivot , Smalls , Rest ).	— Dans Haskell, récursion gardée : partition :: Ord a => [ a ] ​​-> a -> ([ a ],[ a ]) partition [] _ ​​= ( [] , [] ) partition ( x : xs ) p | x < p = ( x : une , b ) | sinon = ( une , x : b ) où ( a , b ) = partition xs p
% Prolog, avec des unifications explicites : % traduction récursive sans queue : partition ([], _ , [], []). partition ( L , Pivot , Petits , Grands ) :- L = [ X | Xs ], ( X @< Pivot -> partition ( Xs , Pivot , Rest , Bigs ), Smalls = [ X | Rest ] ; partition( Xs , Pivot , Smalls , Rest ), Bigs = [ X | Reste ] ).	% Prolog, avec des unifications explicites : % translation récursive de fin : partition ([], _ , [], []). partition ( L , Pivot , Petits , Grands ) :- L = [ X | Xs ], ( X @< Pivot -> Smalls = [ X | Rest ], partition ( Xs , Pivot , Rest , Bigs ) ; Bigs =[ X | Rest ], partition ( Xs , Pivot , Smalls , Rest ) ).

Ainsi, dans la traduction récursive de queue, un tel appel est transformé en créant d’abord un nouveau nœud de liste et en définissant son firstchamp, puis en effectuant l’appel de queue avec le pointeur vers le restchamp du nœud comme argument, à remplir récursivement. Le même effet est obtenu lorsque la récursivité est protégée par un constructeur de données évalué paresseusement, ce qui est automatiquement réalisé dans des langages de programmation paresseux comme Haskell.

Exemple C

Le fragment suivant définit une fonction récursive en C qui duplique une liste chaînée (avec un code Scheme et Prolog équivalent comme commentaires, à titre de comparaison) :

liste de structures typedef { vide * valeur ; structure liste * suivant ; } liste ; liste * dupliquer ( liste const * ls ) { liste * tête = NULL ; si ( ls != NULL ) { liste * p = doublon ( ls -> suivant ); tête = malloc ( taille de * tête ); tête -> valeur = ls -> valeur ; tête -> suivant = p ; } tête de retour ; }	;; dans Scheme, ( définir ( dupliquer ls ) ( si ( pas ( null? ls )) ( contre ( voiture ls ) ( dupliquer ( cdr ls ))) ‘ ()))
%% dans Prolog, dupliquer ([ X | Xs ], R ):- dupliquer ( Xs , Ys ), R = [ X | Oui ]. dupliquer ([],[]).

Sous cette forme, la fonction n’est pas récursive de fin, car le contrôle revient à l’appelant après que l’appel récursif ait dupliqué le reste de la liste d’entrée. Même s’il devait allouer le nœud principal avant de dupliquer le reste, il aurait toujours besoin de brancher le résultat de l’appel récursif dans le nextchamp après l’appel. ^[a] La fonction est donc presque récursive. La méthode de Warren pousse la responsabilité de remplir le nextchamp dans l’appel récursif lui-même, qui devient ainsi l’appel de queue :

liste de structures typedef { vide * valeur ; structure liste * suivant ; } liste ; void duplicate_aux ( const list * ls , list * end ); liste * dupliquer ( liste const * ls ) { tête de liste ; duplicate_aux ( ls , & head ); tête de retour . suivant ; } void duplicate_aux ( liste const * ls , liste * fin ) { si ( ls != NULL ) { fin -> suivant = malloc ( taillede * fin ); fin -> suivant -> valeur = ls -> valeur ; duplicate_aux ( ls -> suivant , fin -> suivant ); } sinon { fin -> suivant = NULL ; } }

;; dans Scheme, ( define ( duplicate ls ) ( let (( head ( list 1 ))) ( let dup (( ls ls ) ( end head )) ( cond (( not ( null? ls )) ( set-cdr! end ( liste ( voiture ls ))) ( dup ( cdr ls ) ( cdr end ))))) (tête cdr )))

%% dans Prolog, doublon ([ X | Xs ], R ):- R = [ X | Ys ], dupliqué ( Xs , Ys ). dupliquer ([],[]).

(Un nœud principal sentinelle est utilisé pour simplifier le code.) L’appelé ajoute maintenant à la fin de la liste croissante, plutôt que de faire précéder l’appelant au début de la liste renvoyée. Le travail est maintenant effectué sur le chemin en avant depuis le début de la liste, avant l’appel récursif qui continue ensuite, au lieu de revenir en arrière depuis la fin de la liste, après que l’appel récursif a renvoyé son résultat. Elle s’apparente donc à la technique d’accumulation des paramètres, transformant un calcul récursif en un calcul itératif.

De manière caractéristique pour cette technique, un cadre parent est créé sur la pile d’appels d’exécution, que l’appelé récursif de queue peut réutiliser comme son propre cadre d’appel si l’optimisation d’appel de queue est présente.

L’implémentation récursive terminale peut maintenant être convertie en une implémentation explicitement itérative, sous la forme d’une boucle d’accumulation :

liste de structures typedef { vide * valeur ; structure liste * suivant ; } liste ; liste * dupliquer ( liste const * ls ) { tête de liste , * fin ; fin = & tête ; tandis que ( ls != NULL ) { fin -> suivant = malloc ( taillede * fin ); fin -> suivant -> valeur = ls -> valeur ; ls = ls -> suivant ; fin = fin -> suivant ; } fin -> suivant = NULL ; tête de retour . suivant ; }	;; dans Scheme, ( définir ( dupliquer ls ) ( laisser (( head ( liste 1 ))) ( faire (( end head ( cdr end )) ( ls ls ( cdr ls ))) (( null? ls ) ( cdr head ) ) ( set-cdr! end ( liste ( voiture ls ))))))
%% dans Prolog, %% N/A

Histoire

Dans un article présenté à la conférence ACM à Seattle en 1977, Guy L. Steele a résumé le débat sur le GOTO et la programmation structurée , et a observé que les appels de procédure dans la position de queue d’une procédure peuvent être mieux traités comme un transfert direct de contrôle à la procédure appelée, éliminant généralement les opérations de manipulation de pile inutiles. ^[2] Étant donné que de tels “appels de queue” sont très courants en Lisp, langage où les appels de procédure sont omniprésents, cette forme d’optimisation réduit considérablement le coût d’un appel de procédure par rapport aux autres implémentations. Steele a fait valoir que des appels de procédure mal mis en œuvre avaient conduit à une perception artificielle que le GOTO était bon marché par rapport à l’appel de procédure. Steele a en outre fait valoir qu ‘”en général, les appels de procédure peuvent être utilement considérés comme des instructions GOTO qui transmettent également des paramètres et peuvent être codés de manière uniforme comme des instructions JUMP [code machine]”, les instructions de manipulation de pile de code machine “considérées comme une optimisation (plutôt que vice versa!)”. ^[2]Steele a cité des preuves que des algorithmes numériques bien optimisés dans Lisp pouvaient s’exécuter plus rapidement que le code produit par les compilateurs Fortran commerciaux alors disponibles, car le coût d’un appel de procédure dans Lisp était beaucoup plus faible. Dans Scheme , un dialecte Lisp développé par Steele avec Gerald Jay Sussman , l’élimination des appels de queue est garantie d’être implémentée dans n’importe quel interpréteur. ^[11]

Modalités de mise en œuvre

La récursivité de queue est importante pour certains langages de haut niveau , en particulier les langages fonctionnels et logiques et les membres de la famille Lisp . Dans ces langages, la récursivité terminale est le moyen le plus couramment utilisé (et parfois le seul moyen disponible) d’implémenter l’itération. La spécification de langage de Scheme exige que les appels de queue soient optimisés afin de ne pas augmenter la pile. Les appels de fin peuvent être effectués explicitement en Perl , avec une variante de l’instruction “goto” qui prend un nom de fonction : goto &NAME;^[12]

Cependant, pour les implémentations de langage qui stockent les arguments de fonction et les variables locales sur une pile d’appels (qui est l’implémentation par défaut pour de nombreux langages, au moins sur les systèmes avec une Pile matérielle , comme le x86 ), l’implémentation d’une optimisation généralisée des appels terminaux (y compris mutuelle récursion terminale) présente un problème : si la taille de l’enregistrement d’activation de l’appelé est différente de celle de l’appelant, un nettoyage ou un redimensionnement supplémentaire du Cadre de pile peut être nécessaire. Dans ces cas, l’optimisation de la récursivité de queue reste triviale, mais l’optimisation générale des appels de queue peut être plus difficile à mettre en œuvre efficacement.

Par exemple, dans la machine virtuelle Java (JVM), les appels récursifs de queue peuvent être éliminés (car cela réutilise la pile d’appels existante), mais les appels de queue généraux ne peuvent pas l’être (car cela modifie la pile d’appels). ^{[13] [14]} En conséquence, les langages fonctionnels tels que Scala qui ciblent la JVM peuvent implémenter efficacement la récursivité de queue directe, mais pas la récursivité de queue mutuelle.

Les suites de compilateurs GCC , LLVM/Clang et Intel effectuent une optimisation des appels terminaux pour C et d’autres langages à des niveaux d’optimisation plus élevés ou lorsque l’ -foptimize-sibling-callsoption est transmise. ^{[15] [16] [17]} Bien que la syntaxe du langage donné puisse ne pas le supporter explicitement, le compilateur peut faire cette optimisation chaque fois qu’il peut déterminer que les types de retour pour l’appelant et l’appelé sont équivalents, et que les types d’arguments passés aux deux fonction sont soit identiques, soit nécessitent la même quantité d’espace de stockage total sur la pile des appels. ^[18]

Diverses méthodes de mise en œuvre sont disponibles.

En montage

Apprendre encore plus Cette section ne cite aucune source . ( juin 2014 )Veuillez aider à améliorer cette section en ajoutant des citations à des sources fiables . Le matériel non sourcé peut être contesté et supprimé . (Découvrez comment et quand supprimer ce modèle de message)

Les appels de queue sont souvent optimisés par des interpréteurs et des compilateurs de langages de programmation fonctionnelle et de programmation logique vers des formes d’ itération plus efficaces . Par exemple, les programmeurs Scheme expriment généralement les boucles while comme des appels à des procédures en position de queue et s’appuient sur le compilateur ou l’interpréteur Scheme pour remplacer les appels de queue par des instructions de saut plus efficaces . ^[19]

Pour les compilateurs générant directement l’assembly, l’élimination des appels de queue est simple : il suffit de remplacer un opcode d’appel par un saut, après avoir fixé les paramètres sur la pile. Du point de vue d’un compilateur, le premier exemple ci-dessus est initialement traduit en langage pseudo-assembleur (en fait, il s’agit d’un assembly x86 valide ) :

foo : appeler B appeler A ret

L’élimination de l’appel de queue remplace les deux dernières lignes par une seule instruction de saut :

foo : appeler B jmp A

Une fois le sous-programme Aterminé, il reviendra directement à l’adresse de retour de foo, en omettant l’instruction inutile ret.

En règle générale, les sous-programmes appelés doivent être fournis avec des paramètres . Le code généré doit donc s’assurer que le cadre d’appel pour A est correctement configuré avant de passer au sous-programme appelé par la queue. Par exemple, sur les plates-formes où la pile des appels ne contient pas seulement l’ adresse de retour , mais également les paramètres de la sous-routine, le compilateur peut avoir besoin d’émettre des instructions pour ajuster la pile des appels. Sur une telle plateforme, pour le code :

fonction foo(données1, données2) B(données1) renvoie A(données2)

(où data1et data2sont des paramètres) un compilateur pourrait traduire cela par : ^[b]

truc : mov reg ,[ sp + data1 ] ; récupérer les données1 du paramètre de pile (sp) dans un registre de travail. pousser reg ; mettre data1 sur la pile où B l’attend appeler B ; B utilise des données1 pop ; supprimer data1 de la pile mov reg ,[ sp + data2 ] ; récupérer les données2 du paramètre de pile (sp) dans un registre de travail. pousser reg ; mettre data2 sur la pile où A l’attend appeler A ; A utilise des données2 pop ; supprimer data2 de la pile. ret

Un optimiseur d’appel final pourrait alors changer le code en :

truc : mov reg ,[ sp + data1 ] ; récupérer les données1 du paramètre de pile (sp) dans un registre de travail. pousser reg ; mettre data1 sur la pile où B l’attend appeler B ; B utilise des données1 pop ; supprimer data1 de la pile mov reg ,[ sp + data2 ] ; récupérer les données2 du paramètre de pile (sp) dans un registre de travail. mov [ sp + data1 ], reg ; mettre data2 là où A l’attend jmpA ; _ A utilise data2 et revient immédiatement à l’appelant.

Ce code est plus efficace à la fois en termes de vitesse d’exécution et d’utilisation de l’espace de la pile.

Grâce au trampoline

Étant donné que de nombreux compilateurs Scheme utilisent C comme code cible intermédiaire, la récursivité de queue doit être encodée en C sans augmenter la pile, même si le compilateur C n’optimise pas les appels de queue. De nombreuses implémentations y parviennent en utilisant un dispositif connu sous le nom de trampoline, un morceau de code qui appelle à plusieurs reprises des fonctions. Toutes les fonctions sont saisies via le trampoline. Lorsqu’une fonction doit en appeler une autre, au lieu de l’appeler directement puis de renvoyer le résultat, elle renvoie l’adresse de la fonction à appeler et les paramètres d’appel au trampoline (à partir duquel elle a été appelée elle-même), et le trampoline se charge d’appeler ensuite cette fonction avec les paramètres spécifiés. Cela garantit que la pile C ne grandit pas et que l’itération peut continuer indéfiniment.

Il est possible de mettre en œuvre des trampolines à l’aide de fonctions d’ordre supérieur dans des langages qui les prennent en charge, tels que Groovy , Visual Basic .NET et C# . ^[20]

L’utilisation d’un trampoline pour tous les appels de fonction est plutôt plus chère que l’appel de fonction C normal, donc au moins un compilateur Scheme, Chicken , utilise une technique décrite pour la première fois par Henry Baker à partir d’une suggestion non publiée d’ Andrew Appel , ^[21] dans laquelle C normal les appels sont utilisés mais la taille de la pile est vérifiée avant chaque appel. Lorsque la pile atteint sa taille maximale autorisée, les objets de la pile sont ramassés à l’aide de l’ algorithme de Cheneyen déplaçant toutes les données en direct dans un tas séparé. Suite à cela, la pile est déroulée (« sautée ») et le programme reprend à partir de l’état sauvegardé juste avant le ramasse-miettes. Baker dit que “la méthode d’Appel évite de faire un grand nombre de petits rebonds de trampoline en sautant occasionnellement de l’Empire State Building.” ^[21] Le ramasse-miettes garantit que la récursion de queue mutuelle peut continuer indéfiniment. Cependant, cette approche nécessite qu’aucun appel de fonction C ne soit renvoyé, car il n’y a aucune garantie que le Cadre de pile de son appelant existe toujours ; par conséquent, cela implique une réécriture interne beaucoup plus dramatique du code du programme : style de passage de continuation .

Relation avec l’ instruction while

La récursivité terminale peut être liée à l’ instruction while , une itération explicite, par exemple en transformant

procedure foo( x ) if p ( x ) return bar( x ) else return foo(baz( x ))

dans

procedure foo( x ) while true if p ( x ) return bar( x ) else x ← baz( x )

où x peut être un tuple impliquant plus d’une variable : si c’est le cas, il faut veiller à implémenter l’ instruction d’affectation x ← baz( x ) afin que les dépendances soient respectées. Il peut être nécessaire d’introduire des variables auxiliaires ou d’utiliser une construction d’ échange .

Plus généralement,

procedure foo( x ) if p ( x ) return bar( x ) else if q ( x ) return baz( x ) … sinon si r ( x ) retourne foo(qux( x )) … sinon retourner foo(quux( x ))

peut être transformé en

procedure foo( x ) while true if p ( x ) return bar( x ) else if q ( x ) return baz( x ) … sinon si r ( x ) x ← qux( x ) … sinon x ← quux( x )

Par exemple, ce programme Python donne une définition récursive non terminale factde la factorielle :

def fact ( n ): if n == 0 : return 1 else : return n * fact ( n – 1 )

En effet, n * fact(n – 1)enveloppe l’appel à fact. Mais il peut être transformé en une définition récursive de queue en ajoutant un argument aappelé un accumulateur . ^[8]

Ce programme Python donne une définition récursive terminale fact_iterde la factorielle :

def fact_iter ( n , a ): if n == 0 : return a else : return fact_iter ( n – 1 , n * a ) def fact ( n ): return fact_iter ( n , 1 )

Ce programme Python donne une définition itérative fact_iterde la factorielle :

def fact_iter ( n , a ): while True : if n == 0 : return a else : n , a = n – 1 , n * a def fact ( n ): return fact_iter ( n , 1 )

Support linguistique

• Clojure – Clojure a recurune forme spéciale. ^[22]
• Common Lisp – Certaines implémentations effectuent une optimisation des appels de fin lors de la compilation si elles sont optimisées pour la vitesse
• Elixir – Elixir implémente l’optimisation des appels de queue ^[23] Comme le font tous les langages ciblant actuellement la VM BEAM.
• Orme – Oui ^[24]
• Erlang – Oui
• F# – F# implémente le TCO par défaut dans la mesure du possible ^[25]
• Aller – Pas de support ^[26]
• Haskell – Oui ^[27]
• JavaScript – Les moteurs compatibles ECMAScript 6.0 doivent avoir des appels de queue ^[28] qui sont maintenant implémentés sur Safari / WebKit ^[29] mais rejetés par V8 et SpiderMonkey
• Kotlin – A tailrecun modificateur pour les fonctions ^[30]
• Lua – La récursivité de la queue est requise par la définition du langage ^[31]
• Objective-C – Le compilateur optimise les appels de queue lorsque l’option -O1 (ou supérieure) est spécifiée, mais il est facilement perturbé par les appels ajoutés par le comptage automatique des références (ARC).
• OCaml – Oui
• Perl – Explicit avec une variante de l’instruction “goto” qui prend un nom de fonction : goto &NAME;^[32]
• PureScript – Oui
• Python – Les implémentations Stock Python n’effectuent pas d’optimisation des appels de queue, bien qu’un module tiers soit disponible pour le faire. ^[33] L’inventeur du langage Guido van Rossum soutient que les traces de pile sont modifiées par l’élimination des appels de queue, ce qui rend le débogage plus difficile, et préfère que les programmeurs utilisent plutôt l’ itération explicite ^[34]
• Raquette – Oui ^[35]
• Rust – l’optimisation des appels de queue peut être effectuée dans des circonstances limitées, mais n’est pas garantie ^[36]
• Scala – Les fonctions récursives de fin sont automatiquement optimisées par le compilateur. De telles fonctions peuvent également éventuellement être marquées d’une @tailrecannotation, ce qui en fait une erreur de compilation si la fonction n’est pas récursive de queue ^[37]
• Schéma – Requis par la définition du langage ^{[38] [39]}
• Tcl – Depuis Tcl 8.6, Tcl a une commande tailcall ^[40]

Voir également

• Portail de programmation informatique

Recherchez la récursivité de la queue dans Wiktionary, le dictionnaire gratuit.

• Récursivité du cours des valeurs
• Récursivité (informatique)
• Extension en ligne
• Sous-programme Feuille
• Corécursion

Remarques

1. ^ Comme ceci : si ( ls != NULL ) { tête = malloc ( taille de * tête ); tête -> valeur = ls -> valeur ; head -> next = duplicate ( ls -> next ); }
2. ^ L’callinstruction pousse d’abord l’emplacement de code actuel sur la pile, puis effectue un saut inconditionnel vers l’emplacement de code indiqué par l’étiquette. L’retinstruction extrait d’abord un emplacement de code de la pile, puis effectue un saut inconditionnel vers l’emplacement de code récupéré.

Références

1. ^ Steven Muchnick; Muchnick et associés (15 août 1997). Implémentation de la conception avancée du compilateur . Morgan Kaufman. ISBN 978-1-55860-320-2.
2. ^ ^{un bc Steele} , Guy Lewis (1977). “Démystifier le mythe de” l’appel de procédure coûteux “ou, les implémentations d’appel de procédure considérées comme nuisibles ou, LAMBDA: The Ultimate GOTO”. Actes de la conférence annuelle de 1977 sur – ACM ’77 . p. 153–162. doi : 10.1145/800179.810196 . hdl : 1721.1/5753 . ISBN 978-1-4503-2308-6. S2CID 9807843 .
3. ^ “Le générateur de code indépendant de la cible LLVM – documentation LLVM 7” . llvm.org .
4. ^ “récursivité – Utilisation de la mémoire de la pile pour les appels de queue – Informatique théorique” . Cstheory.stackexchange.com. 2011-07-29 . Récupéré le 21/03/2013 .
5. ^ ^{un b} “Rapport Révisé ^ 6 sur le Schéma de Langage Algorithmique” . R6rs.org . Récupéré le 21/03/2013 .
6. ^ “Rapport révisé ^ 6 sur le schéma de langage algorithmique – justification” . R6rs.org . Récupéré le 21/03/2013 .
7. ^ “Rapport révisé ^ 6 sur le schéma de langage algorithmique” . R6rs.org . Récupéré le 21/03/2013 .
8. ^ ^{un bc Sussman} , GJ; Abelson, Hal (1984). Structure et interprétation des programmes informatiques . Cambridge, Massachusetts : MIT Press. ISBN 0-262-01077-1.
9. ^ DHD Warren, DAI Research Report 141 , Université d’Édimbourg, 1980.
10. ^ Daniel P. Friedman et David S. Wise, Rapport technique TR19 : Déroulement des récursions structurées en itérations , Université de l’Indiana, décembre 1974.
11. ^ R5RS Sec. 3.5, Richard Kelsey ; Guillaume Clinger; Jonathan Rees; et coll. (Août 1998). “Rapport révisé ⁵ sur le schéma de langage algorithmique” . Calcul d’ordre supérieur et symbolique . 11 (1): 7–105. doi : 10.1023/A:1010051815785 . S2CID 14069423 .
12. ^ Coordonnées. “ALLER À” . perldoc.perl.org . Récupéré le 21/03/2013 .
13. ^ ” Quelle est la différence entre les appels de queue et la récursivité de queue? “, Stack Overflow
14. ^ ” Quelles limitations la JVM impose-t-elle à l’optimisation des appels terminaux ” , Programmers Stack Exchange
15. ^ Lattner, Chris. “Manuel de référence du langage LLVM, section : Le générateur de code indépendant de la cible LLVM, sous : Optimisation des appels de queue” . L’infrastructure du compilateur LLVM . Le projet LLVM . Récupéré le 24 juin 2018 .
16. ^ “Utilisation de la collection de compilateurs GNU (GCC) : options d’optimisation” . gcc.gnu.org .
17. ^ “foptimize-frère-appels” . software.intel.com .
18. ^ “S’attaquer aux appels de queue C++” .
19. ^ Probst, Mark (20 juillet 2000). “récursion de queue appropriée pour gcc” . Projet CCG . Récupéré le 10 mars 2015 .
20. ^ Samuel Jack, Rebondir sur votre queue . Amusement fonctionnel . 9 avril 2008.
21. ^ ^{un b} Henry Baker, “CONS ne devrait pas CONS ses arguments, partie II : Cheney sur le MTA”
22. ^ “(expression récurrente*)” . clojure.org .
23. ^ “Récursivité” . elixir-lang.github.com .
24. ^ Czaplicki, Evan. “Programmation fonctionnelle dans Elm : élimination des appels de queue” .
25. ^ “Appels de queue en F #” . msdn . Microsoft.
26. ^ “proposition : Go 2 : ajoutez l’instruction de devenir pour prendre en charge les appels de queue” . github.com .
27. ^ “Récursivité de queue – HaskellWiki” . wiki.haskell.org . Récupéré le 08/06/2019 .
28. ^ Beres-Deak, Adam. “À regarder : Douglas Crockford parle des nouveaux bons côtés de JavaScript en 2014” . bdadam.com .
29. ^ “ECMAScript 6 dans WebKit” . 13 octobre 2015.
30. ^ “Fonctions : infix, vararg, tailrec – Langage de programmation Kotlin” . Kotline .
31. ^ “Manuel de référence Lua 5.3” . www.lua.org .
32. ^ “ALLER À -perldoc.perl.org” . perldoc.perl.org .
33. ^ “baruchel/tco” . GitHub . 29 mars 2022.
34. ^ Rossum, Guido Van (22 avril 2009). “Neopythonic: Élimination de la récursivité de la queue” .
35. ^ “La référence de raquette” . docs.racket-lang.org .
36. ^ “FAQ sur la rouille” . prev.rust-lang.org .
37. ^ “Bibliothèque standard Scala 2.13.0 – scala.annotation.tailrec” . www.scala-lang.org . Récupéré le 20/06/2019 .
38. ^ “Rapport révisé ^ 5 sur le schéma de langage algorithmique” . www.schemers.org .
39. ^ “Rapport révisé ^ 6 sur le schéma de langage algorithmique” . www.r6rs.org .
40. ^ “page de manuel de tailcall – Commandes intégrées Tcl” . www.tcl.tk .