How do multimethods solve the namespace issue?

Question

I am researching programming language design, and I am interested in the question of how to replace the popular single-dispatch message-passing OO paradigm with the multimethods generic-function paradigm. For the most part, it seems very straightforward, but I have recently become stuck and would appreciate some help.

Message-passing OO, in my mind, is one solution that solves two different problems. I explain what I mean in detail in the following pseudocode.

(1) It solves the dispatch problem:

=== in file animal.code ===

   - Animals can "bark"    - Dogs "bark" by printing "woof" to the screen.    - Cats "bark" by printing "meow" to the screen. 

=== in file myprogram.code ===

import animal.code for each animal a in list-of-animals :    a.bark() 

In this problem, "bark" is one method with multiple "branches" which operate differently depending upon the argument types. We implement "bark" once for each argument type we are interested in (Dogs and Cats). At runtime we are able to iterate through a list of animals and dynamically select the appropriate branch to take.

(2) It solves the namespace problem:

=== in file animal.code ===

   - Animals can "bark" 

=== in file tree.code ===

   - Trees have "bark" 

=== in file myprogram.code ===

import animal.code import tree.code  a = new-dog() a.bark() //Make the dog bark  …  t = new-tree() b = t.bark() //Retrieve the bark from the tree 

In this problem, "bark" is actually two conceptually different functions which just happen to have the same name. The type of the argument (whether dog or tree) determines which function we actually mean.

---

Multimethods elegantly solve problem number 1. But I don't understand how they solve problem number 2. For example, the first of the above two examples can be translated in a straightforward fashion to multimethods:

(1) Dogs and Cats using multimethods

=== in file animal.code ===

   - define generic function bark(Animal a)    - define method bark(Dog d) : print("woof")    - define method bark(Cat c) : print("meow") 

=== in file myprogram.code ===

import animal.code for each animal a in list-of-animals :    bark(a) 

The key point is that the method bark(Dog) is conceptually related to bark(Cat). The second example does not have this attribute, which is why I don't understand how multimethods solve the namespace issue.

(2) Why multimethods don't work for Animals and Trees

=== in file animal.code ===

   - define generic function bark(Animal a) 

=== in file tree.code ===

   - define generic function bark(Tree t) 

=== in file myprogram.code ===

import animal.code import tree.code  a = new-dog() bark(a)   /// Which bark function are we calling?  t = new-tree bark(t)  /// Which bark function are we calling? 

In this case, where should the generic function be defined? Should it be defined at the top-level, above both animal and tree? It doesn't make sense to think of bark for animal and tree as two methods of the same generic function because the two functions are conceptually different.

As far as I know, I haven't found any past work that's solved this problem yet. I have looked at Clojure multimethods, and CLOS multimethods and they have the same problem. I am crossing my fingers and hoping for either an elegant solution to the problem, or a persuading argument on why it's actually not a problem in real programming.

Please let me know if the question needs clarification. This is a fairly subtle (but important) point I think.

---

Thanks for the replies sanity, Rainer, Marcin, and Matthias. I understand your replies and completely agree that dynamic dispatch and namespace resolution are two different things. CLOS does not conflate the two ideas, whereas traditional message-passing OO does. This also allows for a straightforward extension of multimethods to multiple inheritance.

My question specifically is in the situation when the conflation is desirable.

The following is an example of what I mean.

=== file: XYZ.code ===

define class XYZ :    define get-x ()    define get-y ()    define get-z () 

=== file: POINT.code ===

define class POINT :    define get-x ()    define get-y () 

=== file: GENE.code ===

define class GENE :    define get-x ()    define get-xx ()    define get-y ()    define get-xy () 

==== file: my_program.code ===

import XYZ.code import POINT.code import GENE.code  obj = new-xyz() obj.get-x()  pt = new-point() pt.get-x()  gene = new-point() gene.get-x() 

Because of the conflation of namespace resolution with dispatch, the programmer can naively call get-x() on all three objects. This is also perfectly unambiguous. Each object "owns" its own set of methods, so there is no confusion as to what the programmer meant.

Contrast this to the multimethod version:

---

=== file: XYZ.code ===

define generic function get-x (XYZ) define generic function get-y (XYZ) define generic function get-z (XYZ) 

=== file: POINT.code ===

define generic function get-x (POINT) define generic function get-y (POINT) 

=== file: GENE.code ===

define generic function get-x (GENE) define generic function get-xx (GENE) define generic function get-y (GENE) define generic function get-xy (GENE) 

==== file: my_program.code ===

import XYZ.code import POINT.code import GENE.code  obj = new-xyz() XYZ:get-x(obj)  pt = new-point() POINT:get-x(pt)  gene = new-point() GENE:get-x(gene) 

Because get-x() of XYZ has no conceptual relation to get-x() of GENE, they are implemented as separate generic functions. Hence, the end programmer (in my_program.code) must explicitly qualify get-x() and tell the system which get-x() he actually means to call.

It is true that this explicit approach is clearer and easily generalizable to multiple dispatch and multiple inheritance. But using (abusing) dispatch to solve namespace issues is an extremely convenient feature of message-passing OO.

I personally feel that 98% of my own code is adequately expressed using single-dispatch and single-inheritance. I use this convenience of using dispatch for namespace resolution much more so than I use multiple-dispatch, so I am reluctant to give it up.

Is there a way to get me the best of both worlds? How do I avoid the need to explicitly qualify my function calls in a multi-method setting?

---

It seems that the consensus is that

• multimethods solve the dispatch problem but do not attack the namespace problem.
• functions that are conceptually different should have different names, and users should be expected to manually qualify them.

