Interesting Side-Effects Problem & Solution

[Avi Kivity <Avi@xxxxxxxxxxxxx>]

I have recently come across a difficult problem which I would like to 
share with the list:

My data contains empty <page> elements interspersed with the 
content elements (no, I'm not using them to control pagination). The
problem is to locate the nearest <page> element that precedes some
given element in tree order. This <page> element may be a sibling node,
or it may occur as some other type of relative (cousin-node?).

Locating the <page> element is possible by using node navigation, 
however this is very costly (O(number of separating nodes)). A trivial
C++ implementation comes to mind: add a unique pageid attribute to 
<page> elements, and corresponding pageidref attributes to all other 
nodes, and fill them in some sort of prepass. The output would look 
something like this:

<root>
  <page pageid="p0">
  <section pageidref="p0" -- comes from sibling -- >
	blah blah
	<section pageidref="p0" -- comes from sibling of parent -- >
		more blah blah
		<page pageid="p1">
                  goo goo
            </section>
            <section pageid="p1" -- comes from child of sibling -- >
           
  <!-- etc -->

</root>

When trying to contemplate a dsssl implementation, however,
I hit the famous no-side-effects-here barrier. The element processing 
rules only return sosofos, while more information (the page element to 
be linked) is required. So I decided to implement my own rule driver
using node-list-reduce:

(define (process-with-side-effects nl obj)
    (node-list-reduce
        nl
        (lambda(obj snl) ((cdr obj) (car obj) snl))
        obj
    )
)

Where an obj is a pair (value . rule). Value is the result of the operation
(usually a sosofo), and rule is a procedure object that combines a value
with a node, returning a new obj. An example rule is:

(define example-rule
    (lambda(sosofo snl)
        (if (is-element? snl)
            (let 
                 (
                     (recurse 
                          (process-with-side-effects 
                               (children snl)
                               (cons (empty-sosofo) example-rule)
                          )
                     )
                 )
                 (cons
                     (sosofo-append
                         sosofo
                         (make element
                             gi: snl
                             attributes: (copy-attributes snl)
                             (car recurse)
                                 ;processing result of children
                         )
                     )
                     (cdr recurse) 
                          ;propagate state from children
                 )
            )
            (cons      ;non-element node
                  (sosofo-append
                        sosofo
                        (process-node-list snl)  
                  )
                 example-rule
            )
        )
    )
)

This is a fairly verbose (and lacking) version of the jade identity 
transform. Things become interesting, however, when the rule
is defined as:

(define (interesting-rule parameter)
    (lambda(sosofo snl)
         ...
         (do-something-with parameter)
         ...
         (cons 
                a-sosofo
                 (interesting-rule (+ parameter 1))  ;successors use a
different rule
         )
         ...
    )
)

Now, results from processing of a node propagate to its successor,
and results from processing of the children of a node propagate 
upwards to the successor of their parent. Implementing my original
problem becomes trivial. And each node is traversed exactly once.

(An aside: a 'with-mode' would be implemented by returning an altogether
different rule rather than a variant of the current rule)

My questions to the list are:
1. Has anyone survived this long message?
2. Are there other generic solutions to this type of problem? Better? Worse?
3. How would this be accomplished when the transformation language becomes
available?
4. When would the transformation language become available? ;)

(make empty-element gi: "sig" attributes: '(("name" "Avi Kivity") ("email"
"avi@xxxxxxxxxxxxx")))
---------------------
"Thou shalt not travel faster than light" - Carl Sagan, Contact



 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist