Re: [Caml-list] Purity and lazyness

[Florian Weimer <fw@deneb.enyo.de>]

* Dario Teixeira:

> So, my question is whether there is something I'm missing and in fact "purity 
> <=> lazyness", or I am reading too much from those Haskeller presentations,
> because they never meant to say anything beyond "lazyness => purity", and
> freely mixing the two was just a casual oversight.

As specified, Haskell is not a pure language because every pattern
match can have side effects.  The Haskell community is split between
those who think that this is a good thing, and those that consider it
problematic.  (Obviously, there is a large pure subset, much more
useful than Erlang's pure subset and covering almost the whole
language; you just avoid lazy I/O and use unsafePerformIO only for
correcting the type of functions imported through FFI.)

In my very limited experience, there are two kinds of laziness:
essential laziness and laziness for presentation purposes.

Essential laziness occurs when you construct values which would not
otherwise be possible to construct in a pure language.  For instance,
if you have got some sort of compiler, at one point, you might want to
perform name resolution.  At that point, you want to translate names
(references) to the program entities they denote (referents).  In
general, these references do not form a tree (for instance, a function
body can refer to another function by name, which refers to the
original function).  With laziness, you can compute a map from names
to entities, and the entities use this maps to resolve the names they
use as references.  Name lookup is only performed once per name.
Without laziness, you have to perform name lookup each time you follow
a reference because the self-referential nature of the data structure
cannot be reflected in the program.

The other type of laziness occurs when you write programs which work
on large (perhaps even infinite) data structures, and carefully look
only at the parts you need.  This can lead to notationally elegant
programs, but you have to be extremely careful not to keep references
to parts you no longer need, otherwise your program will require too
much memory (the live set might even be unbounded).  Space retention
behavior is quite implementation-dependent, too.

It bothers me a bit that you cannot tell the first form from second
just by looking at the types.  You just don't know if the data
structure is bounded or not.