[mercury-users] Modules, Submodules and Instances.

[Fergus Henderson]

On 01-Feb-1999, Ralph Becket <rwab1 at cam.sri.com> wrote:
> Fergus Henderson wrote on  1 Feb:
> > Fergus Henderson <fjh at cs.mu.oz.au> wrote:
> > > [Re problems with instance declarations for abstract equivalence types.]
> > > 
> > > 	1.  Disallow instance declarations for abstract equivalence types.
> 
> Oh God no!

Well, that's the solution that Haskell adopts, and Haskell programmers
seem to tolerate it, so it can't be *that* bad.

> > > 	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.
> 
> Do the semantics get confused if we do the following?  Whenever the
> compiler sees an abstract equivalence type with an instance
> declaration, it silently turns it into a no-tag type by gensym'ing up
> a constructor? That is,
> 
> 	:- interface.
> 	:-	type t.
> 	:-	instance foo(t).
> 	:- implementation.
> 	:-	type t == u.
> 
> Is detected and translated into
> 
> 	:- interface.
> 	:-	type t.
> 	:-	instance foo(t).
> 	:- implementation.
> 	:-	type t == really_unique_constructor_name_123(u).

I think you mean

 	:-	type t ---> really_unique_constructor_name_123(u).

> by the compiler which then puts in the extra bits of syntax wrapper
> around all predicate/function arguments declared to be of type t, so
> 
> 	:- pred p(t, ...).
> 	p(T0, ...) :-
> 		...,
> 		p(T, ...).
> 
> becomes
> 
> 	:- pred p(t, ...).
> 	p(really_unique_constructor_name_123(T0), ...) :-
> 		...,
> 		p(really_unique_constructor_name_123(T), ...).
> 
> This would save source code from becoming needlessly messy.

Well, the first problem with that suggestion is this: what do you do
if the argument has type `list(t)' or `pred(t)' rather than `t'?
However, that problem is easy to solve, by using a slightly different
translation:

 	:- pred p(foo(...t...), ...).
 	p(F0, ...) :-
 		...,
 		p(F, ...).

becomes

 	:- pred p(foo(...t...), ...).
	p(A0, ...) :-
		A = unsafe_cast(A0),
		'$impl_p'(A, ...).

 	:- pred '$impl_p'(foo(...t...), ...).
 	'$impl_p'(F0, ...) :-
 		...,
 		'$impl_p'(F, ...).

In other words, every call to 'p' from within the module becomes a call
to '$impl_p', which is exactly the same as the original definition of
'p' except that its argument types have had the equivalence type
expanded.  'p' itself then becomes just a wrapper predicate which casts
the arguments to the expanded type and then calls '$impl_p'. 
(Of course here I am talking about what the implementation would do;
the definition of the semantics in the language reference manual would
have to specify the semantics of the type conversion without referring
to unsafe_cast/1.)

The second and probably more serious problem with your suggestion is
that it could result in some counter-intuitive effects.  The semantics
of a particular piece of code could differ depending on what module
that code occurred in.  For example, consider a predicate with an argument
whose declared type is the abstract equivalence type, and which calls
some type class methods using that argument.  If the definition of that
predicate occurs in the module which defined the abstract equivalence
type, or any of that module's children, then any type class method call
will use the instance declarations for the expanded type (e.g. 'u' in
the example above), whereas if it occurs in some other module, then any
type class method call will use the instance declarations for the
unexpanded type ('t' in the example above).  It seems rather unfortunate
for a method call to do different things depending merely on which module
it occurs in.

In other words, the syntactic simplicity that you would gain from
this proposal would come at a price -- the cost would be increased
semantic complexity of the language.  It's not entirely clear
whether the benefit would be worth the cost.

Note that in general, having a method call do different things
depending on which module it is in certainly has the potential to make
cross-module optimization more difficult.  However, the transformation
scheme above would be sufficient to solve that, so long as the
cross-module optimization is applied to the transformed program rather
than the original one.

The final problem, of course, is just that it would not be trivial to
implement.  So for the time being at least, I am still inclined to go
with the conservative (and easy to implement) solution:

	1.  Disallow instance declarations for abstract equivalence types.

We can reconsider this at a later date.


Well, that's my opinion.  But comments on all this would be most welcome.

-- 
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.