Chapter 21: Dispatching Selection Resolution Routing Summary

Any message sent in an OO system may be dispatched in any of several senses. At least three separate aspects of dispatching may be distinguished:

1. Selection of concrete code associated with an invoked operation for a given object.
2. Resolution of the ``best matching'' version of an operation when two or more are defined.
3. Routing of a nonspecific request to a particular object.

Not all senses are directly supported in all OO programming languages and systems. We discuss ways of coping with this later.

Dispatching is a decoupling technique. The three forms of dispatching decouple requests from the corresponding code, versions, and receivers. A dispatching error results when an object sends a message that has no valid receiver or corresponding operation. This can occur when there is not a unique best matching action defined for the message name and types of the actual arguments, including the case where no such operation is defined at all, and in the case of object routing, where no eligible recipient exists.

Dispatching errors are among the most difficult problems to plan for. It is inconceivable to write actions that check to see if each and every message could be dispatched and to take evasive action if not. If dispatching errors do occur, the only recourse is to define top-level error recovery facilities, triggered by dispatching mechanisms. Indeed, one of the main reasons for using a strongly typed design language is to avoid this.

Typed OO dispatching adds a safety guarantee to decoupling. Senders are assured that no matter which receiver, version, and code is dispatched, messages result in the desired effects. Thus, dispatching rules are among the mechanisms by which OO systems support subclass polymorphism. Because of this, the dynamics of dispatching are dependent on the declarative structure of classes and operations.

Dispatching mechanisms associated with code selection are essential for basic OO methods. They are usually uncomplicated, simply linking the version of concrete code defined in a class to the appropriate operation name and message.

Refining Operations in Subclasses

To meet basic safety guarantees, subclass versions of operations must obey the rules for refined transitions given in Chapter 7. To briefly recap, subclass versions may weaken preconditions, add actions, and strengthen result guarantees with respect to superclasses.

These requirements occasionally lead to surprising constraints on subclasses and operations. For example, it may appear reasonable to define an addToBalance operation in class Account of the form:

class Account ...
  fn balance: real;
  op addToBalance(v: real) ==> balance' = balance + v end
end

Suppose now that while the balance attribute in Account is numerically unconstrained, subclass SavingsAccount adds the constraint that balance >= 0. This causes problems. Because balance + v might be negative, the SavingsAccount balance constraint may be broken by the postcondition. Yet the operation cannot be modified to accept only positive values as data and still maintain the subclass justification. Thus, from either perspective, the design is inconsistent.

Several solutions are available. For example, the topmost Account class need not define any operations. Different operations with different names and constraints could be associated with different subclasses. However, this eliminates opportunities for polymorphism, thus complicating the design of client classes that interact with different Account subclasses.

If one would like to ensure that instances of all Account subclasses possess the operation, then the topmost version must be recast. Here, one could define the Account version to accept only nonnegative values of v. Subclasses able to accept negative values as well can then weaken the precondition and/or define additional operations. This would be appropriate only if it were logically impossible to define a subclass requiring a stronger input constraint. For example, it does not allow definition of a subclass requiring that v >= transactionFee.

To allow for arbitrary variation in subclass restrictions, one may adopt a weaker but more general strategy using state abstraction along with a screening function. For example:

class Account ...
  fn canAdd(v: real): bool;
  op addToBalance(v: real) 
    when canAdd(v) then balance' = balance + v 
    else % pend or exception % end
end

The canAdd predicate defines an abstract state. The screening function may be unconstrained (undefined) in the abstract superclass. Subclasses may then add constraints and concrete definitions. Clients of any subclass of Account must be prepared for canAdd to be false for any reason whatsoever. A variant of this tactic is to eliminate the guard and then recast addToBalance to return a boolean result or named reply reporting whether the operation succeeded or failed. Different subclasses may then differently define the conditions under which the operation reports success.

State abstraction and refinement may be exploited in other situations as well. A subclass may specify refined states that distinguish attribute settings that were lumped together in one superclass state. This may result in two or more versions of an operation being defined in the subclass, each of which obey all superclass guarantees, but in different ways. For example, suppose Q is a special checking account class that charges for transactions only if the balance is under a stated minimum. Q may subdivide the nonoverdrawn state of Account into cases of not overdrawn but under minimum balance versus at or over minimum balance. Q may then define two versions of a transaction operation accordingly, distinguished by different guard conditions.

Selection Policies

The details of selection rules may impact how classes and subclasses ultimately become defined in software. Effective use and reuse often relies on more fine-grained types than are usually originally present in a design. For example, consider:

