[mercury-users] Present state of type classes - especially for parametrized types

[Jörg Roman Rudnick]

Hi Ralph,

it will be a pleasure to me, here an interesting quote of yourself:

http://www.mercury.cs.mu.oz.au/mailing-lists/mercury-developers/mercury-developers.0009/0216.html 


Another thread on this behalf was initiated by Michael Day:

http://www.mercury.cs.mu.oz.au/mailing-lists/mercury-users/mercury-users.9911/0012.html 


A relevant example of Russell/Norvig (AI - A Modern Approach) could be a 
fringe for a search algorithm, which for instance could be FIFO or LIFO 
buffer. To my present understanding, an aim of typeclasses is to be able 
to provide type-dependent behaviour.

This surely is already possible with tricky discrimitated unions, but at 
the price that all behaviours most be expressed at a central place - 
introducing a new behaviour upon a new type needs changing this code base.

Type classes, on the other hand, allow defining new instances without 
change of type class code and even the type class user code - one just 
passes a new type which is freshly instanced. Also, the syntax seems to 
be intended to be more elegant - one extracts as much info as possible 
out of the instance's type lore...

When passing buffer instances on behalf of the example above, these may 
well contain info about the content type (e.g., intNode vs. stringNode) 
as well as the buffer behaviour (e.g., fifo(...) vs. lifo(...)) - a job 
for type classes?

Although the mailing list threads were not too encouring, my previous 
experiences with the expressive power of Mercury were so motivating I 
decided to give it a try anyway. You yourself noted the two issues that 
seem relevant to me:

(1) 'O-tone R.B.':

 > The empty/0 func causes us some grief, since it doesn't mention T; 
instead
 > we need to jump through a hoop like

 > func empty(T) = S, % T is a dummy arg to make the types work
 > mode empty(unused) = out is det,

 > which isn't very satisfying.

ASSUMED STATE: Impossible at the moment...

Here you seemingly address what the OO world calls factory methods - as 
such usually are only needed once at instantiation, one can live without 
it for a long time... :-)

(2) 'O-tone R.B.' (others discussed similar ideas in the following):
 > But things get worse: in an instance declaration the parameters must 
all be of the form
 > `typename(typevar, ...)', and not just `typevar', which
 > rules out

 > :- instance sequence(list(T), T).

 > Oh deary me! What is needed, as was discussed at the end of last year,
 > is the ability to handle constructor classes, so we could write

 > :- typeclass sequence(S(T)) where [
 > func empty = S(T),
 > func cons(T, S(T)) = S(T),
 > func head(S(T)) = T,
 > func tail(S(T)) = S(T),
 > ...
 > ].

 > and

 > :- instance sequence(list(T)).

ASSUMED STATE: Difficult to say...

While the compiler seems to tolerate parametrized types in typeclasses -
+ func tail(in) = out works, also pred empty(in) is semidet,
+ typeclass declarations allow type variables in predicates not listed 
among the typeclass parameters,
+ instance declarations allow types which are parametrized (inside), if 
an additional typeclass constraint upon the type variables is added,

there seem to be obstacles:
(a) The content type (e.g. intNode, stringNode) cannot be given 
explicitly in a typeclass declaration, applying functional depencies 
does not appease the compiler.

(b) Without a such lore, the compiler seems not to be able to read it 
from the instance declaration (which in fact contains it) - moreover it 
seems to be more serious than just a 'typecast' issue - wrapping a 
typeclass call in an appropriate function lets the compiler finish 
successfully, but seems to produce an endless loop at execution:

In the attached example code, this loop already happens when 
uncommenting '% _First = first2(Q2),'.

(c) By directly calling first/1 (just deleting the '2' at line 66 and 
recompiling), the compiler complains:
fringe.m:054: In clause for predicate `fringe.main/2':
fringe.m:054: error: ambiguous overloading causes type ambiguity.
fringe.m:054: Possible type assignments include:
fringe.m:054: _First: (pred int) or T

(d) At uncommenting 'insert/2' (equivalent to your 'cons/2') already in 
the typeclass & instance declarations, the compiler throws the following 
miraculous error message:
fringe.m:027: In clause for type class method implementation:
fringe.m:027: in unification of variable `HeadVar__3'
fringe.m:027: and term `q_insert(HeadVar__1, HeadVar__2)':
fringe.m:027: type error in argument(s) of functor `q_insert/2'.
fringe.m:027: Argument 1 (HeadVar__1) has type `(some [T] T)',
fringe.m:027: expected type was `(some [T] T)'.

Does this mean existential types are regarded as per se not unifiable?

------------------------

Under the bottom line, I guess what I am trying to achieve is finding a 
'crude way' of having rank two polymorphism with )o+>0.13. I'm afraid I 
was too optimistic - but my experience is is that I do not stop 
discovering new capabilities of Mercury when going this way - poking and 
experimenting. I just didn't want to give up too early - and, the 
temptation is considerable for somebody stepping out of the OO world 
into Mercury.

Of course, I would be interested in what you would consider to be a good 
style solution of this problem at )o+>0.13 - perhaps by other means.

Thank you in advance,

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20061003/150d89db/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fringe.m
Type: text/x-objcsrc
Size: 1589 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20061003/150d89db/attachment.bin>