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.