你好 我向您介绍了实现JavaScript编程语言的指南翻译的第三部分-PL教程 。

来自翻译

我们将创建自己的编程语言-λ语言 （原始语言 -λanguage）。 在创建过程中，我们将使用许多有趣的技术，例如递归下降，控件传递样式和基本的优化技术。 将创建两个版本的解释器-常规和CPS解释器，即JavaScript中的反编译器。

原著的作者是Mihai Bazon ，著名的UglifyJS库（一种用于最小化和格式化JS代码的工具）的作者。

PS解释器和编译器中存在一个错误：在a() && b()或a() || b()等表达式中 a() || b()这两个部分始终执行。 当然，这是错误的，因为a()对于&&运算符a() false，或者对于||为false。 ，则b()的值不起作用。 这并不难解决。

CPS口译员

我们的λ语言有两个缺点：

• 递归仅限于JS堆栈，因此我们没有正常的循环方法。
• 解释器很慢，因此递归非常慢。

现在，我们将纠正第一个缺陷，而无需注意解释器会变得更慢的事实。 我们将以“连续传递样式”（CPS）样式重写解释器。

什么是“继续转移”

您始终在NodeJS中执行此操作：

 fs.readFile("file.txt", "utf8", function CC(error, data){ //   - "" //     'return', // 'readFile'  ,  . }); 

每一步都有一个回调，当您需要继续时将被调用。 连续转移样式使控件转移“显式”-您无需使用return ， throw ， break或continue 。 代码中没有隐式跳转。 您甚至不能使用带有异步功能的for或while循环。 在这种情况下，为什么我们需要使用编程语言？

以传递延续的方式编写代码既困难又容易出错，但是我们只会以这种方式重写解释器。

evaluate功能

evaluate函数将接收三个参数：表达式（AST），上下文（Environment）和在结果出现时将被调用的函数。 这是代码，每个片段都有一个解释：

 function evaluate(exp, env, callback) { switch (exp.type) { 

对于常量，我们将只返回它们的值。 但是请记住，我们没有return -而是调用回调并传递值。

  case "num": case "str": case "bool": callback(exp.value); return; 

var节点也很简单-从上下文中获取变量并将其传递给函数：

  case "var": callback(env.get(exp.value)); return; 

对于assign节点，我们需要获取左表达式（ right ）的值。 为此，我们调用evaluate ，传入一个将获得结果的函数（用于表达式的右侧）。 然后，我们仅使用变量值调用callback ，在当前上下文中设置变量：

  case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(right){ callback(env.set(exp.left.value, right)); }); return; 

对于binary类型的节点几乎相同，但是在这里我们需要首先获取left字段的值，然后才是right字段的值。 然后，我们只需调用回调，并传递操作结果：

  case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return; 

let节点看起来更复杂，但实际上很简单。 我们有一些变量。 它们的def字段（初始值）可能为空，在这种情况下，我们将其设置为false 。 但是，如果有一个值，那么我们需要递归调用evaluate以获得它。

如果您以前使用过NodeJS，那么您已经做过很多次了。 由于存在回调，因此无法将for ，因此，必须一次解释一个表达式（将evaluate函数想象为异步的）。 下面的loop函数（立即调用）获取上下文和需要处理的定义编号：

• 如果该数目等于变量的数目（ vars.length ），则意味着我们已经定义了所有表达式，因此我们可以执行表达式的主体。 请注意，这一次我们不调用callback ，而是将其传递给evaluate ，然后将其调用。
• 如果此数字较小，则需要在复制上下文之前计算当前定义并传递一个将调用loop(scope, i + 1)的函数。
  

    case "let": (function loop(env, i){ if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function(value){ var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; 

lambda节点将像以前一样在单独的函数中进行处理：

  case "lambda": callback(make_lambda(env, exp)); return; 

为了解释if ，我们首先解释条件。 如果它不是false，那么我们解释then表达式，在另一种情况下，如果存在则解释else ，否则返回false 。 和以前一样，在else我们只需将callback作为表达式的“执行后要执行的操作”即可：

  case "if": evaluate(exp.cond, env, function(cond){ if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; 

prog节点的解释与let节点的解释类似，但是区别在于我们不需要复制上下文或定义变量。 同样，我们有一个loop函数，需要一个表达式编号。 当它等于prog.length ，我们就完成了所有表达式，然后简单地返回最后一个表达式的结果（用单词“ return”表示我用它来调用callback ）。 请注意，我们通过将最后一个值作为参数传递给loop函数来记住最后一个值（开始时，对于主体为空的情况，它为false ）：

  case "prog": (function loop(last, i){ if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){ loop(val, i + 1); }); else { callback(last); } })(false, 0); return; 

对于类型call的节点call我们需要解释func ，然后所有参数都按顺序排列。 同样，还有一个loop函数，其作用原理与let或prog相同，不同之处在于它现在作为结果构建一个数组：

  case "call": evaluate(exp.func, env, function(func){ (function loop(args, i){ if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){ args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; 

好吧，标准结局：如果我们不知道该怎么办，请抛出异常：

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

您可能会注意到上面的每种case以return关键字结尾。 但是没有返回值-结果总是传递给callback函数。

新的make_lambda函数

在此解释器中，所有函数都将收到“ continuation”作为第一个参数-我们必须调用该函数才能传递结果。 其后是通常的函数参数。 这是make_lambda函数的新代码：

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

他没什么不同。 它将新变量添加到新上下文中。 另外，我们必须考虑第一个参数是callback 。 最后， evaluate函数用于在新的上下文中执行函数代码，但是像以前一样，我们传递了一个callback 。

顺便说一句，这是我使用for循环的唯一地方。 这是因为在处理call节点时已经计算出了参数值。

本机功能

在此解释器中，本机函数接收callback作为第一个参数。 定义本机函数时，必须记住这一点。 这是新解释器的示例代码：

 var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment(); // define the "print" primitive function globalEnv.def("print", function(callback, txt){ console.log(txt); callback(false); // call the continuation with some return value // if we don't call it, the program would stop // abruptly after a print! }); // run the evaluator evaluate(ast, globalEnv, function(result){ // the result of the entire program is now in "result" }); 

小考

让我们尝试再次计算斐波那契数：

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) ); 

但是，如果我们尝试找到第27个数字，则会出现堆栈溢出。 总的来说，堆栈的增长速度现在要快得多，因此事实证明，现在我们只能将斐波那契数计算为第12位（至少在我的浏览器中）。 这不是很好，所以您需要以某种方式修复它。

我们保护堆栈

在CPS解释器中，堆栈的增长速度更快，因为解释器始终以递归方式调用函数，而不会返回结果。 尽管我们已经在解释器中return了，但是我们需要它们，但是在非常深层次的递归情况下，我们将永远无法到达它们。

让我们想象一下我们的堆栈如何寻找一个非常简单的程序。 我将显示伪代码，并且没有添加env因为它在这里没有任何作用：

 print(1 + 2 * 3); ## : evaluate( print(1 + 2 * 3), K0 ) evaluate( print, K1 ) K1(print) #  'var',      evaluate( 1 + 2 * 3, K2 ) evaluate( 2 * 3, K3 ) evaluate( 2, K4 ) K4(2) # 2  ,      evaluate( 3, K5 ) #    3,      K5(3) K3(6) #  2*3 evaluate( 1, K6 ) #  ,  K6(1) K2(7) #  1+2*3 print(K0, 7) # ,     'print' K0(false) #  . 'print'  'false'. 

只有在最后一次调用之后，长时间的无用return序列才会减少堆栈。 如果我们为一个简单的程序使用了如此多的堆栈空间，那么很难想象fib(13)会发生什么。

堆栈保护

在我们的新解释器中，根本不需要堆栈。 在callback发生某些表达式之后，需要做的所有事情都作为参数传递。 因此，这里有一个问题：如果JavaScript能够“转储”堆栈，该怎么办？ 然后，我们可以删除堆栈，并且无限深的递归将起作用。

假设我们有一个可以执行此操作的GUARD函数。 它有两个值：要调用的函数和需要传递的参数。 它检查：如果堆栈太深，它将清除堆栈并调用传递的函数。 在另一种情况下，她什么也不做。

使用新功能，我们重写了解释器，如下所示。 我不会对每种情况进行评论，这里有前面描述的代码，但是使用了GUARD函数：

 function evaluate(exp, env, callback) { GUARD(evaluate, arguments); switch (exp.type) { case "num": case "str": case "bool": callback(exp.value); return; case "var": callback(env.get(exp.value)); return; case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(env.set(exp.left.value, right)); }); return; case "binary": evaluate(exp.left, env, function CC(left){ GUARD(CC, arguments); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(apply_op(exp.operator, left, right)); }); }); return; case "let": (function loop(env, i){ GUARD(loop, arguments); if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function CC(value){ GUARD(CC, arguments); var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; case "lambda": callback(make_lambda(env, exp)); return; case "if": evaluate(exp.cond, env, function CC(cond){ GUARD(CC, arguments); if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; case "prog": (function loop(last, i){ GUARD(loop, arguments); if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){ GUARD(CC, arguments); loop(val, i + 1); }); else { callback(last); } })(false, 0); return; case "call": evaluate(exp.func, env, function CC(func){ GUARD(CC, arguments); (function loop(args, i){ GUARD(loop, arguments); if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){ GUARD(CC, arguments); args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; default: throw new Error("I don't know how to evaluate " + exp.type); } } 

对于匿名函数，我们需要添加一个名称，以便可以将其传递给GUARD函数。 我使用的名称是CC （ current continuation ）。 您可以使用arguments.callee ，但这是一个过时的API。

另外， make_lambda变化相同：

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments); // <--  var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

GUARD的实现非常简单。 如何摆脱困境？ 使用异常。 为此，将有一个全局变量，该变量将指示我们可以执行多少递归。 如果达到零，我们将抛出Continuation对象，其中将存在一个continuation-函数和参数：

 var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; } 

最后，我们需要一个将捕获Continuation对象的循环。 我们必须通过此循环调用解释器，以便一切正常：

 function Execute(f, args) { while (true) try { STACKLEN = 200; return f.apply(null, args); } catch(ex) { if (ex instanceof Continuation) f = ex.f, args = ex.args; else throw ex; } } 

Execute函数接受要调用的函数及其参数。 它循环运行，但是如果函数正常工作而没有堆栈溢出，请注意return ，我们会立即停止。 每当我们开始循环迭代时， STACKLEN重置STACKLEN 。 值200合适。 当我们捕获Continuation对象时，我们将替换一个新的函数和参数，然后继续循环。 另外，由于异常，堆栈会被清除，以便我们可以继续。

要启动解释器，我们现在使用Execute ：

 Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]); 

测验

fib函数现在将起作用：

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) ); # 6765, ~300ms 

遗憾的是，但如果您尝试找到fib(27) ，它的时间大约是普通口译员的四倍。 但是现在我们有了无限递归：

 sum = λ(n, ret) if n == 0 then ret else sum(n - 1, ret + n); # compute 1 + 2 + ... + 50000 time( λ() println(sum(50000, 0)) ); # 1250025000, ~700ms 

当然，λ语言比JavaScript慢得多。 试想一下，对变量的每次访问都通过一个Environment对象。 尝试优化解释器没有任何意义-我们不会获得显着的性能提升。 为了提高性能，有一种解决方案：在JS中编译λ语言，这就是我们要做的。 首先，让我们看看使用CPS解释器可以做些有趣的事情。

延续性

现在，解释器以传输连续性的方式工作，并且所有函数（λ语言函数和本机JS函数）都将继续函数作为返回结果的第一个参数（此参数对于JavaScript函数是必需的，尽管对于λ语言函数不可见）。

变量callback意味着整个程序的继续。 该程序接下来将执行的所有操作。 我们将这个变量称为“当前延续”，即代码中的k 。

另外，如果我们不继续执行，则程序将停止。 我们无法使用λ语言来执行此操作，因为make_lambda调用延续。 但是我们可以通过本机函数来做到这一点。 我做了一个函数来展示它是如何工作的：

 globalEnv.def("halt", function(k){}); 

这是什么都不做的功能。 她收到延续（ k ），但没有调用它：

 println("foo"); halt(); println("bar"); 

结论：

 foo 

如果删除halt()调用，则输出将是： foo / bar / ***Result: false （因为最后一个println返回false ）。 但是使用halt()这只会输出foo 。 *现在甚至没有结果，因为halt()不会引起延续，因此，我们永远不会调用传递给我们evaluate的回调-显示字符串***Result的回调。 调用evaluate的函数不会注意到程序已停止。 在NodeJS中，这将是一针见血。

想象一下，我们需要一个sleepe函数，该函数可以在不停止浏览器的情况下停止程序（因此没有愚蠢的循环）。 我们可以使用本机函数轻松实现此目的：

 globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]); //   ,  'false' }, milliseconds); }); 

有点不便之处是，我们必须使用Execute ，因为setTimeout将导致回调，然后引发Continuation ，并且没有人可以捕获它。 使用方法如下：

 let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done"); 

结论：

 0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false 

请注意，每行之间会有一点延迟。 您可以尝试在原始文章中运行此代码。

这已经是您在普通JavaScript中无法做到的事情，除了使用手动传输连续性之外（而且，您不能for使用for循环）：

 (function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done"); //    } })(0); 

想象一下如何以λ语言使用NodeJS API：

 globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){ // error handling is a bit more complex, ignoring for now Execute(k, [ data ]); // hope it's clear why we need the Execute }); }); globalEnv.def("writeFile", function(k, filename, data){ fs.writeFile(filename, data, function(err){ Execute(k, [ false ]); }); }); 

用法：

 copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt"); 

所有这一切都是异步的。 没有更多的回调地狱。

这是一个更有趣的示例。 我编写了以下本机函数：

 globalEnv.def("twice", function(k, a, b){ k(a); k(b); }); 

该程序采用两个参数a和b并调用连续两次，每个参数一次。 让我们尝试调用它：

 println(2 + twice(3, 4)); println("Done"); 

结论：

 5 Done ***Result: false 6 Done ***Result: false 

如果您以前从未使用过延续，但尝试自己理解此代码，则得出的结论很奇怪。 一个小提示：程序启动一次，但返回结果两次。

通用化： CallCC

编写本机函数时，我们经常玩火。 λ语言中没有办法中断当前延续的执行。 CallCC将帮助解决此问题。 该名称是Scheme的功能的缩写call-with-current-continuation调用（在Scheme中通常称为call / cc）。

 globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); }); 

它将当前延续化为可以直接从λ语言调用的函数。 此函数将忽略其原始discarded延续，而是调用传递给CallCC函数的延续。

使用此函数，我们可以实现（已经直接使用λ语言，而不是通过本机函数！）我们甚至从未考虑过的大量执行流控制操作符-从异常开始到以return结束。 让我们从最后开始。

实施return

 foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo); 

