[Haskell-cafe] number of references to a variable

[wren ng thornton]

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.

-- 
Live well,
~wren