Program Transformation

I am most interested in transformations based on programs represented by abstract trees. Transformations are expressed by rules of the form:

Pattern matching -- What is it?

Pattern matching plays an important role in a large number of areas. In a typical pattern matching task, one wants to find the objects that have some known properties. Two objects are presented in a pattern matching system: one is the pattern which expresses the known properties; another is the target, also known as the text, which is the data object to be searched for the occurrences of the pattern. The process of finding the occurrences of the pattern in the target is called the matching process.

Pattern matching has been studied in the context of strings for several decades and is still an active research topic due to its important role in a great number of applications. However, strings are ``flat'' in the sense that they do not carry the information about the hierarchical structure of the data they represent. Trees are a natural choice to serve this purpose. Pattern matching in trees is fundamental in a number of areas, including term rewriting systems functional programming languages, equational logic programming languages, code generation, structured text database systems, transformational programming systems, theorem provers, and computational biology. Much work has been done during the last decades and it is still an active research area.

An example of powerful tree pattern matching is the pattern matching in TrafoLa-H, a functional transformation language. TrafoLa-H was designed to allow for very short and suggestive formulations of program transformations. There exist distributed pattern matching as et of subterms without fixed distances; patterns can match at arbitrary distance from the root of the whole term and anywhere in lists.

These powerful language constructs require special implementation techniques. By transforming TrafoLa-H patterns into regular tree grammars, and generating fast bottum-up parsers, it is possible to match even complex patterns in times linear to the size of the term to be matched.