结论：

 foo ***Result: DONE 

foo函数接收的参数与从JavaScript return的参数相同（但被称为常规函数）。 它跳过当前的延续（将输出“ bar”）并退出函数，返回给定值（“ DONE”）。 当然，这仅在您使用CallCC调用函数以将延续作为return传递时CallCC 。 我们可以为此创建一个包装器：

 with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo(); 

结论：

 foo ***Result: DONE 

这种方法的优点是，当我们调用foo时，我们不再需要使用CallCC 。 当然，如果我们不需要接受return作为参数或使用with-return函数，那会很好，但是在该语言中，无法直接从中添加语法糖，为此，我们至少需要修改解析器（对于Lisp而言为+1）。

转场

例如，我们需要编写一个程序来查找所有最大为100的正整数对，如果它们的乘法结果为84。这不是一件容易的事，您可以立即想象两个嵌套循环来解决它，但是这里我们采用了另一种方法。 我们将创建两个函数： guess和fail 。 第一个会选择号码，第二个会告诉她“尝试另一个号码”。 我们将像这样使用它们：

 a = guess(1); #  -  >= 1 b = guess(a); #  -  >= a if a * b == 84 { #    : print(a); print(" x "); println(b); }; fail(); #    `guess`     

:

 fail = λ() false; guess = λ(current) { CallCC(λ(k){ let (prevFail = fail) { fail = λ(){ current = current + 1; if current > 100 { fail = prevFail; fail(); } else { k(current); }; }; k(current); }; }); }; a = guess(1); b = guess(a); if a * b == 84 { print(a); print(" x "); println(b); }; fail(); 

