Worldlex Wiki
Article de reference

Appel de queue

En informatique , un appel terminal est un appel de sous-programme effectué en dernière étape d'une procédure. Si la cible de l'appel terminal est le même sous-programme, on dit...

Worldlex WikiContenu en francaisLecture gratuite

En informatique , un appel terminal est un appel de sous-programme effectué en dernière étape d'une procédure. Si la cible de l'appel terminal est le même sous-programme, on dit que ce dernier est récursif terminal ; il s'agit d'un cas particulier de récursivité directe . La récursivité terminale est particulièrement utile et souvent facile à optimiser dans les implémentations.

Les appels terminaux 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 courante n'est plus nécessaire et peut être remplacée par celui de l'appel terminal, modifié si besoin (similaire à la superposition pour les processus, mais pour les appels de fonction). Le programme peut alors exécuter la sous-routine appelée. Produire un tel code au lieu d'une séquence d'appels standard est appelé élimination ou optimisation des appels terminaux . L'élimination des appels terminaux permet d'implémenter les appels de procédure en position terminale aussi efficacement que les instructions GOTO , permettant ainsi une programmation structurée efficace . Selon Guy L. Steele , « en général, les appels de procédure peuvent être utilement considérés comme des instructions GOTO qui passent également des paramètres, et peuvent être codés uniformément comme des instructions JUMP [en code machine] ».

Tous les langages de programmation n'imposent pas l'élimination des appels terminaux. Cependant, dans les langages de programmation fonctionnelle , cette élimination est souvent garantie par la norme du langage , permettant ainsi à la récursivité terminale d'utiliser une quantité de mémoire similaire à celle d'une boucle équivalente . Le cas particulier des appels récursifs terminaux, lorsqu'une fonction s'appelle elle-même, peut se prêter davantage à l'élimination d'appels que les appels terminaux en général. Lorsque la sémantique du langage ne prend pas explicitement en charge les appels terminaux en général, un compilateur peut souvent optimiser les appels frères , c'est-à-dire les appels terminaux à des fonctions qui acceptent et renvoient des types identiques à ceux de l'appelant.

adresse de retour , afin de pouvoir y retourner avec le résultat une fois l'appel terminé. Généralement, cette information est enregistrée sur la pile d'appels , une liste d'adresses de retour dans l'ordre où les adresses d'appel ont été atteintes. De plus, les compilateurs allouent de la mémoire pour les variables locales de la fonction appelée et empilent le contenu des registres (le cas échéant et/ou pertinents). Cela se fait généralement en allouant un cadre de pile incluant les registres sauvegardés, l'espace alloué aux variables locales non-registraires, l'adresse de retour et les paramètres d'appel (sauf s'ils sont passés dans des registres). Pour les appels terminaux, il n'est pas nécessaire de mémoriser l'appelant ni de conserver le contenu des registres ; l'élimination des appels terminaux évite l'allocation de nouveaux cadres de pile et n'apporte que les modifications minimales nécessaires au cadre de pile existant avant de le transmettre, la fonction appelée retournant directement à l' appelant initial . Cependant, cela entraîne la perte complète du cadre de pile de l'appelant, ce qui est parfois considéré comme un obstacle au débogage. L'appel terminal n'a pas besoin d'apparaître lexicalement après toutes les autres instructions du code source ; il importe seulement que la fonction appelante retourne immédiatement après l'appel terminal, en retournant le résultat de l'appel terminal le cas échéant, puisque la fonction appelante est ignorée lors de l'optimisation.

Pour les appels de fonctions non récursifs, cette optimisation ne permet généralement qu'un gain minime de temps et d'espace, car le nombre de fonctions appelables est limité. En revanche, pour les fonctions récursives ou mutuellement récursives, où la récursion s'effectue par appels terminaux, l'espace mémoire gagné sur la pile et le nombre de retours économisés peuvent devenir considérables. En effet, une fonction peut s'appeler elle-même, directement ou indirectement, créant ainsi un nouveau cadre de pile à chaque appel. L'élimination des appels terminaux réduit souvent l'espace mémoire asymptotique requis de la pile de manière linéaire ( O (n)) à une manière constante (O(1)). C'est pourquoi elle est exigée par les définitions standard de certains langages de programmation, comme Scheme , et des langages de la famille ML , entre autres. La définition du langage Scheme formalise précisément la notion intuitive de position terminale, en spécifiant les formes syntaxiques autorisant des résultats dans un contexte terminal. Les implémentations permettant un nombre illimité d'appels terminaux actifs simultanément, grâce à l'élimination des appels terminaux, sont qualifiées de « récursives terminales à proprement parler ».

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

Forme syntaxique

Un appel terminal peut être situé juste avant la fin syntaxique d'une fonction.

Scheme :

number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) " 
;; factorielle : nombre -> nombre ;; pour calculer le produit de tous les entiers positifs inférieurs ou égaux à n. ( définir ( factorielle n ) ( si ( = n 0 ) 1 ( * n ( factorielle ( - n 1 )))))

