As a proof-of-concept, an external dispatch mechanism proposal was adapted and implemented for Eiffel. This is the first quite complete compiler version for this mechanism.
A working version of the compiler is finished (with multiple examples). Fill free to try it out (it works for EiffelSoftware/ISE and GOBO compilers, although the latter requires a -gobo argument due to its lack of once classes). No need to install other libraries, a self-contained executable java jar file (version 11) is provided for the compiler.
The approach taken was to build an ED-Eiffel (External Dispatch Eiffel) to Eiffel compiler (using ANTLR4). For the time being, some limitations were imposed: In this compiler, the use of external dispatch is limited to provided classes (to ensure a statically safe implementation, existing library classes were left out because, in current version, those classes are not parsed). Also note that this compiler relegates almost all of Eiffel's semantic validations (those not related with external dispatch) to the Eiffel compiler (develop a front-end for a complete Eiffel compiler is not a trivial task). Another limitation is SCOOP. The generated code is not (yet) thread-safe, thus SCOOP or Eiffel thread library, should not be used with this compiler.
The mechanism
This mechanism generalizes the object-oriented (internal) single dispatch mechanism (dynamic binding) to a (external) dynamic n‑ary dispatch mechanism. It provides a safe OO modular alternative solution to many (related) problems: binary methods, covariant redefinition, decorator pattern, the expression problem, visitor pattern, creational patterns, statically ensured global downcasts.
Let me start with an example that shows the limitations and problems with the – nevertheless, very powerful – single (internal) dispatch OO mechanism (dynamic binding).
Consider the classical problem of devising a solution for handling figures or shapes in a 2D space. For instance: squares, circles, and so on. An object oriented solution starts by looking at the (abstract) data, enriching their interface with proper useful public (exported) features (perimeter, area, position, move, draw, etc.) and their semantics (contracts) [note-1] (Abstract Data Types is the proper formal designation). For instance: CIRCLE, SQUARE, and, of course, the deferred parent class SHAPE.

