Appel de queue - Tail call

En informatique , un appel de queue est un appel de sous - programme effectué comme l'action finale d'une procédure. Si la cible d'une queue est le même sous-programme, le sous-programme est dit récursif de queue , ce qui est un cas particulier de récursivité directe . La récursivité de queue (ou récursion de queue ) est particulièrement utile, et souvent facile à gérer l'optimisation dans les implémentations.

Les appels de queue peuvent être implémentés sans ajouter de nouveau cadre de pile à la pile d'appels . La plupart du cadre de la procédure en cours n'est plus nécessaire et peut être remplacé 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 d'appel de queue ou optimisation d'appel de queue . 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 . Pour reprendre les termes de Guy 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 uniformément codées en tant qu'instructions JUMP [code machine]".

Tous les langages de programmation n'exigent pas l'élimination des appels de queue. 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 d'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.

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 - au lieu de cela, l'élimination de l'appel de queue n'apporte que les modifications minimales nécessaires au cadre de pile avant de le transmettre, et la fonction appelée de queue reviendra directement à l' appelant d' origine . L'appel de queue n'a pas à apparaître lexicalement après toutes les autres instructions 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 la pile et le nombre de retours enregistrés peuvent devenir très importants, car une fonction peut s'appeler, directement ou indirectement, en créant un nouveau cadre de pile d'appels. chaque fois. L'élimination des appels de queue réduit souvent les exigences d'espace de pile asymptotique de linéaire, ou O (n), à constante, 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 , et les langages de la famille ML , entre autres. La définition du langage Scheme formalise exactement la notion intuitive de position de queue, en spécifiant quelles formes syntaxiques permettent d'avoir des résultats dans le contexte de queue. 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 également être appelées « proprement récursives de queue ».

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 continuation-passing (CPS), qui sinon manquerait rapidement d'espace de pile.

Forme syntaxique

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

function foo(data) {
    a(data);
    return b(data);
}

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 :

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

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 :

function foo1(data) {
    return a(data) + 1;
}

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var ret = a(data);
    return (ret == 0) ? 1 : ret;
}

l'appel à a(data)est en position de queue dans foo2, mais il n'est pas en position de queue 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 :

;; factorial : number -> 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)))))

Ce 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é à :

;; factorial : number -> 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))))

Ce programme suppose une évaluation d' ordre applicatif . La procédure interne fact-iters'appelle 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 :

  call factorial (4)
   call fact-iter (1 4)
    call fact-iter (4 3)
     call fact-iter (12 2)
      call fact-iter (24 1)
      return 24
     return 24
    return 24
   return 24
  return 24

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

  call factorial (4)
   call fact-iter (1 4)
   replace arguments with (4 3)
   replace arguments with (12 2)
   replace arguments with (24 1)
   return 24
  return 24

Cette réorganisation permet de gagner de la place car aucun état autre que 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 la pile d'appels 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 de queue-récursive sera sensiblement plus rapide que l'autre variante, mais seulement par un facteur constant.

Certains programmeurs travaillant dans des langages fonctionnels réécriront le code récursif pour qu'il soit récursif afin de pouvoir 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 (comme 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 telle sorte qu'elle mute les références stockées dans d'autres variables.

Récursion de queue modulo contre

La récursion de queue modulo contre est une généralisation de l'optimisation de la récursion de queue introduite par David HD Warren dans le contexte de la compilation de Prolog , considérée comme un langage explicitement défini une fois . Il a été décrit (bien que non nommé) par Daniel P. Friedman et David S. Wise en 1974 comme une technique de compilation LISP . Comme son nom l'indique, il s'applique lorsque la seule opération restante à effectuer après un appel récursif consiste à ajouter une valeur connue devant une liste renvoyée par celle-ci (ou à effectuer un nombre constant d'opérations de construction de données simples, en général). Cet appel serait donc un appel de queue sauf (" modulo ") pour ladite contre opération. 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 lors de l'entrée dans l'appel récursif, construisant ainsi la liste comme effet secondaire , comme dans un paramètre d'accumulateur implicite. Le fragment Prolog suivant illustre le concept :

Exemple de code

% Prolog, tail recursive modulo cons:
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).

-- In Haskell, guarded recursion:
partition :: Ord a => [a] -> a -> ([a],[a])
partition [] _ = ([],[])
partition (x:xs) p | x < p     = (x:a,b)
                   | otherwise = (a,x:b)
   where
      (a,b) = partition xs p

% Prolog, with explicit unifications:
%     non-tail recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs],
 (  X @< Pivot
 -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest]
 ;  partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest]
 ).