class X  a: bool;  b: int;  c: real; end

op useA(p: ?) { if p.a then print("success") end }

What type should be listed for p in useA? Listing p:X would be OK. But it might not be the best choice in the long run. It makes useA too tightly coupled to X. In fact, useA would work perfectly well if applied to an object of type:

class Y   a: bool;  d: String; end

This is a serious limitation to the use of class names in selecting operations. Without evasive action useA will be too tightly bound to unnecessary capabilities, hence, less reusable. Solutions hinge on some specific language policies and dispatching mechanisms.

Conformance.

class AThing  a: bool; end

op useA(a:  AThing)...;

Subsequently, useA could be invoked with something of class X (or rather any concrete subclass of X) whether X had ever been declared to be a subclass of AThing or not. If later, a special form of useA(p:Y) were found to be necessary to deal with Ys, it could be added. The original version would still be applied for Xs.

The only disadvantage of pure conformance is that implicit or unstatable invariants and interdependencies may be broken inadvertently. Despite efforts to the contrary, the placement of a group of attributes and operations within a particular class often implies more dependencies than are actually stated. While this is not at all desirable, the possibilities often exist in real designs.

Still, conformance-based strategies are excellent ways to implement systems, since they are so readily extensible and adaptable. But designs based on conformance assumptions can be difficult to transform into OO implementation languages that do not employ conformance-based dispatching. Most do not.

Dynamic lookups.

Views.

class XBasedAThing  is AThing
  x: X;  FORWARD(x, a)
end
...
useA(new XBasedAThing(x := myX))

This is not always pretty, but is very useful for patching together otherwise incompatible classes and applications. It preserves extensibility while still supporting class-based control of behavior. However, it also complicates object identity issues. An XBasedAThing forwarding messages to an X is not the same object as the inner X.

Refactoring.

Even when dealing with systems supporting conformance, dynamic lookups, or dynamic views, the best strategy is to refactor a hierarchy in a way that accommodates less restrictive usage by retrospectively defining new superclasses using the methods described in Chapter 7. This has the advantage of only explicitly defining classes that make some conceptual sense and/or are of known value to client applications. It has the disadvantage of almost always causing further design iteration.

Different versions of operations may be defined inside classes or at top-level in order to deal with arguments of different types. Resolution rules are required to determine which version to apply in a particular context. We have been implicitly assuming one of the broadest possible rules, dynamic closest match dispatching, which selects the best fitting version defined for the actual participants.

Multiple versions of operations may appear within classes and their subclasses, and/or as sets of ungrouped top-level operations. For simplicity, we will illustrate using top-level cases. For example:  

op credit(acct: Account, amt: Cash);

op credit(acct: CheckingAccount, amt: Cash);

Best-match dispatching follows the logic of relational inheritance (Chapter 7). The best version to use corresponds to the ``deepest'' defined relation/operation among the arguments. Here, when credit(a, x) is invoked in some context, if a were of class Checking Account or some subclass thereof, the credit(CheckingAccount, Cash) version would be selected. But if a were of class Account or some subclass of Account other than Checking Account, the credit(Account, Cash) version would be selected.

Argument-based operation overriding is sometimes easier to manage than subclassing. It is not necessary to explicitly state which version of which operation is being overridden during declarations, nor even to keep track of which version is overriding which, as long as some coherent subclassing relation holds when all versions are considered as a whole. For example, it is often acceptable if neither of two versions overrides the other, but both override a version that might conceptually exist, but because it is never needed, is not defined.

In ODL, the obj in class   construct may be used to indicate and control these mechanics explicitly. Using `` in'' is not a very good way to define operations since it ignores receivers and buries dispatching policies within internals. It is, however, a useful way to view them from a client-side perspective. This is especially valuable when checking the consistency of effects across all defined versions of an operation. For example, the combined view of credit is:

op credit(acct: Account, amt: Cash)
   when acct in CheckingAccount then
     % special version for checking accounts
   elsewhen acct in Account then
     % version for ordinary accounts
   else
     % ``cannot happen''
   end

In ODL, each of a series of guards assumes negation of the previous ones. Here, this reduces to the fact that the first listed matching case is selected. In accord with best-match dispatching policies, the subclass cases are listed first, so that the most special applicable version is invoked.

Ambiguity

In Chapter 7, we discussed measures to avoid ambiguity under multiple inheritance. Sets of operations dispatched on multiple arguments can get even more confusing and require similar care. It is possible to declare sets of versions leading to situations where there can be no best match. For example (using CCA and PCA as stand-ins for effects): 

