Monday, June 28, 2010

Doing It Right

My last compile halted, with a 'This is a message from C to man: Don't place necessary code into DEBUG statements.' core dump.

Which gave me some time to think, and I finally figured out how I am going to do concurrency, or I think I might go in this direction. No locking, no nothing, just tasks. I'll need three primitives: thread f (treat this function as a thread), apply f (apply this thread-like function, send me back the result, and dispose f (you're time is done). A fourth primitive ready f, is to coordinate the results, see if the thread is done yet.

Now f can't be an ordinary function, what I want is a function which can carry its state through several computations. So, coalgebraic functions a gogo: this is approximately what the interface of the thread module will look like.

type threadable = \i \o => i -> (threadable i o, o) // Grin, this typechecks in Hi
type thread_t = \i \o => [ whatever I need here ]

def thread: threadable i o -> thread_t i o
def apply: thread_t i o -> i -> o
def ready: thread_t i o -> bool
def dispose: thread_t i o -> unit

The idea is just to inject a coalgebraic function into a heap/piece of memory, and supply it as many times an argument as you need it. If an argument is supplied, a thread runs the function to completion, returns the result, and puts itself into a new state. The ready routine can be used to check whether a thread is ready to accept new computations.

The thing is entirely impure, but who cares. Also bad is that threads, as far as I am concerned, may migrate between processors, not sure that is good or bad.

It's a pretty raw idea, but this is the direction I guess I am heading.

(I doodled a bit further with this idea, just to see what goes where, and which primitives I need.)

The thread routines allocates a thread structure outside of the heap. Both input and output must be serializable and be placeable into that structure. A new heap is created, the function f is injected into the new heap, together with main/exit/exception wrappers which also refer to the thread structure.

The apply routine places the return location, a new root in the original heap, into the thread structure. It also copies the argument into the thread structure, and starts the [main . . ] f p computation. Main copies the argument out of the thread and runs f.

When the function f finishes, the address of the result is stored, the result is copied to the thread structure and the heap is put back into the accepting state.

The return routine checks if a result is made available, if so, it copies it, wipes the thread structure, and places the thread structure in the ready state, and returns true. If no result is there, it returns false, if the thread structure is in the accepting state, it returns true.

The dispose routine stops the thread and deallocates the thread structure.

It makes the most sense to see a heap/environment as a 'thing' which just holds a function which takes input and produces output - i.e., I need to build everything such that they coalesce.

It's still too much copying, hmmm....

No comments:

Post a Comment