If anybody has strong objections, we need to hear them!
The current BitC specification has two undersirable restrictions around
type class instances:
1. Type class instances may not overlap. In consequence, you cannot
define an instance for (Foo alpha) and then a more specialized
instance for (Foo char). There are unusual but well-motivated cases
where this is highly desirable.
2. Type class non-interference is required on a whole-program basis.
This is immodular, and it cannot be checked at compile time. This
is a huge impediment to separate compilation, and it is impediment
to scalability of engineerable programs.
Two days ago, Swaroop and I considered the possibility of imposing
lexical scope on instance resolution, both because it resolves the
separate compilation issue [2] and it also resolves [1] by imposing a
well-defined lookup order.
Unfortunately this doesn't work if it is done naively. The problem with
it is that my library will never be able to see your specialized type
class instantiations, because my library didn't import your
instantiations and they are therefore not in my library's lexical scope.
As I thought about this, I realized that the "classic" typeclass
implementation using dictionaries resolves all of this very nicely, and
I simply had not noticed. What that implementation does is require the
caller to (implicitly) supply a dictionary that defines a method table.
The lexical scoping rule can then be brought to bear consistently at the
point of dictionary instantiation. Since the dictionary is carried into
the library as a parameter, the library uses any specialized
instantiations that were in scope at the point where the call was made.
I definitely do NOT want to move BitC in a direction that requires a
dictionary-based implementation, but I would like to make such an
implementation legal, and I would like to define the resolution of
instances in a way that is consistent with such an implementation.
So: I'm proposing to eliminate the instance non-collision rule in favor
of the following two rules:
Instances are resolved by lexical lookup at the point where
the associated qualified types are resolved. These resolutions
propagate across any applications.
When an instance is resolved, the lexically innermost instance
that unifies with the instantiated type is selected. This means
that in:
(defTC (myTC 'a) ...)
(defInstance (myTC 'a) ..general implementation..)
(defInstance (myTC 'b) ..second general implementation..)
(defInstance (myTC char) ..specialized implementation..)
(forall (myTC 'a) (define (f x:'a) ...)
1. The second defInstance "shadows" the first one. It is ill-advised,
but it is not an error.
2. If /f/ is instantiated over /char/, it will bind the last instance,
but it /f/ is instantiated over anything else, it will bind the
instance over 'b.
The tricky bit here is to get the "point of binding" definition stated
rigorously, and I'm going to sketch a way in my next note.
Oh. It also means that we will need to introduce an instance naming
scheme to deal with import issues.
[Note: if we adopt this, it almost certainly won't make it into the
upcoming zero'th release!]
shap
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
