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

Question

J'ai parcouru l'ensemble du web à la recherche d'informations sur les continuations, et je suis stupéfait de constater que les explications les plus simples peuvent déconcerter un programmeur JavaScript comme moi. C'est particulièrement vrai lorsque la plupart des articles expliquent les continuations avec du code en Scheme ou utilisent des monades.

Maintenant que je pense enfin avoir compris l'essence des continuations, je voulais savoir si ce que je sais est réellement la vérité. Si ce que je pense être vrai n'est pas réellement vrai, alors il s'agit d'ignorance et non d'illumination.

Donc, voilà ce que je sais :

Dans presque tous les langages, les fonctions renvoient explicitement des valeurs (et le 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 la valeur de retour à un callback 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. Cette fonction est donc appelée une continuation de la première.

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

Answer 1

Je crois que les continuations sont un cas particulier de callbacks. Une fonction peut rappeler un nombre quelconque de fonctions, un nombre quelconque 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, 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, cela s'appelle un appel de fin. Certains langages comme Scheme optimisent les appels de queue. Cela signifie que l'appel de queue ne subit pas toute la surcharge 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 : Procéder à la continuation du style de passing. Considérons 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 la forme de fonctions, 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;
}

En outre, si nous n'étions pas autorisés à renvoyer des valeurs, nous devrions utiliser des 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 où vous devez donc faire circuler des continuations) s'appelle le style continuation passing.

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

1. Le passage de continuations augmente la taille de la pile d'appels. À moins que vous n'utilisiez un langage comme Scheme qui élimine les appels de queue, vous risquez de manquer d'espace sur la pile.
2. Il est difficile 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 revient avant que la continuation ne soit appelée. Ainsi, 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 second problème est généralement résolu à l'aide d'une fonction appelée call-with-current-continuation qui est souvent abrégé en callcc . Malheureusement callcc ne peut pas être entièrement implémenté en JavaScript, mais nous pouvons é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;
}

Le site callcc prend une fonction f et l'applique à la current-continuation (en abrégé cc ). Le site current-continuation est une fonction de continuation qui reprend le reste du corps de la fonction après l'appel à la fonction callcc .

Considérons 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 site current-continuation du second callcc est :

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

De même, le current-continuation du premier callcc est :

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

Depuis le current-continuation du premier callcc contient un autre callcc il 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 callcc convertit logiquement le corps entier de la fonction en ce que nous avons commencé (et donne à ces fonctions anonymes le nom de 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 mettre en œuvre callcc en JavaScript, mais vous pouvez l'implémenter à la manière du 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 callcc peut être utilisé pour mettre en œuvre des structures de flux de contrôle complexes telles que des blocs try-catch, des coroutines, des générateurs, fibres etc.

Answer 2

En dépit de ce magnifique article, 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 doit 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, mais qu'elle met à jour la valeur passée à la continuation (si elle le souhaite). C'est pourquoi il est si facile de convertir une fonction récursive de queue en CPS (il suffit d'ajouter la continuation comme paramètre et d'appeler la continuation sur le résultat).

Il est également un peu étrange d'appeler les continuations un cas spécial de callbacks. Je peux voir comment ils sont facilement regroupés, mais les continuations ne sont pas nées de la nécessité de faire la distinction avec un callback. Une continuation représente en fait le instructions restantes pour terminer un calcul ou le reste du calcul à partir de este point dans le temps. Vous pouvez considérer une continuation comme un trou qui doit être comblé. Si je peux capturer la continuation actuelle d'un programme, je peux alors revenir à l'état exact du programme au moment où j'ai capturé la continuation. (Cela rend certainement les débogueurs plus faciles à écrire).

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 callback]. Un callback peut avoir autant d'arguments qu'il le souhaite et être structuré de la manière qu'il veut. A continuation est donc nécessairement une procédure à un argument qui résout la valeur qui lui est passée. Une continuation doit être appliquée à une seule valeur et l'application doit se faire à la fin. Lorsqu'une continuation finit de s'exécuter, l'expression est complète et, selon la sémantique du langage, des effets secondaires peuvent ou non avoir été générés.