Quelle est la différence entre une continuation et un rappel?

133

J'ai parcouru le Web à la recherche d'éclaircissements sur les suites, et il est ahurissant de voir comment la plus simple des explications peut si complètement confondre un programmeur JavaScript comme moi. Cela est particulièrement vrai lorsque la plupart des articles expliquent les suites avec du code dans Scheme ou utilisent des monades.

Maintenant que je pense enfin avoir compris l'essence des suites, je voulais savoir si ce que je sais est réellement la vérité. Si ce que je pense est vrai n'est pas réellement vrai, alors c'est de l'ignorance et non de l'illumination.

Alors, voici ce que je sais:

Dans presque tous les langages, les fonctions renvoient explicitement des valeurs (et un contrôle) à leur appelant. Par exemple:

var sum = add(2, 3);

console.log(sum);

function add(x, y) {
    return x + y;
}

Maintenant, dans un langage avec des fonctions de première classe, nous pouvons passer le contrôle et renvoyer la valeur à un rappel au lieu de retourner explicitement à l'appelant:

add(2, 3, function (sum) {
    console.log(sum);
});

function add(x, y, cont) {
    cont(x + y);
}

Ainsi, au lieu de renvoyer une valeur à partir d'une fonction, nous continuons avec une autre fonction. Par conséquent, cette fonction est appelée une continuation de la première.

Alors, quelle est la différence entre une continuation et un rappel?

Aadit M Shah
la source
4
Une partie de moi pense que c'est une très bonne question et une partie de moi pense que c'est trop long et aboutit probablement à une réponse «oui / non». Cependant, en raison de l'effort et de la recherche impliqués, je vais avec mon premier sentiment.
Andras Zoltan
2
Quelle est votre question? On dirait que vous comprenez bien cela.
Michael Aaron Safyan
3
Oui, je suis d'accord - je pense que cela aurait probablement dû être un article de blog plus proche de «JavaScript Continuations - ce que je les comprends».
Andras Zoltan
9
Eh bien, il y a une question essentielle: "Alors quelle est la différence entre une suite et un rappel?", Suivie d'un "je crois ...". La réponse à cette question peut être intéressante?
Confusion
3
Cela semble être plus approprié pour être publié sur programmers.stackexchange.com.
Brian Reischl

Réponses:

164

Je crois que les continuations sont un cas particulier de rappels. Une fonction peut rappeler n'importe quel nombre de fonctions, n'importe quel nombre de fois. Par exemple:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;
    for (var i = 0; i < length; i++)
        callback(array[i], array, i);
}

Cependant, si une fonction rappelle une autre fonction en dernier lieu, alors la deuxième fonction est appelée une continuation de la première. Par exemple:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;

    // This is the last thing forEach does
    // cont is a continuation of forEach
    cont(0);

    function cont(index) {
        if (index < length) {
            callback(array[index], array, index);
            // This is the last thing cont does
            // cont is a continuation of itself
            cont(++index);
        }
    }
}

Si une fonction appelle une autre fonction en dernier lieu, elle s'appelle un appel de queue. Certains langages comme Scheme effectuent des optimisations des appels de fin. Cela signifie que l'appel de fin n'entraîne pas la surcharge totale d'un appel de fonction. Au lieu de cela, il est implémenté comme un simple goto (avec le cadre de pile de la fonction appelante remplacé par le cadre de pile de l'appel de queue).

Bonus : passez au style de passe de continuation. Considérez le programme suivant:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return x * x + y * y;
}

Maintenant, si chaque opération (y compris l'addition, la multiplication, etc.) était écrite sous forme de fonctions, alors nous aurions:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return add(square(x), square(y));
}

function square(x) {
    return multiply(x, x);
}

function multiply(x, y) {
    return x * y;
}

function add(x, y) {
    return x + y;
}