% Prolog, with explicit unifications:
%     tail-recursive translation:
partition([], _, [], []).
partition(L, Pivot, Smalls, Bigs) :- 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 un 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 sous un constructeur de données évalué paresseusement, ce qui est automatiquement obtenu 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 :

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list *head = NULL;

    if (ls != NULL) {
        list *p = duplicate(ls->next);
        head = malloc(sizeof *head);
        head->value = ls->value;
        head->next = p;
    }
    return head;
}

;; in Scheme,
(define (duplicate ls)
  (if (not (null? ls))
    (cons (car ls)
          (duplicate (cdr ls)))
    '()))

%% in Prolog,
duplicate([X|Xs],R):- 
  duplicate(Xs,Ys),
  R=[X|Ys].
duplicate([],[]).

Sous cette forme, la fonction n'est pas récursive de queue, car le contrôle revient à l'appelant après que l'appel récursif duplique le reste de la liste d'entrée. Même si elle devait affecter le chef noeud avant de dupliquer le reste, il faudrait encore brancher le résultat de l'appel récursif dans le nextchamp après l'appel. 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 :

typedef struct list {
    void *value;
    struct list *next;
} list;
void duplicate_aux(const list *ls, list *end);

list *duplicate(const list *ls)
{   
    list head;

    duplicate_aux(ls, &head);
    return head.next;
}

void duplicate_aux(const list *ls, list *end)
{
    if (ls != NULL) {
        end->next = malloc(sizeof *end);
        end->next->value = ls->value;
        duplicate_aux(ls->next, end->next);
    } else {
        end->next = NULL;
    }
}

;; in Scheme,
(define (duplicate ls)
  (let ((head (list 1)))
    (let dup ((ls  ls) 
              (end head))
      (cond 
        ((not (null? ls)) 
         (set-cdr! end (list (car ls)))
         (dup (cdr ls) (cdr end)))))
    (cdr head)))

%% in Prolog,
duplicate([X|Xs],R):-
   R=[X|Ys],
   duplicate(Xs,Ys).
duplicate([],[]).

(Un nœud de tête 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é en marche avant depuis le début de la liste, avant l'appel récursif qui continue ensuite, au lieu de reculer depuis la fin de la liste, après que l'appel récursif a renvoyé son résultat. Elle est donc similaire à la technique d'accumulation de paramètres, transformant un calcul récursif en un calcul itératif.

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

L'implémentation de queue-récursive peut maintenant être convertie en une implémentation explicitement itérative, comme une boucle d' accumulation :

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list head, *end;
    end = &head;
    while (ls != NULL)
    {
        end->next        = malloc(sizeof *end);
        end->next->value = ls->value;
        ls = ls->next;
        end = end->next;
    }
    end->next = NULL;
    return head.next;
}

 ;; in Scheme,
 (define (duplicate ls)
   (let ((head (list 1)))
     (do ((end head (cdr end))
          (ls  ls   (cdr ls )))
         ((null? ls) (cdr head))
       (set-cdr! end (list (car ls))))))

%% in Prolog,
%% N/A

Histoire

Dans un document 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 en 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. Étant donné que de tels "appels de queue" sont très courants dans Lisp , un 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 à d'autres implémentations. Steele a fait valoir que des appels de procédure mal mis en œuvre avaient conduit à une perception artificielle selon laquelle le GOTO était bon marché par rapport à l'appel de procédure. Steele a en outre fait valoir que « en général, les appels de procédure peuvent être considérés comme des instructions GOTO qui transmettent également des paramètres et peuvent être uniformément codées en tant qu'instructions JUMP [code machine] », les instructions de manipulation de la pile de code machine « étant considérées comme une optimisation (plutôt que vice versa!)". 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 pour être implémentée dans n'importe quel interprète.

Modalités de mise en œuvre

La récursivité de la 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 du langage de Scheme exige que les appels de queue soient optimisés afin de ne pas augmenter la pile. Les appels de queue peuvent être effectués explicitement en Perl , avec une variante de l'instruction "goto" qui prend un nom de fonction :goto &NAME;

Cependant, pour les implémentations de langage qui stockent des arguments de fonction et des 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 d'appel de queue généralisée (y compris tail recursion) 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. Pour ces cas, l'optimisation de la récursivité de la 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). En conséquence, les langages fonctionnels tels que Scala qui ciblent la JVM peuvent implémenter efficacement la récursivité directe de la queue, mais pas la récursion mutuelle de la queue.

Les suites de compilateurs GCC , LLVM/Clang et Intel effectuent une optimisation d'appel de queue pour C et d'autres langages à des niveaux d'optimisation plus élevés ou lorsque l' -foptimize-sibling-callsoption est passée. Bien que la syntaxe du langage donné ne le supporte pas explicitement, le compilateur peut effectuer 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 transmis aux deux fonctions sont soit les mêmes, soit nécessitent le même quantité d'espace de stockage total sur la pile d'appels.

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

En assemblage

Les appels de queue sont souvent optimisés par des interprètes et des compilateurs de langages de programmation fonctionnelle et de programmation logique pour des formes d' itération plus efficaces . Par exemple, les programmeurs Scheme expriment généralement des boucles while en tant qu'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 .

Pour les compilateurs générant directement l'assembly, l'élimination des tail-call est simple : il suffit de remplacer un opcode d'appel par un jump, 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 pseudo- langage assembleur (en fait, il s'agit d'un assembleur x86 valide ) :

 foo:
  call B
  call A
  ret

L'élimination des appels de queue remplace les deux dernières lignes par une seule instruction de saut :

 foo:
  call B
  jmp  A

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

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 la trame d'appel pour A est correctement configurée avant de sauter au sous-programme appelé queue. Par exemple, sur les plates-formes où la pile d'appels ne contient pas 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 :

function foo(data1, data2)
   B(data1)
   return A(data2)

(où data1et data2sont des paramètres) un compilateur peut traduire cela par :

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

Un optimiseur d'appel de queue pourrait alors changer le code en :

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

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

Grâce au trampoline

Étant donné que de nombreux compilateurs Scheme utilisent C comme code cible intermédiaire, la récursivité de la queue doit être codé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 appelé trampoline , un morceau de code qui appelle à plusieurs reprises des fonctions. Toutes les fonctions sont entrées 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 (d'où elle a été appelée elle-même), et le trampoline s'occupe ensuite d'appeler cette fonction avec les paramètres spécifiés. Cela garantit que la pile C ne se développe pas et que l'itération peut continuer indéfiniment.

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

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 , dans laquelle des appels C normaux 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 Cheney en déplaçant toutes les données en direct dans un tas séparé. Suite à cela, la pile est déroulée ("éclatée") et le programme reprend à partir de l'état enregistré 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 de temps en temps de l'Empire State Building." Le ramasse-miettes garantit que la récursivité mutuelle peut se poursuivre 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 continuation-passing .

Relation avec l' instruction while

La récursivité de queue 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 prendre soin d'implémenter l' instruction d'affectation x ← baz( x ) afin que les dépendances soient respectées. On peut avoir besoin 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)
    ...
    else if r(x)
        return foo(qux(x))
    ...
    else
        return 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)
        ...
        else if r(x)
            x ← qux(x)
        ...
        else
            x ← quux(x)

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

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

En effet, n * fact(n - 1)encapsule l'appel à fact. Mais il peut être transformé en une définition récursive de queue en ajoutant un argument aappelé accumulator .

Ce programme Python donne une définition récursive 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)

