[ANN] Multimethod.py -- multimethods for Python

[Martin von Loewis]

Siggy Brentrup <bsb at winnegan.de> writes:

> Can you point us to a formal definition? Seems like you initially got into
> trouble explaining it by example :)

I can try to produce one right here; please be aware that languages
may use variations of that.

Let A, B, C, T1 .. Tn and Q1 .. Qn denote types. Let A => B denote
specialization, in the sense "A is more special than B" (i.e. A
inherits from B). For purpose of this definition, let A => A (i.e. a
type is a specialization of itself).

Notice that '=>' defines a half-ordering on types: If A=>B and B=>C,
than A=>C; however, there may be A, B so that neither A=>B, nor B=>A.

Now consider a set of signatures, s1 .. sn. All have the same function
name (say, f), but different argument types. We can now extend '=>'
onto signatures as well: s1(T1 .. Tn) => s2(Q1 .. Qn) iff Ti => Qi for
all t from 1 to n.

Given an operation invocation f(a1 ... an), multi-dispatch selects a
signature from the set of all signatures of f, and invokes the
corresponding operation definition.

To do so, the candidates are selected first from the set of
signatures. A signature si(T1..Tn) is candidate iff for each i,
type(ai) => Ti.

If there is candidate, the invocation is in error (no matching function)

If there are candidates, select the maximal specific candidates from
the set S of all candidates. A candidate si is maximal specific, if
there is no other element sk of S so that sk => si.

If there is more than one maximal specific candidate, the invocation
is in error (ambiguous invocation).

If there is exactly one maximal specific candidate, this candidate is
invoked.

In languages with static typing, it is possible to statically verify
that there will be always exactly one most specific candidate. A
sufficient condition is that the set of signatures with the same name
forms a lattice: If there are two signatures sa and sb so that neither
sa=>sb nor sb=>sc, there must be a signature sc so that sc=>sa and
sc=>sb.

Is that what you wanted to hear? :-)

Regards,
Martin

P.S. This is exactly the procedure that is also used for overload
resolution in Java, only that this is all done statically in Java, and
not via dynamic dispatch.