Hello! I present to you the third part of my translation of the manual implementation of my programming language in JavaScript - PL Tutorial .

From translator

We will create our own programming language - λ language (in the original - λanguage). In the process of creation, we will use a lot of interesting techniques, such as recursive descent, control transfer style, basic optimization techniques. Two versions of the interpreter will be created - the regular and the CPS interpreter, the trans compiler in JavaScript.

The original author is Mihai Bazon , the author of the famous UglifyJS library (a tool for minimizing and formatting JS code).

PS In the interpreter and compiler there is a bug: in expressions of the type a() && b() or a() || b() a() || b() always executes both parts. This, of course, is wrong because a() false for the && operator, or not false for the operator || , then the value of b() no longer plays any role. It is easy to fix.

CPS interpreter

Our λ language has two drawbacks:

• Recursion is limited to the JS stack, so we don’t have a normal way to do loops.
• The interpreter is slow, so the recursion is very slow.

Now we will fix the first drawback without paying attention to the fact that the interpreter will become even slower. We will rewrite the interpreter in the continuation-passing style (CPS).

What is a "continuation pass"

You do this in NodeJS all the time:

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

At each step there is a callback, which will be called when you need to continue. The continuation transfer style makes the transfer control "explicit" - you do not use either return , or throw , break or continue . There are no implicit transitions in the code. You cannot even use for or while loops with asynchronous functions. In that case, why do they need us in the programming language?

Writing a code in the transmission of the continuation is difficult and easy to make mistakes, but we will only rewrite the interpreter in such a style.

evaluate function

The evaluate function will receive three arguments: an expression (AST), a context (Environment), and a function that will be called when the result is received. Here is the code, there is an explanation for each fragment:

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

For constants, we will simply return their value. But remember, we don’t have a return - instead we just call the callback and pass the value.

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

The var node is also simple - get the variable from the context and pass it to the function:

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

For assign nodes, we need to get the value of the left expression ( right ). To do this, we call evaluate , passing a function that will get the result (for the right side of the expression). And then we just call the callback with the value of the variable, setting the variable in the current context:

  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; 

Almost the same for nodes of type binary , but here we need to first get the value of the left field, and only then the value of the right field. Then simply call the callback, passing the result of the operation:

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

The let node looks more complicated, but in fact it is simple. We have some number of variables. Their def (initial value) field may be empty, in which case we will set it to false . But if there is a value, then we need to call evaluate recursively to get it.

If you've worked with NodeJS before, you've done this many times before. Because of callbacks, we cannot use for , therefore, we must interpret these expressions in turn (present the evaluate function as asynchronous). The loop function below (immediately called) gets the context and definition number to be processed:

• If this number is equal to the number of variables ( vars.length ), then this means that we have already defined all the expressions, so we can execute the body of the expression. Pay attention, this time we do not call the callback , but pass it to the evaluate , which will then call it.
• If this number is less, then you need to calculate the current definition and pass the function that will call loop(scope, i + 1) , before you copy the context.
  
  

    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; 

The lambda node will be processed in a separate function, as before:

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

In order to interpret if , we first interpret the condition. If it is not false, then we interpret the expression then , in the other case we interpret else if it exists, or we return false if it does not. As before, for then and else we simply pass the callback as an "action to do after executing" the expression:

  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; 

The prog node is interpreted like the let node, but with the difference that we do not need to copy the context or define variables. And again, we have a loop function that takes an expression number. When it is equal to prog.length , then we have executed all the expressions and we simply return the result of the last expression (by the word "return" I mean call the callback with it). Note that we remember the last value by passing it as an argument to the loop function (at the beginning it is false for the case when the body is empty):

  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; 

For a call node, we need to interpret func and then all the arguments in order. And again, there is a loop function that works by the same principle as in let or prog , with the difference that now it builds an array as a result:

  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; 

Well, the standard ending: if we don’t know what to do, we throw an exception:

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

You may have noticed that each case above ends with the keyword return . But there is no return value - the result is always passed to the callback function.

New function make_lambda

In this interpreter, all functions will receive a “continuation” as the first argument — the function we must call to pass the result. After it - the usual function arguments. Here is the new code for the make_lambda function:

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

He is not much different. It adds new variables to the new context. Also, we must take into account that the first argument is a callback . And finally, the evaluate function is used to execute the function code in the new context, but, as before, we pass the callback .

By the way, this is the only place where I used the for loop. This is because the argument values ​​are already calculated when the call node was processed.

Native functions

In this interpreter, native functions get callback as the first argument. We must remember this when we define native functions. Here is a sample code for the new interpreter:

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

Little test

Let's try to calculate the Fibonacci numbers again:

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

But, if we try to find the 27th, we get a stack overflow. In general, the stack is now growing much faster, so it turned out that now we can count the Fibonacci number only until the 12th (at least in my browser). This is not very good, so you need to fix it somehow.

Protecting the stack

In the CPS interpreter, the stack grows much faster because the interpreter always calls functions recursively, never returning a result. Although we have a return in the interpreter, they are needed, but in the case of a very deep recursion, we never reach them.

Let's imagine what our stack looks like for a very simple program. I will show the pseudo-code and I did not add the env because it does not matter here:

 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'. 

Only after the last call, a long sequence of useless return shrink the stack. If we use so much space on the stack for a simple program, it’s hard to imagine what will happen to fib(13) .

Stack protection

