[mercury-users] Mercury applications, AI, backtracking

[Fergus Henderson]

On 14-Sep-1998, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> Laziness makes the operational semantics much more complicated (and the
> optimizations to avoid laziness make it even more complicated, and less
> predictable).

To illustrate this point, let me quote the following article which was
just posted to the Haskell mailing list.

 | Date: Mon, 14 Sep 1998 04:39:38 +0200
 | From: Martin Stein <ms40 at inf.tu-dresden.de>
 | X-Mailer: Mozilla 4.05 [en] (X11; I; Linux 2.0.33 i586)
 | To: haskell mailing list <haskell at dcs.gla.ac.uk>
 | Subject: heap exhausted
 | 
 | Hi,
 | 
 | though I think there was written enough about this theme, I can't still
 | understand the following problem (foldl' from the Prelude.hs):
 | 
 | > seq1 x = (3-x):seq1 x
 | > seq2 x = (3-x):seq2 1
 | >
 | > countOne xs = foldl' (\c x -> if x==1 then c+1 else c) 0 xs
 | >
 | > num1 n = countOne (take n (seq1 1))
 | > num2 n = countOne (take n (seq2 1))
 | 
 | num1 needs lots of heap space, num2 needs very few. Why?
 | (I checked it using ghc and '+RTS -s')

Reasoning about space usage of lazy functional programs seems to be
very difficult.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.