Ce code n'est pas écrit de manière récursive terminale, car la fonction de multiplication (« * ») se trouve en position terminale. On peut le comparer à :

number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (fact-iter 1 n)) (define (fact-iter product n) (if (= n 0) product (fact-iter (* product n) (- n 1)))) " 
;; factorielle : nombre -> nombre ;; pour calculer le produit de tous les entiers positifs inférieurs ou égaux à n. ( définir ( factorielle n ) ( fait-iter 1 n )) ( définir ( fait-iter produit n ) ( si ( = n 0 ) produit ( fait-iter ( * produit n ) ( - n 1 ))))

Ce programme suppose une évaluation dans l'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 à un compilateur de réorganiser l'exécution qui ressemblerait normalement à ceci : 

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

dans la variante la plus efficace , tant en termes d'espace que de temps :

 appel factorielle (4) appel 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 permet de gagner de l'espace car aucun état, hormis l'adresse de la fonction appelante, n'a besoin d'être sauvegardé, ni sur la pile ni sur le tas. De plus, le cadre de pile d'appels fact-iterest réutilisé pour le stockage des résultats intermédiaires. Ainsi, le programmeur n'a plus à craindre de manquer d'espace sur la pile ou le tas lors de récursions extrêmement profondes. Dans les implémentations classiques, la variante récursive terminale est nettement plus rapide que l'autre, mais seulement d'un facteur constant.

Certains programmeurs travaillant avec des langages fonctionnels réécrivent le code récursif pour le rendre récursif terminal et ainsi tirer parti de cette fonctionnalité. Cela nécessite souvent l'ajout d'un argument « accumulateur » ( productdans l'exemple ci-dessus) à la fonction.

récursion terminale modulo cons

La récursion terminale modulo cons est une généralisation de l'optimisation par récursion terminale introduite par David H.D. Warren dans le contexte de la compilation de Prolog , considéré comme un langage à initialisation explicite . Elle a été décrite (sans être nommée) par Daniel P. Friedman et LISP . Comme son nom l'indique, elle s'applique lorsque la seule opération restante après un appel récursif consiste à ajouter une valeur connue au début de la liste renvoyée (ou, plus généralement, à effectuer un nombre constant d'opérations simples de construction de données). Cet appel serait donc un appel terminal, hormis l' opération cons (« modulo ») . Or, ajouter une valeur au début d'une liste à la sortie d'un appel récursif revient à ajouter cette valeur à la fin de la liste en cours d'agrandissement à l'entrée de l'appel récursif, construisant ainsi la liste comme un effet de bord , à la manière d'un paramètre d'accumulateur implicite. Le fragment Prolog suivant illustre ce concept :

Exemple de code

