on polymorphic compare and objects

on polymorphic compare and objects

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I recently came across a post on Janest lamenting the perils of polymorphic 
compare.

  http://ocaml.janestcapital.com/?q=comment/reply/33

They make a great point, and I thought of a solution that has worked well for 
me in the past few months that I would like to share, in part, to solicit 
feedback from the community.

Here is my approach.  It is, in part, excerpted from a conversation with Brain 
Hurt and also posted on the Janest blog.  As warning, my approach does use 
some magic and OCaml guts but no more than what is made available for OCaml/C 
interface.  It is also mostly hidden once done.

- ----

The (compare) function has the signature ('a -> 'a -> bool).  That means it is 
a function that imposes a total ordering for *all* types -- even those that 
have not yet been defined. Clearly, it cannot be the desired ordering for all 
(and future) types.  If OCaml had a "content" equality function (ie. two 
things are equal if they can be used
interchangably in pure functions) it would have a similar problem.

It is my opinion that this approach is really just for convenience and
performance reasons.  The right solution would use something like
type classes or go with Java's object based solution (eg. Comparable
interface).

Here's my solution to this.  I modify the (compare) and other similar 
functions to check for objects and use its appropriate method if available.  
In otherwords, if you call compare on a (int,int) tuple, it has OCaml's 
standard behavior.  But if you call compare on a [int,int] tuple class, it 
will use the class' compare method.  This hybrids
between OCaml's polymorphic solution and the Java, method-dispatch solution.

One might also think of it as a hook.  If the user defines some type that has
unique comparison behavior he/she can do so by wrapping the type in a class
and specifying the unique behavior via the compare method.  This means the
rest of the code never needs to know and use special compare functions.  It
can always use compare, knowing that it will automatically do the right
thing.

In this way (compare) and (content-equals) can actually be well defined for
all (including future) types.  Let's take as an example, the content-equals
function which I'll just call equal for now.  (equal) has a very specific
semantic meaning: it returns true if its two arguments are exchangable in a
pure context (ie. no side-effects).  (equal) is well defined for all simple
types: int, float, string, etc..  For objects, we require that all objects
implement an equal method that satisfies the semantic contract.  Thus (equal)
the function is also well defined on objects.  For all other types, whatever
they may be, either the default structural comparison behavior of (equal)
satisfies the semantic contract or it does not.  If it does, then (equal) is
well defined.  If it does not, we require it to be wrapped in an object so
that an appropriate behavior can be specified.

As a concrete example consider:

  type xycoord = (int, int)

As it happens, structural equality is what we want.  Since (equal) already
does this we are done.

Now consider:

  type rational_number = (int, int)

Here, structural equality is not what we want.  (1/2) is the same rational
number as (2/4) but they are not structurally equal.  Thus in order to satisfy
the semantic contract of (equal) we must instead do:

  class type rational_number = object
    method equal : rational_number -> bool
    ...
  end


Meanwhile, a function like List.assoc, but defined using (equal), works
equally well on both types.

This approach lets you keep the OCaml approach of a polymorphic compare/equal
function, but does not limit you to a single algorithm for performing the 
comparison.  It buys you the power of objects (much like that of type 
classes) but without the requirement that everything be an object.  I have 
found it to be a sweet spot and use it in my code regularly.

- ----


As always, I welcome any comments, suggestions, questions or flames =]


Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFIvcevfIRcEFL/JewRAqQaAJ485qiwtMKy5W9dJbIvNzklH/DZ3wCfQlR6
UrtMhcho4xm4mII2Depv+vs=
=HZ9F
-----END PGP SIGNATURE-----

Re: [Caml-list] on polymorphic compare and objects

[Alain Frisch]

Peng Zang wrote:
> For objects, we require that all objects
> implement an equal method that satisfies the semantic contract.

How do you ensure that the method is indeed implemented and has the 
correct type?

A more robust approach to attaching custom generic operations to 
arbitrary data would be to introduce the equivalent of custom blocks, 
but for OCaml data. This probably amounts to reserving a new GC tag and 
deciding on a memory layout (e.g. a block with this tag has two fields: 
the underlying value and a dictionary of generic functions). Then simple 
modules in stdlib could expose a well-typed interface (ensuring that the 
type of the dictionary's functions is compatible with the type of the 
underlying values). It would even be possible to expose the resulting 
blocks as values of a private record type with two fields, so as to 
preserve pattern matching on the underlying value.


   Alain

Re: [Caml-list] on polymorphic compare and objects

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Wednesday 03 September 2008 02:31:10 am Alain Frisch wrote:
> Peng Zang wrote:
> > For objects, we require that all objects
> > implement an equal method that satisfies the semantic contract.
>
> How do you ensure that the method is indeed implemented and has the
> correct type?

Currently, I require all objects to inherit from a general "Object" class, 
much like in Java.  If you define an object without the equals method for 
example, or with the wrong type, it will complain that it doesn't match the 
type or a method is unimplemented.  However, the user must manually write 
the "inherit object" line.   I would like to use camlp4 to make this 
automatic, but I have yet to learn camlp4.

> A more robust approach to attaching custom generic operations to
> arbitrary data would be to introduce the equivalent of custom blocks,
> but for OCaml data. This probably amounts to reserving a new GC tag and
> deciding on a memory layout (e.g. a block with this tag has two fields:
> the underlying value and a dictionary of generic functions). Then simple
> modules in stdlib could expose a well-typed interface (ensuring that the
> type of the dictionary's functions is compatible with the type of the
> underlying values). It would even be possible to expose the resulting
> blocks as values of a private record type with two fields, so as to
> preserve pattern matching on the underlying value.

I like this approach too.  When I first encountered the polymorphic compare 
issue, custom blocks looked like a great solution.  I couldn't figure out how 
to make it work though.  Even with the helpful description you provided, I'm 
not sure if I could figure out how to do it.

I ended up making objects fit the bill because objects are all about attaching 
functions to data.  I also like how it gives you structural subtyping which I 
love.  I wish it were more robust, but I think proper enforcement would 
require patching the compiler.

I want to emphasize that the implementation is not the point.  It merely 
serves as a motivating example of the general approach: fix polymorphic 
compare (and similar functions) by giving it dynamic dispatch for objects.  
If this approach is reasonable, and it bears the trial of time, I would like 
to patch the compiler to properly enforce it.

Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFIvqFafIRcEFL/JewRAnFQAJ9lloSHWcrS/NoOrlSq4cxdxnlq5ACgnbtu
kHDRxpzodXNcdd0G0aerAqY=
=7XTV
-----END PGP SIGNATURE-----