, , a , 84 , b , 84 / a . guess : start end — . , .

try catch Common Lisp

— catch throw . :

 f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); #  EXIT 

• catch(TAG, function) , , TAG ', function .
• throw(TAG, value) , , TAG ' , value .

:

 ##  , 'throw'   . ##       `error`, ##     JavaScript.    . throw = λ(){ println("ERROR: No more catch handlers!"); halt(); }; catch = λ(tag, func){ CallCC(λ(k){ let (rethrow = throw, ret) { ##   ,     . throw = λ(t, val) { throw = rethrow; #   ,   . if t == tag then k(val) else throw(t, val); }; ##      . ret = func(); ##       (  'throw') ##    .   . throw = rethrow; # XXX ##  . ret; }; }); }; 

一个例子：

 # ... f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); 

catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .

. , catch . , throw , , catch , . 例如：

 exit = false; #  . x = 0; # :   ,   'exit()'  CallCC( λ(k) exit = k ); ## 'exit()'   ... if x == 0 then catch("foo", λ(){ println("in catch"); x = 1; #  exit(); }); println("After catch"); throw("foo", "FOO"); 

结论：

 After catch After catch ERROR: No more catch handlers! 

'After catch' , 'ERROR: No more catch handlers!'. - , 'After catch' , . , '' , catch . , 'XXX' catch , throw , catch .

