"Mark P Jones" <[EMAIL PROTECTED]> wrote:

> Joe: As you've observed, the space behavior of Haskell
> programs is often very subtle, and hard to understand.
> I glanced quickly over your program but didn't see any
> immediate signs of problems.  My first suggestion would
> be that you try using the rudimentary heap profiler that
> Hugs provides to see if this gives some insight into the
> source of the leak.

Ah!  I didn't even know Hugs had this.  Very useful!

This has turned up some interesting results... here's
what I've found so far:

Running the parser by itself (parseInstance :: String ->
[XMLEvent]) yields a nice flat space profile (actually
it's rather spiky, but it definitely runs in bounded space).
So 'parseInstance' by itself doesn't seem to have a space leak.
But when I feed its output to 'preorderTree . treeBuild' (where
treeBuild :: [XMLEvent] -> Tree XMLNode and preorderTree ::
Tree a -> [a]), the space usage grows linearly, with a sharp
dropoff very near the end.

Further investigation shows that the problem is *definitely*
in the tree builder.  It's not specific to Hugs either,
GHC behaves the same way.

> Failing that, it might be worth trying to put together
> a complete example (program and data) that demonstrates
> the problem.  I find it rather hard to think about examples
> like this in the abstract.  Having code that I can actually
> run, can make a big difference in situations like this.

I've boiled it down to a short test case; will post that
here presently.

Some more background on what I'm working on...  There are
two traditional approaches to processing SGML and XML:
the event-driven approach, where the application responds
to start-tag, end-tag, and data events; and the tree-based
approach, where the application has access to the entire
document tree.  The tree-based approach tends to be easier
to use and more flexible, but common wisdom has it that the
event-driven approach is more space-efficient.  I thought:
wouldn't it be neat if you could write programs
in a tree-based style, and automatically get good space
behaviour through the magic of lazy evaluation?

There are a lot of common XML processing tasks that
are naturally expressed as a catamorphism, tree homomorphism,
or downwards accumulation (validation, namespace processing,
many simple translations to other document types,  etc.),
all of which should run in space bounded by the depth of the tree.


--Joe English

  [EMAIL PROTECTED]

Reply via email to