Previous chapter: #30: Make Range (Change)

Dylan Design Notes

Dylan Design Notes: #31: Method Specificity (Change)

#31: Method Specificity (Change)

Version 1, January 1994 Copyright (c) 1993-1994, Apple Computer
This Design Note gives a revised specification of Dylan's handling of method specificity.

Class Precedence List

[This section is intended to present the same class precedence list algorithm as in CLOS.]

The definition of a class specifies a total ordering on that class and its direct superclasses. This ordering is called the local precedence order. In the local precedence order, the class precedes its direct superclasses, and each direct superclass precedes all other direct superclasses following it in the sequence of direct superclasses of the class definition.

The class precedence list for a class C is a total ordering on C and its superclasses that is consistent with the local precedence orders for each of C and its superclasses.

Sometimes there are several possible total orderings on C and its superclasses that are consistent with the local precedence orders for each of C and its superclasses. Dylan uses a deterministic algorithm to compute the class precedence list, which chooses one of the possible total orderings. The algorithm has the effect that the classes in a simple superclass chain are adjacent in the class precedence list, and classes in each relatively separated subgraph are adjacent in the class precedence list.

Sometimes there is no possible total ordering on C and its superclasses that is consistent with the local precedence orders for each of C and its superclasses. In this case, the class precedence list cannot be computed, and Dylan signals an error.

To compute the class precedence list:

Let S be the set of C and all of its superclasses.

For each class c in S, let
        Rc  = {(c, c1), (c1, c2), .... , (cn-1, cn)}
where c1 ,..., cn are the direct superclasses of c in the order in which they are mentioned in the class definition for c.

Let R be the union of all Rc for every class c in S. The set R might or might not generate a partial ordering, depending on whether the Rc are consistent; it is assumed that they are consistent and that R generates a partial ordering. When the Rc are not consistent, it is said that R is inconsistent.

To compute the class precedence list for C, topologically sort C and its superclasses with respect to R. Topological sorting proceeds in the following way:

  1. Find a class N in S such that no other class precedes N according to the elements in R.

    If there are several classes from S with no predecessors, select the one that has a direct subclass rightmost in the partial class precedence list computed so far. In more precise terms, let {N1,...Nm}, m>=2, be the classes from S with no predecessors. Let (C1,...,Cn), n>=1, be the partial class precedence list computed so far. C1 is the most specific class, and Cn is the least specific. Let 1<=j<=n be the largest number such that there exists an i where 1<=i<=m and Ni is a direct superclass of Cj. Select Ni.

  2. Place N first in the result. Remove N from S, and remove all pairs of the form (N, M), such that M is an element of S, from R.

  3. Repeat the process, adding classes with no predecessors to the end of the result. Stop when no element can be found that has no predecessor.
If S is not empty and the process has stopped, R is inconsistent because it contains a loop. That is, there is a chain of classes C1,....,Cn in S such that Ci precedes Ci+1, 1<=i<n, and Cn precedes C1. When R is inconsistent, there is no possible total ordering on C and its superclasses that is consistent with the local precedence orders for each of C and its superclasses, and an error is signaled.

Ordering of methods by specificity

[Our approach is similar to that in the language Cecil (Craig Chambers, University of Washington). This approach is different from CLOS in that there is no reference to the lexicographic order of arguments when multimethods are sorted. See the Examples section for more detail on these differences.]

Method dispatch occurs in three phases. First, all the applicable methods are selected. Next, the applicable methods are sorted by specificity. Then the most specific method is called. This section covers how methods are sorted by specificity.

For any two methods A and B that are applicable to a given generic function call, one method may be more specific than the other, or the methods may be ambiguous methods.

To order two methods A and B with respect to a particular set of arguments, compare each of A's specializers with B's specializer in the corresponding position using the corresponding argument. The comparison works in the following way.

The method A is more specific than the method B if and only if A precedes B or is unordered with respect to B in all required argument positions, and precedes B in at least one argument position. Similarly, B is more specific than A if and only if B precedes A or is unordered with respect to A in all required argument positions, and precedes A in at least one argument position. If neither of these cases apply, i.e. neither method is more specific than the other, then A and B are ambiguous methods.

When the applicable methods are sorted by specificity, the sorted list is divided into two parts, each possibly empty. The first part contains methods that are more specific than every method that follows them. The second part (which need not be sorted itself) begins at the first point of ambiguity; there are at least two methods that could equally well go first in the second part. If the first part is empty, generic function dispatch signals an "ambiguous method" error. If the last method in the first part calls next-method, the call signals an "ambiguous next method" error.


Examples:

