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

He estado navegando por toda la web en busca de iluminació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é es realmente la verdad. Si lo que creo que es verdad no es verdad, entonces es ignorancia y no iluminación.

Entonces, esto es lo que sé:

En casi todos los idiomas, las funciones devuelven explícitamente valores (y control) a la persona que llama. 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 el valor de retorno a una devolución de llamada en lugar de regresar explícitamente 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 continuación de la primera.

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

Creo que las continuaciones son un caso especial de devoluciones de llamada. Una función puede devolver cualquier cantidad de 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 vuelve a llamar a otra función como lo último que hace, la segunda función se llama continuación de la primera. 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 lo último que hace, entonces se llama una llamada de cola. Algunos lenguajes como Scheme realizan optimizaciones de llamada de cola. Esto significa que la llamada de cola no incurre en la sobrecarga total de una llamada de función. En cambio, se implementa como un simple goto (con el marco de la pila de la función de llamada reemplazado por el marco de la pila de la llamada de cola).

Bonificación : proceder al 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, si cada operación (incluida la suma, multiplicación, etc.) se escribiera en forma de funciones, 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, tendríamos que usar las siguientes continuaciones:

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 se le permite devolver valores (y, por lo tanto, debe recurrir a pasar las continuaciones) se llama estilo de paso de continuación.

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

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

El primer problema se puede resolver fácilmente en JavaScript llamando a las continuaciones de forma asincrónica. Al llamar a la continuación de forma asincrónica, la función vuelve antes de que se llame a 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-continuationque a menudo se abrevia como callcc. Desafortunadamente 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 callccfunción toma una función fy la aplica a current-continuation(abreviada como cc). La current-continuationes una función de continuación que envuelve el resto del cuerpo de la función después de la llamada a callcc.

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

El current-continuationde la segunda callcces:

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

Del mismo modo, el current-continuationprimero callcces:

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

Como el current-continuationprimero callcccontiene otro callcc, debe convertirse al estilo de paso de continuación:

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

Así que, esencialmente, callccconvierte lógicamente todo el cuerpo de la función a lo que comenzamos (y le da el nombre a esas funciones anónimas cc). La función de Pitágoras que usa esta implementación de callcc se convierte 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 callccen JavaScript, pero puede implementar el estilo de paso de continuación 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 callccse puede utilizar para implementar estructuras de flujo de control complejas, como bloques try-catch, corutinas, generadores, fibras , etc.

A pesar de la maravillosa crítica, creo que estás confundiendo un poco tu terminología. Por ejemplo, tiene razón en que una llamada de cola ocurre cuando la llamada es lo último que necesita ejecutar una función, pero en relación con las continuaciones, una llamada de cola 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). Es por eso que convertir una función recursiva de cola a CPS es tan fácil (simplemente agrega la continuación como parámetro y llama a la continuación en el resultado).

También es un poco extraño llamar a las continuaciones un caso especial de devoluciones de llamada. Puedo ver cómo se agrupan fácilmente, pero las continuidades no surgieron de la necesidad de distinguir de una devolución de llamada. Una continuación en realidad representa las instrucciones restantes para completar un cálculo , o el resto del cálculo desde este punto en el tiempo. Puede pensar en una continuación como un agujero que necesita ser llenado. 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 hace 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 desee y estructurarse de la forma que desee. Una continuación , entonces, es necesariamente un procedimiento de un argumento que resuelve el valor que se le pasa. Se debe aplicar una continuación a un valor único 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, los efectos secundarios pueden o no haberse generado.

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

Considere la función:

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

(Uso la sintaxis de Javascript, aunque Javascript no es compatible con las continuaciones de primera clase porque esto fue en lo que usted dio sus ejemplos, y será más comprensible para las personas que no estén familiarizadas con la sintaxis de Lisp).

Ahora, si le 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 pasarle una continuación que hace lo mismo que la devolución de llamada, así:

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

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

En este sentido, aunque invocar una continuación parece una llamada de función, de alguna manera es más parecido a una declaración de retorno o arrojando una excepción.

De hecho, call / cc puede usarse para agregar declaraciones de retorno a idiomas que no las admiten. Por ejemplo, si JavaScript no tenía una declaración de retorno (en cambio, como muchos lenguajes de Lips, solo devolvía el valor de la última expresión en el cuerpo de la función) pero tenía call / cc, podríamos implementar return de esta manera:

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 callcc()que devuelva el índice ien el que targetse encontró myArray.

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

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

Para aclarar algunas posibles interpretaciones erróneas:

• La optimización de llamadas de cola no se requiere de ninguna manera para admitir continuaciones de primera clase. ¡Tenga en cuenta que incluso el lenguaje C tiene una forma (restringida) de continuaciones en forma de setjmp(), que crea una continuación y longjmp()que invoca una!

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

• No hay ninguna razón particular para que una continuación tome solo un argumento. Es solo que los argumentos para la continuación se convierten en los valores de retorno de call / cc, y call / cc generalmente se define como que tiene un solo 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 Scheme), sería completamente posible tener continuaciones que acepten múltiples valores.