Ce qui est queue appel optimisation ?

Question

Très simplement, ce qui est optimisation d’appels terminaux ? Plus précisément, quelqu'un peut-il montrer quelques extraits de code petite où elle pourrait être appliquée et où pas, avec une explication de pourquoi ?

Answer 1

Queue-appel d'optimisation est l'endroit où vous êtes en mesure d'éviter d'allouer un nouveau cadre de pile pour une fonction, car l'appel de la fonction renvoie simplement la valeur que l'on obtient à partir de la fonction appelée. L'utilisation la plus courante est la queue de la récursivité, où une fonction récursive écrites pour profiter de la queue-appel de l'optimisation de l'utilisation constante de l'espace de pile.

Scheme est l'un des rares langages de programmation de cette garantie dans la spec que la mise en œuvre doit fournir à cette optimisation, voici donc deux exemples de la fonction factorielle dans le Schéma:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

La première fonction n'est pas de queue récursive car lors de l'appel récursif est fait, la fonction a besoin de garder une trace de la multiplication, il doit faire avec le résultat après les retours d'appel. En tant que tel, la pile se présente comme suit:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

En revanche, la trace de la pile pour la queue factorielle récursive se présente comme suit:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Comme vous pouvez le voir, nous avons seulement besoin de garder une trace de la même quantité de données pour chaque appel à la queue parce que nous sommes simplement en retournant la valeur que l'on obtient en passant par le haut. Cela signifie que même si j'étais à l'appel de fact (1000000), j'ai seulement besoin de la même quantité d'espace que fact (3). Ce n'est pas le cas avec les non-récursives terminales fait, et que ces valeurs élevées peut provoquer un débordement de pile.

Answer 2

Prenons un exemple simple: la fonction factorielle en œuvre dans C.

Nous commençons par l'évidence définition récursive

unsigned fac(unsigned n)
{
    if(n < 2) return 1;
    return n * fac(n - 1);
}

Une fonction se termine par une queue d'appel si la dernière opération avant le retour de fonction est un autre appel de fonction. Si cet appel invoque la même fonction, c'est la queue-récursive.

Même si fac() semble récursives terminales au premier coup d'œil, il n'est pas comme ce qui se passe réellement est

unsigned fac(unsigned n)
{
    if(n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

c'est à dire la dernière opération de la multiplication et de ne pas l'appel de la fonction.

Toutefois, il est possible de réécrire fac() à la queue-récursive en passant la valeur accumulée en bas de la chaîne d'appels comme un argument supplémentaire et de passer uniquement le résultat final de nouveau, comme la valeur de retour:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if(n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Maintenant, pourquoi est-ce utile? Parce que nous les retourner immédiatement après l'appel tail, nous ne pouvons ignorer la précédente structure de pile avant d'appeler la fonction dans la queue de la position, ou, dans le cas des fonctions récursives, la réutilisation de la structure de pile.

La queue-appel d'optimisation transforme notre récursive code dans

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if(n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Cela peut être incorporé fac() et nous arrivons à

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if(n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

ce qui est équivalent à

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for(; n > 1; --n)
        acc *= n;

    return acc;
}

Comme nous pouvons le voir ici, suffisamment avancée optimiseur peut remplacer la queue de la récursivité à l'itération, qui est beaucoup plus efficace que vous évitez d'appel de fonction, les frais généraux et de n'utiliser qu'une quantité constante de l'espace de pile.

Answer 3

Coût total de possession (la Queue d'Appel d'Optimisation) est le processus par lequel une smart compilateur peut faire un appel à une fonction de prendre aucun autre espace de pile. La seule situation dans laquelle cela se produit est que si la dernière instruction exécutée dans une fonction f est un appel à une fonction g (notez que g peut être f). La clé ici est que f n'a plus besoin d'espace de pile - il appelle simplement g, puis renvoie ce que g serait de retour. Dans ce cas, l'optimisation peut être faite que g juste exécute et retourne quelle que soit la valeur qu'elle aurait à la chose qui a appelé f.

Cette optimisation peut faire des appels récursifs prendre de la constante d'espace de pile, plutôt que d'exploser.

Exemple: cette fonction factorielle n'est pas TCOptimizable:

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

Cette fonction fait des choses en plus d'appeler une autre fonction dans son instruction return.

Ci-dessous la fonction est TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

C'est parce que la dernière chose à se produire dans l'une de ces fonctions est d'appeler une autre fonction.

Answer 4

Probablement le meilleur haut niveau de description que j'ai trouvé pour la queue appels récursifs de la queue des appels et de la queue d'appel d'optimisation est le suivant:

http://web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/blog/archives/000211.html

Ce que j'aime à propos de cette description est la façon succincte et il est facile à saisir pour ceux à venir à partir d'un langage impératif d'arrière-plan (C, C++, Java)

Answer 5

Notons tout d'abord que toutes les langues ne la soutiennent.

TCO applys à un cas particulier de la récursivité. L'essentiel, c'est que, si la dernière chose que vous faites dans une fonction est d'appeler lui-même (par exemple, il est d'appeler lui-même à partir de la "queue" de la position), ce qui peut être optimisé par le compilateur à agir comme l'itération au lieu de la norme de la récursivité.

Vous voyez, normalement, au cours de la récursivité, le moteur d'exécution besoin de garder une trace de tous les appels récursifs, de sorte que quand on rentre il peut le reprendre à l'appel précédent et ainsi de suite. (Essayez manuellement l'écriture du résultat d'un appel récursif pour avoir une idée visuelle de la façon dont cela fonctionne.) Garder une trace de tous les appels prend de la place, qui devient importante lorsque la fonction s'appelle elle-même beaucoup. Mais avec le coût total de possession, il suffit de dire "revenir au début, seulement cette fois, changez les valeurs des paramètres de ces nouvelles". Il peut le faire parce que rien après l'appel récursif se réfère à ces valeurs.