On Tuesday 06 December 2005 04:00 pm, haskell-cafe.mail.zooloo@xoxy.net wrote:
From: "Shae Matijs Erisson - shae@ScannedInAvian.com" Sent: Tuesday, December 06, 2005 6:16 PM
haskell-cafe.mail.zooloo@xoxy.net writes:
being occupied with learning both languages, I'm getting curious if Haskell couldn't achieve most of the performance gains resulting from uniqueness typing in Clean by *automatically* determining the reference count of arguments wherever possible and subsequently allowing them to be physically replaced immediately by (the corresponding part of) the function's result. Are there any principal obstacles, or *could* this be done, or *is* this even done already, e. g. in ghc?
Maybe you're describing speculative evaluation?
Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs http://citeseer.ist.psu.edu/ennals03optimistic.html --
Thanks for the pointer - I have heard a little about optimistic evaluation already, but don't know much of the details (yet). Anyway, from what I know, I think it's a different thing.
In Clean, you can (and often are required to) assign uniqueness attributes to some parts of a function's type signature. The extended type checker ensures that none of those parts is referred to more than once during a single run of the program. Based on this guarantee, a function does not have to allocate new memory at all to store a unique result but can overwrite the unique arguments in place.
Apparently, the uniqueness assignments have to comply with very tight laws - getting a program through the Clean type checker can be tough, once it reports an uniqueness coercion error. I suppose, no explicit uniqueness attributing is going to be implemented in Haskell, anyway.
My question is - and this might better suit to Haskell -, can't uniqueness be inferred (and exploited) automatically in many cases?
Yes, probably. There is a technique called sharing analysis that attempts to determine when a datastructure is only referenced once (ie, NOT shared). If you can prove a datastructure node is not shared then you can reuse it destructively. Here is a paper on the technique. It's written for lisp cons cells, but one might be able to generalize the technique to ADT. I don't know where to find a free copy. http://portal.acm.org/citation.cfm?id=99375 There has also been some similar work done along these lines for Mercury (a logic programming language). http://www.cs.mu.oz.au/research/mercury/information/papers.html Search for papers with the word "reuse" in the title. I'm not very familiar with this work, so I don't know how applicable this might be.