Wed Sep 2 08:59:36 CEST 2009

Staging Control Flow of Data Driven Languages

I've worked on a data flow language in Staapl[1] a couple of months
ago, and I recently realized that because it is staged (all control
flow can be known at compile time) it's worth it to generalize it to
constraint propagation[4] based approach (equations instead of

The key insight is that Abstract Interpretation[2] can be used to
capture the following nuance: at compile time, you know the
availability of data asserts (inputs) but you don't know the value.
Abstractly interpreting the program with only this information allows
you to 1. sequence rule evaluation and 2. directionalize the rules
into functions.

It seems to me that this principle can be generalized.  Any kind of
non-standard control flow can be statically sequenced as long as it
depends only on availability of data, and you known this availability
at compile time.

Note that you cannot do this in cases where the control flow depends
on the values themselves, so attempting to stage `amb' (prolog /
backtracking) might not be so useful, except for adding discrete
constraints that are satisfiable at compile time.

An interesting implementation technique for Abstract Interpretation
are staged macros[3].

[1] http://zwizwa.be/staapl
[2] http://en.wikipedia.org/wiki/Abstract_interpretation
[3] entry://../plt/20090719-142813
[4] entry://../staapl/20090831-155006