Qual é a diferença entre uma continuação e um retorno de chamada?

Estive navegando por toda a web em busca de esclarecimentos sobre continuações, e é espantoso como a explicação mais simples pode confundir totalmente um programador de JavaScript como eu. Isso é especialmente verdade quando a maioria dos artigos explica continuações com código no esquema ou usa mônadas.

Agora que finalmente acho que entendi a essência das continuações, queria saber se o que sei é realmente a verdade. Se o que penso ser verdade não é verdade, é ignorância e não iluminação.

Então, aqui está o que eu sei:

Em quase todos os idiomas, as funções retornam explicitamente valores (e controle) para o chamador. Por exemplo:

var sum = add(2, 3);

console.log(sum);

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

Agora, em um idioma com funções de primeira classe, podemos passar o controle e retornar o valor para um retorno de chamada em vez de retornar explicitamente ao chamador:

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

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

Assim, em vez de retornar um valor de uma função, continuamos com outra função. Portanto, essa função é chamada de continuação da primeira.

Então, qual é a diferença entre uma continuação e um retorno de chamada?

Acredito que as continuações são um caso especial de retornos de chamada. Uma função pode retornar qualquer número de funções, qualquer número de vezes. Por exemplo:

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

No entanto, se uma função chama de volta outra função como a última coisa que faz, a segunda função é chamada de continuação da primeira. Por exemplo:

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

Se uma função chama outra função como a última coisa que faz, então é chamada de chamada final. Alguns idiomas como o Scheme realizam otimizações de chamada de cauda. Isso significa que a chamada final não incorre na sobrecarga completa de uma chamada de função. Em vez disso, é implementado como um simples goto (com o quadro da pilha da função de chamada substituído pelo quadro da pilha da chamada final).

Bônus : Prosseguindo para o estilo de passagem continuada. Considere o seguinte programa:

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

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

Agora, se todas as operações (incluindo adição, multiplicação, etc.) fossem escritas na forma de funções, terí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;
}

Além disso, se não nos fosse permitido retornar valores, teríamos que usar continuações da seguinte maneira:

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

Esse estilo de programação em que você não tem permissão para retornar valores (e, portanto, você deve recorrer a repetições) é chamado de estilo de passagem de continuação.

No entanto, existem dois problemas com o estilo de passagem de continuação:

1. Passar por continuações aumenta o tamanho da pilha de chamadas. A menos que você esteja usando uma linguagem como o Scheme, que elimina chamadas finais, você corre o risco de ficar sem espaço na pilha.
2. É difícil escrever funções aninhadas.

O primeiro problema pode ser facilmente resolvido no JavaScript chamando continuações de forma assíncrona. Chamando a continuação de forma assíncrona, a função retorna antes que a continuação seja chamada. Portanto, o tamanho da pilha de chamadas não 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);
}

O segundo problema geralmente é resolvido usando uma função chamada call-with-current-continuationque é frequentemente abreviada como callcc. Infelizmente, callccnão pode ser totalmente implementado em JavaScript, mas poderíamos escrever uma função de substituição para a maioria de seus 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;
}

A callccfunção pega uma função fe aplica-a ao current-continuation(abreviado como cc). A current-continuationé uma função de continuação que envolve o restante do corpo da função após a chamada para callcc.

Considere o corpo da função pythagoras:

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

O current-continuationsegundo callccé:

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

Da mesma forma, o current-continuationprimeiro callccé:

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

Como o current-continuationprimeiro callcccontém outro, callccele deve ser convertido para o estilo de passagem de continuação:

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

Então, basicamente, callcclogicamente converte todo o corpo da função de volta ao que começamos (e dá o nome a essas funções anônimas cc). A função de pitágoras usando esta implementação de callcc passa a ser:

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

Novamente, você não pode implementar callccem JavaScript, mas pode implementá-lo no estilo de passagem de continuação em JavaScript da seguinte maneira:

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

A função callccpode ser usada para implementar estruturas complexas de fluxo de controle, como blocos try-catch, coroutines, geradores, fibras , etc.

Apesar da maravilhosa descrição, acho que você está confundindo um pouco sua terminologia. Por exemplo, você está certo de que uma chamada final acontece quando a última coisa que uma função precisa executar, mas em relação às continuações, uma chamada final significa que a função não modifica a continuação com a qual é chamada, apenas que atualiza o valor passado para a continuação (se desejar). É por isso que a conversão de uma função recursiva da cauda para o CPS é tão fácil (basta adicionar a continuação como parâmetro e chamar a continuação no resultado).

