Re: [Sml-implementers] extensions to SML

[Matthias B. <bl...@re...>]

Stephen Weeks wrote:
> 
> > I would eliminate equality polymorphism entirely.
> 
> I have several objections to dropping polymorphic equality.
> 
> * Loss of overloaded = on ints, words, chars, etc.
> * Loss of performance.
> * Excessive code to write, and decrease in maintainability.
> 
> The first point is obvious, but minor.  The next two points are neither obvious
> nor minor, so I will explain.  Suppose I want to implement equality on the
> following datatype.
> 
> datatype t = A | B | C
> 
> If there is no polymorphic equality, I have to write
> 
> val equals: t * t -> bool =
>   fn (A, A) => true
>    | (B, B) => true
>    | (C, C) => true
>    | _ => false
> 
> On the other hand, with polymorphic equality, I can write
> 
> val equals: t * t -> bool = op =
> 
> For large enumerations (I can think of one in the MLton sources with over 150
> variants), the first approach is a lot of code.  It is also error prone, since I
> have to remember to add a new case whenever I add a variant.  Finally, I don't
> think any SML compiler will do the right thing for the first approach, which is
> to implement equals as a single integer comparison.  I know that for the second,
> MLton will use a single comparison, and I hope that other compilers do too.
> 
> Similar arguments apply even when there are non-value carrying variants.

I agree with Bob and others who would rather drop polymorphic equality.  However,
you have a point in what you write above, so some other, more useful mechanism should
be added to replace it.  (By this I do not mean type classes.)

Why do I not want polymorphic equality:  Because it rarely does the Right Thing.  In fact,
I never ever use it in my code.  The overloading problem can be fixed as such: by using
overloading.  Loss of performance only applies to some cases.  In real programs I found that
custom equality predicates are better.  Excessive code -- perhaps that one is true
to some extend (which is why we should consider designing an alternative to PE).

-------------------------------------------------------------------------
Here is a strawman design, just for fun.  Don't take it too serious!

What I would like to see is a new syntactic construct that
takes a type constructor T of arity n and binds a function name to a comparison function for
instantiations of T parameterized by comparison functions for the type arguments of T.
To make this concrete, let me invent some syntax for a new kind of expression.

There is a new keyword "equality" and a new expression of the form

    <expr> ::= <tycon> equality

For example "int equality" would be an expression of type (int * int -> bool), and Steve's
"equals" function could be defined using "val equals = t equality", and hopefully it would
be implemented at least as efficient for this type as the PE version.

If <tycon> has arity > 0, then the expression takes additional curried arguments which are
comparison functions for the respective type parameters.  Example:

    list equality : ('a * 'a -> bool) -> 'a list * 'a list -> bool

    ((list equality) (t equality)) : t list * t list -> bool

So "equality" is a shorthand for writing out what Steve did above.  It has the advantage of
being brief and automatically exhaustive without having the disadvantage of requiring an entire
data structure to be compared under structural equality.  For example, I could have a type
"symbol = int * string" for which I define equality by hand as

   fun samesymbol ((stamp, _): symbol, (stamp', _): symbol) = stamp = stamp'

which then allows me to define equality of symbol lists as

   val samesymbols = (list equality) samesymbol

The point is that one can "roll ones own" equality test wherever necessary while still being
able to incorporate structural equality tests at minimal notational cost where this is appropriate.
(For recursive types one might want some form of explicit fixpoint construct to avoid having to do
a fully recursive structural equality test for the recursive part of that type. I am not sure what
one would want the syntax for this to look like.)
---------------------------------end of strawman-------------------------------------

In any case, this is not supposed to be a serious proposal.  Instead, I tried to show that there
are alternative designs that do not require polymorphic equality and which are as powerful and more
flexible.

Matthias