Consider the following class definitions
define class <sentient> (<life-form>) ... end class;
define class <bipedal> (<life-form>) ... end class;
define class <intelligent> (<sentient>) ... end class;
define class <humanoid> (<bipedal>) ... end class;
define class <vulcan> (<intelligent>, <humanoid>) ... end class;

Computing the class precedence list for <vulcan> yields

(<vulcan>,<intelligent>,<sentient>,<humanoid>,<bipedal>,<life-form>)

In this class precedence list, note that classes in the simple superclass chains (<intelligent>,<sentient>) and (<humanoid>,<bipedal>) are kept adjacent.

The class precedence lists computed for two different classes may have different precedence orders for some intermediate superclasses. This is not a problem as long as there is no class which inherits from both classes. For example, we could define a class <human> as follows:

define class <human> (<humanoid>, <intelligent>) ... end class;

For the class <human> defined as above, the class precedence list would be (<human>,<humanoid>,<bipedal>,<intelligent>,<sentient>,<life-form>)

It is not a problem that the two class precedence lists give different orders to some of the intermediate superclasses such as <bipedal> and<sentient> as long as no class is added which inherits from both<vulcan> and <human>.

When sorting the applicable methods, each specializer pair needs to be compared with respect to the class precedence list for the class of the argument passed to the generic function in that argument position, because the class precedence list might be different depending on which class it was computed from. For example, given the following definitions

define class <vulcan> (<intelligent>, <humanoid>) end class;
define class <human> (<humanoid>, <intelligent>) end class;
define method psychoanalyze (being :: <intelligent>) ... end method;
define method psychoanalyze (being :: <humanoid>) ... end method;

calling the generic function psychoanalyze on a being of type <human>would cause the method for <humanoid> to be called first, while calling the generic function on a being of type <vulcan> would cause the method for <intelligent> to be called first.

There is no reference to lexicographic order in sorting multimethods. This is different from CLOS. Given the above class definitions, the following methods are unambiguous when superior-being is called on two beings of type <vulcan> or two beings of type <human>, but the methods are ambiguous when superior-being is called on a being of type <vulcan> and a being of type <human> (because it is ambiguous whether to choose the most-intelligent-being, or the best-looking-being):

define method superior-being (a :: <intelligent>, b :: <intelligent>) 
  most-intelligent-being (a, b)
  end method;

define method superior-being (a :: <humanoid>, b :: <humanoid>)
  best-looking-being (a, b)
  end method;
On the other hand, under the CLOS system, when superior-being is called on a being of type <vulcan> and a being of type <human>, the best-looking-being is chosen when the <human> is the first argument, and the most-intelligent-being is chosen when the <vulcan> is the first argument.

Sometimes two methods are ambiguous, and you have to define an extra method to disambiguate between them. This typically happens when the ambiguity is between two methods that are actually equivalent. For example,

define method intersection (l1 :: <list>, l2 :: <empty-list>) 
  #() 
  end method;

define method intersection (l1 :: <empty-list>, l2 ::<list>)
  #() 
  end method;

define method intersection (l1 :: <empty-list>, l2 :: <empty-list>)
  #() 
  end method;

The third method is needed because intersection(#(), #()) would otherwise signal an "ambiguous method" error.


Notes:

We considered requiring an error to be signaled in cases where the local precedence orders are insufficient, but this is unacceptable because of certain generic functions like initialize. For example, suppose that every class has an initialize method, every initialize method has to be called, and every initialize method calls next-method. The class precedence list defines a total ordering for calling all the initialize methods in sequence, consistent with all the local precedence orders.

Although the algorithm which computes the class precedence list may make some arbitrary choices in the precedence ordering of classes, we feel any program which explicitly depends on these choices is bizarre.

There are languages which take a different approach, creating a total ordering of all classes which is used for tie-breaking. This makes method specificity independent of the particular arguments passed to the generic function, a nice simplification. The problem with this is that the example classes <vulcan> and <human> would each be valid by itself, but an attempt to define them both in the same Dylan object space would signal an error because no total ordering of classes exists that is consistent with both of them. That militates against modular programming. One answer to this is to make the total ordering independent of existing class definitions, for example to use alphabetical order. Thus the class precedence lists would be:

(<vulcan>,<intelligent>,<humanoid>,<bipedal>,<sentient>,<life-form>) (<human>,<humanoid>,<bipedal>,<intelligent>,<sentient>,<life-form>)

Note that this still does not produce total consistency, since the local precedence lists were inconsistent to begin with. Also, using alphabetical order of class names would be a very bad idea in Dylan, which strives to maintain a clean separation between names and objects. This is why we feel that the rather complicated set of rules being proposed are better than seemingly simpler alternatives.

Next chapter: #32: Module Defining Forms (Addition)