Sun Oct 11 09:53:57 CEST 2009

Z -> C

Given a specification of a filter in terms of stream operators, derive
the routine that implements the loop.  When done in several steps,
this is quite straightforward.

     1 convert a `z' notation to normal form by pushing the operator
       through the expression / network to end up at stream offsets.

     2 generate loop code in imperative Scheme, converting `~' to `ref'

     3 convert imperative Scheme to C AST and concrete syntax.

Step 1 produces code like this:

   ((~ v1 0) (+ (~ a 0) (~ a 1)))
   ((~ x 0)  (* (~ v1 0) (~ v1 0)))

representing a dataflow network.  (In the case above we could specify
that the stream `v1' won't be observed, meaning it can be implemented
as a scalar.)

Ok, full circle:

box> (ast-emit (stx->c-stmt (dfl/z->scheme #'((v1 (+ a (z a))) (x (* v1 v1))))))
for ((i = 0); (i < n); (i)++)
  (v1[(i + 0)] = (a[(i + 0)] + a[(i + 1)]));
  (x[(i + 0)] = (v1[(i + 0)] * v1[(i + 0)]));

The memoized + loop shift version also +- works, but it needs more
infrastructure to connect to, to get an idea the requirements.  In any
case, the memo code seems straightforward / tedious so I'm going to
leave that alone for now, and concentrate on the loops themselves.

One thing is quite clear though: building more elaborate compilers as
a sequence of steps is very doable, but once the number of
transformation steps gets larger, it's probably best to switch to a
different representation form (i.e. a typed language), to make the
invariants more explicit.  Currently I'm using just scheme syntax
objects (s-expressions with marked identifiers).  I.e. the code
explained here uses the following forms (dfl = dataflow Scheme).

  - dfl with stream variables and `z' operator
  - dfl with `~' operator (stream variable + offset)
  - imperative Scheme expressions with `set!', `for' and `ref'
  - C ast (c.plt)
  - C concrete syntax

So: basic infrastructure is mostly there.

Next: this should rest until after I did some more reading on
dependence-based compilation and loops.