chickadee » sxml-transforms » pre-post-order

pre-post-order tree bindingsprocedure

(See also pre-post-order*, which is preferred on Chicken.)

Traversal of an SXML tree or a grove: a <Node> or a <Nodelist>

A <Node> and a <Nodelist> are mutually-recursive datatypes that underlie the SXML tree:

    <Node> ::= (name . <Nodelist>) | "text string"

An (ordered) set of nodes is just a list of the constituent nodes:

    <Nodelist> ::= (<Node> ...)

Nodelists, and Nodes other than text strings are both lists. A <Nodelist> however is either an empty list, or a list whose head is not a symbol (an atom in general). A symbol at the head of a node is either an XML name (in which case it's a tag of an XML element), or an administrative name such as '@'. See SXPath.scm and SSAX.scm for more information on SXML.

Pre-Post-order traversal of a tree and creation of a new tree:

pre-post-order:: <tree> x <bindings> -> <new-tree>

   <bindings> ::= (<binding> ...)
   <binding> ::= (<trigger-symbol> *preorder* . <handler>) |
                 (<trigger-symbol> *macro* . <handler>) |
                 (<trigger-symbol> <new-bindings> . <handler>) |
                 (<trigger-symbol> . <handler>)
   <trigger-symbol> ::= XMLname | *text* | *default*
   <handler> :: <trigger-symbol> x [<tree>] -> <new-tree>

The pre-post-order function visits the nodes and nodelists pre-post-order (depth-first). For each <Node> of the form (name <Node> ...) it looks up an association with the given 'name' among its <bindings>. If failed, pre-post-order tries to locate a *default* binding. It's an error if the latter attempt fails as well. Having found a binding, the pre-post-order function first checks to see if the binding is of the form

(<trigger-symbol> *preorder* . <handler>)

If it is, the handler is 'applied' to the current node. Otherwise, the pre-post-order function first calls itself recursively for each child of the current node, with <new-bindings> prepended to the <bindings> in effect. The result of these calls is passed to the <handler> (along with the head of the current <Node>). To be more precise, the handler is _applied_ to the head of the current node and its processed children. The result of the handler, which should also be a <tree>, replaces the current <Node>. If the current <Node> is a text string or other atom, a special binding with a symbol *text* is looked up.

A binding can also be of a form

(<trigger-symbol> *macro* . <handler>)

This is equivalent to *preorder* described above. However, the result is re-processed again, with the current stylesheet.