Thu Sep 3 10:45:38 CEST 2009

DFL/CPL : Control flow staging


In the application I am looking at, the guiding priciple should be the

   The resulting code should be free of unbounded recursion.  This
   means the structure of the C code is can be flattened to a finite
   size combinatory network.

   Within that framework, how can the specifications be abstracted in
   useful ways such that they can be reduced to this form using
   information available at compile time.

DFL: data flow language
CPL: (deterministic) constraint propagation language

Before implementing it, let's look at the usefulness first.


For DFL it's not disputed: allowing parallel presentation of
operations is an advantage over having to specify the order manually.

There are some degrees of freedom in how the DFL -> function/procedure
is implemented, but this is the classical _inline_ vs. _call_ debate,
and can be mostly related to static inlining vs. run-time function
calls.  Note that in this case, the use of recursion is an
_implementation issue_ mostly related to memory use and memory
locality for both code and data.  DFL specs with code sharing lead to
directed acyclic graphs


Adding unspecified directionality (equations instead of directed data
flow operators) brings us to constraint propagation based networks: at
compile time, constraints specified as equations can be translated
into data flowoperators, in addition to fixing the order of DFL
operator evaluation.

One problem with constraints propagation networks however is that they
are _sparse_.  I.e. they cannot solve parallel constraints (systems of
linear/nonlinear equations).  It is probably my bias towards these
kinds of constraint specifications that makes me think there is a
problem here.. So is there?

In order to augment N x 1 constraints over N variables to M parallel
constraints, one needs a static `directionalization algorithm' that
turns the equation into a function from the known parameters to the
dependent ones (which can then trigger further constraint evaluations.

Open issues

Is local consistency[1] useful, or are we looking at more global
constraints like sets of equations?

[1] http://en.wikipedia.org/wiki/Local_consistency