Finite State Tree Transducers

A Tree transducer implements a function (or relation) from trees to trees. In contrast to strings, which have a left/right symmetry, trees have a very different structure depending on whether one navigates them top-down or bottom-up. We will focus on bottom-up transductions here.¹

Recall that we are using unranked trees; trees where the number of daughters that a node may have is not determined by its label. The reason for this is simply because it accords with linguistic practice; a VP node might have one daughter (in case of an intransitive V) or two daughters (in case it has a specifier), or three daughters (in some older analyses prior to the widespread adoption of a binary branching hypothesis). A simple inductive definition of such objects can be given as follows: a tree consists of a node label followed by a list of trees.

data Tree a = Node a [Tree a] deriving (Show,Eq)

According to this definition, every node has a list of daughter subtrees. A leaf is a Node with an empty list of daughter subtrees.

We begin with the concept of a tree homomorphism. A homomorphism can be thought of as a transducer with just one state. Thus, if a transducer is homomorphic, it cannot use the context of a node in any way to influence its translation. A homomorphism is therefore fully determined by its kernel – a function which specifies how to interpret each node in isolation. Note that a node is interpreted as a way of combining the interpretations of its daughters. So if a subtree is interpreted as a tree, a node must be interpreted as a way of combining a list of trees into another tree.

type Kernel a b = a -> [b] -> Maybe b
type Hom a b = Tree a -> Maybe b
extend :: Kernel a b -> Hom a b
extend ker (Node a ts) = traverse (extend ker) ts >>= ker a
{- traverse :: (a -> Maybe b) -> [a] -> Maybe [b]
if any element of the input list is mapped to @Nothing@, then the output is @Nothing@.
otherwise, behaves as @map@, ignoring the @Just@ wrapped around the outputs:
traverse f [] = Just []
traverse f (b:bs) =
  case f b of
    Nothing -> Nothing
    Just x ->
      case traverse f bs of
        Nothing -> Nothing
        Just xs -> Just (x : xs)

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
If the input is @Nothing@, so is the output.
Otherwise, applies the function inside of the @Just@:
Nothing >>= f = Nothing
Just x >>= f = f x
-}

Note that each node in isolation must be interpreted as an operation that combines the translations of its daughters into some new output. Specifying (and then varying) these operations will give us a wide variety of different tree transducer models.

As noted previously, the kind of objects that a transducer associates with subtrees can be changed. Here we explore allowing not just trees, but lists of trees to be the output of a transduction.³ (Multi-homomorphisms will not be treated separately, we can obtain them as the special case of a multi-transducer where states are of unit type (and thus record no information).) A multi-rule is much the same as before, except that it outputs a list of contexts. Another 'difference' (really, making explicit what was implicit before) is that the previous assumption that each state corresponds to just one translated tree no longer holds. Thus we need to indicate along with each state the number of translated trees it corresponds to.

type MultRule i s o = ((i,[(s,Int)]),(s,[Context o]))

A multirule will have the form: \(f(q_{1}(t_{1,1},\ldots,t_{1,k_{1}}),\ldots,q_{n}(t_{n,1},\ldots,t_{n,k_{n}})) \rightarrow q(c_{1},\ldots,c_{k})\) where f is the node of the tree being processed, the \(q_{i}\) are the states of the transducer after processing the \(i^{\mbox{th}}\) daughter, the \(t_{i,j}\)s are the trees associated with the \(i^{\mbox{th}}\) state, and the \(c_{i}\) are the contexts associated with the output state. Such a rule would be rendered in the following way as our Haskell type MultRule: ((f,[(q1,k1)..(qn,kn)]),(q,[c1..ck]))

Given a list of multi-rules, we can construct a Kernel.

mkMultKernel :: (Eq i,Eq s,Eq o) => [MultRule i s o] -> Kernel i (s,[Tree o])
mkMultKernel rules i bs = 
  do
    (sn,cs) <- lookup (i,ss) rules
    ts <- flip tree_substitution (concat trees) `traverse` cs
    return (sn,ts)
  where
    (states,trees) = unzip bs
    ss = zip states $ fmap length trees               

We can again use transduce to allow us to filter out those tree tuples which are associated with the wrong states

mkMultTrans :: (Eq a,Eq s,Eq b) => [MultRule a s b] -> [s] -> Hom a ([Tree b])
mkMultTrans rs fins = transduce fins $ extend $ mkMultKernel rs

A multi-transducer is also much the same as our previous transducer. The difference is of course the type of the transition function, which is of course quite similar to the type of a multi rule.