class PreferredClient is Client ... end

op inspect(c: Client, a: CheckingAccount)  ==> CCA end

op inspect(c: PreferredClient, a: Account) ==> PCA end

Neither of these is an override of the other, although both of them are related to the ``base'' form:

op inspect(c: Client, a: Account) ==> CA end

None of these versions would be a unique best choice if inspect were invoked with a PreferredClient and a Checking Account. It is easiest to see this when these versions are unrolled using when and in. There are two ways to do it:

op inspect(c: Client, a: Account) % version 1
   when  c in PreferredClient then
     when   a in CheckingAccount then % (*) 
     else % a in Account %            PCA end
   else % c in Client 
     when   a in CheckingAccount then CCA
     else % a in Account %            CA  end end

op inspect(c: Client, a: Account) % version 2
   when   a in CheckingAccount then
     when   c in PreferredClient then % (*) 
     else % c in Client %             CCA end
   else % a in Account 
     when   c in PreferredClient then PCA
     else % c in Client %             CA  end end

It is just not clear from the declarations what to write in case (*). The two different unrollings make either PCA or CCA most tempting. While it is surely most reasonable to declare that this case somehow combines the effects of PCA and CCA, no one, least-wise a dumb dispatching rule, can do this for you. Either the design should be completed to cover all cases or else special dispatch resolution rules must be defined (as in CLOS  [2]).

Simulating Multiple Dispatch

Most object-oriented programming languages do not support full best-match dispatching rules. As with other caveats we have noted, this can affect the expression of designs, without affecting their logic.

Lack of best-match dispatching is a common source of programming-level errors. Without it, operations may be ``unrolled'' using type-tests. Another strategy is to transform it to simple selection dispatching. Here we describe the mechanics. These details may be safely ignored unless you need them, although they do demonstrate a model protocol that can be established across different classes for many related purposes.

Double Dispatching.

class A ... end
class SubA is A ... end

class B ... end
class SubB is  B ... end

op f(a: A,    b: B)    { P }
op f(a: SubA, b: SubB) { Q }
op f(a: A,    b: SubB) { R }

This setup corresponds to that seen for Accounts and Clients supporting inspect operations. P, Q and R are just stand-ins for the concrete code. A fourth version, f(SubA, B) could be added without changing any of the following logic.

The first step is to rename the versions depending on either one of the argument types. It does not matter which one, but for ambiguous designs the different choices will result in different behaviors. This is one reason to avoid ambiguous designs. Let's choose B. If we distinguish the versions on the exact B type, we can also recast all SubB declarations as just B. The procedure name will tell us which one to use.

op fB(a: A,    b: B) { P }
op fB(a: SubA, b: B) { Q }  

op fSubB(a: A, b: B) { R }

Because we arranged that the second argument ``does not matter'' for dispatching purposes, we may now safely embed these inside the A classes corresponding to the first argument types:

class A ...
  op fB(b: B)    { P }
  op fSubB(b: B) { R }
end
class SubA is A ...  
  op fB(b: B)    { Q }  
end

We could stop here, except that callers would need to know the right versions to invoke, which they do not. But the B's do. We may place the appropriate forwarders in the corresponding classes:

class B ...         
  op f(a: A) { a.fB(self) }    
end

class SubB is B ... 
  op f(a: A) { a.fSubB(self) } 
end

Optionally, a single top-level version may be defined to start things rolling:

op f(a: A, b: B) { b.f(a) }

Genericity and Dispatching

Selection and resolution rules also come into play with generic classes. There is some leeway between subclassing and parameterization for defining collections and related classes. For example, in Chapter 17, we could have defined a stack as follows:  

class NonParamStack
  empty: bool;
  op push(x: Any): ();
  op top: Any;
  op pop;
end

This would define a stack that could hold instances of any kind of objects whatsoever. This is OK for putting things into a stack, but sometimes less so when they are pulled out. Unless it somehow happens to have additional information, a client looking at the top element does not know anything at all about its capabilities. As far as type information is concerned, it could be anything.

On the other hand, if a client has a STACK[Window], it knows that all elements are Windows. The objects might still be of any subclass of Window; perhaps Bordered Window, Scrollable Window or whatever. But they are surely at least Windows. This guarantees that clients can perform window-based operations on all of the objects without having to bother with error-handling details. Parameterized classes are thus generally safer than unrestricted classes and lead to simpler use by clients.

