Pourquoi les trampolines fonctionnent-ils?

104

Je fais du JavaScript fonctionnel. Je pensais que l’ optimisation des appels en attente avait été mise en œuvre, mais j’ai eu tort. Ainsi, j'ai dû apprendre moi-même le trampoline . Après un peu de lecture ici et ailleurs, j'ai pu comprendre les bases et construire mon premier trampoline:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

Mon plus gros problème est que je ne sais pas pourquoi cela fonctionne. J'ai eu l'idée de réexécuter la fonction dans une boucle while au lieu d'utiliser une boucle récursive. Sauf que, techniquement, ma fonction de base a déjà une boucle récursive. Je n'exécute pas la loopyfonction de base , mais je l'exécute à l'intérieur. Qu'est-ce qui empêche foo = foo()de provoquer un débordement de pile? Et n'est-ce pas foo = foo()techniquement en mutation, ou est-ce que je manque quelque chose? Peut-être que c'est juste un mal nécessaire. Ou une syntaxe me manque.

Y a-t-il même un moyen de le comprendre? Ou est-ce juste un bidouillage qui fonctionne? J'ai pu parcourir tout le reste, mais celui-ci me laisse perplexe.

Ucenna
la source
5
Oui, mais c'est toujours la récursivité. loopyne déborde pas parce qu'il ne s'appelle pas lui-même .
Tkausl
4
"J'avais pensé que le TCO avait été mis en œuvre, mais je me suis trompé." Il a été au moins en V8 dans la plupart des scenaros. Vous pouvez l'utiliser par exemple dans n'importe quelle version récente de Node en demandant à Node de l'activer dans V8: stackoverflow.com/a/30369729/157247 Chrome l'avait (derrière un drapeau "expérimental") depuis Chrome 51.
TJ Crowder
125
L'énergie cinétique de l'utilisateur est transformée en énergie potentielle élastique à mesure que le trampoline s'affaisse, puis en énergie cinétique à mesure qu'elle rebondit.
user253751
66
@immibis, au nom de tous ceux qui sont venus ici sans vérifier de quel site Stack Exchange il s'agissait, merci.
user1717828
4
@ jpaugh vouliez-vous dire "sautiller"? ;-)
Hulk

Réponses:

89

La raison pour laquelle votre cerveau se rebelle contre cette fonction loopy()est qu’elle est de type incohérent :

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Un grand nombre de langues ne vous permettent même pas de faire des choses comme celle-ci, ou du moins exigent beaucoup plus de dactylographie pour expliquer à quel point cela est sensé. Parce que ce n'est vraiment pas le cas. Les fonctions et les entiers sont des types d'objets totalement différents.

Alors passons en revue cette boucle while:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Initialement, fooest égal à loopy(0). C'est quoi loopy(0)? Eh bien, c'est moins de 10000000, alors nous avons function(){return loopy(1)}. C'est une valeur de vérité, et c'est une fonction, donc la boucle continue.

Maintenant nous arrivons à foo = foo(). foo()est le même que loopy(1). Puisque 1 est toujours inférieur à 10000000, cela retourne function(){return loopy(2)}, auquel nous attribuons ensuite foo.

fooest toujours une fonction, alors nous continuons ... jusqu'à ce que foo soit égal à function(){return loopy(10000000)}. C'est une fonction, donc nous faisons foo = foo()une fois de plus, mais cette fois, lorsque nous appelons loopy(10000000), x n'est pas inférieur à 10000000, donc nous récupérons simplement x. Comme 10000000 n’est pas non plus une fonction, cela termine également la boucle while.

Kevin
la source
1
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Yannis
C'est vraiment juste un type de somme. Parfois connu comme une variante. Les langages dynamiques les supportent assez facilement car chaque valeur est étiquetée, alors que pour les langages statiques, vous devrez spécifier que la fonction renvoie une variante. Les trampolines sont facilement possibles en C ++ ou en Haskell, par exemple.
GManNickG
2
@GManNickG: Oui, c'est ce que je voulais dire par "beaucoup plus de dactylographie". En C, vous devez déclarer une union, déclarer une structure qui étiquette l’union, compresser et décompresser la structure à l’une ou l’autre des extrémités, décompresser et décompacter l’union à une extrémité et (probablement) déterminer à qui appartient la mémoire que la structure habite. . C ++ est très probablement moins de code que cela, mais ce n’est pas conceptuellement moins compliqué que C, et c’est encore plus verbeux que le Javascript de OP.
Kevin
Bien sûr, je ne conteste pas cela, je pense simplement que l'accent que vous mettez sur le fait que ce soit étrange ou qui n'a pas de sens est un peu fort. :)
GManNickG
173

