Re: Coroutine protected calls (the return of)

[skaller <skaller@...>]

On Sun, 2005-01-23 at 08:45, Mike Pall wrote:
> Hi,
> 
> John Skaller wrote:
> > > Stackless Python does stack ripping for many core functions 
> > 
> > What's stack ripping?
> 
> The canonical reference for this term is:
> 
> http://www.usenix.org/events/usenix02/full_papers/adyahowell/adyahowell_html/
> 
> This is "C lingo" for continuation passing. Except that you have to do it
> manually or with the help of a precompiler, due to the lack of closures.

I'd not seen that paper, thanks! Felix uses resumptions,
the technique seems simpler: ignoring reads and complications:


// driver:
while (p) p=p->resume();

//user code
struct cont {
  int pc; 
  cont *resume() {
    switch (pc) {
      ...
      case 99: ....
        pc = 100;     // yield
        return this;
      case 100: ...
    }
  }
}

This example shows a simple yield: set the 'return' address,
and return 'this'. To call a subroutine:

	pc = 100;
	return new subroutine(this, ..);
      case 100:


and to return from a subroutine:

     return caller;

where caller was set to the 'this' of the caller. 

It's a bit more complex -- the this pointer of the lexical
parents are passed too, to provide context for 'upvalues'.
This is done in the constructor .. afterwards the created
object is a closure.

[With gcc, a computed goto is used instead of a switch.]

The 'this' pointer + the pc variable togther
act as the 'program counter' and 'stack pointer',
and also represent a function which when resumed()
will execute the rest of the program, and hence
are a continuation.

The stack frames are allocated on the heap, and collected
by a garbage collector. The collector knows nothing
of the C stack.

> Suffice to say it gets ugly when the call chain is more complicated.
> But it's the only truly portable way to do it. In a controlled environment
> and when you have only a handful of functions, it's quite doable.

By hand -- it's quite doable in general with a 'precompiler'
.. such as Felix :)

> The Lua VM already employs the technique when you look closely at lvm.c
> and ldo.c. It just does not go far enough (yet).

Yes, that's what I thought. This was also the case with Python.
Christian Tismer (if I recall) observed Python *already* created 
it's own stack frames, so to make the continuation based system 
work only required a couple of lines to be changed in the 
interpreter, so code yielded the next place to execute instead 
of executing it (or something like that).

I expect the same from Lua -- it already has its own stack,
it's already re-entrant (no static variables -- yea!)
and there is no reason the bytecode interpreter would
call itself recursively gratuitously. 

I doubt fixing up the bytecode interpreter would be a problem
in Lua. The problem is likely to be that the C API would change.

So  the issue probably reduces to whether it is possible
to do it and still provide a 'legacy' API so existing
code continues to work.

> > Neither copying nor switching works properly in C++
> > due to exception handling stuff :(
> 
> Depends. You can make it work if you are very careful to preserve the
> call frame chain. But this gets awfully tricky on some CPUs (e.g. Itanium).
> You are lost if the frame unwind code depends on compiler generated stack
> offset tables.

It isn't just the CPU, it depends on the C++ compiler as well,
and even worse, possibly compiler switches.

> That's another reason why I do not think that C stack switching or copying
> is a realistic option for the (otherwise highly portable) Lua core.

Agree. With one caveat: pcall already isn't portable because
it uses setjump/longjump which works fine in ISO C, and 
works fine in C++ provided there are no exceptions..
but user code can throw exceptions.

> See src/lvm.c, case OP_CALL and case OP_RETURN. The return address is
> saved in the CallInfo stack, the new instruction pointer is set up and
> the VM just continues with the main loop. The C stack level is unchanged.

Except for pcall and loadfile?

> > This will change the C API though .. hmmm.. sorry just
> > rambling .. :)

> But I didn't get very far back then. Coordinating the CallInfo stack and
> the object stack was a major problem. 

That should be possible though. The separate value
stack is a nice feature that allows coroutines to
communicate bidirectionally.

Felix integrated stack frames don't allow that
to be done easily .. :(

> Adding C functions in the midst of
> the stack was troublesome, too. Have to look at it again.

Plain C functions should be fine, the problem is mainly
callbacks IMHO. If Lua code calls a C function that calls a
C function that calls Lua, the Lua callback code is
separated from the Lua caller code by stuff C put
on the machine stack.

Felix can't handle this. In Felix this is more serious
than you'd otherwise expect, since Felix *functions*
use the machine stack -- they're more or less ordinary
C functions. In Felix functions can't yield, only
*procedures* can yield.

Yet the system is workable I think.

However Lua may be able to do it better anyhow,
using the idea that a function is really a tail yielding
coroutine, it can probably use a unified approach 
for Lua code.

This callback problem can be solved 'somthing like'
instead of re-entering the Lua code, just schedule it.
If the code really *must* be done before the callback
returns, the function calling the callback has to be
put into another pthread (and then it blocks in the callback, 
and waits for the Lua thread to run the function before returning).

BTW: this sounds messy. But it may be really 
easy to do! What's required is a virtual interpreter,
one that executes by telling another interpreter to
run some bytecodes, then blocks until it has been
done. The real interpreter will have to look
into an 'event queue' for stuff to run at appropriate
times. This may require a small change to the Lua
core -- but probably only a hook in the right place
(not sure though).

There may be more solutions than that, the simplest
one is to say that you can't yield() across
a C callback.

Again sorry for rambling .. 

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net