( , .)

CallCC (, , CallCC ). , — CallCC .

Yield

, , yield :

 foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); # 1 println(foo()); # 2 println(foo()); # 3 println(foo()); # DONE 

yield , . , return . , , yield , .

:

 fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

fib . . yield . , , 50 , 50 .

, , , , .

, .

yield , , . , , return . , , yield , yield , . , . :

 with-yield = λ(func) { ## with-yield     λ() { CallCC(λ(kret){ # kret     let (yield) { ##  yield yield = λ(value) { # yield  ,    CallCC(λ(kyld){ # kyld    yield... func = kyld; # ...     kret(value); #  . }); }; ## , ,  ,   yield. func(yield); }; }); }; }; 

yield , . , , , "DONE".

, . , - , , 4 :

 println(foo()); foo(); 

.

№1: yield

, , , , yield ( kyld , , ) :

  yield(2); yield(3); "DONE"; 

yield ? yield , , yield . , . , yield return , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); # 'return'  ,     }); #        . }; # λ(val) { # CallCC(λ(kret){ # return = kret; # <-  func(val || yield); }); }; }; }; 

, , yield , yield ( ). yield .

, , println(foo()) :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; func(val || yield); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); 

, . , print(foo()); foo() . , println(foo()) ? ...

№2: WTF?

