A Data Flow Approach to
Higher Order Functions for
Recursive Numerical Applications
Ralf Ebner
Multilevel algorithms for the numerical solution of partial
differential equations like multi-grid methods, recursive
substructuring techniques or algorithms based on sparse grids are
naturally implemented as recursive programs that operate on adaptive
tree structures. They typically apply a function to each tree node
during two different kinds of tree traversal: a downward mapping,
where each function application to a node's value depends on the
result of its parent node, and an upward mapping, where the result of
all children nodes are needed. A sequence of these algorithmic patterns
can easily be expressed as combination of higher order functions.
A higher order extension of the functional language FASAN, which
generates data flow graphs as abstract evaluation machines, permits an
efficient combination of downward and upward mappings. The unnecessary
overhead of construction and decomposition of the tree structures
induced by the higher order function combination is deviated by the
data flow concept of {\em wrapper streams} replacing ordinary tree
constructors. Wrapper streams yield direct communication channels in
the data flow graph, so locality of the tree node values, often
large matrices or equation systems, is achieved.
A special syntax for partial function applications allows the neatless
integration of higher order functions within the Pascal-like syntax of
FASAN.