[Haskell-cafe] Preventing sharing

[Oleg]

> > Thus "performing a time optimization
> > which is a space pessimization" is exactly what laziness is all about
> > -- as the article mentioned earlier argued. Laziness isn't an absolute
> > good -- it is a time-space trade-off, which is not always beneficial.
>
> I don't agree at all.  To my mind you are assigning blame to the wrong
> thing.  The operational semantics of
>
>     f () = let x = <a large lazy structure> in ...
>
> are perfectly clear.  x is reallocated each time, and is free to be released
> between calls to f.  It's only when an "optimization" rewrites this to
>
>     x = <a large lazy structure>
>
>     f () = ...
>
> that there is a space leak.  Exactly the same applies if the language is
> strict.

Let us take a step back. The article on my web page noted the great
difficulty of writing AI search program in Haskell because the search
tree is evaluated lazily: whenever a node is evaluated, its result is
memoized for further use. That is precisely the wrong thing to do for
such problems. Again, this problem is precisely of lazy evaluation (as
defined in the book below). The obvious way to avoid memoization was
to introduce thunks -- which didn't work. The article then developed a
more involved solution. Yes, -no-full-laziness would have worked just
as well. However, the solution in the article works on the
case-by-case basis whereas -no-full-laziness affects the whole
compilation unit. It is for that reason that I pointed out the article
in this discussion.

Let us turn to the problem of the "optimization" that we are
discussing. Does it have anything to do with laziness? Yes, it
does. Please see Chap 15 of the excellent book

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

which explains the full laziness.

Once I mention the book I must point out Chap 23 of the book (near the
end). It should be the required read. The introduction to the section
contains the following emphasized statement (emphasized by the author,
Simon Peyton Jones):

   A major weakness of functional languages is the difficulty
   of reasoning about their space and time behavior.

The last paragraph of the introduction says ``No good solutions
are yet known to most of these problems.'' This is true even
today. Sec 23.3 ``Space behavior'' is the excellent collection of the
problems with lazy evaluation and full laziness. The book was
published in 1987. The problems are still with us.