19.2 How generic functions and methods are invoked

The library (vicare language-extensions multimethods) is designed to work with type definitions from the library (vicare) (<fixnum>, <string>, et cetera); these types and their hierarchy are identified by unique symbols (UID). For example:

(type-unique-identifiers <string>)
⇒ (vicare:scheme-type:<string>
    vicare:scheme-type:<top>)

Every method has arguments specified by a tuple of type identifiers; for example, the method definition:

(define-method (fluff {A <string>} {B <struct>} {C <top>})
  ---)

has arguments specified by the tuple of identifiers:

(<string> <struct> <top>)

Every tuple of operands to which a multimethod is applied is associated to a tuple of type identifiers; for example, in the multimethod application:

(define {B <struct>} ---)
(define {C <top>}    ---)
(fluff "ciao" B C)

the type of the operands is specified by the tuple of type identifiers:

(<string> <struct> <top>)

This way each tuple of method’s arguments and each tuple of operands is associated to a tuple of UIDs lists. For example, the tuple of type identifiers:

(<string> <struct> <top>)

is associated to the tuple of UID lists:

((vicare:scheme-type:<string> vicare:scheme-type:<top>)
 (vicare:scheme-type:<struct> vicare:scheme-type:<top>)
 (vicare:scheme-type:<top>))

A tuple of UID lists is called signature. Each multimethod holds an internal collection in which every method’s closure object is associated to a signature.

Ordinary multimethods

Ordinary multimethods allow the association of a single method to a type signature. When an ordinary multimethod is applied to a tuple of operands, the following happens:

1. For each operand a type is determined and the list of UIDs representing the type hierarchy is acquired. The operands’ signature is formed.
2. The internal collection of methods is queried for all the methods applicable to the tuple of operands, using the operands’ signature as search key.
3. The list of applicable methods is sorted from the most specific to the least specific for the operands’ signature. From now on the list of sorted, applicable methods is handled as a stack.
4. The next method is popped from the stack and its closure applied to the tuple of arguments; the return value of this application becomes the return value of the generic function application. If the function calls its “next method”: recurse to step 4 (see Invoking the next method).

Starred multimethods

Starred multimethods allow the definition of four qualified methods: :primary, :around, :before and :after; we can think of ordinary multimethods as starred generics supporting only :primary methods. The short description is that: :around methods are applied first, then :before, :primary and :after methods are applied in this order.

For each method qualification (:primary, :around, …): a starred multimethod holds an internal collection in which every method’s closure is associated to an arguments’ signature.

When a starred multimethod is applied to a tuple of operands, the following happens:

1. For each operand a type is determined and the list of UIDs representing the type hierarchy is acquired. The operands’ signature is formed.
2. For each method qualification: the internal collection is queried for all the methods applicable to the tuple of operands, using the operands’ signature as search key.
3. For each method qualification: the list of applicable methods is sorted from the most specific to the least specific for the operands’ signature. The list of :after methods is reversed: from the least specific to the most specific.

From now on the lists of sorted applicable methods are handled as stacks; the stacks of :primary, :around and :before methods have the most specific method on the top; the stack of :after methods has the least specific method on the top.

From now on the application of the multimethod enters an implicit loop in which more methods’ closures can be applied to the same tuple of operands. The loop can terminate if a method’s closure throws an exception or, for :around and :primary methods, if it does not take the special action of calling call-next-method.

The loop is a bit articulated, so we may have to read the following descriptions multiple times. We split the description in two branches: First a simplified invocation for multimethods having at least one applicable :primary method, no :around methods, and performing no calls to call-next-method; then the full application algorithm.

Here is the simplified branch with no :around methods and no calls to call-next-method:

4. Pop all the :before methods from the stack and apply their closures to the tuple of operands. The return values of these applications are discarded.
5. Pop the next :primary method from the stack and apply its closure to the tuple of operands. The return value of this application is saved in a temporary location.
6. Pop all the :after methods from the stack and apply their closures to the tuple of operands. The return values of these applications are discarded.
7. Return the saved return value of the :primary method.

here is the full application algorithm:

4. Test if this function application originated from a call to call-next-method from a :before or :after method; if it has: raise an assertion violation.
5. Test if this function application originated from a call to call-next-method from a :primary method; if it has:
   1. If the stack of :primary methods is empty raise an assertion violation.
   2. Pop the next :primary method from the stack and apply its closure to the tuple of operands.
   3. Break out returning the return value of this application: it becomes the return value of call-next-method.
6. If the stack of :primary methods is empty: raise an assertion violation. This condition means that the multimethod has no applicable methods for the tuple of operands.
7. If the stack of :around methods is not empty: pop the next :around method and apply its closure to the tuple of operands. Break out returning the return value of this application.
8. Pop all the :before methods from the stack and apply their closures to the tuple of operands. The return values of these applications are discarded.
9. Pop the next :primary method from the stack and apply its closure to the tuple of operands. The return value of this application is saved in a temporary location.
10. Pop all the :after methods from the stack and apply their closures to the tuple of operands. The return values of these applications are discarded.
11. Return the saved return value of the :primary method.

The :primary methods are meant to do the real work of the function. Only the most specific is applied to the operands, however it can use call-next-method to invoke a least specialised version and use its return value, and so on recursively until there are no more next methods.

:before and :after methods are meant to execute additional work before and after the primary methods; for example test pre and post conditions on the operands. While :before methods are applied from the most specific to the least specific, :after methods are applied from the least specific to the most specific. Notice that the :after methods have no access to the return value of the :primary methods.

:around methods are yet another level for performing tasks before and after the primary methods; only the most specific is applied to the operands. It is expected, but not mandatory, that an :around method invokes call-next-method; when such invocations are performed recursively: they will consume all the applicable :around methods, from the most specific to the least specific, and then will start the application of :before, :primary and :after methods.

The protocol of application for methods in a starred multimethod is meant to be the same as the standard method combination for CLOS methods as defined by the Common Lisp standard⁴.