Implementing yield

First, let's see what yield is by looking at some usage examples.

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

println(foo());  # prints 1
println(foo());  # prints 2
println(foo());  # prints 3
println(foo());  # prints DONE

When called, yield stops execution of the function and returns a value. Pretty much like return so far. But when you call the function again, it resumes from where the last yield left off, as you can see in the above example. It prints 1, 2, 3, DONE.

A more real-world usage:

fib = with-yield(λ(yield){
  let loop (a = 1, b = 1) {
    yield(b);
    loop(b, a + b);
  };
});

## print the first 50 fibonacci numbers
let loop (i = 0) {
  if i < 50 {
    println(fib());
    loop(i + 1);
  };
};

The fib function contains an infinite loop. There is no termination condition. But yield interrupts that loop and returns the current number. Calling the function again resumes from where it left off, so to print the first 50 numbers then we just need to call the function 50 times.

This program will also run much faster than the duble-recursive version of fib, because it keeps track of the previous two values internally and just returns the next one.

A failed implementation attempt

I wouldn't waste your time with a failed attempt unless there were valuable lessons to learn from it, so please bear with me.

To implement yield it seems we need to save the initial continuation of the function. We need that so we can exit early, like we do for return. However, before actually returning from a yield we also have to save yield's own continuation, in order to be able to return later to that point inside the function. That's what it seems, at least. We can attempt an implementation like this:

with-yield = λ(func) {
  ## with-yield returns a function of no arguments
  λ() {
    CallCC(λ(kret){        # kret is the "return" continuation
      let (yield) {

        ## define yield
        yield = λ(value) { # yield takes a value to return
          CallCC(λ(kyld){  # kyld is yield's own continuation…
            func = kyld;   # …save it for later
            kret(value);   # and return.
          });
        };

        ## finally, call the current func, passing it the yield.
        func(yield);
      };
    });
  };
};

This was my first stab at implementing yield and it all seemed to make sense. But if we try to run the first sample above for this definition of with-yield, it will be an endless loop. Try it below if you wish, but be prepared to refresh the page (I actually modified Execute in this page to use setTimeout instead of exceptions for clearing the stack, so it won't freeze your browser). If you click Run you'll briefly notice in the output that it prints 1, 2, 3, followed by an endless stream of "DONE".

The reason why it loops is subtle. But first, if you want to see something even more bizarre, edit the code above and change the last 4 println lines to this:

println(foo());
foo();

The output will be exactly the same. Again: if you ran this example you should refresh your page, otherwise it will run endlessly, draining the battery and eventually all your computer's RAM.

Problem 1: yield never changes

One problem to notice is that the continuation we save for the first yield (kyld, which becomes the next func to call, if you follow the implementation of with-yield) embeds this computation:

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

But who is yield in this continuation? It's the same as the first yield, which actually returns to the first kret continuation ever saved, which is to print the result and continue from there, resulting in a loop. Fortunately there's an easy fix for that. Clearly enough, we should create the yield closure only once, since we cannot change it in the function after the first call; in order to return to the proper exit point we maintain a new return variable:

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);       # return is set below, on each call to the function
      });                    # it's always the next return point.
    };                       #
    λ(val) {                 #
      CallCC(λ(kret){        #
        return = kret;       # <- here
        func(val || yield);
      });
    };
  };
};

Additionally, recognizing that it doesn't make sense to pass yield each time to the function, but only the first time, this new version allows passing another value on each invocation (except for the first). That will be yield's own return value.

The following code still uses the “foo” example, but it has println(foo()) only three times:

It appears to work properly. It's a clear improvement over the first version, which looped on code like print(foo()); foo(). But what happens if you add another println(foo())? LOOP!

Problem 2: WTF?

The reason for looping this time is a little more profound. It has to do with the unlimited nature of our continuations: they encode the whole future of the computation and that happens to include returning from the first call to foo(). What happens when we return from it? — we start all over:

println(foo()); ## yield 1 <----------------- HERE -------------------+
println(foo()); ## yield 2                                            |
println(foo()); ## yield 3                                            |
println(foo()); ## we reached "DONE", so the first foo() RETURNS -->--+

Let's look at this line from with-yield:

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

When func exits via an invocation of yield, it calls a continuation, so the execution doesn't reach the #... line. But by the time it finishes, for reaching the end of the function (the "DONE" line), func will have been effectively reduced to a function which returns "DONE" to the original continuation, which is to call the first print. The foo() on the second line just loops over, but all those "DONE" lines are printed by the first print line. You can verify this by running the following code:

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

The output will be: 1, bar, 2, 3, DONE, bar, DONE, bar, ....

So for a possible fix, we simply must set func to something else when it returns “naturally” (that is to say simply, “finishes”). We'll make it a do-nothing function which just returns "no more continuations".

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

It no longer loops now, but be prepared to be confused when running the code below:

We would have hoped for 1, 2, 3, DONE, but we also get "NO MORE CONTINUATIONS" three times. To figure out what happens we can interleave some prints, like this:

