[<<][sm][>>][..]
Fri Jan 10 14:16:52 CET 2020

Manual example

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

The task is a CSP copy task:

  (let ((a0 123))  ;; some constant present in all frames
    (loop
      (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
  be avoided.

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

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

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





Was a good exercise.  The conclusion is that it isn't nearly as simple
as anticipated, but some constraints got clarified in the process.
Important conclusions:

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








[Reply][About]
[<<][sm][>>][..]