On Mon, Feb 18, 2008 at 11:40:42PM -0800, Andrew Lentvorski wrote:
Without closures/continuations, there is no way to suspend the "stack"
information from a recursive set of calls to be resumed later (C, C++,
Java, for example). When you have closures/continuations, suddenly you
get recursive solutions popping up. Witness the number of "yield"-based
XML traversal solutions in Python (yield is a weak continuation construct).
Attempting to do something like this is how I figured out that Common Lisp
does not have first-class continuations. It has continuations, but they
don't survive the stack frame they're created on. I ended up coding
several different approaches to the problem, none of which made me very
happy:
- Lazy sequences. The remaining elements are captured with a "promise"
which is essentially a closure that will evaluate the item and the rest
of the list. I had to implement some primitives, such as lazy-append,
lazy-mapcar, and lazy-mapcan to make this work. I got frustrated when
it ended up reading in the entire structure before giving the first
result anyway, which defeated the entire purpose. Turns out that
getting lazy lists is very tricky, apparently, as people who try to use
lazy/force in Scheme discover my same problem.
- OO-style iterator class. The stack of pending requests gets managed
directly. This is just like SAX and friends.
- Continuation-passing style. Didn't get very far with this. The
problem is that the CPS is rather infectious, and would require me to
rewrite large parts of my program in CPS style. I suppose in Common
Lisp I could build macros that will rewrite my normal lisp code into
CPS style, but that's a good portion of the way to implementing a
language that supports continuations.
The main reason that drives this isn't the depth of the recursion, but the
size of the whole structure. Without some way of stopping part way
through, the code can only read the entire entity into memory. This is
actually normal for webpages and stuff, but imagine a network XML stream,
or a traversal of a filesystem.
The other reason is when you need to traverse two structures, say to
compare them. The comparer needs to be able to traverse each as it sees
fit.
To be fair, though, lots of the junk in the SAX way of traversing XML is to
deal with the fact that XML "nodes" are polymorphic while the
implementation language is statically typed.
Franz has an elegant (and rather small) xml parser/generator. It reads XML
and turns it into equivalent sexps. Most of the work is dealing with XML's
many idiosyncrasies. The result is something like:
(:html (:head (:title "Page title"))
(:body (:h1 "Section 1 title")
(:p "This is some text in this thing" (a :href "link.html" "Text in the
link".)))
with just a bit more for attributes.
David
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
