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