Também é um pouco estranho chamar continuações como um caso especial de retorno de chamada. Eu posso ver como eles são facilmente agrupados, mas as continuações não surgiram da necessidade de distinguir de um retorno de chamada. Uma continuação na verdade representa as instruções restantes para concluir um cálculo , ou o restante do cálculo a partir deste momento. Você pode pensar em uma continuação como um buraco que precisa ser preenchido. Se eu conseguir capturar a continuação atual de um programa, posso voltar exatamente ao estado do programa ao capturar a continuação. (Isso certamente facilita a gravação dos depuradores.)

Nesse contexto, a resposta para sua pergunta é que um retorno de chamada é uma coisa genérica chamada em qualquer momento especificado por algum contrato fornecido pelo chamador [do retorno de chamada]. Um retorno de chamada pode ter quantos argumentos desejar e ser estruturado da maneira que desejar. Uma continuação , então, é necessariamente um procedimento de um argumento que resolve o valor passado para ele. Uma continuação deve ser aplicada a um único valor e o aplicativo deve ocorrer no final. Quando uma continuação termina de executar, a expressão é concluída e, dependendo da semântica do idioma, efeitos colaterais podem ou não ter sido gerados.

A resposta curta é que a diferença entre uma continuação e um retorno de chamada é que, depois que um retorno de chamada é invocado (e finalizado), a execução é retomada no ponto em que foi invocada, enquanto a invocação de uma continuação faz com que a execução seja retomada no ponto em que a continuação foi criada. Em outras palavras: uma continuação nunca retorna .

Considere a função:

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

(Eu uso a sintaxe Javascript, mesmo que o Javascript não seja compatível com continuações de primeira classe, porque foi nisso que você forneceu seus exemplos e será mais compreensível para pessoas que não estão familiarizadas com a sintaxe Lisp.)

Agora, se passarmos um retorno de chamada:

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

então veremos três alertas: "antes", "5" e "depois".

Por outro lado, se passarmos uma continuação que faça a mesma coisa que o retorno de chamada, assim:

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

então veríamos apenas dois alertas: "before" e "5". Invocar por c()dentro add()termina a execução add()e causa o callcc()retorno; o valor retornado por callcc()foi o valor passado como argumento para c(ou seja, a soma).

Nesse sentido, mesmo que invocar uma continuação pareça uma chamada de função, é, de certa forma, mais semelhante a uma instrução de retorno ou gerando uma exceção.

De fato, call / cc pode ser usado para adicionar instruções de retorno a idiomas que não as suportam. Por exemplo, se o JavaScript não tivesse uma declaração de retorno (em vez disso, como muitas linguagens do Lips, retornando apenas o valor da última expressão no corpo da função), mas tivesse call / cc, poderíamos implementar return 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.
    });
}

A chamada return(i)invoca uma continuação que encerra a execução da função anônima e faz callcc()com que retorne o índice ino qual targetfoi encontrado myArray.

(NB: existem algumas maneiras pelas quais a analogia de "retorno" é um pouco simplista. Por exemplo, se uma continuação escapar da função em que foi criada - sendo salva em um global em algum lugar, digamos -, é possível que a função que criou a continuação pode retornar várias vezes, embora tenha sido chamado apenas uma vez .)

A chamada / cc também pode ser usada para implementar o tratamento de exceções (throw e try / catch), loops e muitas outras estruturas de controle.

Para esclarecer alguns possíveis equívocos:

• A otimização da chamada de cauda não é de forma alguma necessária para oferecer suporte a continuações de primeira classe. Considere que mesmo a linguagem C possui uma forma (restrita) de continuações na forma de setjmp(), que cria uma continuação e longjmp()que invoca uma!

  • Por outro lado, se você tentar ingenuamente escrever seu programa no estilo de passagem contínua sem otimização de chamada de cauda, ​​estará fadado a eventualmente sobrecarregar a pilha.

• Não há razão específica para uma continuação precisar de apenas um argumento. É apenas que o argumento para a continuação se torna o valor de retorno da chamada / cc, e a chamada / cc é normalmente definida como tendo um único valor de retorno, portanto, naturalmente, a continuação deve levar exatamente um. Em idiomas com suporte para vários valores de retorno (como Common Lisp, Go ou mesmo Scheme), seria perfeitamente possível ter continuações que aceitassem vários valores.