延续和回调有什么区别?

IT技术 javascript continuations callcc continuation-passing
2021-03-10 22:04:51

我一直在浏览整个网络以寻找有关延续的启迪,令人难以置信的是,最简单的解释如何让像我这样的 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);
}

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

那么延续和回调有什么区别呢?

3个回答

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

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

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

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. 编写嵌套函数很痛苦。

第一个问题可以在 JavaScript 中通过异步调用 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 块、协程、生成器、纤维等。

@JohnHenry JS 需要一流的延续(将它们视为捕获调用堆栈某些状态的机制)。但它只有 First Class 函数和闭包,因此 CPS 是模拟延续的唯一方法。在 Scheme 中,conts 是隐式的,callcc 的部分工作是“具体化”这些隐式 conts,以便消费函数可以访问它们。这就是为什么 Scheme 中的 callcc 需要一个函数作为唯一的参数。JS 中 callcc 的 CPS 版本不同,因为 cont 作为显式 func 参数传递。所以Aadit的callcc对于很多应用来说已经足够了。
2021-04-17 22:04:51
@JohnHenry - 实际上有一个由 Matt Might 在 JavaScript 中实现的 call/cc 实现(matt.might.net/articles/by-example-continuation-passing-style - 转到最后一段),但请不要不要问我它是如何工作的或如何使用它:-)
2021-04-23 22:04:51
谢谢你的回答。不知道你能否对JavaScript中不能实现callcc的说法提供更多的支持?可能解释一下 JavaScript 需要什么来实现它?
2021-05-09 22:04:51
我很感激无法用言语来形容。我终于在直觉层面一口气理解了所有与延续相关的概念!点击后我就新建了,它会很简单,我会在不知不觉中看到我多次使用该模式,就像那样。非常感谢精彩而清晰的解释。
2021-05-12 22:04:51
蹦床是相当简单但功能强大的东西。请查看Reginald Braithwaite关于它们的帖子
2021-05-13 22:04:51

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

将延续称为回调的特殊情况也有点奇怪。我可以看到它们是如何很容易地组合在一起的,但是延续并不是因为需要与回调区分开来。延续实际上表示完成计算的剩余指令,或从时间点开始计算的剩余部分您可以将延续视为需要填补的漏洞。如果我可以捕获程序的当前延续,那么我就可以准确地回到我捕获延续时程序的状态。(这确实使调试器更容易编写。)

在这种情况下,您的问题的答案是,回调是一种通用的东西,在调用者[回调]提供的某个合同指定的任何时间点都会被调用。回调可以有任意数量的参数,并且可以按照它想要的任何方式构造。因此,continuation必然是一个解析传递给它的值的单参数过程。必须将延续应用于单个值,并且应用程序必须发生在最后。当延续完成执行时,表达式就完成了,并且根据语言的语义,可能会或可能不会产生副作用。

@AaditMShah 很有趣,我在这里继续讨论:programmers.stackexchange.com/questions/212057/...
2021-04-24 22:04:51
谢谢你的澄清。你是对的。延续实际上是程序控制状态的具体化:程序在某个时间点的状态的快照。可以像普通函数一样调用它的事实无关紧要。延续实际上不是函数。另一方面,回调实际上是函数。这就是延续和回调之间的真正区别。尽管如此,JS 不支持一流的延续。只有一流的功能。因此,在 JS 中用 CPS 编写的延续只是简单的函数。谢谢您的意见。=)
2021-04-27 22:04:51
@AaditMShah 是的,我在那里说错了。延续不需要是一个函数(或我称之为过程)。根据定义,它只是对未来事物的抽象表示。然而,即使在 Scheme 中,延续也像过程一样被调用并作为一个过程传递。嗯.. 这提出了一个同样有趣的问题,即延续看起来像什么,而不是一个函数/过程。
2021-05-14 22:04:51

简短的回答是延续和回调之间的区别在于,在调用回调(并完成)后,执行会在它被调用的点恢复,而调用延续会导致执行在创建延续的点恢复。换句话说:延续永远不会返回

考虑函数:

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

(我使用 Javascript 语法,尽管 Javascript 实际上并不支持一流的延续,因为这是您给出示例的内容,对于不熟悉 Lisp 语法的人来说,它会更容易理解。)

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

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

然后我们将看到三个警报:“before”、“5”和“after”。

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

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

那么我们只会看到两个警报:“before”和“5”。调用c()insideadd()结束执行add()并导致callcc()返回;返回的值callcc()是作为参数传递给的值c(即总和)。

从这个意义上说,尽管调用延续看起来像一个函数调用,但它在某些方面更类似于 return 语句或抛出异常。

事实上, call/cc 可用于向不支持它们的语言添加 return 语句。例如,如果 JavaScript 没有 return 语句(相反,像许多 Lisp 语言一样,只返回函数体中最后一个表达式的值)但有 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()返回itarget中找到的索引的延续myArray

(注意:在某些方面,“返回”类比有点简单化。例如,如果延续从创建它的函数中逃逸 - 通过保存在全局某处,比如说 - 函数可能创建延续的对象可以多次返回,即使它只被调用一次。)

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

澄清一些可能的误解:

  • 为了支持一流的延续,绝不需要尾调用优化。考虑一下,即使是 C 语言也有一种(受限的)形式的延续,形式为setjmp(),它创建了一个延续,而longjmp(),它调用了一个!

    • 另一方面,如果您天真地尝试在没有尾调用优化的情况下以连续传递风格编写程序,您注定最终会溢出堆栈。
  • 没有什么特别的理由让一个延续只需要一个参数。只是延续的参数变成了 call/cc 的返回值,并且 call/cc 通常被定义为具有单个返回值,因此延续自然必须恰好是一个。在支持多个返回值的语言中(如 Common Lisp、Go 或实际上是 Scheme),完全有可能有接受多个值的延续。

“调用延续会导致在创建延续的点恢复执行”——我认为您将“创建”延续与捕获当前延续混淆
2021-04-29 22:04:51
我是否正确理解您在此答案中谈论的是无分隔的延续,而接受的答案谈论的是分隔的延续?
2021-04-30 22:04:51
@Alexey:这是我赞同的那种迂腐。但是大多数语言不提供任何方法来创建(具体化的)延续,而不是通过捕获当前延续。
2021-05-01 22:04:51
@jozef:我当然是在谈论无限的延续。我认为这也是 Aadit 的意图,但正如 dcow 指出的那样,接受的答案未能区分延续与(密切相关的)尾调用,并且我注意到分隔的延续无论如何都等同于功能/过程:community.schemewiki.org/ ?composable-continuations-tutorial
2021-05-05 22:04:51
如果我在 JavaScript 示例中犯了任何错误,我深表歉意。写这个答案大约使我编写的 JavaScript 总量翻了一番。
2021-05-06 22:04:51