De plus, si nous n'étions pas autorisés à renvoyer des valeurs, nous devrons utiliser les continuations comme suit:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    square(x, function (x_squared) {
        square(y, function (y_squared) {
            add(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

Ce style de programmation dans lequel vous n'êtes pas autorisé à renvoyer des valeurs (et par conséquent, vous devez recourir à la transmission de continuations) est appelé style de passage de continuation.

Il y a cependant deux problèmes avec le style de passage de continuation:

  1. La transmission de continuations augmente la taille de la pile d'appels. À moins d'utiliser un langage comme Scheme qui élimine les appels de queue, vous risquez de manquer d'espace dans la pile.
  2. C'est pénible d'écrire des fonctions imbriquées.

Le premier problème peut être facilement résolu en JavaScript en appelant les continuations de manière asynchrone. En appelant la continuation de manière asynchrone, la fonction retourne avant que la continuation ne soit appelée. Par conséquent, la taille de la pile d'appels n'augmente pas:

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    square.async(x, function (x_squared) {
        square.async(y, function (y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

Le deuxième problème est généralement résolu en utilisant une fonction appelée call-with-current-continuationqui est souvent abrégée en callcc. Malheureusement, callccne peut pas être entièrement implémenté en JavaScript, mais nous pourrions écrire une fonction de remplacement pour la plupart de ses cas d'utilisation:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    var x_squared = callcc(square.bind(null, x));
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

function callcc(f) {
    var cc = function (x) {
        cc = x;
    };

    f(cc);

    return cc;
}

La callccfonction prend une fonction fet l'applique au current-continuation(abrégé en cc). La current-continuationest une fonction de continuation qui enveloppe le reste du corps de la fonction après l'appel à callcc.

Considérez le corps de la fonction pythagoras:

var x_squared = callcc(square.bind(null, x));
var y_squared = callcc(square.bind(null, y));
add(x_squared, y_squared, cont);

Le current-continuationde la seconde callccest:

function cc(y_squared) {
    add(x_squared, y_squared, cont);
}

De même, le current-continuationpremier callccest:

function cc(x_squared) {
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

Puisque le current-continuationdu premier en callcccontient un autre, callccil doit être converti en style de passage de continuation:

function cc(x_squared) {
    square(y, function cc(y_squared) {
        add(x_squared, y_squared, cont);
    });
}

Donc, essentiellement, callccconvertit logiquement tout le corps de la fonction en ce que nous avons commencé (et donne le nom à ces fonctions anonymes cc). La fonction pythagoras utilisant cette implémentation de callcc devient alors:

function pythagoras(x, y, cont) {
    callcc(function(cc) {
        square(x, function (x_squared) {
            square(y, function (y_squared) {
                add(x_squared, y_squared, cont);
            });
        });
    });
}

Encore une fois, vous ne pouvez pas implémenter callccen JavaScript, mais vous pouvez l'implémenter le style de passage de continuation en JavaScript comme suit:

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    callcc.async(square.bind(null, x), function cc(x_squared) {
        callcc.async(square.bind(null, y), function cc(y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

function callcc(f, cc) {
    f.async(cc);
}

La fonction callccpeut être utilisée pour implémenter des structures de flux de contrôle complexes telles que des blocs try-catch, des coroutines, des générateurs, des fibres , etc.

Aadit M Shah
la source
10
Je suis tellement reconnaissant que les mots ne peuvent pas décrire. J'ai enfin compris au niveau de l'intuition tous les concepts liés à la continuation en un seul passage! Je nouveau une fois qu'il a cliqué, cela allait être simple et je verrais que j'ai utilisé le modèle plusieurs fois avant sans le savoir, et c'était juste comme ça. Merci beaucoup pour l'explication merveilleuse et claire.
ata
2
Les trampolines sont des trucs assez simples mais puissants. Veuillez consulter le post de Reginald Braithwaite à leur sujet.
Marco Faustinelli
1
Merci d'avoir répondu. Je me demande si vous pourriez fournir plus de support pour l'instruction que callcc ne peut pas être implémentée en JavaScript? Peut-être une explication de ce dont JavaScript aurait besoin pour l'implémenter?
John Henry
1
@JohnHenry - en fait, il y a une implémentation call / cc en JavaScript faite par Matt Might ( matt.might.net/articles/by-example-continuation-passing-style - allez au tout dernier paragraphe), mais s'il vous plaît ne faites pas ' t demandez-moi comment cela fonctionne ni comment l'utiliser :-)
Marco Faustinelli
1
@JohnHenry JS aurait besoin de continuations de première classe (considérez-les comme un mécanisme pour capturer certains états de la pile d'appels). Mais il n'a que des fonctions et des fermetures de première classe, donc CPS est le seul moyen d'imiter les suites. Dans Scheme, les conts sont implicites et une partie du travail de callcc est de "réifier" ces conts implicites, de sorte que la fonction consommatrice y ait accès. C'est pourquoi callcc dans Scheme attend une fonction comme seul argument. La version CPS de callcc dans JS diffère, car le cont est passé en tant qu'argument func explicite. Le callcc d'Aadit est donc suffisant pour de nombreuses applications.
scriptum
27

Malgré la merveilleuse rédaction, je pense que vous confondez un peu votre terminologie. Par exemple, vous avez raison de dire qu'un appel de queue se produit lorsque l'appel est la dernière chose qu'une fonction a besoin d'exécuter, mais en ce qui concerne les continuations, un appel de queue signifie que la fonction ne modifie pas la continuation avec laquelle elle est appelée, seulement qu'elle met à jour la valeur passée à la suite (si elle le souhaite). C'est pourquoi la conversion d'une fonction récursive de queue en CPS est si simple (il vous suffit d'ajouter la continuation en tant que paramètre et d'appeler la continuation sur le résultat).

Il est également un peu étrange d'appeler les continuations un cas particulier de rappels. Je peux voir comment ils sont facilement regroupés, mais les suites ne découlent pas de la nécessité de les distinguer d'un rappel. Une suite représente en fait les instructions restantes pour terminer un calcul , ou le reste du calcul à partir de ce moment. Vous pouvez considérer une continuation comme un trou qui doit être comblé. Si je peux capturer la continuation actuelle d'un programme, alors je peux revenir exactement à la façon dont le programme était lorsque j'ai capturé la suite. (Cela facilite certainement l'écriture des débogueurs.)

Dans ce contexte, la réponse à votre question est qu'un rappel est une chose générique qui est appelée à tout moment spécifié par un contrat fourni par l'appelant [du rappel]. Un callback peut avoir autant d'arguments qu'il le souhaite et être structuré comme il le souhaite. Une continuation est donc nécessairement une procédure à un argument qui résout la valeur qui y est passée. Une continuation doit être appliquée à une valeur unique et l'application doit se produire à la fin. Lorsqu'une continuation termine l'exécution, l'expression est terminée et, selon la sémantique du langage, des effets secondaires peuvent ou non avoir été générés.

dcow
la source
3
Merci pour la clarification. Vous avez raison. Une continuation est en fait une réification de l'état de contrôle du programme: un instantané de l'état du programme à un moment donné. Le fait qu'elle puisse être appelée comme une fonction normale n'a pas d'importance. Les continuations ne sont pas réellement des fonctions. Les rappels sont en fait des fonctions. C'est la vraie différence entre les continuations et les rappels. Néanmoins, JS ne prend pas en charge les continuations de première classe. Seulement des fonctions de première classe. Par conséquent, les suites écrites en CPS dans JS sont simplement des fonctions. Merci pour votre participation. =)
Aadit M Shah
4
@AaditMShah oui, je me suis mal exprimé. Une continuation n'a pas besoin d'être une fonction (ou une procédure comme je l'ai appelée). Par définition, il s'agit simplement de la représentation abstraite des choses à venir. Cependant, même dans Scheme, une continuation est invoquée comme une procédure et transmise comme telle. Hmm ... cela soulève la question tout aussi intéressante de savoir à quoi ressemble une continuation qui n'est pas une fonction / procédure.
dcow le
@AaditMShah assez intéressant pour que je continue la discussion ici: programmers.stackexchange.com/questions/212057/…
dcow
14

La réponse courte est que la différence entre une continuation et un rappel est qu'après qu'un rappel est appelé (et s'est terminé), l'exécution reprend au point où elle a été invoquée, tandis que l'invocation d'une continuation entraîne la reprise de l'exécution au moment où la continuation a été créée. En d'autres termes: une suite ne revient jamais .

Considérez la fonction:

function add(x, y, c) {
    alert("before");
    c(x+y);
    alert("after");
}

(J'utilise la syntaxe Javascript même si Javascript ne prend pas en charge les continuations de première classe car c'est ce dans quoi vous avez donné vos exemples, et ce sera plus compréhensible pour les personnes qui ne sont pas familières avec la syntaxe Lisp.)

Maintenant, si nous lui passons un rappel:

add(2, 3, function (sum) {
    alert(sum);
});

puis nous verrons trois alertes: "avant", "5" et "après".

D'un autre côté, si nous devions lui passer une continuation qui fait la même chose que le rappel, comme ceci:

alert(callcc(function(cc) {
    add(2, 3, cc);
}));

alors nous verrions juste deux alertes: "avant" et "5". L'appel à l' c()intérieur add()met fin à l'exécution add()et provoque callcc()le retour; la valeur renvoyée par callcc()était la valeur passée comme argument àc (à savoir, la somme).

En ce sens, même si invoquer une continuation ressemble à un appel de fonction, cela ressemble plus à une instruction return ou à une exception.

En fait, call / cc peut être utilisé pour ajouter des instructions de retour aux langages qui ne les prennent pas en charge. Par exemple, si JavaScript n'avait pas d'instruction return (à la place, comme beaucoup de langages Lips, renvoyant simplement la valeur de la dernière expression dans le corps de la fonction) mais avait call / cc, nous pourrions implémenter return comme ceci:

function find(myArray, target) {
    callcc(function(return) {
        var i;
        for (i = 0; i < myArray.length; i += 1) {
            if(myArray[i] === target) {
                return(i);
            }
        }
        return(undefined); // Not found.
    });
}

L'appel return(i)appelle une continuation qui met fin à l'exécution de la fonction anonyme et provoque callcc()le renvoi de l'index idans lequel a targetété trouvé myArray.

(NB: il y a des façons dont l'analogie du "retour" est un peu simpliste. Par exemple, si une suite s'échappe de la fonction dans laquelle elle a été créée - en étant sauvegardée quelque part dans un global, disons - il est possible que la fonction qui a créé la continuation peut renvoyer plusieurs fois même si elle n'a été invoquée qu'une seule fois .)

Call / cc peut également être utilisé pour implémenter la gestion des exceptions (throw et try / catch), des boucles et de nombreuses autres structures de contrôle.

Pour dissiper certains malentendus possibles:

  • L'optimisation des appels de queue n'est en aucun cas nécessaire pour prendre en charge des continuations de première classe. Considérez que même le langage C a une forme (restreinte) de continuations sous la forme de setjmp(), qui crée une continuation, et longjmp(), qui en appelle une!

    • D'un autre côté, si vous essayez naïvement d'écrire votre programme dans un style de continuation sans optimisation des appels de queue, vous êtes condamné à déborder éventuellement la pile.
  • Il n'y a aucune raison particulière pour qu'une continuation ne prenne qu'un seul argument. C'est juste que le ou les arguments de la continuation deviennent la ou les valeurs de retour de call / cc, et call / cc est généralement défini comme ayant une seule valeur de retour, donc naturellement la continuation doit en prendre exactement une. Dans les langages prenant en charge plusieurs valeurs de retour (comme Common Lisp, Go ou même Scheme), il serait tout à fait possible d'avoir des suites acceptant plusieurs valeurs.

cpcallen
la source
2
Toutes mes excuses si j'ai commis des erreurs dans les exemples JavaScript. La rédaction de cette réponse a pratiquement doublé la quantité totale de JavaScript que j'ai écrit.
cpcallen
Dois-je bien comprendre que vous parlez de continuations non délimitées dans cette réponse, et la réponse acceptée parle de continuations délimitées?
Jozef Mikušinec
1
"invoquer une continuation provoque la reprise de l'exécution au moment où la continuation a été créée" - je pense que vous confondez "créer" une continuation avec la capture de la continuation actuelle .
Alexey
@Alexey: c'est le genre de pédantisme que j'approuve. Mais la plupart des langages ne fournissent aucun moyen de créer une continuation (réifiée) autrement qu'en capturant la continuation actuelle.
cpcallen
1
@jozef: Je parle certainement de suites non limitées. Je pense que c'était aussi l'intention d'Aadit, bien que, comme le note dcow, la réponse acceptée ne distingue pas les continuations des appels de queue (étroitement liés), et je note qu'une continuation délimitée équivaut de toute façon à une fonction / procédure: community.schemewiki.org/ ? composable-continuations-tutorial
cpcallen