延续和回调之间有什么区别？

Question

我一直在浏览整个网络,寻找关于延续的启示,并且令人难以置信的是,最简单的解释如何能够如此完全混淆像我这样的JavaScript程序员.当大多数文章使用Scheme中的代码解释延续或使用monad时尤其如此.

现在我终于认为我已经理解了延续的本质,我想知道我所知道的是否真的是事实.如果我认为真实的事实并非如此,那么它就是无知而不是启蒙.

所以,这就是我所知道的:

在几乎所有语言中,函数显式地将值(和控制)返回给它们的调用者.例如:

var sum = add(2, 3);

console.log(sum);

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

现在,在具有第一类函数的语言中,我们可以将控制和返回值传递给回调,而不是显式返回给调用者:

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

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

因此,不是从函数返回值,而是继续使用另一个函数.因此,这个函数被称为第一个的延续.

那么延续和回调之间的区别是什么？

Answer 1

我相信延续是回调的一个特例.函数可以任意次数回调任意数量的函数.例如:

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

但是,如果一个函数回调另一个函数作为它做的最后一个函数,那么第二个函数被称为第一个函数的延续.例如:

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

如果一个函数调用另一个函数作为它做的最后一件事,那么它被称为尾调用.一些语言如Scheme执行尾调用优化.这意味着尾调用不会产生函数调用的全部开销.相反,它实现为一个简单的goto(调用函数的堆栈帧被尾调用的堆栈帧替换).

奖励:继续传递风格.考虑以下程序:

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

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

现在,如果每个操作(包括加法,乘法等)都以函数的形式编写,那么我们将:

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

此外,如果我们不被允许返回任何值,那么我们将不得不使用如下的continuation:

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

这种编程风格不允许返回值(因此你必须求助于传递延续)称为延续传递风格.

然而,继续传递风格有两个问题:

1. 传递延续会增加调用堆栈的大小.除非你使用像Scheme之类的语言来消除尾部调用,否则你将面临堆栈空间不足的风险.
2. 编写嵌套函数很痛苦.

通过异步调用continuation,可以在JavaScript中轻松解决第一个问题.通过异步调用continuation,函数在调用continuation之前返回.因此调用堆栈大小不会增加:

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

第二个问题通常使用一个call-with-current-continuation通常缩写为的函数来解决callcc.遗憾的是callcc,无法在JavaScript中完全实现,但我们可以为其大多数用例编写替换函数:

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

该callcc函数接受一个函数f并将其应用于current-continuation(缩写为cc).这current-continuation是一个延续函数,它在调用之后将函数体的其余部分包装起来callcc.

考虑函数的主体pythagoras:

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

所述current-continuation第二的callcc是:

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

同样current-continuation,第一个callcc是:

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

由于current-continuation第一个callcc包含另一个,callcc它必须转换为延续传递样式:

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

所以基本上callcc逻辑上将整个函数体转换回我们开始的(并给这些匿名函数命名cc).使用callcc的这种实现的毕达哥拉斯函数变为:

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

您再次无法callcc在JavaScript中实现,但您可以在JavaScript中实现延续传递样式,如下所示:

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

该函数callcc可用于实现复杂的控制流结构,如try-catch块,协同程序,生成器,光纤等.

Answer 2

尽管写得很精彩,但我认为你的术语有点令人困惑.例如,当调用是函数需要执行的最后一件事时,发生尾调用是正确的,但是对于continuation,尾调用意味着函数不会修改它被调用的延续,只是它更新传递给continuation的值(如果需要).这就是为什么将尾递归函数转换为CPS是如此简单(只需将continuation添加为参数并在结果上调用continuation).

将continuation称为回调的特殊情况也有点奇怪.我可以看到它们如何轻松地组合在一起,但延续并不是因为需要区分回调.延续实际上表示剩余的指令以完成计算,或者从该时间点开始计算的剩余部分.你可以把延续想象成一个需要填补的漏洞.如果我能捕捉到一个程序的当前延续,那么我可以回到我捕获延续时程序的确切方式.(这确实使调试器更容易编写.)

在这种情况下,您的问题的答案是回调是一种通用的东西,它可以在[回调]调用者提供的某个契约指定的任何时间点调用.回调可以包含任意数量的参数,并以任何方式构建.因此,延续必然是一个解析传递给它的值的一个参数过程.必须将延续应用于单个值,并且应用程序必须在最后发生.当继续完成执行时,表达式已完成,并且,根据语言的语义,可能已生成或可能未生成副作用.

Answer 3

简短的回答是延续和回调之间的区别在于,在调用回调(并且已经完成)之后,执行将在调用它时恢复,而调用继续会导致执行在创建延续时恢复.换句话说:延续永远不会回来.

考虑功能:

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

(我使用Javascript语法,即使Javascript实际上不支持一流的延续,因为这是你给出的例子,对于不熟悉Lisp语法的人来说,它会更容易理解.)

现在,如果我们传递一个回调:

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

然后我们会看到三个警告:"之前","5"和"之后".

另一方面,如果我们传递一个与回调相同的延续,就像这样:

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

那么我们只会看到两个警告:"之前"和"5".调用c()内部add()结束执行add()并导致callcc()返回; 返回的值callcc()是作为参数传递的值c(即总和).

从这个意义上讲,即使调用一个continuation看起来像一个函数调用,它在某些方面更类似于return语句或抛出异常.

实际上,call/cc可用于将return语句添加到不支持它们的语言中.例如,如果JavaScript没有return语句(相反,就像许多Lips语言一样,只返回函数体中最后一个表达式的值)但确实有call/cc,我们可以像这样实现return:

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

呼叫return(i)调用终止匿名函数的执行,并导致持续callcc()到返回指数i在其target在被发现myArray.

(注意:在某些方面,"返回"类比有点简单.例如,如果延续从它创建的函数中逃脱 - 通过保存在某个地方的某个地方,比如说 - 可能是函数创建延续的可以返回多次,即使它只被调用一次.)

Call/cc可以类似地用于实现异常处理(throw和try/catch),循环和许多其他控制结构.

澄清一些可能的误解:

• 无论如何都不需要尾调用优化来支持一流的延续.考虑到即使是C语言也有一种(限制)形式的延续形式setjmp(),它会创建一个延续,并且longjmp()会调用一个!

  • 另一方面,如果你天真地尝试在没有尾调用优化的情况下以延续传递方式编写程序,那么注定最终会溢出堆栈.

• 持续性只需要一个参数就没有特别的理由.只是连续的参数成为call/cc的返回值,而call/cc通常被定义为具有单个返回值,所以自然地,continuation必须只取一个.在支持多个返回值的语言中(如Common Lisp,Go或者甚至是Scheme),完全有可能具有接受多个值的continuation.