Copy on read

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...]

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe