Multiple Dispatch: A Powerful Programming Paradigm

Julia is one of my all-time favorite programming languages. Not only is it easy to pick up like Python, but it also has the speed of C. It is said, however, that Julia users come for the performance and stay for multiple dispatch. But what is this curious feature, and what makes it appealing for newcomers and veterans alike?

How does Multiple Dispatch Work?

We begin by recollecting what Julia’s dynamic type system looks like. Julia types can be classified as concrete or abstract (there’s also composite and parametric, but let’s forget about those for the time being). Abstract types form the backbone of the type hierarchy into which concrete types may fit.

There are many ways to represent numbers in Julia: a given number might be real or complex, rational or irrational, signed or unsigned. They are organized in a hierarchy, a subset of which has been laid out in the tree above. Leaf nodes are concrete types, while intermediate nodes are abstract types. Indeed, concrete types may not be subtyped in Julia; their super-types are always abstract types. This reflects the inheritance of behavior rather than structure. For a more detailed overview of the Julia type system, we refer to the user manual.

We also note the distinction between functions and methods. A function can have multiple behaviors. By definition, one possible behavior of a function is called a method. For an in-depth discussion about Julia methods, see here.

Now, multiple dispatch is an execution rule by which the behavior of a function is determined by the combination and count of argument types (according to their highest levels of specificity). In other words, multiple dispatch decides which method to execute depending on the combination of the input types of a function.

For example, we may define the following:

The function encounter is overloaded, and for a given input combination, will choose the desired behavior based on input types. In the code above, a Tourist is a subtype of Person, but a deer will have a different reaction to a Tourist than a generic Person. We can easily define additional and more complex function behaviors by adding an additional input arguments, for example foo.

Matching based on all input types is sensible in many settings, including in mathematics:

Multiple dispatch is particularly useful for mathematical code, where it makes little sense to artificially deem the operations to "belong" to one argument more than any of the others: does the addition operation in x + y belong to x any more than it does to y? (Julia Manual)

We highlight two concrete benefits of multiple dispatch below.

Expressivity

Languages which implement multiple dispatch have exponentially greater expressiveness than those which do not. Under zero dispatch, a function has only a single behavior for any admissible combination of inputs. Under single dispatch (where a function dispatches on a single input), the number of possible behaviors or methods is linear in the size of the input space. Under multiple dispatch, the number of possible behaviors depends on the product of the sizes of all input spaces! In other words, the number of behaviors that can be expressed is on the order of

This is certainly a large space and allows the user ample room to exert control over function behavior via higher order specificity.

Code Reuse

As touted in my go-to guide to best Programming practices, Extreme Programming Explained by Kent Beck and Cynthia Andres, code reuse is of utmost importance in software design. It saves us programmers valuable time and energy by eliminating code duplication as much as possible.

How does multiple dispatch facilitate the sharing, repurposing, and ultimately reuse of Julia packages written by authors who’ve never met or spoken to one another? In Julia, one can build upon a predefined type and its host of behaviors simply by defining a new function which operates on a different combination or ordering of input types. For example, if I wanted to extend the demo.jl code above, I could import the package and build on existing types or define new behaviors for the encounter function as follows.

It is straightforward to preserve and add on to predefined types and functions, such as Person, Tourist, and encounter.

Tip: to extend a function from another package, one must import it explicitly. For example, to extend the determinant **** function from the linear algebra module, one must first add the following line to the top of the script

We remark that familiar concepts such as structure inheritance and function overloading in statically typed languages are not as optimal for code-reuse for subtle reasons. In a statically typed system like C++, for example, the static types of the arguments of an overloaded function are used to determine function behavior, rather than more specific types possibly unknown to the compiler until runtime. This makes it difficult to efficiently enforce correct behavior. Indeed, multiple dispatch is largely responsible for the uncommonly large amount of code reuse in the Julia ecosystem.

Summary

Multiple dispatch enables higher order expressivity by dispatching on combinations of types of function inputs. Multiple dispatch also promotes code reuse kudos to these two properties:

We can define new types on which existing operations can be applied
We can define new operations which can be applied on existing types

These make it easy for users to build on existing packages and the functionalities and predefined types they bring. As it turns out, it also contributes to Julia’s speed and performance by facilitating specialization and optimization of compiled code for various data types. Multiple dispatch is undoubtedly a valuable feature that sets Julia apart from other scientific computing languages like Matlab and a boon for the members of the Julia community.