[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Walking the DOM (was: XML APIs)

• From: John Cowan <cowan@l...>
• To: XML Dev <xml-dev@i...>
• Date: Tue, 03 Nov 1998 14:12:43 -0500

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@c...
	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@i...
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@i... the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@i... the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@i...)

• References:
  • Re: Walking the DOM (was: XML APIs)
    • From: Tim Bray <tbray@t...>

• Prev by Date: RE: CDATA by any other name... (was The raw and the cooked)
• Next by Date: Unicode, xml:lang, and variant glyphs
• Previous by thread: Re: Walking the DOM (was: XML APIs)
• Next by thread: Scheme (was: Walking the DOM)
• Index(es):
  • Date
  • Thread