[Haskell-cafe] Copy on read

[Malcolm Wallace]

> If Haskell had uniqueness typing, maybe the compiler could be made  
> to infer when values are used in a unique way. And maybe if the  
> compiler can detect data being used in a unique way, it could code  
> for in-place updates instead of copying, and thereby gain a  
> performance advantage.

Uniqueness typing does not lead to in-place update.  If a value is  
only used once, then there is no need to update it at all!  In fact, I  
believe ghc does this analysis, and has a minor optimisation that  
omits the thunk-update.  That is, if an unevaluated thunk is forced,  
but it has a unique usage, the original thunk is not overwritten with  
an indirection to the reduced value (as it normally would be), but the  
reduced value is just used directly.

I believe that rather than _uniqueness_, you are really trying to  
describe _linear_ usage, that is, multiple uses, but in a single non- 
branching sequence.  Single-threaded usage of a data structure might  
permit in-place modification of its parts.  The analysis for linear  
usage is much more difficult than for uniqueness, and David Wakeling's  
PhD Thesis "Linearity and Laziness" (circa 1990) did some experiments,  
but was ultimately pessimistic about the value.

Regards,
    Malcolm