nœud de liste et l'initialisation de son firstchamp, puis en un appel terminal avec le pointeur vers le champ du nœud restcomme argument, lequel sera rempli récursivement. Le même résultat est obtenu lorsque la récursion est protégée par un constructeur de données évalué paresseusement, ce qui est automatique dans les 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 du code Scheme et Prolog équivalent en commentaires, à titre de comparaison) :

next); head = (LinkedList*)malloc(sizeof(*head)); head->value = ls->value; head->next = p; } return head; } " 
typedef struct LinkedList { void * valeur ; struct LinkedList * suivant ; } LinkedList ;LinkedList * dupliquer ( const LinkedList * ls ) { LinkedList * tête = NULL ;if ( ls ) { LinkedList * p = duplicate ( ls -> next ); head = ( LinkedList * ) malloc ( sizeof ( * head )); head -> value = ls -> value ; head -> next = p ; } return head ; }
next = (LinkedList*)malloc(sizeof(*end)); end->next->value = ls->value; duplicate_aux(ls->next, end->next); } else { end->next = NULL; } } LinkedList* duplicate(const LinkedList* ls) { LinkedList head; duplicate_aux(ls, &head); return head.next; } " 
void duplicate_aux ( const LinkedList * ls , LinkedList * end ) { if ( ls ) { end- > next = ( LinkedList * ) malloc ( sizeof ( * end )); end- > next- > value = ls- > value ; duplicate_aux ( ls- > next , end- > next ); } else { end- > next = NULL ; } }LinkedList * dupliquer ( const LinkedList * ls ) { LinkedList tête ;duplicate_aux ( ls , & head ) ; return head.next ; }​
cadre parent est créé sur la pile d'appels d'exécution, que l'appelé récursif terminal peut réutiliser comme son propre cadre d'appel si l'optimisation d'appel terminal est présente.

L'implémentation récursive terminale peut désormais être convertie en une implémentation explicitement itérative, sous la forme d'une boucle cumulative :