I then believe that, in cases where single-inheritance single-dispatch is sufficient, message-passing OO is more convenient than generic functions.

This sounds like it is open research then. If a language were to provide a mechanism for multimethods that may also be used for namespace resolution, would that be a desired feature?

I like the concept of generic functions, but currently feel they are optimized for making "very hard things not so hard" at the expense of making "trivial things slightly annoying". Since the majority of code is trivial, I still believe this is a worthwhile problem to solve.

Answer 1

Dynamic dispatch and namespace resolution are two different things. In many object systems classes are also used for namespaces. Also note that often both the class and the namespace are tied to a file. So these object systems conflate at least three things:

• class definitions with their slots and methods
• the namespace for identifiers
• the storage unit of source code

Common Lisp and its object system (CLOS) works differently:

• classes don't form a namespace
• generic functions and methods don't belong to classes and thus are not defined inside classes
• generic functions are defined as top-level functions and thus are not nested or local
• identifiers for generic functions are symbols
• symbols have their own namespace mechanism called packages
• generic functions are 'open'. One can add or delete methods at any time
• generic functions are first-class objects
• mathods are first-class objects
• classes and generic functions are also not conflated with files. You can define multiple classes and multiple generic functions in one file or in as many files as you want. You can also define classes and methods from running code (thus not tied to files) or something like a REPL (read eval print loop).

Style in CLOS:

• if a functionality needs dynamic dispatch and the functionality is closely related, then use one generic function with different methods
• if there are many different functionalities, but with a common name, don't put them in the same generic function. Create different generic functions.
• generic functions with the same name, but where the name is in different packages are different generic functions.

Example:

(defpackage "ANIMAL" (:use "CL"))  (in-package "ANIMAL")  (defclass animal () ()) (deflcass dog (animal) ()) (deflcass cat (animal) ()))  (defmethod bark ((an-animal dog)) (print 'woof)) (defmethod bark ((an-animal cat)) (print 'meow))   (bark (make-instance 'dog)) (bark (make-instance 'dog)) 

Note that the class ANIMAL and the package ANIMAL have the same name. But that is not necessary so. The names are not connected in any way. The DEFMETHOD implicitly creates a corresponding generic function.

If you add another package (for example GAME-ANIMALS), then the BARK generic function will be different. Unless these packages are related (for example one package uses the other).

From a different package (symbol namespace in Common Lisp), one can call these:

(animal:bark some-animal)  (game-animal:bark some-game-animal) 

A symbol has the syntax

PACKAGE-NAME::SYMBOL-NAME 

If the package is the same as the current package, then it can be omitted.

• ANIMAL::BARK refers to the symbol named BARK in the package ANIMAL. Note that there are two colons.
• AINMAL:BARK refers to the exported symbol BARK in the package ANIMAL. Note that there is only one colon. Exporting, importing and using are mechanisms defined for packages and their symbols. Thus they are independent of classes and generic functions, but it can be used to structure the namespace for the symbols naming those.

The more interesting case is when multimethods are actually used in generic functions:

(defmethod bite ((some-animal cat) (some-human human))   ...)  (defmethod bite ((some-animal dog) (some-food bone))   ...) 

Above uses the classes CAT, HUMAN, DOG and BONE. Which class should the generic function belong to? What would the special namespace look like?

Since generic functions dispatch over all arguments, it does not make direct sense to conflate the generic function with a special namespace and make it a definition in a single class.

Motivation:

Generic functions were added in the 80s to Lisp by developers at Xerox PARC (for Common LOOPS) and at Symbolics for New Flavors. One wanted to get rid of an additional calling mechanism (message passing) and bring dispatch to ordinary (top-level) functions. New Flavors had single dispatch, but generic functions with multiple arguments. The research into Common LOOPS then brought multiple dispatch. New Flavors and Common LOOPS were then replaced by the standardized CLOS. These ideas then were brought to other languages like Dylan.

Since the example code in the question does not use anything generic functions have to offer, it looks like one has to give up something.

When single dispatch, message passing and single inheritance is sufficient, then generic functions may look like a step back. The reason for this is, as mentioned, that one does not want to put all kinds of similar named functionality into one generic function.

When

(defmethod bark ((some-animal dog)) ...) (defmethod bark ((some-tree oak)) ...) 

look similar, they are two conceptually different actions.

But more:

(defmethod bark ((some-animal dog) tone loudness duration)    ...)  (defmethod bark ((some-tree oak)) ...) 

Now suddenly the parameter lists for the same named generic function looks different. Should that be allowed to be one generic function? If not, how do we call BARK on various objects in a list of things with the right parameters?

In real Lisp code generic functions usually look much more complicated with several required and optional arguments.

In Common Lisp generic functions also not only have a single method type. There are different types of methods and various ways to combine them. It makes only sense to combine them, when they really belong to a certain generic function.

Since generic functions are also first class objects, they can be passed around, returned from functions and stored in data structures. At this point the generic function object itself is important, not its name anymore.

For the simple case where I have an object, which has x and y coordinates and can act as a point, I would inherit for the objects's class from a POINT class (maybe as some mixin). Then I would import the GET-X and GET-Y symbols into some namespace - where necessary.

There are other languages which are more different from Lisp/CLOS and which attempt(ed) to support multimethods:

• MultiJava
• Runabout
• C#
• Fortress

There seems to be many attempts to add it to Java.

Answer 2

Your example for "Why multimethods won't work" presumes that you can define two identically-named generic functions in the same language namespace. This is generally not the case; for example, Clojure multimethods belong explicitly to a namespace, so if you have two such generic functions with the same name, you would need to make clear which you are using.

In short, functions that are "conceptually different" will always either have different names, or live in different namespaces.