In our new interpreter, the stack is simply not needed. All that needs to be done after an expression occurs in a callback , which is passed as an argument. So here we have a question: what if javascript would allow to reset the stack. Then we will be able to drop the stack, and infinitely deep recursion will work.

Let's imagine that we have a GUARD function that can do this. It receives two values: the function to call, and, the arguments that it needs to pass. It checks: if the stack is too deep, it will clear the stack and call the passed function. In another case, she does nothing.

Using the new function, we will rewrite the interpreter as shown below. I will not comment on each individual case, there is a code that is described earlier, but using the GUARD function:

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

For anonymous functions, we needed to add a name so that we could pass them to the GUARD function. I used the name CC ( current continuation ). You could use arguments.callee , but this is an obsolete API.

Also, the same change in 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; } 

The implementation of GUARD very simple. How to get out of deep challenge? Using exceptions. For this there will be a global variable that will indicate how much more we can do recursions. If it reaches zero, we throw a Continuation object, in which there will be a continuation - a function and arguments:

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

And in the end, we need a loop that will catch Continuation objects. We must call the interpreter through this loop for everything to work:

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

The Execute function accepts the function to be called and the arguments for it. It works in a loop, but notice the return if the function works without a stack overflow, we stop right away. STACKLEN reset every time we start the loop iteration. A value of 200 fits well. When we catch a Continuation object, we substitute a new function and arguments, and continue the loop. Also, due to the exception, the stack is cleared, so that we can continue.

To run the interpreter, we now use Execute :

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

Test

The fib function will now work:

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

It’s a pity, but if you try to find fib(27) , it will take about four times longer than the usual interpreter. But now we have endless recursion:

 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 

Of course, the λ language is much slower than javascript. Just imagine, every access to a variable goes through an Environment object. It makes no sense to try to optimize the interpreter - we will not get significant performance gains. To improve performance there is one solution: compile the λz in JS, and this is what we will do. At first, let's see what interesting we can do with a CPS interpreter.

Continuations

Now, when the interpreter works in the continuation transfer style, all functions, both λ functions and native JS functions, get the continuation function as the first argument to return the result (this argument is required for JavaScript functions, although it is invisible for λ language functions).

The variable callback means the continuation of the entire program. All that the program will do next. We will call this variable 'current continuation', or k in code.

Also, if we do not cause a continuation, the program will stop. We cannot do this from the λ language because make_lambda in any case causes a continuation. But we can do it from the native function. I made this function to show how it works:

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

This is a function that does nothing. She gets a sequel ( k ) but does not call it

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

Conclusion:

 foo 

If you remove the halt() call, the output will be like this: foo / bar / ***Result: false (because the last println returns false ). But with halt() it only outputs foo . * Now there is not even a result, because halt() does not cause a continuation and, therefore, the callback that we passed to evaluate - the one that displays the string ***Result , is never called. The function that caused evaluate does not notice that the program has stopped. In NodeJS this would be a shot in the foot.

Imagine we need a sleepe function that stops the program without stopping the browser (therefore, without stupid loops). We can easily implement this using the native function:

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

A slight inconvenience is that we have to use Execute , since setTimeout will call a callback, which then throws away Continuation , and no one will catch it. Here's how to use it:

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

Conclusion:

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

Note, there is a slight delay between each line. You can try to run this code in the original article .

This is something that you cannot do in regular JavaScript, except for using manual continuation transfers (and also, you cannot use a for loop for ):

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

Imagine how you can use the NodeJS API in λ language:

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

Using:

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

And it all works asynchronously. No more "callback hell".

And here is a more interesting example. I wrote the following native function:

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

The program takes two arguments a and b and calls the continuation twice, once for each argument. Let's try to call it:

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

Conclusion:

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

The conclusion is strange, if you have never worked with the transmission of sequels before, but try to understand this code yourself. Little hint: the program runs once, but returns the result twice.

Summary: CallCC

We used to play with fire when writing native functions. In λ, there is no way to interrupt the execution of the current continuation. The CallCC feature will help solve this problem. The name - the abbreviation of a function from Scheme is call-with-current-continuation (which is usually called call / cc in Scheme).

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

It retains (reifies) the current sequel to a function that can be called directly from the λ language. This function will ignore its original continuation ( discarded ) and will instead invoke a continuation that was passed to the CallCC function.

Using this function, we can implement (already directly in the λ language, not through native functions!) A large set of flow control statements, which we hadn’t even thought of before - starting from exceptions, ending with return . Let's start from the last.

return implementation

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

Conclusion:

 foo ***Result: DONE 

The foo function takes an argument that does the same as the return from JavaScript (but is called as a normal function). It skips the current continuation (which would output 'bar') and exits the function, returning the specified value ("DONE"). Of course, this only works if you call a function using CallCC to send the continuation as return . We can create a wrapper for this:

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

Conclusion:

 foo ***Result: DONE 

The advantage of this method is that we no longer need to use CallCC when we call foo . It would be nice, of course, if we did not need to accept return as an argument or use the with-return function, but in the λ language there is no possibility to add syntactic sugar directly from it, for this you need to at least modify the parser (+1 for Lisp).

Transitions

For example, we need to write a program that will look for all pairs of positive integers up to 100 such that if their multiplication gives 84. This is not a difficult task and you could immediately introduce two nested loops to solve it, but here we will go a different way. We will create two functions: guess and fail . The first will pick a number, and the second tells her to "try another number." We will use them like this:

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

Example:

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

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

. , catch . , throw , , catch , . For example:

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

Conclusion:

 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 , .

Practical example:

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

Conclusion:

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

— !