Kevin explique succinctement le fonctionnement de cet extrait de code (avec la raison pour laquelle il est tout à fait incompréhensible), mais je voulais ajouter quelques informations sur le fonctionnement des trampolines en général .

Sans optimisation d'appel final (TCO), chaque appel de fonction ajoute un cadre de pile à la pile d'exécution en cours. Supposons que nous ayons une fonction pour imprimer un compte à rebours de nombres:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

Si nous appelons countdown(3), analysons l’apparence de la pile d’appel sans le coût total de possession.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

Avec le TCO, chaque appel récursif à countdownest en queue (il ne reste plus qu'à renvoyer le résultat de l'appel), de sorte qu'aucune trame de pile n'est allouée. Sans TCO, la pile explose même légèrement n.

Le trampoline contourne cette restriction en insérant un wrapper autour de la countdownfonction. Ensuite, countdownn'effectue pas d'appels récursifs mais renvoie immédiatement une fonction à appeler. Voici un exemple d'implémentation:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

Pour mieux comprendre comment cela fonctionne, regardons la pile d'appels:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

A chaque étape , la countdownHopfonction abandonne le contrôle direct de ce qui se passe ensuite, de retour à la place d' une fonction d'appel qui décrit ce qu'il vous se passer ensuite. La fonction de trampoline prend alors ceci et l'appelle, puis appelle la fonction qui revient, et ainsi de suite jusqu'à ce qu'il n'y ait plus d '"étape suivante". Cela s'appelle trampoline parce que le flux de contrôle "rebondit" entre chaque appel récursif et l'implémentation de trampoline, au lieu de la fonction directement récurrente. En abandonnant le contrôle sur qui fait l'appel récursif, la fonction de trampoline peut assurer la pile ne soit pas trop grand. Note latérale: cette implémentation trampolineomet de renvoyer des valeurs pour plus de simplicité.

Il peut être difficile de savoir si c'est une bonne idée. Les performances peuvent pâtir de chaque étape consistant à allouer une nouvelle fermeture. Des optimisations intelligentes peuvent rendre cela viable, mais on ne sait jamais. Le trampoline est principalement utile pour contourner les limites strictes de la récursivité, par exemple lorsqu'une implémentation linguistique définit une taille de pile d'appel maximale.

Jack
la source
18

Il devient peut-être plus facile de comprendre si le trampoline est implémenté avec un type de retour dédié (au lieu d’abuser d’une fonction):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Comparez cela à votre version de trampoline, où le cas de récursivité est celui où la fonction renvoie une autre fonction et le cas de base, le cas échéant.

Qu'est-ce qui empêche foo = foo()de provoquer un débordement de pile?

Il ne s'appelle plus. Au lieu de cela, il retourne un résultat (dans mon implémentation, littéralement a Result) qui indique s'il faut continuer la récursion ou s'ouvrir.

Et n'est-ce pas foo = foo()techniquement en mutation, ou est-ce que je manque quelque chose? Peut-être que c'est juste un mal nécessaire.

Oui, c'est exactement le mal nécessaire de la boucle. On pourrait aussi écrire trampolinesans mutation, mais cela nécessiterait à nouveau une récursion:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Néanmoins, cela montre encore mieux l’utilité de la fonction de trampoline.

Le point de trampoline consiste à extraire l'appel récursif de la fonction qui veut utiliser la récursion dans une valeur de retour et à faire la récursion réelle à un seul endroit - la trampolinefonction peut ensuite être optimisée à un seul endroit pour utiliser un boucle.

Bergi
la source
foo = foo()C'est une mutation dans le sens de la modification de l'état local, mais je considérerais généralement cette réaffectation car vous ne modifiez pas réellement l'objet de fonction sous-jacent, vous le remplacez par la fonction (ou la valeur) qu'il renvoie.
JAB
@JAB Oui, je ne voulais pas impliquer de muter la valeur qui foocontient, seule la variable est modifiée. Une whileboucle nécessite un état modifiable si vous voulez qu'elle se termine, dans ce cas la variable fooou x.
Bergi
J'ai déjà fait quelque chose comme ça il y a quelque temps dans cette réponse à une question sur le dépassement de capacité au sujet de l'optimisation des appels de queue, des trampolines, etc.
Joshua Taylor
2
Votre version sans mutation a converti un appel récursif de fnen un appel récursif à trampoline- je ne suis pas sûr que ce soit une amélioration.
Michael Anderson
1
@ MichaelAnderson Il est uniquement destiné à démontrer l'abstraction. Bien sûr, un trampoline récursif n'est pas utile.
Bergi