Binary Methods
Consider now the problem of shape interaction, for instance, the distance between two shapes. How can we provide a modular, extendible OO solution?
Clearly, the (analytical closed-form formula) distance function depends on the type of two (possibly different) shapes. One may accept that the distance of two similar shapes (e.g. CIRCLE) could be the responsibility of the CIRCLE class, but what about the distance between a CIRCLE and a SQUARE? Should it be in CIRCLE? In SQUARE? In both? Elsewhere?
What about the distance of two shape objects whose direct types can only be known at runtime?
This is a typical example of a binary method (equal feature is another one).
Clearly, to fetch the proper distance function, a single dispatch approach will not be enough. We need a dynamic binding mechanism applicable to multiple dispatch objects (two).
The next problem is: where should this function be placed? Inside one of the dispatch object's class [note-2]? Outside classes (multi-methods: Common LISP, Cecil)? Elsewhere?
Inside one of the dispatch objects, raises symmetry problems (should we put it in all participating dispatch object classes?), and, most of all, serious extendibility and modularity problems: adding a new class (e.g. a triangle) to the pool would break existing classes (smashing Meyer's open-closed principle). A new player requires taking into consideration all its relations with existing players (triangle-circle, triangle-square, and so on).
Outside classes is not Object-Oriented (period). The target of the message is not an object (we would lose "the baby with the bath water" resulting, IMHO, in an hybrid ugly and non modular procedural-OO approach).
The proposed solution
Elsewhere is the answer. The approach taken is simple to state (but it does require some time to fully grasp all the implications and involving details): generalize the object oriented creation mechanism to allow (external) dynamic n‑ary dispatch, and leave untouched all remaining object oriented language mechanisms (after creation, external dispatched objects behave like any other). As such, with this approach, in the creation of an external dispatch object we no longer know the direct type of the created object (but we do know its target type).
Syntactically, the external dispatch creation construct requires new creation alternatives (no extra reserved word is required). For the shape problem:
two_shapes: TWO_SHAPES (...) -- create instruction: create (s1,s2).two_shapes -- external dispatch! s1 and s2 are non-Void references to SHAPE objects -- or, using a create expression: two_shapes := create {TWO_SHAPES}(s1,s2) -- external dispatch! (s1,s2) is the object dispatch tuple (...) print(two_shapes.distance.out + "%N")
Creating an external dispatched object requires a non-empty [note-3] tuple of objects (Void is not an option) and proper type rules to ensure a static safe mechanism.
In an external dispatch class the objects involved in the creation dispatch tuple behave exactly as "Current" in Eiffel ("this" in Java, C++). They are non-Void immutable read-only entities (with the difference, in Eiffel, of being exported to all clients) whose type (may) vary covariantly in descendant classes. Thus, one may foresee that the type safety of Current applies also to those entities (it does).
In this shape example, we could have a target external dispatch class TWO_SHAPES* (deferred), accepting two SHAPE objects in its creation dispatch tuple.
deferred class TWO_SHAPES(s1,s2: SHAPE) feature distance: REAL_64 deferred end end -- TWO_SHAPES
Of course a statically safe mechanism must ensure external dispatch class instantiability for all possible pair instances of SHAPE objects, thus we need enough TWO_SHAPES effective descendant classes to ensure that (the compiler ensures this type rule). We also need static rules to ensure no ambiguity in this dispatch instantiation (ignoring some implementation BUG that I might have not detected, both rules are statically ensured in the developed compiler). In this example, we need classes to provide an analytical solution to the distance problem between two specific SHAPE objects. TWO_CIRCLES, TWO_SQUARES, SQUARE_CIRCLE (no need for a CIRCLE_SQUARE), and so on.
class TWO_CIRCLES(c1,c2: CIRCLE) inherit TWO_SHAPES ... end class TWO_SQUARES(s1,s2: SQUARE) inherit TWO_SHAPES ... end class SQUARE_CIRCLE(s: SQUARE; c: CIRCLE) inherit TWO_SHAPES ... end
Look at the example "shapes" for a concrete working application of the mechanism.
Please note that the excellent abstraction and modularity properties of OOP are at our disposal in this approach. An intersect boolean function can be fully implemented in the TWO_SHAPES class, applicable to all existing and future SHAPES:
intersect: BOOLEAN do Result := distance <= 0 end
Covariance and contravariance
A covariant redefinition in the signature of inherited routines (to be more precise, covariant formal arguments types, covariant return types are not as problematic) is a problem in OO programming languages that allow it (such as Eiffel). Several solutions have been proposed. Outside Eiffel world, demonizing it is a frequent one, with several authors defending the opposite contravariant approach. However, a contravariant redefinition (IMHO) is only appealing from a theoretical point of view (for contractless routines). In practice, I'm still looking for convincing examples (on the other hand, many can be found for covariance). Finally, a contravariant redefinition is not compatible with contracts [note-4].
In Eiffel, global analysis and catcall type rule are possible solutions, but sometimes they might be too conservative (rejecting correct programs). The proposed external dispatch language construct is a statically safe alternative to solve this problem. In fact, binary methods (in general, n‑ary methods/routines) are close related with the covariance problem. A dynamic binding mechanism that selects the proper (covariant) method is the solution. All the examples given, have statically safe covariant redefinitions (not of routine's formal arguments, but of external dispatch class formal arguments).
Decorators
A decorator is an useful pattern presented by GoF. The idea it to enhance a type with extra behavior (an extended interface, and/or add extra behavior to existing classes). To achieve that, both inheritance and client relation are used to a given class, and all public features are redefined to invoke the applicable client's attribute feature:
class EA inherit A redefine ... end create make feature make(obj: A) do a := obj ... end a: A; f do a.f end -- extra behavior can be added or replace previous one ... end -- EA
This solution works very well, except when we might require multiple related "decorations" (that is, decorate a class A, and also decorate an A's descendant B class to a different implementation). To achieve that, an external single dispatch mechanism would do the trick (it does). See geometry examples ("is_convex").
The Expression Problem
This problem exposes the duality dilemma between procedural/functional and OO approaches. In the former, it is easy to add a new function, but hard to extend with new data (for all existing functions); The latter, is easy to add new data, but difficult to extend with a new function (to all existing ADTs). To be more rigorous, the last sentence is not entirely correct (inheritance, polymorphism and dynamic binding makes all the difference). If one can add the new function (feature) in the topmost parent class, and its implementation works for descendant classes, it is a simple and easy solution. Nevertheless, it requires opening the parent class, and there are indeed many cases where the sentence is essentially correct.
Again, an external dispatch mechanism gives a very modular and simple solution. See expression-problem example.
Visitors
Another very useful design pattern is the visitor (ANTLR4 supports its use to iterate parse trees). Visitors allow the execution of operations (e.g. semantic analysis, interpretation, ...) on elements of a data structure (e.g. a tree) without changing them. In general, the operation to be performed depends on the type of element. To solve this problem, visitors use a double-dispatch approach. As such, it comes as no surprise that external dispatch is an alternative (simpler and more modular) solution.
Existing visitor pattern requires a previous knowledge of all of the (to be) visited classes of the visit (accept) usage. That is, to implement a visitor one need to prepare the elements of the data structure to be visited with an accept (alike) operation implemented with a (single dispatch) visit of the visitor concrete operation. That is a lot of error prone code implementation (necessary in existing languages to implement double-dispatch). With external dispatch no such restrictions and bookkeeping are required. One can simply implement a visitor alike application to any element type. No accept and visit operations are required (one can name them for what they do), and the data structure elements don't need to know of such future visit operation. In the prefix-calculator visitors were implemented for semantic analysis (the "visit" was named: "passed"), and for execution/interpretation (here the "visit" was named "value").
See prefix-calculator and (dummy) visitor examples (in the former, I've "abused" on external-dispatch, using it for semantic analysis, expression interpretation, and binary operators application).
Creational patterns
The approach taken of extending object creation for an n‑ary external dispatch mechanism makes it a very strong candidate to be used for different creational patterns. For example, one may devise a single external dispatch application, that abstracts object creating, allowing the construction of either debug versions of objects (with proper logging registration), or normal versions, depending only on the type of a single selection object (e.g. DEBUG, NORMAL).
Aspect-Oriented Programming
The last log example is also one of the classical applications of aspect-oriented programming. The external dispatch mechanism allows adding/modifying the behavior of existing classes without changing them (the prefix-calculator example shows that clearly). It is not AOP, but it does provide a statically safe and modular alternative to, at least, some of the same problems (without some modularity problems that exist in AOP). One can separate different aspects completely from existing classes. The prefix-calculator example shows it in practice, by completely separating semantic analysis, and expression interpretation from the nodes of the created parse tree.
Statically ensured global downcasts
Consider now the problem of downcast an object reference to a subtype entity reference. In Eiffel we can do that either with the (now obsolete) reverse assignment attempt, or with an object test expression. The external dispatch mechanism provides another alternative. In fact, a possible may of looking at it, is that it is a static safe mechanism to "downcast" the dispatch tuple object(s) to Current alike attributes in external classes. In each of those classes there will exist downcasted safe non-Void references to those objects. The compiler is able to statically ensure a successful downcast (to whatever effective external dispatch classes defined). Thus, no exception will ever arise from an unsuccessful downcast. Of course this downcast operation is not local (as the existing ones) [note-5], and also not to a single type, but externalized to external dispatch classes (each one with its downcasted references in their class formal arguments). Sometimes that might be desirable (separation of concerns), other times is might not. Either way it is a new programming alternative at our disposal. See example "downcast".
Once objects
Using object creation for n‑ary dynamic binding raises the immediate objection that an object needs to be instantiated whenever we need to (externally) dispatch. Although, in practice, we may alleviate the problem (in the first example given, one can store all TWO_SHAPES objects and the iterate them to get distances), it is, nevertheless, a correct statement (so far).
To solve this problem when necessary, an once("object") class mechanism was also implemented to ensure the dispatch the same object given a tuple of dispatch objects (a class singleton is also implemented). See examples: geometry-once, dummy06-once-object, and dummy05-once (for class singleton).
Concluding remarks
Multiple dispatch exists for many years and it is widely recognized as a solution for some of the listed problems. However, few programming languages support it, and, to my knowledge, all of them use language mechanisms that either are not OO, or have serious symmetry and modularity problems. The presented language mechanism – extending the object creation to allow n‑ary (dynamic) dispatch – does not have these problems, providing an OO, modular, static safe solution.
—
[note-1] Unlike the procedural (dual) approach (that starts by looking at the top functions to be implemented), the OO approach is, by far, a much better problem solving approach. In short, because: - it allows the definition of deferred classes and features (no similar counterpart in the procedural approach) -- for instance SHAPE*; - strongly coupled features are kept together in modular self-contained entities (instead of being spread away in functions strongly coupled with many data structures); - polymorphism and dynamic binding allows a safe selection, at runtime, of the proper feature to be executed. These excellent problem solving features make OOP stand apart among other programming alternatives (procedural, functional, logical programming approaches), specially when solving large complex problems.
[note-2] If the dispatch targets one of the dispatch tuple objects (or "Current" in normal OO mechanism), then we have an internal dispatch mechanism; otherwise it will be an external dispatch mechanism.
[note-3] An empty tuple is the same as a non-existing tuple. That is, the normal OO creation mechanism (consistent with Eiffel's approach of omitting braces when no argument exists).
[note-4] A dummy example (using presented SHAPE classes) just to prove the point:
class A feature f(c: CIRCLE) require c.radius = 1 -- unitary circle required do ... end end class B inherit A redefine f end feature f(s: SHAPE) -- invalid Eiffel (contravariant redefinition) do ... end endIn class B, what is the meaning of radius in a SHAPE object?
[note-5] As such, it can be questioned my use of the term "downcast" in this context. Nevertheless, I decided to use it because it does provide a downcast solution, and because it is an interesting alternative point of view of the external dispatch mechanism.