RE: Interesting Side-Effects Problem & Solution

Subject: RE: Interesting Side-Effects Problem & Solution
From: Avi Kivity <Avi@xxxxxxxxxxxxx>
Date: Tue, 15 Dec 1998 10:53:41 +0200
On Tuesday, December 15, 1998 05:55, Chris Maden [SMTP:crism@xxxxxxxxxxx]
> Interesting.  I prefer another approach for this particular problem.
> The list of <page>s is generated within each construction rule, and
> then iterated over until one is found whose (all-element-number) is
> greater than the current node.  It's probably heavier on the

The question is, how much heavier?

Say that a document contains N nodes, P <page>s, and R locations 
where <page> references are required.

Values for N, P, and R are (say) 3,000,000, 1,000, and 10,000.

In Jade, O(N) node accesses are required to build the grove and iterate
over <pages>. This is done R times, so the expected running time is
O(N*R) = 3*10**10 node accesses.

If a better implementation of (tree-before?) and (subtree) is assumed, then 
this drops to O(N+R*P) = 10**7 node accesses. This might be acceptable,
but is quadratic in the size of the document (assuming a constant page 

The linear implementation is O(N), however it requires a separate pass (see 

A sufficiently aggressive DSSSL engine might achieve O(R) operation using
something like (process-node-list (ipreced nd)) -- that is, defining the
recursively -- if caching of procedure calls is provided. But it would
take more than O(N**R**P) to actually implement this.

Does anyone know what it would take to achieve this using the transformation
language, assuming only "natural" use?

> processor, but it means that you can process arbitrary nodes and get
> the right results.  For example, in your case, determining the page of
> a cross-reference destination would probably be difficult.

Indeed, determining the page of a cross-reference is the only reason for
this at all! The processing described is a pre-pass, which adds PAGEID 
attributes to all <page>s, and PAGEIDREF attributes to all referenceable
It becomes a simple matter of double referencing to get to the <page>
associated with a cross-reference.

I am not happy with my solution; too often pre-processing passes have to be
invoked on the data, which is exactly the opposite of what my conception of
dsssl processing should be like -- a sequence of transformations, followed
by a 
rendering, but performed in parallel (composed) rather than sequentially

 DSSSList info and archive:

Current Thread