memoization hints

David Feuer
Wed, 23 Jan 2002 04:13:16 -0500 (EST)

(sorry I can't reply directly, but my mail situation is a bit messed up)

Simon Marlow said:
> Take a standard sort of example:
> fib n =3D let
>                 f =3D 0:1:zipWith (+) f (tail f)
>            in
>                 f !! n
> -- code that first calculates fib 1000, then fib 3, fib 4, then does
> some other stuff
> I believe that the entire list will be maintained (when compiled with
> ghc -O) after calculating fib 1000, despite the fact that it=20
> will never
> be used again.

GHC will retain the list only if it determines that it might still be
required, in other words if fib might be called again.  If fib will
never be called again, then the chances are that the list will be
garbage collected. (I'm being intentionally imprecise, because of course
the compiler can't in general determine accurately whether fib will or
will not be called again).=20

If you don't want the list to be retained at all, you can use the
-fno-full-laziness flag to GHC.  Unfortunately there's no way to do this
at the level of a single binding.


What I was talking about was whether it would be possible/practical to
extend the language to allow this control at the single-binding level.
This kind of control seems useful even without full laziness, but with
full laziness it becomes essential--it is no longer possible to hide
something in a function to prevent it from being persistent, and as all
here know, it is often much better to compute values of a list over and
over than to store the whole list in memory.  This seems to require some
weird form of garbage collection, where an accessible object which may be
used again is collected.  It is necessary, however, to ensure that enough
information is retained to be able to reconstruct the value when
necessary.  I don't know nearly enough about GC to say what this might
involve, but I'd be interested to hear what other people think about this
problem, this (vague) solution, and perhaps other solutions.

/Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72
400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor
fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m
(brought to you by the)m(letter alpha and the number pi.)m(David Feuer)
m( showpage