Re: [Caml-list] JIT & HLVM, LLVM

["Mikkel Fahnøe Jørgensen" <mikkel@dvide.com>]

First, sorry for the rough post (it was late), I see some typos and
slightly more confusing mistakes, but hopefully not too bad, or please
ask.

>> A function can push other functions to the global queue. This in
>> effect creates a continuation, and the concept is similar to
>> continuation passing style or LWT threads, *but requires no
>> continuation arguments to drag around*.

> Could you elaborate?

Yes,
I'm probably not the best to explain continuation passing style, but
I'll give it a shot.

In OCaml you do not have continuations, but you do have partial evaluation.

This means the function

  let sum a b = a + b

can be called partially like

  let sum_creator a = sum a

This won't execute the sum code, but will have it pending until we get
the last argument b. In this sense the sum_creator function is a
sleeping thread waiting to execute.

We can combine several functions in this way to get a complex
calculation which won't evaluate until the continuation argument b is
supplied.

For example we can create a complex boolean expression combining
several primitive and / or functions that take a variable x as
argument. The entire expression is suspended until x is given, and in
principle the OR subexpressions could execute in parallel. We can also
build parse expressions where it is not a variable x, but the rest of
the input string that is missing.

Instead of evaluating a sum or boolean expression, the function could
do something else, like filling a buffer from a socket. The k argument
does not need to be used at all, we just use it to avoid computation
before we need it.

We can use this to create threads by having an extra dummy argument
that we will call k. We don't really need k we just need the
expression to not evaluate before we say so. This is the continuation
being dragged (passed) around.

(In monadic stream parsers, the k continuation is replaced by io state
which is dragged around, and contrary to k it provides useful
information. These parsers allow parsing to sleep when the input
stream dries up temporarily, and the parsers can explore several parse
paths concurrently (useful for error reporting), so there is an analog
to concurrent threads consuming i/o).

A function can also return a recursive call to itself supplying new
state such as bytes left to read, or a partial call to another
function, in both cases supplying new state information, but failing
to supply to the k argument such that "the next task to execute" is
returned instead of actually executing this task.

A now it starts to get complex, but you get a hold of an entire tree
of partially evaluated functions that are parked waiting for the last
argument.

A clean way to put one function after another so they execute in
sequence as dependent tasks is to use a monadic bind operation:

 http://ocsigen.org/docu/last/Lwt.html#VALbind

But this requires the function to be designed in a clean way and
conform to certain monadic rules, and getting it wrong creates a mess
in the type errors.

What we effectively achieve is a lot of functions queued up on a the
call stack in the form of closures allocated to hold the partially
evaluated parameters.

Now, we might as well just push a closure onto a queue instead of on
the call stack. This avoid a lot of complexity in the function type
design, and we get a lot more flexibility in how we dispatch the tasks
(arguably we could do the same or possibly more, in continuation
passing style, but it will give you a headache).

We might loose some type safety by using queues, but I'm sure one
could dream up some queue type system to enforce certain conditions.

More importantly, it is much simpler to understand a closure on a
queue, than continuation passing style.

And finally, with queues you have an elegant way of extending this to
multiple OS threads (or ocaml green threads), although again this is
also doable in continuation passing style.

Someone could probably argue that a queue is also just a continuation
state or something, but we a dealing with making threaded abstractions
that are easy to use and implement, not mathematical equivalence
relations.

2009/9/30 Stéphane Glondu <steph@glondu.net>:
> Mikkel Fahnøe Jørgensen a écrit :
>> A function can push other functions to the global queue. This in
>> effect creates a continuation, and the concept is similar to
>> continuation passing style or LWT threads, *but requires no
>> continuation arguments to drag around*.
>
> Could you elaborate?
>
>
> Best regards,
>
> --
> Stéphane
>
>