The Arboretuum Programming Language

March 2008, Chris Pressey, Cat's Eye Technologies.

Description

Arboretuum is a language based on an experimental variant of tree-rewriting which we call forest-rewriting. Appropriate to its name, during forest-rewriting, multiple trees (specifically, a finite set) are rewritten. Each tree is labelled with a name; a rewriting pattern can refer to multiple trees, and must match all of them simultaneously in order for a replacement to occur.

As an experiment, Arboretuum was not entirely a success. Forest-rewriting unfortunately turned out to be insufficient for what I wanted to apply it to, namely compiler specification. The idea was to have each tree associated with some data structure used in the compilation process (AST, symbol table, output buffer, etc.) However, it became apparent that, by itself, forest-rewriting could not synchronize the data across the trees the way it would need to be synchronized in a real compiler. I plan to tackle the problem again, with a different variation on rewriting, in a future project.

Regardless, Arboretuum is Turing-complete, as tree-rewriting is simply a special case of forest-rewriting: just have one tree in the forest.

Implementation

I will refer you to the reference implementation of Arboretuum for details on the semantics of the language. Ordinarily I frown upon this sort of practice — normatively defining a language by an implementation rather than by a specification — but the interests of brevity, the experimental tack of the project, the unsuccessful outcome of the experiment, and the relative well-definedness of the implementation language (the purely functional subset of R5RS Scheme) conspire to make the consequences of this choice less painful than usual.

The reference implementation comprises the following files:

• preprocess.scm

  Pre-processes the input program into an internal format suitable for forest-rewriting.

• unify.scm

  Implementation of the unification algorithm which is used to match the pattern part of rewriting rules to the forest.

• forest-rewrite.scm

  Implements the forest-rewriting process proper.

• utils.scm

  Miscellanous support procedures, including mergesort, vector-store (a side-effect-free alternative to vector-set!), print and test.

In addition, the following supplementary files which are not definitive w.r.t. the Arboretuum language are included in the project:

• tests.scm

  Gives a set of unit tests to confirm the absence of certain erroneous behaviours. (Obviously, no number of unit tests could confirm the absence of errors...)

• tree-rewrite.scm

  Some basic tree-rewriting code, to provide contrast between it's complexity and that of forest rewriting.

Note that the Scheme implementation of algorithms in the above files are to be taken as pedantic rather than efficient. They are meant to be read (perhaps even enjoyed?) and only incidentally to be executed.

History

This project was begun in January 2006. I'd been meaning to release it for a while before actually doing so in March of 2008.

Happy forest-rewriting!

-Chris Pressey
Cat's Eye Technologies
March 4, 2008
Chicago, Illinois, USA