tfof-deforest is a small demo package around a case study into transformation of functional programs, more specifically: on eliminating intermediate trees by deforestation.

Background

Deforestation Theory

Based on Philip Wadler's paper: P. L. Wadler. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science, 73(2):231--248, 1990. http://citeseer.ist.psu.edu/wadler90deforestation.html

Type Inferencing Theory

Tiny First-Order Functional language (TFOF)

TFOF Syntax

TFOF Tools

Deforestation

---

Listing of example tfof-files

---

TFOF Modules (*.tfmd)

• datatypes.tfmd
  • Definition of basic datatypes (Tree and List)

• basic-operators.tfmd
  • For typing purposes only: the standard arithmetic, relational and boolean operators.

• list-basic.tfmd
  • A treeless definition of append (appending two lists).
  • Some list-flattening functions. flatten0 is not treeless, flatten1 and its helper flatten1' are treeless.

• tree-basic.tfmd
  • A treeless definition of flip (at each Branch node, flip the two branches.
  • A non-treeless definition of fleaves (collect all leaves in a list)

• int-arith.tfmd
  • Some basic integer computations.

• list-arith.tfmd
  • Some computations on lists (sum, sequares, etc.)

• tree-arith.tfmd
  • Some computations on trees (sum, sequares, etc.)

TFOF Example files (*.tfof)

• append.tfof
  • term1a and term1b are two distinct nested FunApps^? but should transform to the same resulting term and helper functions.
  • term2 is not linear, only inlining should occur.
  • term3 is just ok. Nothing should happen.

• flatten.tfof
  • term1a calls the nontreeless flatten0 and should transform to two helper functions that are identical to flatten1 and flatten1'.
  • term1b does in fact the same, but now by literally containing the body of flatten0 already. Now only an equivalent of flatten1' should be generated.

• flip.tfof
  • term1 is the example from Wadler's article, p.9.

• leaves.tfof
  • t0 .. t4 only work if a separate rule for simple expressions is added, such that e.g. `(+) v 0' does not lead to additional inlining and deforestation.
  • t5 and t6 fail, since fleaves itself is non-treeless

• nestedcase-renaming.tfof
  • Tests whether transformation of two nested case-statements correctly handles renaming (to prevent undesirable re-binding of variables)

• typetest-*.tfof
  • Small tests for the type-inferencer.

• test-1.tfof
  • Initially used as a parser test.
  • No valid input for deforestation.

• test-2.tfof
  • Initially used as a parser test.
  • term1 is already treeless.

-- ArthurVanDam - 22 Mar 2004