[mercury-users] Type inheritance?

[Tyson Richard DOWD]

John Griffith wrote:
> Just started trying to write a small program in mercury.  Getting the
> hang of it, but I'm not quite clear on the type system.
> 
> Is there any way to get inheritance of types?
> 
> For example, I have some type declarations like:
> 
> (1)
> 
> :- type ft
>    ---> bot
>    ;    typ(typ)
>    ;    feat(string,ft)
>    ;    and(ft,ft)
>    ;    or(ft,ft)
>    ;    not(ft).
> 
> :- type typ
>    ---> top
>    ;    a
>    ;    b.
> 
> which is fine, except I'd really like to get rid of the typ/1
> constructor in the declaration for ft.  Essentially I want to write
> something like this instead:
> 
> (2)
> 
> :- type ft
>    ---> bot
>    ;    { typ }
>    ;    feat(string,ft)
>    ;    and(ft,ft)
>    ;    or(ft,ft)
>    ;    not(ft).
> 
> :- type typ
>    ---> top
>    ;    a
>    ;    b.
> 
> and have it be equivalent to having written:
> 
> (3)
> 
> :- type ft
>    ---> bot
>    ;    top
>    ;    a
>    ;    b
>    ;    feat(string,ft)
>    ;    and(ft,ft)
>    ;    or(ft,ft)
>    ;    not(ft).
> 
> I want to define predicates with arguments of type typ but call them
> with arguments of type ft.

This is something like an undiscriminated union, or (as you've pointed
out in your other mail) perhaps subtyping.
We don't have them in Mercury, you need to use a constructor such as
	typ(typ)
as you have in (1). You could also do subtyping with the mode system,
by declaring a 'typ' inst - this often works well. I think the language
reference manual has an example of this.

We are not working on subtyping at the moment - typeclasses are on the 
verge of implementation, and I think it would be best to use them for a
while before considering other changes to the type system.

> 
> Is this possible?  If not, then is there a cost associated with the
> constructors or do they get "compiled away"?  In other words, is there
> an efficiency difference between (1) and (3)?
>

Yes there is a difference. It's difficult to say whether (3) is more
efficient, however, because you have a large number of constructors, so
some constructors would be allocated using a secondary tag (e.g. a
tagged pointer to a vector whose first word is another tag, and
subsequent words are arguments - uses one extra word, whereas (1)
involves one extra dereference). At least, on a 32-bit machine this
would happen. On a 64-bit machine we get 3 tag bits, so it would
probably be more efficient. But it's a probably a pretty slim
difference...

Is this causing efficiency problems in your code, or are you just
curious?

-- 
       Tyson Dowd           #          Another great idea from the 
                            #            people who brought you
      trd at .cs.mu.oz.au      #               Beer Milkshakes!
http://www.cs.mu.oz.au/~trd #	         Confidence --- Red Dwarf