Strictification of computations on trees

An attribute grammars describes a computation over a recursive data structure (syntax tree). The corresponding evaluator can be directly encoded as a set of lazy evaluated functions. In this paper we show how this set may be converted into a larger set of strict functions and a collection of new data types. We call this process, which is based on a global dataflow analysis, strictification. The resulting set of small functions and the new data types are amenable to further analysis and optimization. Especially the elimination transformation leads to very efficient programs, both in time and space, and which are much more suited for incremental (i.e. memoized) and parallel evaluation