Walking the DOM (was: XML APIs)

[John Cowan]

Tim Bray wrote:

> Wouldn't the effects of recursion will be lost in the static,
> compared to the effects of loading the doc into memory to facilitate
> tree processing?

That produces slow processing, not a hard failure (unless indeed there
is simply too much document for even virtual memory).  Java, and
all other HLLs I know of, provide no way to recover from
stack overflow, short of starting the app all over again with
a command-line switch for a bigger stack.

A general-purpose routine ought not to generate a preventable
hard failure no matter what the document looks like, IMHO.

> BTW, what languages can be relied on to do tail recursion?

Scheme and ML and their descendants.  The Scheme version of
Stephen's algorithm will detect the tail recursion, and will
be recursive down the tree and iterative across it.

Indeed, Scheme *has* no (primitive) way to do iteration except
with tail recursion (there are macros that syntactically sugar
this, if you want).  As a result, Scheme compilers can concentrate
on making the very few constructs they have to understand
(function call, function closure, assignment, IF) very very
efficient.
 
> Also, shorter algorithms are better. -Tim

But constant-space algorithms are better too.

-- 
John Cowan	http://www.ccil.org/~cowan		cowan at ccil.org
	You tollerday donsk?  N.  You tolkatiff scowegian?  Nn.
	You spigotty anglease?  Nnn.  You phonio saxo?  Nnnn.
		Clear all so!  'Tis a Jute.... (Finnegans Wake 16.5)

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)