[racket-dev] Generics

I have a long-running branch on github where I've been working on making
the set datatype generic the way dictionaries are, and improving the
generic system to support that effort.  Some of the people here at
Northeastern know about it, but I should probably make more people aware of
the work.  This is still a work in progress, it will be a while before it's
ready for final review and push.

  https://github.com/carl-eastlund/racket/tree/generic-sets

For sets, the main purpose has been to add gen:set and allow the set
datatype to be extended.  Along with that, I've added mutable sets and
make-custom-set, akin to make-custom-hash, and made lists usable as sets
based on equal? comparisons.

I've made an effort to put a lot of methods in gen:set, rather than the
bare minimum to make a set work.  My goal  is for an implementer to provide
whatever subset of the operations is necessary or desirable for a given set
representation, and have fallback implementations that will automatically
be used for other methods.  For example, a simple representation might
implement only set-member? and set-add, leaving set-union to the default
behavior using repeated set-add.  A more clever representation, such as
red-black tree sets, might have a custom efficient set-union operation.

At first I encoded this pattern by having separate back-end methods for
implementers to provide via gen:set, and wrapper functions that called set
operations if present and used default implementations otherwise.  But this
is cumbersome to program, and probably other generics will want it.  So I
extended define-generics to take a #:fallbacks option.  Now generic methods
can be given a fallback implementation in terms of the other methods that
will be used for any representations that do not provide a specific
implementation.

I have also added a #:extend option to define-generics, so a new generic
method group can extend one or more others.  If generic method group A
extends B and C, then implementations of methods for A should include any
definitions for the methods of B and C, and the new type will belong to all
three of A, B, and C.  This feature is more speculative than #:fallbacks; I
don't have a use for it in sets, but I think it would be valuable if we
make pervasive use of generics in the near future.

It would be much more convenient to use generics with #:extend if structure
properties supported "diamond-shaped" derivation graphs.  That is, if
property A derives B and C, and B and C each derive D, currently
make-struct-type raises an error because an implementation of A results in
multiple implementations of D.  This prevents some natural patterns of
related generics.  It would be nice to have some way of disambiguating
implementations to allow this, for instance if a struct type directly
provides an implementation for property D, it overrides any derived from A,
B, and C so that they can all coexist.

Right now I'm working on the behavior of make-custom-set, which has raised
some questions about the behavior of make-custom-hash.  I think I'll save
that discussion for a separate email in the near future, so as to keep to
more or less one topic and not go sprawling on for pages.  More pages, I
mean.

Anyway, I hope this is all stuff that looks good to people, because I've
put a lot of work into it, but I'm open to feedback if I've taken a wrong
turn somewhere.

Carl Eastlund
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130617/9e6d1afa/attachment.html>