A Functional Language for the Specification of Complex Tree Transformations

Reinhold Heckmann

Abstract

Transformations of trees and rewriting of terms can be found in various settings, e.g. transformations of abstract syntax trees in compiler construction and program synthesis.

A language is proposed combining features of a general purpose functional language with special means to specify tree transformations. Atomic transformations are considered first order functions and described by pattern matching. The pattern specification language allows for partitioning trees by arbitrary vertical and horizontal cuts. This goes beyond what is possible in similar languages [Hope, SML, Miranda]. High order functions and functional combinators are used to express strategies for the controlled application of transformations.


[Paper.ps.gz (17p, 34k, from troff, reformatted)]


Reinhold Heckmann / heckmann@absint.com