[m-rev.] for review: user-defined comparison

[Mark Brown]

Hi,

I've only reviewed the design and some of the documentation so far.
I haven't yet reviewed any of the code.

On 29-Oct-2002, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> Estimated hours taken: 20
> Branches: main
> 
> Allow user-defined comparison functions using the syntax
> :- type t ---> t where equality is t_equal, comparison is t_compare.
> .
> Allow user-defined equality and comparison for foreign types using the syntax
> :- pragma foreign_type(c, t, "c_t") where
> 		equality is t_equal, comparison is t_compare.

> library/builtin.m:
> 	Add types and insts to allow declaration of user-defined
> 	comparison predicates using `with_type` and `with_inst`.
> 	We already have types and insts `builtin__comparison_pred',
> 	but they have a different argument ordering to `compare/3'.

Yes, you should define new types for "user-defined" comparison because
the existing types are for "user-supplied" comparison (that is, a
comparison argument that is explicitly passed in).  Aside from the
different argument order, a good reason to keep these concepts
distinct is that the constraints we place on user-defined orders
are likely to be stronger than the constraints we place on user-supplied
orders.

The reason the latter may be more general is that they are not used in
as many places as the former: user-defined comparison can be used anywhere
that standard comparison is, whereas user-supplied comparison can only be
used if an explicit interface is provided.  For example, user-defined
orders should work correctly with map__lookup, but user-supplied orders
wouldn't work in general so map__lookup doesn't provide an interface for
them.

Conversely, whenever a library predicate has a user-supplied-order
version, there is (nearly?) always a version that uses the standard
(and hence the user-defined) order.

> Index: doc/reference_manual.texi
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/doc/reference_manual.texi,v
> retrieving revision 1.259
> diff -u -u -r1.259 reference_manual.texi
> --- doc/reference_manual.texi	1 Oct 2002 08:13:26 -0000	1.259
> +++ doc/reference_manual.texi	25 Oct 2002 06:42:19 -0000
> @@ -3355,29 +3357,67 @@
>          subset(S2, S1).
>  @end example
>  
> +A comparison predicate can also be supplied.

Perhaps make it clearer that you may supply either or both.  E.g.:

A comparison predicate may also be supplied, or both an equality
predicate and a comparison predicate may be supplied.

> +
> + at example
> +:- type set(T) ---> set(list(T))
> +        where equality is set_equals, comparison is set_compare.
> +
> +:- pred set_compare(comparison_result::uo, set(T)::in, set(T)::in) is det.
> +set_compare(promise_only_solution(set_compare_2(Set1, Set2)), Set1, Set2).
> +
> +:- pred set_compare_2(set(T)::in, set(T)::in,
> +                comparison_result::uo) is cc_mulit.
> +set_compare_2(set(List1), set(List2), Result) :-
> +        compare(Result, list__sort(List1), list__sort(List2)).
> + at end example
> +
> +If a comparison predicate is supplied and the unification predicate
> +is omitted, a unification predicate is generated by the compiler
> +in terms of the comparison predicate.  For the @samp{set} example,
> +the generated predicate would be:
> +
> + at example
> +set_equals(S1, S2) :-
> +        set_compare((=), S1, S2).
> + at end example
> +
> +If a unification predicate is supplied without a comparison predicate,
> +the compiler will generate a comparison predicate which throws an
> +exception when called.

It would be useful to document what exception is thrown.

> +
>  A type declaration for a type @samp{foo(T1, @dots{}, TN)} may contain a
> - at samp{where equality is @var{equalitypred}} specification only
> -if the following conditions are satisfied:
> + at samp{where equality is @var{equalitypred}, comparison is @var{comparepred}}
> +specification only if the following conditions are satisfied:

I think it would be better to separate these constraints into two lists:
one for the constraints on equality preds and one for the constraints on
comparison preds.

> @@ -3427,6 +3467,15 @@
>  implementation may compute any answer at all (@pxref{Semantics}),
>  i.e.@: the behaviour of the program is undefined.}.
>  
> + at item
> +Any comparisons of type @var{T} are computed using the specified predicate
> + at var{comparepred}.
> +
> + at item
> + at var{comparepred} should be a partial order relation: that is
> +it must be antisymmetric, reflexive and transitive.  The
> +compiler is not required to check this.
> +

This point should go in the constraints list, rather than the semantics
list.

Also, I'm not convinced that requiring a _partial_ order is the right
constraint.  Why not a total order?  The mode of the comparison
predicate implies that all pairs of elements are comparable anyway.
Suggesting that they only need to be partial orders is misleading,
because many library predicates (e.g. list__sort) depend on the order
being total.

Perhaps you mean that the order is partial because the predicate can
throw an exception when the elements are not comparable?  If so, this
is an abuse of the notion of exception, IMHO.  In a partial order (e.g.,
the subset relation) it is perfectly normal to find two elements that
are not comparable (e.g., sets {1} and {2}) -- it is not an exceptional
circumstance at all -- so using an exception to indicate this is bad
design.

Finally, on a technical note, the adjectives "reflexive", etc, usually
apply to binary operators but the comparison predicate has arity three,
and you haven't explicitly stated what they mean in this context.

> Index: library/builtin.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/builtin.m,v
> retrieving revision 1.80
> diff -u -u -r1.80 builtin.m
> --- library/builtin.m	24 Sep 2002 06:55:16 -0000	1.80
> +++ library/builtin.m	26 Oct 2002 12:57:02 -0000
> @@ -178,6 +180,9 @@
>  	% unify(X, Y) is true iff X = Y.
>  :- pred unify(T::in, T::in) is semidet.
>  
> +:- type unify(T) == pred(T, T).
> +:- inst unify == (pred(in, in) is semidet).
> +
>  :- type comparison_result ---> (=) ; (<) ; (>).
>  
>  	% compare(Res, X, Y) binds Res to =, <, or >
> @@ -191,6 +196,9 @@
>  :- mode compare(uo, ui, in) is det.
>  :- mode compare(uo, in, ui) is det.
>  
> +:- type compare(T) == pred(comparison_result, T, T).
> +:- inst compare == (pred(uo, in, in) is semidet).
> +

You should document the constraints on values of these types here, in
addition to the reference manual.

It would also be useful to document here the distinction between compare
and comparison_pred, that is, that the former are used for the "where ..."
part of type declarations.

Cheers,
Mark.

--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------