[mercury-users] polymorphism

[Tyson Richard DOWD]

Tomas By wrote:
> Hi all,
>
> Thanks for the replies Tyson, Fergus. I'm not really sure
> you answered my question, because I'm not sure what I'm
> trying to ask. :-)
>
> So I'll explain the problem. Any feedback appreciated. At
> this point I'm interested in elegant design rather than
> efficiency.
>
> I'm writing an XML library. The interface consists of a
> document type and procedures to read/write/validate etc.
> The problem with XML documents is that apps might want to
> treat them either as a stream of elements or as a tree
> structure, and that you sometimes want to preserve
> whitespace and sometimes not.
>
> So you need four different types:
>
>    stream with whitespace            [ stream(byte) ]
>    stream without whitespace         [ stream(word) ]
>    tree with whitespace              [ tree(byte) ]
>    tree without whitespace           [ tree(word) ]
>
> My solution is to have 'list(item(V,T))' as the document
> type, declared as follows.
>
> --------------------------------------------------------
> :- type item(V,T) ---> v(V) ; token(T) ; spec(spec) .
>
> :- type s(_) ---> start_tag(string,list(attribute))
>                 ; end_tag(string)
>                 .

I'm a bit confused about this type - why have a type parameter if you're
not going to use it?

>
> :- type t(T) ---> element(string,list(attribute),tree(T))
>                 .
>
> :- type bs_item = item(s(byte),byte).
>
> :- type stream(T) = list(item(s(T),T)).
> :- type tree(T) = list(item(t(T),T)).
>

Hmm, you're missing some type definitions (what's v? where's token?).
Anyway, you use item with the first type as s(T) or t(T) or s(byte).
s doesn't use it's type parameter anyway.

Fergus's redefintion of item is would probably make it a bit clear
what is going on.

>
> I want a procedure 'dump' for example that can handle all the
> four types above. The reason I don't want it to handle other
> things is I don't want to write the code. :-)

Ahhh... so you really want p/1 to be overloaded, so that it can handle
those types.

Fergus has discussed the type-class emulation approach, and just
encoding tokens and using insts to do subtypes, or do runtime subtype
errors.

One other possibility is to use univs.

You can still turn those types into a single type, and
write dump code that does a test (it tests which of the 4 combinations
it is, and then handles it accordingly).

Or, you can use runtime type checking, using the type 'univ'.

For example, the code for io__print does something like this:

io__print(Term) -->
        % `string', `char' and `univ' are special cases for io__print
        { type_to_univ(Term, Univ) },
        ( { univ_to_type(Univ, String) } ->
                io__write_string(String)
        ; { univ_to_type(Univ, Char) } ->
                io__write_char(Char)
        ; { univ_to_type(Univ, OrigUniv) } ->
                io__write_univ(OrigUniv)
        ;
                io__print_quoted(Term)
        ).

By converting the type to a univ, you can then do runtime type checks
by trying to convert it back to a type. The calls to univ_to_type are
semidet, if the type of the second argument is the same as the type
stored within the univ, it succeeds, and binds the second argument to
the value stored within the univ. The compiler figures out what type the
second argument is using type inference - in this case the calls
	io__write_string io__write_char and io__write_univ
make the inference pretty easy.

This is a bit hacky, and you shouldn't do it except in situations where
	- you want to handle a few special types specially, and others
	  in a generic fashion
	- you are likely to need to extend the predicate to deal with
	  other types in future.
	- you have a predicate which needs to _exclude_ types from
	  being handled.

(It's actually a lot more useful when you have typeclasses, then you
can do a conversion to a typeclass -- you can use this to do "feature
tests", ie "if this type has 'foo' defined for it, do foo").

>
> In general, if I have a procedure with several modes, eg:
>
>   :- pred stream_tree(stream(T),tree(T)).
>   :- mode stream_tree(in,out) is det.
>   :- mode stream_tree(out,in) is det.
>
> but I can't use the same code for both modes, how do I write
> the "top-level"?

You can't. You need to use the same logic for all modes (unless it's
written in C using `pragma c_code'. If they are done using different
logic, its best to write two different predicates.

(The reason this isn't allowed is that you might not write two logically
equivalent pieces of code for the procedure, but the compiler may assume
that the code is equivalent when doing transformations or optimisations).

The techinque Fergus mentions is a way of getting around this that is
still logical, and has very little overhead.

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