The dreaded M-R

John Hughes rjmh at
Mon Jan 30 08:07:22 EST 2006

    it would also be possible to require the compiler 'memoize' all top
    level bindings on their type parameter. then the problem goes away, but
    at the cost of hiding some machinery under the hood. however the type
    analysis pass mentioned above would often be able to discard of this
    'under the hood' memoization and.

We discussed this idea when Haskell was first designed. The trouble is,
there's an awful interaction with space leaks. 

Imagine you have a binding

	let x = ...e1... in ...e2...

where e1 contains pointers to some large structure, and then somewhere in e2 
you need to drop those pointers. You write x `seq` ... at the place where you
want to drop the pointers, right? (Assuming the pointers are no longer
referred to from x's value). Wrong! If x is overloaded, then you've only
forced the evaluation of *one instance* of x, and e1, together with the 
structures it points to, have to be retained in case you ever evaluate a
*different* instance of x in the future! Memooising x on its type makes no
difference to this: you have to retain e1 until every possible instance of
x has been evaluated. If there's a fixed finite number of possibilities
then this might be possible, if awkward ((x::Integer)`seq` (x::Float)`seq`...),
but if there are infinitely many possible instances then you're screwed.

So if it is to be *possible* to fix space leaks, then memoisation is not
a good alternative to shared bindings.


More information about the Haskell-prime mailing list