You might think that you could declare something like class WindowStack is NonParamStack to get the same effects through subclassing. But this cannot be done without breaking subclass substitutability rules. The definition of push in NonParamStack indicates that Any kind of object may be pushed onto it. This must be restricted in the subclass to only push Windows. However, then the subclass would not be substitutable.

Type restrictions.

We will digress with an example that illustrates some of the resulting issues. Views and parameterized classes are often found together in designs. For example, suppose you need to define ordered sets, where the ordering may be based on any kind of key held by any kind of class: 

class Keyed  key: Any; end

class KeyedSet is SET[Keyed] ...
  op put(x: Keyed) { ... if lessThan(x.key, first.key) then ... end }
end

This could be used to hold, say, Accounts, via a view:

class KeyedAccount is Keyed
  a: Account;
  key: Balance { a.balance }
end  

fn lessThan(x: Balance, y: Balance): bool { x.val < y.val }

myset := new KeyedSet(...);
myset.put(new KeyedAccount(myAcct)); ...

This is not as safe as it looks. Because the KeyedSet can hold anything viewable as Keyed, any particular instance might be filled with just about anything. Maybe that is what you want. But if other such objects return different kinds of keys, then the comparison in put may attempt to compare Balances to, say, Bananas. Most likely you did not even define a version of lessThan that compares such things. This would result in a dispatch failure.

This problem is a consequence of the laxness of parameterized type rules. Here, it leads to the insensible notion that you can meaningfully compare any two arbitrary objects with a less-than operation, which you cannot.

The simplest way to maximize safety in this and most related situations is to define different kinds of ordered sets based on the types of their keys. The same general construction applies, but controlled by different kinds of Key classes, returning types for which less-than functions are known to be defined. More elegant-sounding solutions (if they exist) are hard to obtain without introducing more controversial type apparatus.

In Chapter 18, we noted that multiparticipant operations may be transformed into classes. Instead of defining deposits, withdrawals, and inspections as free-standing operations (or worse, as inappropriately received by clients, tellers, or accounts per se) they may be defined as the responsibility of corresponding coordinators:  

class Trans
  op inspect;
  op deposit(amt: Cash); ...
end

class CheckingTrans is Trans... end

class TransV1 is Trans
  generator TransGen1
  locals 
    c: fixed Client;  a: fixed Account;  t: fixed Teller; 
  end
  op inspect; ...
end

class CheckingTransV1 is CheckingTrans ...  
   generator CTransGen1 
end

By placing constructors within generators, clients may rely on the third sense of dispatching, object routing, providing the highest level of decoupling:

class TransGen1 ...  
  op mk(c: Client, a: Account, t: Teller): TransV1; 
end

class CTransGen1 ...
  op mk(c: Client, a: CheckingAccount, t: Teller): CheckingTrans;
end

op user { 
  t := TransGen1$mk(client1, account402, aTeller);
  t.deposit(100.00); ... }

The main limitation of this approach is that clients must know exactly which version of coordinator they wish to construct. Avoiding this entails creation of another top-level operation that uses argument-based dispatching to route construction requests to the appropriate generator, so that clients do not have to do so themselves. Thus, the two forms of dispatching do not always completely substitute for each other.

Routing Structures

Object routing is usually implemented via mediator objects. These can take several forms, including name servers and relays.

Name Servers.

A name server (or ID server) accepts requests describing the kinds of services needed, and returns the identity or other specifier of an object providing the service. For an extremely stripped down example:

class IDServer
  p: Printer;  d: Display;
  op getServer(req: Request): Any {
     if req.svc = "print" then reply p else reply d end }
end

Of course, the basic idea can and should be extended. The server may hold updatable collections of objects providing different services, maintain descriptions of their interfaces, find the ``best-fitting'' server for any given request, redirect inquiries to others when a good fit cannot be made, and so on.

These designs have intrinsic static typability problems. For example, the get Server procedure is listed as having a result type only of Any, since it returns identities of different kinds of objects corresponding to different kinds of requests. There is no simple way to say anything more specific at the type level. For the sake of safety, clients should be prepared for anything:

...
p: Any := reg.getServer("print");
if p in Printer then p.print(myPrintJob) else ... end;

Relays.

A relay receives requests and then routes them to designated service objects. For another overly simplified example:

class ServiceRelay ...
  m: MAP[ServiceDescription, Server];
  op register(s: ServiceDescription, v: Server) { m.put(s, v) }
  op svcRequest(s: ServiceDescription) {
     if m.has(s) then m.at(s).serve end }
end