data MultBU s i o =
  MultBU {statesMult :: [s]
         , iAlphMult :: [i]
         , oAlphMult :: [o]
         , finalStsMult :: [s]
         , transMult :: i -> [(s,Int)] -> Maybe (s,[Context o])}

As expected, we can construct a multi-transducer from a specification of the rules, and the final states.

mkMultBU :: (Eq i,Eq s,Eq o) => [MultRule i s o] -> [s] -> MultBU s i o
mkMultBU rs fins = MultBU sts iAl oAl fins tr
  where
    (iAlDups,stsDups,oAlDups) = unzip3 $ fmap (\((i,ss),(s,ctxs)) -> (i,s:(fmap fst ss),ctxs >>= getNodes)) rs
    sts = L.nub $ concat $ stsDups
    iAl = L.nub iAlDups
    oAl = L.nub $ concat oAlDups
    tr = curry (flip lookup rs)

Using trees (or lists thereof) as the output data structure entails that nodes in the translations of different daughters must be independent (i.e. they must not dominate each other) in the final output structure. This can sometimes be too restrictive. For example, if we are transducing a tree into a string (qua monadic tree), we would like to be able to have nodes (i.e. letters) from one subtree dominate nodes from another one. The obvious solution to this problem is to change the output data structure. We would like a data structure which can be modified not only at the root (like a tree), but also at its frontier. Luckily, we have been using one such: Context. If our trees should be transduced into tree contexts, then each node must be an operation which takes contexts as arguments, and produces contexts; a context context.

data CContext a = 
  NodeCC a [CContext a] | CHole0 Int | CHole1 Int [CContext a]
  deriving (Show,Eq)

If we are going to be manipulating contexts, we will need to replace the holes of our contexts not with trees, but with other contexts. This operation is called context composition. It is, as code, identical to tree_substitution, but for the constructors on the right hand sides; in tree_substitution we return a Node a dtrs whereas here we return a NodeC a dtrs.

ctxt_composition :: Context a -> [Context a] -> Maybe (Context a)
ctxt_composition (Hole i) g = get g i
ctxt_composition (NodeC a cs) g = 
  do
    dtrs <- flip ctxt_composition g `traverse` cs
    return (NodeC a dtrs)

We will also need to perform the analogue of tree_substitution, but where we are substituting contexts for the internal holes of a context context! This operation makes use of context composition, so as to put the contexts which are the daughters of an internal hole inside of the context we are filling the hole in with.

cCtxt_substitution :: CContext a -> [Context a] -> Maybe (Context a)
-- if you are a leaf hole, that stays the same
cCtxt_substitution (CHole0 i) _ =  Just (Hole i)

-- if you are a node, just do the substitution on all daughters
cCtxt_substitution (NodeCC a ccs) cs = 
  do
    dtrs <- flip cCtxt_substitution cs `traverse` ccs
    -- doing the substitution on all daughters
    return (NodeC a dtrs)

-- if you are an internal hole, replace it with the appropriate
-- context (obtained via @get cs i@).  Because the daughters of this
-- guy are still @CContext@s, we need to turn them into @Contexts@ by
-- substituting into the open @CHole1@s the appropriate contexts from
-- @cs@.  Then we can compose the contexts.
cCtxt_substitution (CHole1 i ccs) cs =
  do
    ctx <- get cs i
    -- getting the appropriate context to replace the internal hole
    ctxts <- flip cCtxt_substitution cs `traverse` ccs
    -- turning the daughters of the internal hole into normal contexts
    ctxt_composition ctx ctxts

A Macro Tree Transducer rule is much the same as our previous transducer models (in particular, the bottom-up one); this time however nodes are associated with tree context contexts.

type MacroRule i s o = ((i,[s]),(s,CContext o))

Given a set of macro rules, we can construct a Kernel in the same way we always do.

mkMacroKernel :: (Eq i,Eq s) => [MacroRule i s o] -> Kernel i (s,Context o)
mkMacroKernel rules a bs = 
  do
    (s,cctx) <- lookup (a,states) rules
    ctx <- cCtxt_substitution cctx ctxts
    return (s,ctx)
  where
    (states,ctxts) = unzip bs

This allows us to construct a macro transduction using transduce:

mkMacroTrans :: (Eq i,Eq s) => [MacroRule i s o] -> [s] -> Hom i (Context o)
mkMacroTrans rs fins = transduce fins $ extend $ mkMacroKernel rs