[Haskell-cafe] Copy on read

Andrew Coppin andrewcoppin at btinternet.com
Sat May 10 08:42:50 EDT 2008

I just had a random idea, which I thought I'd share with you all.

I've heard about systems that do "copy on write". That is, all users 
share a single copy of some structure, until somebody tries to write on 
it. At that moment they get a personal copy to modify so they don't 
upset everybody else. This way, you don't have to go to all the expense 
of copying a potentially large structure unless it's actually necessary 
to do so.

Then I started thinking about Clean's "uniqueness typing". If I'm 
understanding this correctly, it lets you do things like mutate data 
in-place without requiring a monad. The restriction is that the compiler 
has to be satisfied, at compile-time, that you will never try to access 
the old data you just overwrote.

Although I once held more optimistic beliefs, as far as I can tell no 
current, real-world Haskell implementation ever mutates the fields of 
algebraic data types in-place. (Ignoring for a moment the issue of 
overwriting a thunk with it's result.) This strikes me as rather 
pessimistic. I was thinking... 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.

I don't know how viable this would be - the thing that immediately jumps 
out at me is that in practice there might be comparatively few places 
where you can *guarantee* the transformation is safe, and so it might 
not get applied very much. And considering all this would likely take a 
fair bit of work on the compiler, that wouldn't be a great payoff. 
Still, the idea of the compiler transparently rewriting your pure 
functional code to efficient mutable updates (when safe) is very 
appealing for performance reasons.

Thoughts, people? [I'd be surprised if I'm the first person ever to have 
this idea...]

More information about the Haskell-Cafe mailing list