Par langue

• Haskell - Oui
• Erlang - Oui
• Common Lisp - Certaines implémentations effectuent une optimisation d'appel de queue pendant la compilation si elles sont optimisées pour la vitesse
• JavaScript - Les moteurs compatibles ECMAScript 6.0 devraient avoir des appels de queue qui sont maintenant implémentés sur Safari / WebKit mais rejetés par V8 et SpiderMonkey
• Lua - La récursivité de la queue est requise par la définition du langage
• OCaml - Oui
• Python - Les implémentations Python de stock n'effectuent pas d'optimisation d'appel de queue, bien qu'un module tiers soit disponible pour le faire. L'inventeur du langage Guido van Rossum soutient que les traces de pile sont altéré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 une itération explicite.
• Rust - l'optimisation de l'appel de queue peut être effectuée dans des circonstances limitées, mais n'est pas garantie
• Schéma - Requis par la définition de la langue
• Raquette - Oui
• Tcl - Depuis Tcl 8.6, Tcl a une commande tailcall
• Kotlin - A tailrec modificateur pour les fonctions
• Elixir - Elixir implémente l'optimisation des appels de queue Comme tous les langages ciblant actuellement la VM BEAM.
• Perl - Explicite avec une variante de l'instruction "goto" qui prend un nom de fonction :goto &NAME;
• Scala - Les fonctions récursives de queue sont automatiquement optimisées par le compilateur. De telles fonctions peuvent également être éventuellement marquées avec une @tailrecannotation, ce qui en fait une erreur de compilation si la fonction n'est pas récursive.
• 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 de références (ARC).
• F# - F# implémente le TCO par défaut dans la mesure du possible
• Clojure - Clojure a une forme spéciale récurrente .
• Allez - Non

Voir également

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

Remarques

Les références

Cet article est basé sur du matériel extrait du Dictionnaire gratuit en ligne de l'informatique avant le 1er novembre 2008 et incorporé sous les termes de "relicensing" de la GFDL , version 1.3 ou ultérieure.