| Abstract: |
We demonstrate that composition techniques for tree transducers are
suitable to eliminate intermediate results in functional programs.
We consider two composition techniques, which view special functional
programs as (restricted) macro tree transducers: The first uses
composition techniques for macro tree transducers directly. The second
is indirect in that it (i) translates macro tree transducers into
attributed tree transducers, (ii) uses a composition technique for
attributed tree transducers, and (iii) translates the composition
result back into a macro tree transducer. We informally compare these
techniques with the deforestation technique of Wadler. In particular
we show that the composition techniques eliminate intermediate results
for certain kinds of function definitions, for which classical
deforestation fails.
|