[mercury-users] Modules, Submodules and Instances.

[Fergus Henderson]

On 30-Jan-1999, Ralph Becket <rwab1 at cam.sri.com> wrote:
> Following on from the recent discussion, I think I may have found a
> bug in the compiler.
> 
> I've been having a go at the battleships challenge.  Now, I have the
> following modules:
> 
> main.m		- imports battle & rwab1, exports main.
> battle.m	- defines player/1 typeclass and exports game engine.
> rwab1.m		- defines various instances of player/1.
> rwab1.silly.m	- implementation of silly player.
> rwab1.human.m	- implementation of human player; uses rwab1.view.
> rwab1.logging.m	- implementation of logging player.
> rwab1.view.m	- implementation of game board ADT.
> 
> But I'm getting a very odd error message from the compiler at link
> time:
...
> Undefined                       first referenced
>  symbol                             in file
> mercury_data___base_typeclass_info_batt:player_1 Mercury/os/main.o
> mercury_data___base_typeclass_info_batt:player_1 Mercury/os/main.o

There's two bugs involved here.  One is that the demangler is not
properly demangling the names for instance declarations involving
nested modules.  This makes the error message rather incomprehensible.
The actual undefined symbols are
	mercury_data___base_typeclass_info_battle__player_1__rwab1_0_silly_0_
	mercury_data___base_typeclass_info_battle__player_1__rwab1_0_human_0_
which should demangle to something like
	<instance declaration for battle:player(rwab1:silly/0)>
	<instance declaration for battle:player(rwab1:human/0)>
	
That one should be reasonably simple to fix, I think.

The other bug is more complicated, but in short the problem
is that instance declarations for exported abstract equivalence types
don't work.  We actually discovered this one a while ago,
but we still haven't decided what to do about it.  Here's what
I wrote about it when we first realized the problem, interspersed
with a little additional commentary:

Fergus Henderson <fjh at cs.mu.oz.au> wrote:
> Tyson Dowd <trd at cs.mu.OZ.AU> wrote:
> > If you have an instance in module x:
> > 	:- module x.
> > 	:- instance foo(bar).
> > 
> > and bar is an abstract equivalence defined in the implementation of
> > x:
> > 	:- implementation.
> > 	:- type bar == floobie.
> > 
> > then the compiler will create a base_typeclass_info__....foo_1__floobie_0
> > declaration for the instance.
> > 
> > But in another module, y, that imports x, it will create references to
> > base_typeclass_info__....foo_1__bar_0 which leads to a link error.
> > 
> > Workaround is to define bar as a no-tag type, e.g.
> > 	:- type bar ---> bar(floobie).
> 
> This is a difficult language design issue.
> There are several possibilities:
> 
> 	1.  Disallow instance declarations for abstract equivalence types.
> 
> 	    Drawbacks: abstract equivalence types are no longer first-class.
> 	    Users may well want to define instance declarations for types
> 	    such as `map(K,V)', indeed the Mercury language reference manual
> 	    uses that type as one of its examples.  If instance declarations
> 	    were disallowed for such types, then it would become bad style
> 	    to ever declare such a type.  So if we're going to do this,
> 	    then we might as well go with possibility 2 (below).
> 
> 	2.  Disallow abstract equivalence types.
> 
> 	    Drawbacks: breaks backwards compatibility.
> 	    Also, users have to use "no-tag" types instead, which is less
> 	    convenient -- they need to do lots of wrapping and unwrapping
> 	    to get the types right.

BTW, a "no-tag" type is a type with one functor which takes one argument:
instead of
	:- type foo == bar
you use
	:- type foo ---> foo(bar).

Note that there's usually no efficiency cost in doing this,
the compiler will generate pretty much the same code.
But it does make the source code a bit more cluttered.

> 	3.  Allow instance declarations for abstract equivalence types.
> 
> 	    If we allow them, then we need to decide on the semantics.
> 	    It's difficult to figure out a semantics that makes sense,
> 	    doesn't lead to lots of overlapping instance declarations,
> 	    and that is easy to implement.  Some seemingly simple
> 	    approaches make cross-module optimization much harder.
> 
> Of these possibilities, I think that number 1 is (by a small margin)
> the least worst.
>
> If we go with number 1, then the behaviour of the current implementation --
> reporting an error at link time -- is correct.  The only thing that needs
> changing is the language reference manual.
> We could also try to improve the quality of the diagnostic.

Number 1 is also the approach used by Haskell, and it's also probably
the most conservative approach, so I'm inclined to go with it, at least
for now.

Hmm, thinking about it a bit more I see there is another possibility:

 	4.  Extend the language to support abstract instance declarations,
	    and allow abstract instance declarations for abstract
	    equivalence types, if those declarations occur in the interface
	    of the module defining the abstract equivalence type.
	    For an equivalence type `:- type foo == bar',
	    the instance definition for `foo' would implicitly be the same
	    as the instance definition for `bar' (and if there was no
	    instance definition for `bar' visible in the module's
	    implementation section, you should get a compile error).

	    This approach means that equivalent types always have equivalent
	    instance definitions, so it avoids the problems that approach 3
	    has with overlapping instance definitions and cross-module
	    optimization. 

	    On the other hand, it still has has most of the same drawbacks
	    as approach 1, because abstract instance declarations are not
	    first class.  <Sigh>.

So, any comments/suggestions?

In the absence of any other feedback, I'll go with approach 1 for now, and
change the language reference manual accordingly.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.