The dreaded M-R
John Hughes
rjmh at cs.chalmers.se
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.
John
More information about the Haskell-prime
mailing list