[<<][libprim][>>][..]Sat Aug 14 11:47:46 CEST 2010

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 necessary. [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

[Reply][About]

[<<][libprim][>>][..]