The main difference between relays and name servers lies in their interfaces. A pure relay silently connects objects, while a pure name server tells one object who it should connect to. They have the same overall function as our object dispatching strategies and amount to manual simulations, extensions, or implementations of them. For example, we could have expressed the name server example directly in ODL as Printer$print(myPrintJob). The reverse transformation is pragmatically valuable. Any design implemented using languages and tools that do not support object dispatching (most do not) needs to be transformed to use manually defined name server and relay objects.

Topologies

Routers and dispatchers of all sorts must keep track of the existences and capabilities of many other objects. The resulting mediation networks may be organized into a number of topologies. It is often preferable to postpone commitments about particular forms to take advantage of those supported by system tools and services.

Central arbitration.

In a centrally arbitrated design, only one object or service knows about the entire system. All other objects register themselves and their interfaces with a master ``broker''. All communication is mediated by this master broker. It forwards all events to the appropriate objects. Backup forwarders may also be present to protect the system against failure of the main broker.  

Point-to-point.

In a fully distributed, point-to-point design, each object maintains all object and dispatching information for the system, locally resolves messages, and directly sends requests to the appropriate recipients.

Broadcast.

Broadcasts offer tremendous simplification of point-to-point strategies. In a broadcast-based design, objects send nonlocal requests to all other objects. Recipients simply ignore nonapplicable requests. Objects need not know about nonlocal capabilities at all, at the expense of generating a possibly unacceptable level of message traffic. 

Tree-structured.

Tree-structured designs represent a midpoint between fully central and fully distributed information. Each object (or an associated helper) knows about one or more routing-tree descendent objects, and routes those requests itself. All other nonlocal requests are sent to a parent object that might either be the recipient, or might know which of its tree descendents to send the message to, or failing these might forward to its parent. Various redundancies (e.g., secondary forwarders) may be built into this framework to protect against failures. The general idea of structured distributed OO routing is sometimes called cooperative dispatching. Systems developed in such a way are sometimes termed federated architectures. The history of network design suggests that as OO systems grow ever bigger and more distributed, such designs will remain among the few tractable options. Even though they possess increased complexity and dynamic overhead, they scale quite well.

Mixtures.

Aspects of these strategies may be combined. For example, a system might use point-to-point schemes for most messages, while also employing broadcast or restricted broadcast for others. These decisions might be based in part on physical system issues including communication hardware support and its reliability.

Controlling actions by reference to class membership is central to OO dispatching rules. Overriding operations abstractly and/or concretely defined in superclasses provides a means for specializing behaviors that correspond to the special properties of a subclass. Similarly, defining multiple versions of scripted operations on the basis of the class membership of their participants is a way of specializing coordinated actions to deal with special kinds of participants. Without these, extensibility, polymorphism, generality, and the concomitant ability to specialize would be lost.

Further Reading

Many of the readings noted in Chapter 7 include discussions of polymorphism and dispatching. Argument-based dispatching was pioneered in CLOS [2] and its precursors; see also Shrefl and Keppel [6]. Simulation of multiple dispatch was first described by Ingalls [4]. General routing and communication topologies are discussed in many texts, including Bertsekas and Gallager [1].

Exercises

1. Operation overriding is often used extensively in design, but not in analysis. Why is this so?

2. Some people think that obj in class is an evil construct that should not even be present in OO design and programming systems. Give one argument pro and one con.

3. Why is multiple versioning considered to be a better design practice than the use of type tests, even though they can be used to equivalent effect?

4. Explain how to reduce triple dispatching to double dispatching.

5. What is wrong with declaring
   class Comparable fn lessThan(other: Comparable): bool; end
   and using it as a basis for defining ORDERED_SETs?

6. Given the fact that relays and name servers of any form can be built, why are typed object routing mechanisms still useful?

References

1

D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, 1987.

2

D. Bobrow, L. DeMichel, R. Gabriel, S. Keene, G. Kiczales, and D. Moon. Common lisp object system specification. SIGPLAN Notices, September 1988.

3

A. Goldberg. Smalltalk 80: The Interactive Programming Environment. Addison-Wesley, 1984.

4

D. Ingalls. A simple technique for handling multiple dispatch. In OOPSLA '86. ACM, 1986.

5

R. Raj, E. Tempero, H. Levy, A. Black, N. Hutchinson, and E. Jul. Emerald: A general purpose programming language. Software -- Practice and Experience, 1991.

6

J. Shrefl and G. Keppel. Cooperation contracts. In 10th International Conference on the Entity-Relational Approach. Springer-Verlag, 1991.

Next: Chapter 22