Notes on Macro Tree Transducers

This is an intuitive (informal) description of the general idea behind Macro Tree Transducers (MTT)'s, as I understand them. It was derived largely from a reading of Stefan Reuther's thesis, which gives an excellent formal description.

What are MTTs? Why are they interesting?

An MTT is a program which transforms trees into trees. Different classes of MTTs have different time and space complexity bounds, and for many classes of MTTs there are methods for composing two MTTs into a single MTT of the same class. This is one of the main reasons why MTTs are interesting.

You can think of an MTT as a functional program with some restrictions imposed upon it.

First, some definitions:

The first line is simply a definition for the tree data structure we'll be using. We allow tree nodes of unbounded arity here, but in fact there must be some fixed upper bound on the arity (so a tuple would be more appropriate, but would make the exposition more difficult). The second line is the type signature for all MTTs. Note that an MTT takes a tree and a list of trees and returns a single tree.

The type variable a refers to the type of the nodes in the input tree, while the type variable b refers to the type of the nodes in the output tree. With this in mind, we can see that an MTT takes two arguments; the first argument is potentially part of the input, and the second argument is potentially part of the output. We will refer to the first parameter as the input parameter and the second input as the accumulation parameter.

In order to fully specify an MTT, you also need to provide an initial accumulation parameter; sort of a base case.

Restrictions

No Introspection on Accumulation Parameters

Here is where we encounter the first restriction of MTTs: your program may not pattern match on values of type Tree b. So, if you write your mtt like this:

You can't put a “case tb of” on the right hand side, nor can the tb on the left hand side be a pattern. But you can certainly include tb as part of the answer you return.

Pattern Matching on the Head Only

The second restriction is that the pattern which matches against ta may only inspect the head of ta, and may only match against immediate children of the topmost node.

So, this is acceptable:

But these are not:

because the first example inspects the head of a node other than the topmost node, and the second example matches elements other than the immediate children of the topmost node.

Must Pattern Match (Deconstruct) the Head

We will also insist that the pattern on the left hand side matches a literal against the head of the tree, and we will prohibit “@” from being used on the first argument. So, these would be unacceptable:

Basically you must “disassemble” the input tree. Whether or not you're allowed to put it back together and insert that in the output depends on the other restrictions which may or may not be imposed on the MTT.

Must use a [,,,] pattern on the body of ta

Although the Haskell type [Tree a] includes lists of unbounded length, MTTs are defined only on trees with bounded arity. Different nodes of the tree may have different arities, but there must be an overall limit on the maximum allowable arity.

Technically, MTTs are defined such that for any particular value of type a, the arity of a tree whose head is that value is fixed. However, it's easier to explain in Haskell (and equivalent) if we impose the matching restriction instead.

Special Classes of MTTs

There are several special classes of MTTs:

• Top-Down Tree Transducers (“Top”) do not use their accumulating parameter (tb).

• Recursion-Linear Tree Transducers (“Xlin”) never duplicate references to values of type Tree a.

• Context-Linear Tree Transducers (“Ylin”) never duplicate references to values of type Tree b.

• Linear (“Lin”) MTTs are both recursion-linear and context-linear.

• Recursion-Nondeleting Tree Transducers (“Xnd”) never discard references to values of type Tree a.

• Context-Nondeleting Tree Transducers (“Ynd”) never discard references to values of type Tree b.

• Basic Transducers never make nested recursive calls; that is, the right hand side will never include an invocation of mtt with an argument built from the result of a call to mtt.

• Weakly Single-Use Transducers are transducers for which any particular value of type a appears in the right hand side of at most one of the rules. This means that we can meaningfully refer to “the invocation which caused the recursive invocation of rule r”.

• Single-Use Transducers are weakly single-use and context-linear.

• Atmost Transducers are recursion-linear and either context-linear or basic.

• Atleast Transducers are recursion-nondeleting and either context-nondeleting or basic.

Automata

The paper Pushdown Machines for the Macro Tree Transducer describes a class of automata which perform the operations described by compositions of macro tree transducers. These machines correspond to finite state machines with a recursive pushdown stack (that is, a pushdown stack whose elements may be recursive pushdown stacks).

To Do

Can trees be of unbounded arity?

Double-check “Weakly Single-Use Transducers”

rendered from WIX