Example Transformation: Deforestation

On this page, we give an example of a transformation which can be perfomed on programs written in a simple functional language. The transformation is called deforestation [1,2], because it transforms program to remove intermediate trees.

The abstract syntax of the language is given below.
pr ::= e Program
e ::= n Integer Constant
| v Variable
| e1 op e2 Operator Application
| c e1...en Constructor Application
| f e1...en Function Application
| case e0 of p1:e1|...|pk:ek Case Expression
| let v = e0 in e1 Let Expression
| let f v1...vn = e0 in e1 Function Definition
op ::= +|-|*|/|=|<>|<|<=|>|>= Arithmetic Operator
p ::= c v1...vn Pattern
The only constants in the abstract syntax of the language are integers. Booleans are represented by the values True and False. Note that booleans are considered to be constructors in the abstract syntax of the language. This is so that pattern matching can be performed upon them, since pattern matching is allowed only on constructors. The conditional can therefore be expressed as follows:

case e0 of True: e1 | False: e2

This has the same meaning as the more traditional form of conditional:

if e0 then e1 else e2

Empty lists are represented by Nil and non-empty lists are represented by an expression of the form Cons e1 e2, where the head of the list is denoted by e1, and the tail of the list is denoted by e2. Lists are decomposed using a case expression of the following form:

case e0 of Nil: e1 | Cons v1 v2: e2

In the expression e2, the head of the list e0 is represented by the variable v1, and the tail of this list is represented by the variable v2. There is therefore no need to add explicit head and tail operators to the basic functions.

An example program is given in the left hand text area of the applet below. In this program, an intermediate list is created by appending the list ys to the list xs. This list is then decomposed again when the list zs is appended to it. Press the button and see the result of transforming this program. As you can see, the resulting program contains no intermediate lists. Try entering your own programs in the text area on the left, press the button again, and see the resulting of transforming these programs in the text area on the right.

[1] P. Wadler "Deforestation: Transforming Programs to Eliminate Trees" Theoretical Computer Science 73:231-248, 1990

[2] G.W. Hamilton "Higher Order Deforestation" Proceedings of the Eighth International Symposium on Programming Languages, Implementations, Logics, and Programs, 213-227 Aachen, Germany, September 1996 Springer Lecture Notes in Computer Science LNCS 1140