. : , foo() . , ? — .

 println(foo()); ## yield 1 <-----------------  ---------------------------+ println(foo()); ## yield 2 | println(foo()); ## yield 3 | println(foo()); ##   "DONE",   foo()  -->--+ 

with-yield :

  func(val || yield); #... 

yield , , #... . , , ( "DONE" ), , "DONE" , . foo() , "DONE" . :

 println(foo()); println("bar"); println(foo()); println(foo()); foo(); 

: 1, bar, 2, 3, DONE, bar, DONE, bar, ... .

func - , . , "no more continuations" :

  val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); 

:

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); println(foo()); 

, :

 1 2 3 DONE NO MORE CONTINUATIONS NO MORE CONTINUATIONS NO MORE CONTINUATIONS ***Result: false 

1, 2, 3, DONE , "NO MORE CONTINUATIONS" . , :

 print("A. "); println(foo()); print("B. "); println(foo()); print("C. "); println(foo()); print("D. "); println(foo()); ##   : A. 1 B. 2 C. 3 D. DONE B. NO MORE CONTINUATIONS C. NO MORE CONTINUATIONS D. NO MORE CONTINUATIONS ***Result: false 

, : , , , , "B." .

, yield , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 ***Result: false 

, (, ), " ".

: reset shift

yield : reset shift . " " — , . reset , shift , CallCC .

