On Fri, Mar 09, 2007 at 10:58:43AM -0500, Jan-Willem Maessen wrote:
* Linear or Uniqueness types are almost what we want. I think Josef Svenningson was the one who captured this the best: Uniqueness type *require* that the *caller* of these routines make sure that it is not sharing the data. So we need two copies of our linear algebra library---one which takes unique arrays as arguments and updates in place, and one which takes non-unique arrays and allocates. And we have to pick the right one based on context. What we want, it seems to me, is one library and a compiler which can make informed judgments.
wansbrough's simple usage polymorphism paper details an analysis that infers types that are 'polymorphic' in their usage qualities. The paper brings up the possibility of generating specialized versions of functions 'usage-specialization' based on these types. which seems to be exactly the sort of thing you would want out of a compiler for the above. http://citeseer.ist.psu.edu/292462.html it would also seem like it would be possible to actually pass these usage types at run-time and choose operations based on that. This seems like it would be an ideal way to go, it would behave in a very predictable way for haskell programmers used to type specialization and haskell classes and the middle-end work wouldn't be as much as system f is already typed and these usage types would behave like other type variables in a lot of ways after their initial inference. usage specialization could occur via the same RULES mechanism that type specialization uses now...
I'd love to hear if anyone has insights / pointers to related work on any of the issues above; I'm especially keen to learn if there's work I didn't know about on fusion of multiple traversals. In my day job with Fortress we are looking at RULES-like approaches, but they founder quickly because the kind of problems David is trying to solve are 90% of what our programmers want to do.
I think the simple usage polymorphism paper (and the thesis that goes along with it) can provide some fertile ideas for exploration here.. John -- John Meacham - ⑆repetae.net⑆john⑈