[Haskell-cafe] number of references to a variable
wren ng thornton
wren at freegeek.org
Sun Nov 2 15:06:31 EST 2008
Alberto G. Corona wrote:
> * "Certainly a worthy research goal, but probably not what you had in mind
> *Not at all, My interest on that was on to improve RefSerialize. Although
> the Clean people has done a superb job on optimization. By the way, I'm not
> sure if uniqueness is the cause of his performance. I tested Haskell code
> generated using Maybe with and without monad instance and the monad does not
> impose any overhead at all.
Oh, I wasn't saying that monads impose any overhead. Rather, the Clean
folks aren't fans of monads and so they use uniqueness typing in order
to provide the same kind of solution to IO while retaining functional
purity. GHC's implementation of IO is actually very similar under the
hood to what Clean does, though that's not necessarily true of other monads.
Even though they seem to intersect at IO, the ideas of monads and linear
logics are orthogonal. The big optimization trick with linear logic is,
since you know when some object is uniquely referenced, you know when
it's safe to destructively update it in situ. For example, you can
reverse a spine-unique list in linear time with zero space (modulo
registers) by just inverting the spine pointers as you traverse it.
Since it's uniquely referenced, noone else will notice so referential
transparency is preserved. Doing it this way saves on allocation costs
and on garbage collection.
There are certainly other ways to use the information that some object
is held only by a single reference, but Clean's optimizations are the
first that leap to my mind.
More information about the Haskell-Cafe