"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]
