[PRL] laziness

[David A. Herman]

> Potentially yes, Empirically no. We tend not to write programs that lop
> off whole sub-computations, and when we do, this goal is so explicit
> that  little is gained through doing it automatically. (see okasaki's
> book)

Yeah, I don't think there are any computations that can be prevented from
eventually being performed in my program. Here's what I'm actually working
with: I ported Daan Leijen's pretty-printing library, written in Haskell,
to PLT Scheme:

    http://www.cs.uu.nl/~daan/pprint.html
    http://www.ccs.neu.edu/home/dherman/code/pprint.ss

It's based on some papers by Hughes, Peyton-Jones, and Wadler on deriving
a combinator library from an algebraic specification. It builds up a
"smart document" from the AST, and then the abstract document can be
rendered according to various parameters. I ported it naively to Scheme
in a completely eager way, and now I'm finding strange cases where, with
slight tweaks to the AST, the pretty-printer can either run so slowly that
I don't get a response after minutes (haven't actually let it run to see
how long it would take) or get a result almost instantly. I'm not sure if
this is due to a bug in my port, the nature of the library, or something
to do with laziness.

(I'd just try it in Haskell to see what happens, but it's non-trivial: the
AST comes from a parsed Java program. I might try and hack together a
little mock Java-AST in Haskell to see, but I don't want to get too
side-tracked.)

So I'm wondering, if one of the intermediate trees is actually pretty
huge, can laziness save you a lot of space, because it only needs to hang
on to the current piece of the intermediate tree that it's working with?
In other words, the "smart document" might be huge, so just working with a
small piece of it at a time could save enormous amounts of memory.

I would try running the Scheme code through a profiler, but one of the
problems with the PLT profiler is that when my program is so slow that I
want to profile it to figure out how to improve it, running with profiling
turned on is so unbearably slow as to be unusable! Rgh.

Dave