Sat Aug 14 11:47:46 CEST 2010

Tree permutation machine

I'm thinking about implementing PF in a higher level fashion.

    1. Specification as binary tree transformation machine.

    2. Automatic implementation.

Here 1. has as few primitives as possible to guarantee correctness and
2. "caches" some of the composite operations that are used a lot.
Which ops to cache could be defined as a formal search problem.
(I.e. given this much code space, find the best decomposition of ops,
and find a suitable "unrolling" of the tree into registers).

So, what are the primitives of binary tree transformation?

Let's start with the tree transformation group.  A link Antti
suggested [1].  Is this relevant?  I don't see it immediately.

What I'm looking for is generators of the group of permutations of
infinite binary trees.  Each permutation has a finite reach, so can
also be performed on finite trees of sufficient depth.

Are swap and rotate left/right enough?  In [2] I write that a right
rotation can be constructed from a left rotation between swaps, but
it's a bit more complicated:

(A B) C  -R->  A (B C)

A (B C)  -L->  (A B) C

A (B C)  -S->  (B C) A
         -R->  B (C A)
         -S->  (C A) B
         -R->  C (A B)
         -S->  (A B) C

Denoting the group action G on tree t as tG we write G1 followed by G2
as G1G2.  This gives  L = SRSRS.

What are the permutations generated by these primitives?  Can we
generate all binary tree permutations?

An interesting place to look is Wouter van Oortmerssen's [5]
aardappel[6] language from his PhD thesis[7].

( A quick reminder..  Practically, what was the motivation again?
Linear languages are good for embedded systems because they have
immediate resource reclaim, which is important when
resource-allocation becomes a real issues, which is often the case
with components instantiated in hardware.  This is where a-synchronous
mark/sweep collectors to not fare well, as they assume a large pool of
resources that can be reclaimed infrequently. )

I'm playing with the math in [8].  Seems that a "return stack" is a
necessary element to be able to gain locality.  Also, for
non-conservative operations an infinite chain of free nodes is

[1] http://www.research.att.com/~njas/sequences/A089840
[2] entry://20090823-100042
[3] http://stackoverflow.com/questions/651565/permutations-of-a-binary-tree
[4] http://en.wikipedia.org/wiki/Random_binary_tree
[5] http://strlen.com/programming-languages
[6] http://strlen.com/aardappel-language
[7] http://strlen.com/files/lang/aardappel/thesis.pdf
[8] entry://../math/20100814-142538