next = (LinkedList*)malloc(sizeof(*end)); end->next->value = ls->value; ls = ls->next; end = end->next; } end->next = NULL; return head.next; } " 
LinkedList * dupliquer ( const LinkedList * ls ) { LinkedList tête ; LinkedList * fin ; fin = & tête ; tant que ( ls ) { fin- > suivant = ( LinkedList * ) malloc ( sizeof ( * fin ) ) ; fin- > suivant- > valeur = ls- > valeur ; ls = ls- > suivant ; fin = fin- > suivant ; } fin- > suivant = NULL ; retourner tête.suivant ; }
ACM de Seattle en 1977, Guy L. Steele a résumé le débat sur l'instruction GOTO et la programmation structurée . Il a observé que les appels de procédure en fin d'exécution peuvent être considérés comme un transfert direct de contrôle à la procédure appelée, éliminant généralement les manipulations de pile inutiles. Ces « appels terminaux » étant très fréquents en Lisp , langage où les appels de procédure sont omniprésents, cette optimisation réduit considérablement le coût d'un appel de procédure par rapport à d'autres implémentations. Steele a soutenu que des appels de procédure mal implémentés avaient engendré l'idée fausse que l'instruction GOTO était peu coûteuse comparée à l'appel de procédure. Il a également affirmé qu'« en général, les appels de procédure peuvent être utilement considérés comme des instructions GOTO qui passent également des paramètres et peuvent être codés uniformément comme des instructions JUMP [en code machine] », les instructions de manipulation de pile en code machine étant « considérées comme une optimisation (et non l'inverse !) ». Steele a cité des preuves que des algorithmes numériques bien optimisés en 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 en Lisp était beaucoup plus faible. En Scheme , un dialecte Lisp développé par Steele avec Gerald Jay Sussman , l'élimination des appels terminaux est garantie dans tout interpréteur.

Méthodes de mise en œuvre

La récursivité terminale est importante pour certains langages de haut niveau , notamment les langages fonctionnels et logiques ainsi que les membres de la famille Lisp . Dans ces langages, la récursivité terminale est la méthode la plus courante (et parfois la seule disponible) pour implémenter l'itération. La spécification du langage Scheme exige que les appels terminaux soient optimisés afin de ne pas augmenter la taille de la pile. Les appels terminaux peuvent être effectués explicitement en Perl , grâce à une variante de l'instruction « goto » qui prend un nom de fonction : goto &NAME;

Cependant, pour les implémentations de langages qui stockent les arguments de fonction et les variables locales sur une pile d'appels (ce qui est le comportement par défaut pour de nombreux langages, du moins sur les systèmes dotés d'une pile matérielle , comme l' architecture x86 ), l'optimisation généralisée des appels terminaux (y compris la récursivité terminale mutuelle) pose problème : si la taille de l'enregistrement d'activation de l'appelé diffère de celle de l'appelant, un nettoyage ou un redimensionnement supplémentaire du cadre de pile peut s'avérer nécessaire. Dans ces cas, l'optimisation de la récursivité terminale reste simple, mais l'optimisation générale des appels terminaux peut être plus difficile à implémenter efficacement.

Par exemple, dans la machine virtuelle Java (JVM), les appels récursifs terminaux peuvent être éliminés (car cela réutilise la pile d'appels existante), mais les appels terminaux généraux ne peuvent pas l'être (car cela modifie la pile d'appels). Par conséquent, les langages fonctionnels tels que Scala , qui ciblent la JVM, peuvent implémenter efficacement la récursivité terminale directe, mais pas la récursivité terminale mutuelle.

Les suites de compilation GCC , LLVM/Clang et Intel effectuent l'optimisation des appels terminaux pour le C et d'autres langages à des niveaux d'optimisation élevés ou lorsque l' -foptimize-sibling-callsoption correspondante est spécifiée. Même si la syntaxe du langage ne la prend pas explicitement en charge, le compilateur peut effectuer cette optimisation dès lors qu'il détermine que les types de retour de l'appelant et de l'appelé sont équivalents et que les types des arguments passés aux deux fonctions sont identiques ou nécessitent la même quantité d'espace mémoire total sur la pile d'appels.

Différentes méthodes de mise en œuvre sont disponibles.

En assemblage

les interpréteurs et les compilateurs des langages de programmation fonctionnelle et logique pour produire des itérations plus efficaces . Par exemple, les programmeurs Scheme expriment généralement les boucles while comme des appels à des procédures en position terminale et comptent sur le compilateur ou l'interpréteur Scheme pour remplacer ces appels terminaux par des instructions de saut plus efficaces .

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

paramètres . Le code généré doit donc s'assurer que le cadre d'appel de A est correctement initialisé avant d'exécuter le dernier sous-programme appelé. Par exemple, sur les plateformes où la pile d'appels contient non seulement l' adresse de retour , mais aussi les paramètres du sous-programme, le compilateur peut avoir besoin d'émettre des instructions pour ajuster la pile d'appels. Sur une telle plateforme, pour le code :

fonction foo(data1, data2) B(données1) renvoyer A(data2)

(où data1et data2sont des paramètres) un compilateur pourrait traduire cela comme :

secteur d’amorçage ). Cela transforme physiquement la pile d’appels en une machine à états bornés.

Relation avec les coroutines

Un appel terminal sans récursivité est physiquement équivalent à une de coroutines hautes performances . En remplaçant la boucle traditionnelle style de programmation par continuation , où le programme ne retourne jamais, mais effectue une séquence d'appels terminaux pour passer d'un état coopératif à un autre.

Par le trampoline

Étant donné que de nombreux compilateurs Scheme utilisent le C comme code cible intermédiaire, la récursivité terminale doit être encodée en C sans augmenter la taille de la pile, même si le compilateur C n'optimise pas les appels terminaux. De nombreuses implémentations y parviennent grâce à un mécanisme appelé trampoline , un bloc de code qui appelle des fonctions de manière itérative. Toutes les fonctions sont appelées via le trampoline. Lorsqu'une fonction doit effectuer un appel terminal, au lieu de l'appeler directement puis de retourner le résultat, elle renvoie l'adresse de la fonction à appeler et les paramètres d'appel au trampoline (d'où elle a été appelée). Le trampoline se charge alors d'appeler cette fonction avec les paramètres spécifiés. Ceci garantit que la pile C ne s'agrandit pas et que l'itération peut se poursuivre indéfiniment.

Il est possible d'implémenter des trampolines en utilisant des fonctions d'ordre supérieur dans les langages qui les prennent en charge, tels que Groovy , Visual Basic .NET et C# .

Utiliser un trampoline pour tous les appels de fonction est bien plus coûteux qu'un appel de fonction C classique. C'est pourquoi au moins un compilateur Scheme, Chicken , utilise une technique initialement décrite par Henry Baker, d'après une suggestion non publiée d' Andrew Appel [ Dans cette technique, les appels C classiques 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 qui s'y trouvent sont ramassés par l' algorithme de Cheney, en déplaçant toutes les données actives dans un tas séparé. Ensuite, la pile est dépilée et le programme reprend à partir de l'état sauvegardé juste avant le ramasse-miettes. Baker affirme que « la méthode d'Appel évite de multiplier les petits rebonds sur le trampoline en sautant occasionnellement du haut de l'Empire State Building » . Le ramasse-miettes garantit la poursuite indéfinie de la récursivité terminale mutuelle. Cependant, cette approche implique qu'aucun appel de fonction C ne se termine, car rien ne garantit que le cadre de pile de l'appelant existe encore. Elle implique donc une réécriture interne beaucoup plus radicale du code : le passage de continuations .

Lien avec la whiledéclaration

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

procédure foo( x ) si p ( x ) retourner bar( x ) sinon retourner foo(baz( x ))

dans

procédure foo( x ) tant que vrai si p ( x ) retourner bar( x ) sinon x ← baz( x )

où x peut être un tuple contenant plusieurs variables : dans ce cas, il convient d’être vigilant lors de l’implémentation de l’ instruction d’affectation x ← baz( x ) afin de respecter les dépendances. Il peut être nécessaire d’introduire des variables auxiliaires ou d’utiliser une construction d’échange .

Plus généralement,

procédure foo( x ) si p ( x ) retourner bar( x ) sinon si q ( x ) retourner baz( x ) ... sinon si r ( x ) retourner foo(qux( x )) ... sinon renvoyer foo(quux( x ))

peut être transformé en

procédure foo( x ) tant que vrai si p ( x ) retourner bar( x ) sinon si q ( x ) retourner baz( x ) ... sinon si r ( x ) x ← qux( x ) ... sinon x ← quux( x )

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

Clojure Common Lisp Elixir Orme Erlang F# Aller Haskell Les moteurs JavaScript conformes ECMAScript 6.0 devraient prendre en charge les appels terminaux , ce qui est désormais implémenté sur Safari / WebKit mais rejeté par V8 et SpiderMonkey.Kotlin Lua Objective-C le comptage automatique des références .OCaml Perl Prolog SWI-Prolog implémente l'optimisation de la récursivité terminale.
  • PureScript Python Guido van Rossum, l'inventeur du langage, affirmait que l'élimination des appels terminaux modifiait les traces de pile , rendant le débogage plus difficile, et préconisait plutôt l'utilisation d'itérations explicites . Python 3.14 a introduit un nouvel interpréteur utilisant la répartition des opcodes Python basée sur les appels terminaux. Ceci a permis d'améliorer globalement les performances par rapport à Python 3.13.
  • R Raquette Ruby Rust Scala Schéma Swift Tcl Zig

    Plus d articles de Worldlex Wiki

    Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.

    Explorer l index