Are functions mutable in multiple dispatch systems?

Question

Have I understood correctly that in (most? some?) multiple dispatch languages each method gets added to the function at some point in time of program's execution.

Can I then conclude that multiple dispatch as a feature forces functions to be mutable?

Is there a multiple dispatch language, where all methods are attached to a (generic)function together (at load time?), so that it's not possible to see the function in different states at different points in time?

Perhaps a short answer is that in Julia, each *generic function* is a collection of functions, for different signatures, each of which is not mutable. Most Julia *generic function* calls choose the specific function signature to call at compile time using the type inference system. If you would detail the *stateless programming* features you are concerned about, it would help address them. — Dan Getz, Nov 18 '16 at 09:34
@DanGetz, I wasn't actually *concerned* about mutability -- I just wanted to understand multimethods better. I now edited my question accordingly. — Aivar, Nov 18 '16 at 10:38

score 5 · Accepted Answer · answered Nov 18 '16 at 12:22

at some point in time of program's execution.

In Common Lisp the methods get added/replaced when the method definitions are executed - for a compiled system this is typically at load-time of the compiled code - not necessarily during the program's execution.

Remember, that Common Lisp has an object system (CLOS, the Common Lisp Object System), which is defined by its behaviour. It's slightly different from a language or a language extension.

Common Lisp allows runtime modification of the object system. For example also adding/removing/replacing methods.

Common Lisp also may combine more than one applicable method into an effective method, which then gets executed. Typical example: all applicable :before methods and the most specific applicable primary method will be combined into one effective method.

There exist extensions for CLOS in some implementations, which seal a generic function against changes.

For a longer treatment of the idea of an object system see: The Structure of a Programming Language Revolution by Richard P. Gabriel.

score 3 · Answer 2 · answered Nov 21 '16 at 10:31

In Common Lisp, you can read the following from the specification:

7.6.1 Introduction to Generic Functions

When a defgeneric form is evaluated, one of three actions is taken (due to ensure-generic-function):

If a generic function of the given name already exists, the existing generic function object is modified. Methods specified by the current defgeneric form are added, and any methods in the existing generic function that were defined by a previous defgeneric form are removed. Methods added by the current defgeneric form might replace methods defined by defmethod, defclass, define-condition, or defstruct. No other methods in the generic function are affected or replaced.

If the given name names an ordinary function, a macro, or a special operator, an error is signaled.

Otherwise a generic function is created with the methods specified by the method definitions in the defgeneric form.

7.6.2 Introduction to Methods

When a method-defining form is evaluated, a method object is created and one of four actions is taken:

If a generic function of the given name already exists and if a method object already exists that agrees with the new one on parameter specializers and qualifiers, the new method object replaces the old one. For a definition of one method agreeing with another on parameter specializers and qualifiers, see Section 7.6.3 (Agreement on Parameter Specializers and Qualifiers).

If a generic function of the given name already exists and if there is no method object that agrees with the new one on parameter specializers and qualifiers, the existing generic function object is modified to contain the new method object.

If the given name names an ordinary function, a macro, or a special operator, an error is signaled.

Otherwise a generic function is created with the method specified by the method-defining form.

The definition of ensure-generic-function:

If function-name specifies a generic function that has a different value for the :lambda-list argument, and the new value is congruent with the lambda lists of all existing methods or there are no methods, the value is changed; otherwise an error is signaled.

If function-name specifies a generic function that has a different value for the :generic-function-class argument and if the new generic function class is compatible with the old, change-class is called to change the class of the generic function; otherwise an error is signaled.

If function-name specifies a generic function that has a different value for the :method-class argument, the value is changed, but any existing methods are not changed.

You also have add-method and remove-method.

As you can see, generic functions retain their identify between defmethod definitions, and even between defgeneric definitions. Generic functions are mutable in Common Lisp.

In Julia, you can read the following from the documentation:

Defining Methods

To define a function with multiple methods, one simply defines the function multiple times, with different numbers and types of arguments. The first method definition for a function creates the function object, and subsequent method definitions add new methods to the existing function object.

As you can see, functions objects are mutable in Julia.

This says nothing about all other multiple dispatch languages. You can invent a multiple dispatch language right now just for the purpose of showing you can do it with immutability, e.g. adding methods would return a new function similar to the previous function but with the added method. Or a language where functions are generated statically at compile-time, such that you can't change it at runtime in any way, not even to add or remove methods.

score 2 · Answer 3 · edited Jun 20 '20 at 09:12

Paraphrasing from the excellent "Getting started with Julia" book which has a nice section on this (emphasis mine):

We already saw that functions are inherently defined as generic, that is, they can be used for different types of their arguments. The compiler will generate a separate version of the function each time it is called with arguments of a new type. A concrete version of a function for a specific combination of argument types is called a method in Julia. To define a new method for a function (also called overloading), just use the same function name but a different signature, that is, with different argument types.

A list of all the methods is stored in a virtual method table ( vtable ) on the function itself; methods do not belong to a particular type. When a function is called, Julia will do a lookup in that vtable at runtime to find which concrete method it should call based on the types of all its arguments; this is Julia's mechanism of multiple dispatch, which neither Python, nor C++ or Fortran implements. It allows open extensions where normal object-oriented code would have forced you to change a class or subclass an existing class and thus change your library. Note that only the positional arguments are taken into account for multiple dispatch, and not the keyword arguments.

For each of these different methods, specialized low-level code is generated, targeted to the processor's instruction set. In contrast to object-oriented (OO) languages, vtable is stored in the function, and not in the type (or class). In OO languages, a method is called on a single object, object.method(), which is generally called single dispatch. In Julia, one can say that a function belongs to multiple types, or that a function is specialized or overloaded for different types. Julia's ability to compile code that reads like a high-level dynamic language into machine code that performs like C almost entirely is derived from its ability to do multiple dispatch.

So, the way I understand this (I may be wrong) is that:

The generic function needs to be defined in the session before you can use it
Explicitly defined methods for concrete arguments are added to the function's multiple-dispatch lookup table at the point where they're defined.
Whenever a function is called with specific arguments for which an explicitly defined method does not exist, a concrete version for those arguments is compiled and added to the vtable. (however, this does not show up as an explicit method if you run methods() on that function name)
The first call of such a function will result in some compilation overhead; however, subsequent calls will use the existing compiled version*.

I wouldn't say this makes functions mutable though, that's an altogether different issue. You can confirm yourself they're immutable using the isimmutable() function on a function 'handle'.

_{*I know modules can be precompiled, but I am not entirely sure if these on-the-fly compiled versions are saved between sessions in any form -- comments welcome :)}

score 2 · Answer 4 · answered Nov 18 '16 at 13:15

Dynamicity can be a real asset in your application, if only for debugging. Trying to prevent a function from being later updated, redefined, etc. might be a little bit short-sighted. But if you are sure you want static dispatch, you can define your own class of generic functions thanks to the MOP, the Meta-Object Protocol, which is not part of the standard but still largely supported. That's what the Inlined-Generic-Function library provides (and this is possible because CLOS is open to extensions).

score 1 · Answer 5 · answered Oct 17 '18 at 00:40

In Dylan, methods are generally added to a generic function at compile time, but they may also be added at run time (via add-method or remove-method). However, a generic function may be sealed, which prevents libraries other than the one in which the g.f. is defined from adding methods. So to answer your question, in Dylan generic functions are always mutable within the defining library but they may be rendered immutable to other libraries.

Are functions mutable in multiple dispatch systems?

5 Answers5