[Haskell-cafe] Copy on read
malcolm.wallace at cs.york.ac.uk
Sat May 10 13:31:48 EDT 2008
> 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.
More information about the Haskell-Cafe