print("A. "); println(foo());
print("B. "); println(foo());
print("C. "); println(foo());
print("D. "); println(foo());

## and the output is:
A. 1
B. 2
C. 3
D. DONE
B. NO MORE CONTINUATIONS
C. NO MORE CONTINUATIONS
D. NO MORE CONTINUATIONS
***Result: false

Which shows that the problem remained: a natural exit from the function still goes back to the first continuation; but because the function is now a no-op, the "B." line won't trigger a loop.

Our implementation is still useful, provided that the function never finishes and only exits via yield. Here's for the Fibonacci example:

But if we want a solid implementation (so, one that doesn't return to the first call site when the function finishes), we need another concept called “delimited continuations”.

We're going to implement yield in terms of two other operators, reset and shift. They provide “delimited continuations” — these are continuations that return, like an ordinary function. reset creates a frame and shift intercepts the continuation only upto that frame, instead of “the whole future of the program” like CallCC does.

Both reset and shift take a single function argument. During the execution of the reset function, a call to shift will allow us to return a value to the place where reset was called.

First, let's see how with-yield will look:

with-yield = λ(func) {
  let (yield) {
    ## yield uses shift to return a value to the innermost
    ## reset call.  before doing that, it saves its own
    ## continuation in `func` — so calling func() again will
    ## resume from where it left off.
    yield = λ(val) {
      shift(λ(k){
        func = k;  # save the next continuation
        val;       # return the currently yielded value
      });
    };
    ## from with-yield we return a function with no arguments
    ## which uses reset to call the original function, passing
    ## to it the yield (initially) or any other value
    ## on subsequent calls
    λ(val) {
      reset( λ() func(val || yield) );
    };
  }
};

Note that each call to the function is now embedded in a reset. This ensures that we don't enclose the whole continuation of the program, but only the part up to this reset. By definition it is now impossible to loop. When the function finishes naturally, the program will just continue execution instead of going back to the place of the first call.

You can run our troublesome program below and you'll see that it finally behaves as expected. It prints nothing more nor less than it should, and it doesn't loop.

These operators are quite tricky to implement, although the code is short. Prepare for some headaches. I'll give you two solutions. I am not the author of this method and I can tell you I stared at the code for a long time before it clicked. I found it in this Scheme program by Oleg Kiselyov. I recommend these articles to understand more about this mind-blowing concept.

As primitives

In this page they are implemented as primitive functions. In primitives, the current continuation is explicit (we don't need CallCC), and this makes it somewhat easier to understand what's going on under the covers. Here's the complete implementation (left):

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

with-yield = λ(func) {
  let (yield) {
    yield = λ(val) {
      shift(λ(SK){
        func = SK;
        val;         ## return val
      });
    };
    λ(val) {
      reset( λ() func(val || yield) );
    };
  }
};

The key is that both reset and shift use _goto, which isn't a “normal” function. It has no continuation of its own. _goto receives a normal function and invokes it with a continuation (KGOTO). Any continuations caught during the execution of f (even by CallCC) can only capture “the future of the computation” upto this KGOTO, since there's nothing above it. Therefore, no matter if f exits normally, or by calling a continuation, it will eventually get to run KGOTO — which takes the next continuation from the stack and applies it on the result.

reset pushes its own continuation (KRESET) to the stack before _goto(th). If it didn't do that, the program would stop when the function exits, because nothing else happens after _goto. So when the function exits, in any way, KGOTO will resume to this KRESET.

Finally, shift calls the function with the KGOTO continuation, so if it exits normally then KGOTO will resume from the top of pstack, and it passes to it a SK function which is able to return to the point where shift itself was called (by using shift's own continuation, KSHIFT). SK is a delimited continuation — it has the ability to return a value, like a function — hence we need to push its k1 continuation to the stack as well. To illustrate the difference I included in this page a shift2 primitive which is just like the shift above but without this line: pstack.push(k1);. Try this sample:

shift gives us a continuation (k) which is the delimited continuation upto the enclosing reset. In this case the continuation is to add 1 to whatever the result of shift was:

1 + [?]

When we're calling k, we're replacing the ? above with a value. We call it twice k(k(2)). We supply 2 and continue the program, hence the inner k(2) will return 3. Therefore what follows is k(3) which supplies a 3, also in place of the question mark, yielding 4 as the final result.

shift2 is incorrect: the inner k(2) never returns.

CallCC-based

As stated, if we had no means to define primitive functions and CallCC was all we had, it'd still be possible to implement delimited continuations. The code below does pretty much the same as the primitives version, but since we don't have JS arrays it uses lists to maintain the stack (as we saw some time back, we can implement lists directly in λanguage, although here they are provided as primitives). The code is a bit longer because we need those CallCC-s in order to fetch the current continuation (which we get as an explicit argument in primitives).

The trickiest part in the code below is how it implements goto, and why it has to do it like this, but I'll leave to you the pleasure of figuring it out.

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