On Mon, Apr 16, 2012 at 11:22 AM, Jonathan S. Shapiro <[email protected]> wrote: > So more on this > > The most common motivations for multiple instances at a single type come > from ordering examples. For example: we want a sorted collection, but one > sorted in reverse of the "natural" ordering. This is a case where we really > want to bind the TC instance explicitly, so we intend to say something like > [making up syntax here] > > struct BTree = > ordering : Ord('a) > root : BTNode('a) > > > the intuition that I'm reaching for here is that we can (sort of) view > Ord('a) as a type, and define a BTree as something requiring an explicitly > provided instance. > > In C/C++, we would have done this by providing an ordering function, and we > wouldn't have seen anything wrong with that solution. Why is it that we > reach for a type class in Haskell or BitC? It's actually kind of disturbing, > because the fact that different idioms are preferred tends to suggest that > we are missing something important here. > > Alternatively, why not parameterize our ordering by up/down: > > struct BTree = > reversed : bool > root : BTNode('a) > > > Or do what we really do: > > struct BTree('a, 'b) = > method insert(key: 'a, value: 'b) -> unit > method remove(key: 'a) -> unit > method lookup(key: 'a) -> 'b > root : opt BTNode('a) > > ordering = Ord('a) => > def CreateBTree() = { BTree(none) } > > > which has the effect of forcing the ordering operation to be inlined > throughout by instantiation. > > I think what's going on here in Haskell/BitC comes down to several different > things: > > We associate the notion of ordering with a type class, so we reach for a > type class solution when we are trying to solve ordering problems > We know that type classes are compile-time constants, and that BTree types > are concretely instantiated. It is therefore true that the last approach > will get us a very efficient encoding. > > But when you stop to think about it, the second point is silly, because > procedures are compile-time constants too. It wouldn't be that hard to do > something like: > > def CreateBTree(instantiate sortfn : 'a x 'a -> bool) -> BTree('a, 'b) = { > } > > > with the intended meaning that the sort function should be instantiated > through when possible rather than carried as a procedure reference in the > closures of the respective method implementations. It's advisory, because we > may not call CreateBTree with a compile-time constant value, but when > possible it is every bit as efficient as the TC-instance approach. > > And there's actually an advantage to the procedure approach, because it > doesn't bind the choice of ordering into the type of the BTree. This leaves > us free to implement a merge function that doesn't care about the orderings > of the input and update trees. > > Initially, I thought that named instance parameters were important so that > we could deal with issues like multiple orderings. But the more I think > about it, the less convinced I am that this is motivated. > > What do people think?
I think this is the right direction, though it's a bit more complicated since procedures aren't always compile time constants due to closures. In the C++ template case, this is handled by passing around function objects which allow the programmer to choose the boundary between compile time and runtime. In a functional language it'd be nice to avoid polluting the type system with this distinction between function objects and functions. In the case of sort, the advantage of passing in a function object instead of a closure transparent to the caller is that it allows the sort function to be partially evaluated without inlining it (if it's inlined everything is easy even with closures). Is it feasible to hint to the compiler that we want certain things partially evaluated without polluting the type system? Geoffrey _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
