[Nomen-dev] Cilk as continuations

[Brian H. <bh...@sp...>]

Another postcard from the deep weeds.

Continuations are a deep idea.  Quickie introduction to continuations as I 
understand them.  When, in C, we call a function, the program passes in, 
in addition to the arguments the function itself needs, also a return 
address and stack frame address to return *to*.  OK, generally the stack 
frame on return is calculated from the current stack frame, but we can 
consider it implicitly passed in.  When the function exits, it gotos that 
return address and return stack frame (conceptually).

The returning function doesn't have to return from whence it came.  It can 
return to an entirely different point.  Actually, often times C compilers 
will do this.  In GCC, for example, if you have code like:

    void bar(void) {
        ...
    }

    void foo(...) {
        ...
        bar();
    }

Gcc will produce code like:

.globl bar
bar:
	...
	ret

.globl foo
foo:
	...
	jmp	bar

I.e. it'll thread the calls and eliminate the unnessecary call/return 
pair.

Continuations just make this obvious and visible to the programmer.  
Instead of the return address being implicit and dealt with by the 
program, they are passed in explicitly.

Cilk is just a specific use of continuations.  The act of spawning a 
thread in Cilk is just putting two continuations on the runnable stack at 
the same time.  Since a continuation includes both the location to start 
executing and the environment (stack frame) to execute within, the 
differing continuations can be moved from one thread to the next with 
little trouble.  This is what Cilk does.

Cilk gaurentees a certain relationship between cilk-threads.  When thread 
A spawns thread B, thread B starts executing immediately.  What if, 
instead, we look at it the following way: we now have two runnable 
continuations, A and B, and the scheduler picks between them.  This would 
allow the introduction of "third source" runnable continuations into the 
environment.

This is what I was hinting at earlier.  The "thread" to handle the user 
clicking on the cancel button is just onther continuation to be executed.  
So now we have three runnable continuations- compute threads A and B, and 
user interface handler thread C.  If thread schedule points happen often 
enough, this is sufficient.

So the question is, how to make sure thread schedule points happen often 
enough?  Every function call is too often, especially as all non-local 
variable accesses are implicitly function calls to accessors.  Some larger 
chunk is necessary.

Another idea I've been playing with: lock recovery codelets.  Basically, 
every lock is "breakable".  When the run time environment gets a lock, it 
passes in a pointer to a codelet to run when the lock is broken.  
Basically, add transactions to the language, with commit and rollback.  
I'd have to think about how this would work.

Brian