[bitc-dev] Moose, rugs, and separate compilation

Swaroop Sridhar swaroop at cs.jhu.edu
Fri Mar 6 15:08:14 EST 2009


Sandro Magi wrote:
> Jonathan S. Shapiro wrote:
>> So the problem in the large is separate compilation, in the sense of
>> "separated by an air gap". If we want to support modules written by
>> truly unrelated development groups, we need a way to survive colliding
>> instances. The only way that I can really see to do that is by using
>> lexical scoping, but lexical scoping in the presence of polymorphism
>> is a very strange thing.
>>
>> The issue is that you have a call to f() that in turn calls g() in
>> some other module. Both modules have an instance in scope for (EXAMPLE
>> (list char)), but they are not the same instance.
>>
>> The question is: which instance should be used in the compilation of
>> g()? That is: which lexical environment should be used to decide what
>> instance to use? There is truly no right answer to this.
> 
> Let's suppose we're dealing with an Eq 'a type class. Suppose f knows
> the concrete type of the list it's dealing with, list char. Suppose that
> g does not, and handles list 'a.
> 
> I would expect the answer is to transitively use whatever instance f
> specifies. In other words, the beginning of the call chain where the
> type class is first required dominates. I think of type classes as
> abstracting vtables, so f is the one building the vtable being passed to
> g, so g should be slaved to f.
> 
> In pseudo-code:
> 
> typeclass Eq 'a with
>   eq: 'a -> 'a -> bool
> 
> val f: list char -> bool
> val g: Eq 'a => list 'a -> 'a bool
> 
> (* f builds the vtable passed to g, so the "Eq char" instance
>  * in f's scope would seem to be the most straightforward answer.
>  *)
> let f list = g list '\n'
> 
> To be consistent, I think the same reasoning should apply if both f and
> g are monomorphic. g is accepting an Eq char from f, so f should specify
> the behaviour of Eq char. Hopefully I'm not missing anything obvious.

So, the rule is we use is that all instances in scope at any point of
time can be used, but the instances at the callee override the instances
of the caller, right?

One issue that I think we must consider here is the effect on
optimization, similar to the effect of vtable dispatch.
For example, if different instances of Eq char are defined in the
modules where f and g are defined, the instance at f overrides the one
in g. So, the (== 10 20) expression in g cannot be optimized at compile
time (even if a satisfying instance is available) since its meaning
differs with respect to different calls. We can only perform these
optimizations at link time.

Swaroop.



More information about the bitc-dev mailing list