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

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?

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.

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.

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.