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

133

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?

Aadit M Shah
fonte
4
Uma parte de mim acha que essa é uma pergunta muito boa e parte de mim acha que é muito longa e provavelmente resulta apenas em uma resposta "sim / não". No entanto, devido ao esforço e à pesquisa envolvidos, vou com o meu primeiro sentimento.
Andras Zoltan
2
Qual a sua pergunta? Parece que você entende isso muito bem.
Michael Aaron Safyan
3
Sim, eu concordo - acho que provavelmente deveria ter sido um post de blog mais parecido com 'Continuações JavaScript - como eu as entendo'.
Andras Zoltan
9
Bem, há uma pergunta essencial: "Então, qual é a diferença entre uma continuação e um retorno de chamada?", Seguido por um "eu acredito ...". A resposta para essa pergunta pode ser interessante?
Confusão
3
Parece que isso pode ser postado de maneira mais apropriada em programmers.stackexchange.com.
Brian Reischl

Respostas:

164

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.

Aadit M Shah
fonte
10
Sou tão grato que palavras não podem descrever. Finalmente entendi no nível da intuição todos os conceitos relacionados à continuação de uma só vez! Eu sabia que, uma vez clicada, seria simples e eu usaria o padrão muitas vezes antes, sem saber, e era exatamente assim. Muito obrigado pela explicação maravilhosa e clara.
ATA
2
Trampolins são coisas bastante simples, mas poderosas. Por favor, verifique a publicação de Reginald Braithwaite sobre eles.
Marco Faustinelli
1
Obrigado pela resposta. Gostaria de saber se você poderia fornecer mais suporte à declaração de que o callcc não pode ser implementado em JavaScript? Possivelmente uma explicação de que JavaScript precisaria para implementá-lo?
John Henry
1
@JohnHenry - bem, na verdade, há uma implementação de chamada / cc no JavaScript feita por Matt Might ( matt.might.net/articles/by-example-continuation-passing-style - vá para o último parágrafo), mas por favor, não ' não me pergunte como ele funciona nem como usá-lo :-) #
223 Marco Faustinelli
1
O @JohnHenry JS precisaria de continuações de primeira classe (pense nelas como um mecanismo para capturar certos estados da pilha de chamadas). Mas ele possui apenas funções e fechamentos de primeira classe, portanto, o CPS é a única maneira de imitar continuações. No esquema, os conts são implícitos e parte do trabalho do callcc é "reificar" esses con implícitos, para que a função consumidora tenha acesso a eles. É por isso que callcc no Scheme espera uma função como o único argumento. A versão CPS do callcc no JS é diferente porque o cont é passado como um argumento explícito da função. Portanto, o callcc da Aadit é suficiente para muitas aplicações.
Scriptum
27

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.

dcow
fonte
3
Obrigado pelo seu esclarecimento. Você está certo. Uma continuação é na verdade uma reificação do estado de controle do programa: uma captura instantânea do estado do programa em um determinado momento. O fato de poder ser chamado como uma função normal é irrelevante. Continuações não são realmente funções. Os retornos de chamada, por outro lado, são realmente funções. Essa é a diferença real entre continuações e retornos de chamada. No entanto, o JS não suporta continuações de primeira classe. Somente funções de primeira classe. Portanto, continuações escritas no CPS em JS são simplesmente funções. Obrigdo por sua contribuição. =)
Aadit M Shah
4
@AaditMShah sim, eu errei lá. Uma continuação não precisa ser uma função (ou procedimento como eu a chamei). Por definição, é simplesmente a representação abstrata das coisas ainda por vir. No entanto, mesmo no esquema, uma continuação é invocada como um procedimento e transmitida como um. Hmm ... isso levanta a questão igualmente interessante de como uma continuação se parece e que não é uma função / procedimento.
Dcow 20/09/2013
@AaditMShah interessante o suficiente para que eu continue a discussão aqui: programmers.stackexchange.com/questions/212057/…
dcow
14

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.

cpcallen
fonte
2
Desculpas se cometi algum erro nos exemplos de JavaScript. Escrever esta resposta dobrou aproximadamente a quantidade total de JavaScript que eu escrevi.
cpcallen
Entendo corretamente que você está falando sobre continuações não limitadas nesta resposta, e a resposta aceita fala sobre continuações delimitadas?
Jozef Mikušinec
1
"invocar uma continuação faz com que a execução seja retomada no ponto em que a continuação foi criada" - acho que você está confundindo "criando" uma continuação com a captura da continuação atual .
Alexey
@ Alexey: este é o tipo de pedantismo que eu aprovo. Porém, a maioria dos idiomas não fornece nenhuma maneira de criar uma continuação (reificada) que não seja a captura da continuação atual.
cpcallen
1
@jozef: Eu certamente estou falando de continuações não limitadas. Penso que essa também era a intenção de Aadit, embora, como observa o dcow, a resposta aceita não consiga distinguir continuações de chamadas de cauda (intimamente relacionadas), e observo que uma continuação delimitada é equivalente a uma função / procedimento de qualquer maneira: community.schemewiki.org/ ? composable-continuations-tutorial
cpcallen