Re: Coroutine protected calls (the return of)

[Mike Pall <mikelu-0501@...>]

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.

Of course you already know this. But to keep this on topic and so everyone
else understands what we two are talking about, here is an example of
continuation passing in Lua:

function mythread()
  local a = 1            -- a local context variable
  ...
  yield(function()
      local b = a + 1    -- access context variable via closure
      ...
      yield(function()
        local c = a + b  -- access context variables from different scopes
        ...
      end)
    end)
end

In C you need to bundle all context variables and the continuation function
yourself or with the help of a precompiler. Whenever you need to yield
deep down in the call chain you must be able to pass back the context all
the way down to the scheduler. A stack diagram shows a sawtooth pattern
instead of the usual mountain pattern -- I guess that's where the name
"stack ripping" comes from.

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.

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

[End of explanation, back to the discussion.]

> > plus C stack copying 
> 
> It uses continuation passing AFAIK..

Last time I looked it used both, depending on the circumstances. But I'm not
following it closely enough to tell whether they have changed the model.

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

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.

> This is probably right. However note that
> the bytecode interpreter does actually schedule
> execution of bytecodes.
> 
> If you re-enter it recursively (using loadfile or whatever),
> you're screwed. But this can be fixed with a mechanical
> transform to CPS (Continuation Passing Style) ..
> pass the bytecode return address as an argument
> instead of pushing it onto the stack.

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.

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

I've toyed with the idea to extend the API to manipulate the CallInfo array.
I.e. the ability to push and pop frames. Sure opens up a bunch of interesting
possibilities. E.g. a function that does the equivalent of 'return' ;-).
Or a finalizer approach that adds/removes frames below your current call.
Good for dynamic AOP, too. And a saner example: push/keep your own function,
push a callback and then return. Weird stuff.

But I didn't get very far back then. Coordinating the CallInfo stack and
the object stack was a major problem. Adding C functions in the midst of
the stack was troublesome, too. Have to look at it again.

Bye,
     Mike