[bitc-dev] Instance coherence: the shape of a solution

Sandro Magi naasking at higherlogics.com
Mon Apr 16 10:48:12 PDT 2012

On 16/04/2012 12:25 AM, Jonathan S. Shapiro wrote:
> It is permitted to have overlapping, open instances in a single
> resolution contour. It is /not/ permitted to have two precisely matching
> instances in a single resolution contour. Ambiguous instance matches are
> resolved by adopting the /latest/ open instance in the resolution
> contour. Thus:
>    instance TC('a, 'b) { ... }  // fine
>    instance TC('a, int) {...} // okay - /partially/ shadows previous
>    instance TC(char, char) {...} // okay - /partially shadows /previous
>    instance TC(char, char) {...} // error - /fully/ shadows previous
>    instance TC(int, 'a) {...} // okay - ambiguous at TC(int, int), but
> preferred as the later resolution
> Note that because of the opening process, an instance declared in a
> distant module cannot impact the behavior of my module without my
> consent. The notable exception to this is instances declared and opened
> in the preamble, because all preamble imports are performed as opening
> imports.

I think this can be refined further. Typed multiple dispatch languages
force overloads to form a semi-lattice [1], so:

  instance TC('a, 'b) { ... }
  instance TC('a, int) {...}
  instance TC(int, 'a) {...}

Is inherently ambiguous, and would require a module importing both to
also have the following instance in scope:

  instance TC(int, int) {...}

"Latest match wins" might be ok if the *exact* same overload is
redefined, although I'm a little wary of that.

Another proposal to solve overlapping instances is "instance chains"
[2]. I thought I had mentioned this work on the list before, but a quick
search didn't turn anything up. This type class proposal was made for
the Habit language.


[1] http://www.mpi-sws.org/~skilpat/papers/multipoly.pdf
[2] http://web.cecs.pdx.edu/~jgmorris/pubs/morris-icfp2010-instances.pdf

More information about the bitc-dev mailing list