How would shallow generators compose with lambda?

[Jason Orendorff]

On Thu, May 14, 2009 at 12:25 PM, Mark S. Miller <erights at google.com> wrote:
> Given both shallow generators and lambda, I don't understand how they
> would interact.

This is a good question. I don't have the answer, but thinking aloud:

You can implement shallow generators either by doing the CPS
transformation you described or by storing (a reference to) the top
stack frame in the generator-iterator object. (The latter is how
SpiderMonkey and CPython currently do it.)

Now, suppose 'yield' and 'return' are extended in analogous ways in lambdas.

1. A lambda can escape and be called from other code.  So both
implementation approaches must be modified:

* The CPS transformation would have to be applied to almost all
functions, even functions not lexically inside the generator-function.
This is a major change.

* The stack-snapshot approach would have to store (a reference to) a
range of stack frames, which may include frames for functions not
lexically inside the generator-function. This might be a minor change.

So much for duality. :-|

2. With shallow generators, there is a check so that you can't call
.next() on a generator if it's already executing.  It just throws a
TypeError.  This enforces an invariant:

* In the continuations view, each captured continuation will be called
(resumed) at most once.

* In the stack-snapshot view, no stack frame may ever appear twice in the stack.

The implementation of the check is unaffected by lambdas--.next() can
trivially check a bit in the generator-iterator, regardless of
implementation.  But with lambdas, the invariants take on a new
meaning.  In particular, note that generators+lambdas are not fully as
powerful as delimited continuations. They are more like coroutines.
...In fact, you might be able to use them to implement coroutines.

3. When a lambda yields, the lines of code corresponding to the
topmost captured frame (or, the beginning of the delimited
continuation) and the bottommost (the tail end of the delimited
continuation) are both lexically inside the generator-function. But
there may be other functions on the stack, in between. You can't
always statically tell which ones.  This means that generator
semantics affect the integrity of code that isn't in a generator.

In ES5, when you call a function, you can expect it to return or throw
eventually.  (Unless you run out of memory, or time, and the whole
script gets terminated.)  With shallow generators, this is still true.
 A 'yield' might never return control, but function calls are ok.  But
with generators+lambdas, almost any function call *anywhere* in the
program might never return or throw.  This weakens 'finally', at
least.

-j