, reset shift — . reset , shift , reset .

, with-yield :

 with-yield = λ(func) { let (yield) { ## 'yield'  'shift'     ##  'reset'.  ,   ,    ##   'func' — ,   `func()` ##    ,    . yield = λ(val) { shift(λ(k){ func = k; #    val; #    }); }; ##  `with-yield`      ##   'reset',    ,  ##   'yield' ( )    ##    λ(val) { reset( λ() func(val || yield) ); }; } }; 

, reset . , , , reset . , . , .

:

 with-yield = λ(func) { let (yield) { yield = λ(val) { shift(λ(k){ func = k; val; }); }; λ(val) { reset( λ() func(val || yield) ); }; } }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); #  1 println(foo()); #  2 println(foo()); #  3 println(foo()); #  DONE 

reset shift

, . . . , , , . Scheme ( — Oleg Kiselyov ). .

, ( CallCC ) . :

 var pstack = []; function _goto(f) { f(function KGOTO(r){ var h = pstack.pop(); h(r); }); } globalEnv.def("reset", function(KRESET, th){ pstack.push(KRESET); _goto(th); }); globalEnv.def("shift", function(KSHIFT, f){ _goto(function(KGOTO){ f(KGOTO, function SK(k1, v){ pstack.push(k1); KSHIFT(v); }); }); }); 

, reset , shift _goto , — . . _goto ( KGOTO ). , f ( CallCC ) - KGOTO , . , f , , KGOTO , , .

reset ( KRESET ) _goto(th) . , , , _goto . , , KGOTO KRESET .

, shift KGOTO , KGOTO pstack , SK , , shift ( shift — KSHIFT ). SK — — ( k1 ) . , shift2 , , pstack.push(k1); ：

 println(reset(λ(){ 1 + shift( λ(k) k(k(2)) ); })); println(reset(λ(){ 1 + shift2( λ(k) k(k(2)) ); })); 

结论：

 4 3 ***Result: false 

shift ( k ), reset . — 1 shift :

 1 + [?] 

k , ? . — k(k(2)) . 2 , k(2) 3. , k(3) 3 , 4.

shift2 : k(2) .

CallCC

, , CallCC , . , JS, , , . , CallCC , .

— goto , ( ):

 pstack = NIL; goto = false; reset = λ(th) { CallCC(λ(k){ pstack = cons(k, pstack); goto(th); }); }; shift = λ(f) { CallCC(λ(k){ goto(λ(){ f(λ(v){ CallCC(λ(k1){ pstack = cons(k1, pstack); k(v); }); }); }); }); }; let (v = CallCC( λ(k){ goto = k; k(false) } )) { if v then let (r = v(), h = car(pstack)) { pstack = cdr(pstack); h(r); } }; 

— !