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?
shap
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
