Sun May 2 15:13:42 EDT 2010
MEMO-EXPR (dag) ---------> SSA <---------- DFN (dag)
1. Starting from expressions and variables.
The memo-expr is the basic form of functional code: value reuse
through function abstraction or let-binding. Adding variables allows
one to move from trees to directed acyclic graphs (value reuse).
SSA is a MEMO-EXPR without expression nesting, i.e. all bindings are
2. Starting from dataflow notation (input/output variables).
A dataflow network consists of:
- a set of nodes
- a set of input-output relations between nodes
- a constraint: each node is the output node of exactly one relation
Node that the difference with expressions is that a DFN has _explicit_
output node naming, while for expressions this is _mostly_ implicit,
except for memoized expressions, and of course for SSA, which can be
interpreted as a DFN. A memo-expression has _explicit_ dependency
order (lexical scope), but implicit data allocation.
dependency order explicit implicit
output alloc implicit explicit
An SSA expression is _both_ a MEX and a DFN.