Fri Jan 10 14:16:52 CET 2020
Create a manually compiled example, then refine it to something that
can be automatically compiled.
The DMX example is actually quite nice, as it has 4 event kinds: USB
input, DMX output, DMX input, USB output. This is going to come back
in a lot of data converter tasks.
Example of code generator output. Work bottom up: start by manually
creating some C code, then model the compiler to produce that kind
The task is a CSP copy task:
(let ((a0 123)) ;; some constant present in all frames
(let* ((a (recv c0))) ;; a is not present in recv k
(a1 (+ a 1)))
(send c1 a1)
(send c2 a1)))
- This has 3 continuations for the three channel rendez-vous points.
One of the sends can be left out to simplify.
- This already exposes ownership and lifetime of data, which is a
general problem. We solve it by storing the data to be transferred
in the sender's stack frame, and letting the receiver copy the data.
- There is also a tail call here at the end of the loop, which
destroys the stack frame. Maybe it is better to model that
explicitly? No let's keep the loop as a primitive. It will make
the reuse of stack frames simpler, allowing first class function to
- To represent in C: I'm thinking it might be simplest to generate one
struct per continuation type. Otherwise the dereference notation is
going to be too hard to read in the generated C code.
- How to re-write things to not pollute continuations? E.g. if
variables are short-lived they can just go on the C stack. Does it
actually matter that we keep junk in the suspended contination?
E.g. for the send continuations, the variable a is sill visible but
no longer needed so could actually just be removed. Maybe it is best
to not make the distinction at all in the beginning. Just allocate
everything in the struct, then later when it is all working, add an
optimization that allocates intermediate variables on the stack if
they are not used after a point.
- Simplification: program will need to be in ANF such that the value
passed into a continuation has a well known place at the top of the
- C representation: incoming and outgoing continuation do not have any
required relation, but in practice they will share the bottom of the
stack. I would like to avoid copying. However, there might be many
intermediate forms. This is going to take bookkeeping, so maybe
local variables that do not make it into the closure should just not
- The type of the output stack depends on the code path! So how do we
know what the continuation output type is? From the function that
interprets it. So continuation struct types are always associated
to the associated function, and only that function knows how to
interpret the data.
- Growing upward is going to be simplest. Fits best in C struct view.
- Let's assume that the continuation can be modified in-place, and it
is the responsibility of the function to do this.
- About output: it's really not clear how to anticipate the shape of
the output continuation. The more I think about this, the more I
believe that explicit stacks might no be the way to go. Otoh static
guarantees are nice.
- Loops and conditionals need to be handled somehow. These could be
expressed as continuations, but there's a distinction between
non-blocking and blocking continuations. I ran into this before
doing the DMX converter box: the main loop structure doesn't
correspond to blocking points. This is exactly why you would want
to automatically transform to CPS, partially.
- Harping on that: maybe compiling to flat form is better. That way
'goto' can be used and we can have tail calls. And suspension is
just taking the label of that goto. Let's rework the example.
- If the program is in ANF form between control points, then it would
probably be simpler to manage stack frames because there is only on
C struct per "chain", that could be partially filled.
- Recursive calls can also have copy optimization to re-use the
Was a good exercise. The conclusion is that it isn't nearly as simple
as anticipated, but some constraints got clarified in the process.
- use ANF, with the exception that non-block C functions can be
collapsed into expressions.
- suspensions and control structs (loop + conditional) are very
different from scheduling point, but should be put on the same
footing in the language. a single C struct per machine makes this
possible. that also makes the generated code a bit more modular at
the C level
- the scheduler doesn't need to know the type of the contination.
however a continuation's code pointer does identify the type of the
data associated. obvious in retrospect, but wasn't starting out.
- grow upward. easier for C structs.