[Python-3000] Generic functions vs. OO

[Guido van Rossum]

I'd like to take the opportunity to present another example of what
I'd like to be able to do with abilities and generic functions. It's
short on implementation and I don't want to emphasize syntax, but it's
high on concepts. The baseline assumption is that most built-in
operations, especially binary operators, are implemented as generic
functions.

Let's suppose we didn't have a set type yet, and we wanted to introduce it.

I'd start by defining three abilities: MinimalSet which only provides
the 'in' operator; IterableSet which also provides iteration (but not
len(); it may aply to infinite sets); and StandardSet which adds most
standard operations on sets, but still not len(). The operations on
standard sets are: & (intersection), | (union), ^ (symmetric
difference), - (asymmetric difference), <= (is subset), >= (is
superset), < (strict subset), and > (strict superset). Sets also
implement == and !=, as these are inherited from an even more basic
ability (say, Object). Mutable operations are not part of this
ability.

One reason why I'm saying ability instead of interface is that not
every object that implements the above operations should automatically
be considered a set! If a class claims to be a set, it should conform
to a much richer contract, which guarantees the basic properties of
mathematical sets. For example, a&b == b&a, a&a == a, and so on. The
contract implies the existence of an empty set, and all empty sets
should compare equal (even if they have different underlying
implementations).

So StandardSet implies more than a bunch of operations! In particular,
subclassing int and adding implementations for __contains__ and
__iter__ should *not* result in that subclass having the StandardSet
ability (unless I explicitly declare it). Note: while this appears
incompatible with Phillip's proposal "interfaces are just collections
of operations", I think this can be consolidated easily by allowing
some kind of "marker" operation.

Now I'd like to introduce a standard set implementation. It implements
all those operations. But I'd like it to automatically accept operands
of other set implementations, as long as they claim the relevant
ability. For example, in Python 2.4, the built-in set implementation's
__and__ is defined roughly like this (ignoring some optimizations,
like that it's written in C :-):

# This a method of class 'set', a concrete set implementation

def __and__(self, other):
  if not isinstance(other, baseset):
    return NotImplemented
  result = set()
  for elem in self:
    if elem in other:
      result.add(elem)
  return result

But I'd like to be able to write it like this instead (still inside
the 'set' class):

def __and__(self, other: MinimalSet):
  result = set()
  for elem in self:
    if elem in other:
      result.add(elem)
  return result

which means that it automatically interoperates with other set implementations.

The header "def __and__(self, other: MinimalSet)" is meant to be
enough syntax to declare an implementation of the pre-existing __and__
operations for the pair (set, MinimalSet) -- the first being a
concrete type (class), the second being an ability.

Actually, I might want to define three implementations of __and__: one
for the pair (set, set), which could be optimized based on knowledge
of the internals; one for (set, MinimalSet); and one for (MinimalSet,
set). The exact syntax for all this is not that important; the latter
one may have to be defined outside the class as a true generic
function; or defining a method __radd__ could do the trick; or even
aliasing __radd__ to __add__ (like we would do today).

I believe this example captures an important requirement that has been
expressed both by Bill Janssen and by Andrew Koenig (needless to say I
agree): abilities should be able to imply contracts that go beyond a
collection of methods (without necessarily being able to express those
contracts in code).

The example doesn't show a way to test whether an object has an
ability, but I certainly want to make that possible and even
efficient; maybe isinstance(x, A) could be made to work (it's already
pretty flexible under the hood, and could easily be turned into a GF
itself), or maybe you'll have to write has_ability(x, A).

Note that I haven't shown syntax for declaring the various abilities.
That is because I don't have a concrete proposal yet. However, I would
prefer syntax that looks declarative (similar to a class declaration)
for the normal case. Syntax that looks procedural (e.g. "IterableSet =
MinimalSet + iter") might be available as an alternative way to create
abilities more dynamically, just like in a pinch we can create a new
class today by calling type(name, bases, classdict).

I still don't have new ideas for how to add regular-looking methods
(like keys()) to an ability.

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)