Hi
You're not the first:
Jurriaan Hage and Stefan Holdermans. Heap recycling for lazy
languages. In John Hatcliff, Robert Glück, and Oege de Moor, editors,
_Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation
and Semantics-Based Program Manipulation_, PEPM'08, San Francisco,
California, USA, January 7--8, 2008, pages 189--197. ACM Press, 2008.
http://doi.acm.org/10.1145/1328408.1328436.
Like I said to them in private mail - nice idea, but without
benchmarks its only an idea. You have to consider effects of cache,
generational garbage collection, complexity etc. I think they are
going to do the benchmarks at some point, when we'll know if the idea
was a good one.
Thanks
Neil
On Sat, May 10, 2008 at 1:42 PM, Andrew Coppin
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe