javascript - ¿Cuál es la diferencia entre una continuación y una devolución de llamada?

continuations callcc

Question

He estado navegando por toda la web en busca de información sobre las continuaciones, y es alucinante cómo las explicaciones más simples pueden confundir por completo a un programador de JavaScript como yo. Esto es especialmente cierto cuando la mayoría de los artículos explican las continuaciones con código en Scheme o usan mónadas.

Ahora que finalmente creo haber entendido la esencia de las continuaciones, quería saber si lo que sé realmente es la verdad. Si lo que creo que es cierto no es realmente cierto, entonces es ignorancia y no iluminación.

Entonces, esto es lo que sé:

En casi todos los idiomas, las funciones devuelven valores (y control) explícitamente a su interlocutor. Por ejemplo:

var sum = add(2, 3);

console.log(sum);

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

Ahora, en un lenguaje con funciones de primera clase, podemos pasar el control y devolver el valor a una devolución de llamada en lugar de volver de forma explícita a la persona que llama:

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

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

Por lo tanto, en lugar de devolver un valor de una función, continuamos con otra función. Por lo tanto, esta función se llama una continuación de la primera.

Entonces, ¿cuál es la diferencia entre una continuación y una devolución de llamada?

Answer 1

A pesar de la maravillosa reseña, creo que estás confundiendo un poco tu terminología. Por ejemplo, tiene razón en que ocurre una llamada final cuando la llamada es lo último que necesita ejecutar una función, pero en relación con las continuas, una llamada final significa que la función no modifica la continuación con la que se llama, solo que actualiza el valor pasado a la continuación (si lo desea). Esta es la razón por la cual la conversión de una función recursiva de cola a CPS es muy fácil (simplemente agrega la continuación como parámetro y llama a la continuación sobre el resultado).

También es un poco raro llamar a las continuaciones un caso especial de devolución de llamada. Puedo ver cómo se agrupan fácilmente, pero las continuas no surgieron de la necesidad de distinguir de una devolución de llamada. Una continuación representa realmente las instrucciones restantes para completar un cálculo , o el resto del cálculo a partir de este punto en el tiempo. Puede pensar en una continuación como un agujero que debe completarse. Si puedo capturar la continuación actual de un programa, entonces puedo volver exactamente a cómo era el programa cuando capturé la continuación. (Eso asegura que los depuradores sean más fáciles de escribir).

En este contexto, la respuesta a su pregunta es que una devolución de llamada es una cosa genérica que se llama en cualquier momento especificado por algún contrato proporcionado por la persona que llama [de la devolución de llamada]. Una devolución de llamada puede tener tantos argumentos como quiera y estar estructurado de la manera que quiera. Una continuación , entonces, es necesariamente un procedimiento de un solo argumento que resuelve el valor pasado a él. Una continuación se debe aplicar a un único valor y la aplicación debe suceder al final. Cuando una continuación termina de ejecutarse, la expresión se completa y, dependiendo de la semántica del lenguaje, es posible que se generen efectos secundarios o no.

Answer 2

Creo que las continuaciones son un caso especial de devoluciones de llamada. Una función puede devolver varias funciones, cualquier cantidad de veces. Por ejemplo:

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);
}

Sin embargo, si una función llama a otra función como la última cosa que hace, entonces la segunda función se llama continuación del primero. Por ejemplo:

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 una función llama a otra función como la última cosa que hace, se llama una llamada final. Algunos lenguajes como Scheme realizan optimizaciones de llamadas finales. Esto significa que la llamada final no genera la sobrecarga total de una llamada a función. En su lugar, se implementa como un goto simple (con el marco de pila de la función de llamada reemplazado por el marco de pila de la llamada final).

Bonificación : continuar con el estilo de pase de continuación. Considere el siguiente programa:

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

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

Ahora bien, si cada operación (incluida la suma, multiplicación, etc.) se escribiera en forma de funciones, entonces tendríamos:

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;
}

Además, si no se nos permitiera devolver ningún valor, entonces tendríamos que usar las continuaciones de la siguiente manera:

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);
}

Este estilo de programación en el que no está permitido devolver valores (y, por lo tanto, debe recurrir a las continuidades de paso) se denomina estilo de paso de continuación.

Sin embargo, hay dos problemas con el estilo de paso de continuación:

1. Pasar por las continuidades aumenta el tamaño de la pila de llamadas. A menos que esté usando un lenguaje como Scheme que elimina las llamadas de cola, correrá el riesgo de quedarse sin espacio en la pila.
2. Es un dolor escribir funciones anidadas.

El primer problema se puede resolver fácilmente en JavaScript llamando a continuaciones de forma asincrónica. Al llamar a la continuación de forma asincrónica, la función regresa antes de que se invoque la continuación. Por lo tanto, el tamaño de la pila de llamadas no aumenta:

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);
}

El segundo problema generalmente se resuelve usando una función llamada call-with-current-continuation que a menudo se abrevia como callcc . Lamentablemente, callcc no se puede implementar completamente en JavaScript, pero podríamos escribir una función de reemplazo para la mayoría de sus casos de uso:

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 función callcc toma una función f y la aplica a la current-continuation (abreviada como cc ). La current-continuation es una función de continuación que envuelve el resto del cuerpo de la función después de la llamada a callcc .

Considera el cuerpo de la función pythagoras :

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

La current-continuation de la segunda callcc es:

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

Del mismo modo, la current-continuation de la primera callcc es:

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

Como la current-continuation del primer callcc contiene otro callcc , debe convertirse al estilo de continuación de paso:

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

Así que, esencialmente, callcc convierte de forma lógica todo el cuerpo de la función en lo que comenzamos (y da a esas funciones anónimas el nombre cc ). La función pythagoras usando esta implementación de callcc se convierte entonces en:

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

Nuevamente, no puede implementar callcc en JavaScript, pero puede implementarlo en JavaScript de la siguiente manera:

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 función callcc se puede usar para implementar estructuras complejas de flujo de control, como bloques de try-catch, corutinas, generadores, fibers , etc.

Answer 3

La respuesta breve es que la diferencia entre una continuación y una devolución de llamada es que después de que se invoca (y ha finalizado) la ejecución se reanuda en el punto en que se invocó, mientras que al invocar una continuación la reanudación se reanuda en el punto donde se creó la continuación. En otras palabras: una continuación nunca regresa .

Considera la función:

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

(Utilizo la sintaxis de Javascript aunque Javascript no admite las continuas de primera clase porque esto es lo que le dio a sus ejemplos, y será más comprensible para las personas que no estén familiarizadas con la sintaxis de Lisp).

Ahora, si lo pasamos una devolución de llamada:

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

luego veremos tres alertas: "antes", "5" y "después".

Por otro lado, si tuviéramos que pasar una continuación que hace lo mismo que la devolución de llamada, así:

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

entonces solo veríamos dos alertas: "antes" y "5". La invocación de c() dentro de add() finaliza la ejecución de add() y hace que callcc() vuelva; el valor devuelto por callcc() fue el valor pasado como argumento para c (es decir, la suma).

En este sentido, aunque invocar una continuación parece una llamada de función, en cierto modo es más parecido a una declaración de devolución o lanzar una excepción.

De hecho, call / cc se puede usar para agregar declaraciones de devolución a idiomas que no las admiten. Por ejemplo, si JavaScript no tiene declaración de retorno (en cambio, como en muchos idiomas Lips, simplemente devuelve el valor de la última expresión en el cuerpo de la función) pero sí tenía call / cc, podríamos implementar un retorno como este:

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.
    });
}

Llamar return(i) invoca una continuación que finaliza la ejecución de la función anónima y hace que callcc() devuelva el índice i en el que se encontró el target en myArray .

(NB: hay algunas formas en que la analogía del "retorno" es un poco simplista. Por ejemplo, si una continuación se escapa de la función en la que fue creada - al ser guardada en un lugar global, digamos - es posible que la función que creó la continuación puede regresar varias veces a pesar de que solo se invocó una vez ).

Call / cc se puede usar de manera similar para implementar el manejo de excepciones (throw y try / catch), bucles y muchas otras estructuras de control.

Para aclarar algunos posibles malentendidos:

• La optimización de la llamada de la cola no se requiere de ninguna manera para apoyar las continuaciones de primera clase. Considere que incluso el lenguaje C tiene una forma (restringida) de continuaciones en forma de setjmp() , que crea una continuación, y longjmp() , ¡que invoca a uno!

  • Por otro lado, si ingenuamente intentas escribir tu programa en un estilo continuo sin la optimización de la cola de llamada, estás condenado a desbordar la pila.

• No hay una razón particular para que una continuación necesite tomar solo un argumento. Es solo que los argumentos para la continuación se convierten en los valores de devolución de call / cc, y call / cc se define típicamente como tener un único valor de retorno, por lo que, naturalmente, la continuación debe tomar exactamente uno. En idiomas con soporte para múltiples valores de retorno (como Common Lisp, Go o incluso Scheme) sería completamente posible tener continuaciones que acepten valores múltiples.