Sun Aug 23 10:00:42 CEST 2009

Tree permutations

It's suspiciously difficult because of the possible type exceptions
that might mess up temporary storage on the data stack.  So let's
forget about optimality and write well-factored code.

A linear language specification needs a sublanguage for specifying
_tree permutations_.  Essentially, once you've figured out which
pointers permute, the inverse is just the inverse permutation.  This
needs to be split in two parts:

      - make sure the tree has the structure you expect (type check)

      - perform permutation

Essentially, I want th tree transformation to be safe and guaranteed
linear in the first place, and correct in the 2nd place (which is then
easily checked in the terminal).

Probably Knuth has something to say about this.  Also, I ran into a
tree transformation language a while back.  Forgot where..  Was a
Belgian guy.

Also, I did something like this before.  Probably hidden somewhere in
Staapl / Brood code archives..  Poke?

This looks like a nice exercise to write a compiler for.

Can it be done using binary tree rotations?

( Really, I've done all this before..  But where? )

Suppose the stack is this: (L . S)

`cons' will be something like  (L . (d . S)) -> ((d . L) . S)
then the reverse `uncons' is:  ((d . L) . S) -> (L . (d . S))

They are indeed simple tree rotations.

A left rotation can be transformed into a right rotation as

Nope!  They are not tree rotations.  They are rotations followd by a
particular flip:

               LEFT                 FLIP
(L . (d . S))  --->  ((L . d) . S)  --->   ((d . L) . S)

Anyways, it doesn't seem so difficult to compile such a definition
into a program that deconstructs the list, and then re-uses the list
cells to reconstruct it.

This can even be done manually.  I've summarized it in the next post.