By: Great Lakes Consulting

Re-posted from: https://blog.glcs.io/multiple-dispatch

Julia is a relatively new,
free, and open-source programming language.
It has a syntax
similar to that of other popular programming languages
such as MATLAB and Python,
but it boasts being able to achieve C-like speeds.

One of the core design philosophies of Julia
that distinguishes it
from a lot of other languages
is multiple dispatch.
In essence,
multiple dispatch allows
writing multiple implementations
of a single function
based on different input types.
But unlike single dispatch
which relies on the static, compile-time types
of all but one of the inputs,
multiple dispatch chooses what implementation to call
using the runtime types.

It makes writing generic code a cinch,
allowing packages to work together seamlessly
and enabling a high degree of composability.

In this post,
we will learn about
multiple dispatch
in Julia.
We will discuss how to utilize it
and how it compares to single dispatch,
typically used
in object-oriented languages.

This post assumes you already have
a basic understanding
of Julia’s type system.
If you haven’t yet,
check out our earlier
post to learn more.

Functions and Methods

To understand multiple dispatch,
we first need to understand
the difference between functions and methods.

In Julia,
a function essentially is just a name.
This name is used to refer to the function
and to call the function.
What a function does when called
is determined by the methods
associated with the function.
A method is an implementation
of a function
for a given set of input types.

Let’s illustrate this concept with code.

First, we will define a function
with no methods,
just to show that it can be done:

julia> function no_methods end
no_methods (generic function with 0 methods)

When declaring a function, however,
we typically also define an associated method:

julia> function func(x, y) # Method 1
           x + y
       end
func (generic function with 1 method)

Here,
we created the function func
and defined a method
that adds the two function inputs.
Call this method 1.

Now let’s add another method,
method 2.
To do so,
we need to provide type annotations
to the input variables:

julia> function func(x::String, y::String) # Method 2
           x * y
       end
func (generic function with 2 methods)

Notice that we didn’t create
a new function with one method.
Because we used the same function name,
we added a method to the already existing function.

Let’s add one more method,
method 3:

julia> function func(x::String, y::Integer) # Method 3
           x^y
       end
func (generic function with 3 methods)

Methods can also have different numbers of arguments.
The previous methods all had two arguments,
so let’s create a method with three arguments,
method 4:

julia> function func(x::String, y::Integer, z::Integer) # Method 4
           func(x, y)[1:z]
       end
func (generic function with 4 methods)

Now let’s see multiple dispatch in action.

Multiple Dispatch

When func is called,
Julia uses the types of the input arguments
to determine which method to dispatch to.
In particular,
the input types of multiple arguments
(actually, all of them)
are considered,
hence the name multiple dispatch.
If the types of the inputs
match one of the method signatures,
that method will be called.

But what about func("hi", "there")?
In this case,
both inputs are Strings,
so that matches method 2.
But String is a subtype of Any,
so the inputs also match method 1!
In cases like this
where multiple methods match,
the most specific method will be called.
So, in this case,
func("hi", "there") will dispatch to method 2
because String is a more specific type than Any.

If no methods match
or if there is not one single most specific method,
a MethodError will be thrown.

So,
the methods we defined for func
will be called in the following cases:

• Method 1:
  When two inputs are given
  and no more specific methods exist.
  Examples:

  julia> func(1, 2)
  3
  
  julia> func([3, 4], [5, 6])
  2-element Vector{Int64}:
    8
   10
  

• Method 2:
  When two String inputs are given.
  Example:

  julia> func("hi ", "there")
  "hi there"
  

• Method 3:
  When two inputs are given:
  first a String and then an Integer.
  (Remember, though, that abstract types,
  like Integer,
  cannot be instantiated,
  so when we say the second input is an Integer,
  we really mean it is of a type
  that is a subtype of Integer.
  In other words,
  y isa Integer must evaluate to true.)
  Examples:

  julia> func("eat ", 3)
  "eat eat eat "
  
  julia> func("speak ", UInt32(2))
  "speak speak "
  

• Method 4:
  When three inputs are given:
  first a String, then an Integer,
  and then another Integer.
  (Note that y and z
  do not have to be of the same type,
  i.e., y could be an Int64,
  while z could be a Bool.)
  Examples:

  julia> func("repeat", 5, 6)
  "repeat"
  
  julia> func("first letter", 1, true)
  "f"
  

Now, you may be thinking
that this just looks like method overloading.
And you would be correct
that the above examples
haven’t really demonstrated
the power of multiple dispatch.
So,
let’s compare multiple dispatch
to single dispatch.

Multiple Dispatch vs Single Dispatch

Having many method definitions
is also possible
with single dispatch.
However,
with single dispatch,
the compile-time types of the inputs
(except the first)
are used to decide which method to call.

Single dispatch uses the runtime type
of just the first function argument,
while multiple dispatch uses the runtime types
of all the function arguments.

Consider the following Java example:

abstract public class A
{
    public void func(A a)
    {
        System.out.println("Method AA");
    }
}

public class B extends A
{
    public void func(A a)
    {
        System.out.println("Method BA");
    }

    public void func(B b)
    {
        System.out.println("Method BB");
    }
}

public class Main
{
    public static void main(String[] args)
    {
        A ab = new B();
        B b = new B();

        ab.func(ab); // Method BA
        b.func(b); // Method BB
    }
}

In this example,
even though both ab and b
are instantiated as B objects,
b.func(ab) prints Method BA,
whereas b.func(b) prints Method BB.
This difference is because
ab and b have different compile-time types
(also called declared or static types):
ab is of type A,
whereas b is of type B.

Now let’s compare this to Julia:

# From package PkgA.jl
abstract type A end
func(a1::A, a2::A) = println("Method AA")

# From package PkgB.jl
import PkgA: A, func
struct B <: A end # `B <: A` means `B` is a subtype of `A`
func(b::B, a::A) = println("Method BA")
func(b1::B, b2::B) = println("Method BB")

# In the REPL or in a .jl file
using PkgA, PkgB

ab::A = B()
b::B = B()

func(ab, ab) # Method BB
func(b, b) # Method BB

In this case,
both func(ab, ab) and func(b, b) print Method BB,
despite annotating ab to be of type A,
because both ab and b
are of type B at runtime.

Again,
multiple dispatch uses the runtime types
of all input arguments
to determine the method to call.

One of the main resulting benefits
is that composability is easy in Julia.

Composability

Composability is the ability
to use different pieces of code together
to provide new functionality.

First,
we will see an instance
where composability is difficult to achieve.

Let’s add to our Java example.
We will add a class C
that depends on A
but is independent of B:

public class C
{
    public static void run(A a1, A a2)
    {
        a1.func(a2);
    }
}

And we will add the following lines to main:

C.run(ab, ab); // Method BA
C.run(b, b); // Method BA - `C.run` cannot call Method BB!

Notice that,
even though b has a runtime type of B,
C.run(b, b) sill prints out Method BA.
This is because in class C,
the static type
of the second input to run is A, not B.
There are two ways to get run to print out Method BB:

1. The author of class C changes their code
   to add better support for using objects of type B,
   e.g., by adding additional methods to run.
2. The author of class Main reimplements run
   to take into account the existence of class B.

In either case,
code needs to be modified
for class B and class C
to compose well.
That’s not ideal for composability.

Now let’s see how this works out in Julia.
Suppose someone writes a package PkgC.jl
that contains the following:

using PkgA
run(a1::A, a2::A) = func(a1, a2)

Then we can update our example:

# In the REPL or in a .jl file
using PkgA, PkgB, PkgC

ab::A = B()
b::B = B()

PkgC.run(ab, ab) # Method BB
PkgC.run(b, b) # Method BB

Notice that PkgC.run(b, b) prints Method BB,
even though PkgC.jl
knows nothing about PkgB.jl!
No code changes were necessary
for PkgB.jl and PkgC.jl to compose.
That’s the power of multiple dispatch!

More Tips, Tricks, and General Advice

Now we will discuss various additional aspects
of multiple dispatch in Julia.

More Fine-Tuned Dispatching

Previously,
we saw that the method
func(x::String, y::Integer, z::Integer)
allowed y and z to be of different types
(as long as both were Integers).

What if we want a method
where y and z need to be
of the same type?
We can do so
by introducing a type parameter:

julia> function func(x::String, y::T, z::T) where T<:Integer # Method 5
           println(x, ": y and z are both of type ", T)
       end
func (generic function with 5 methods)

julia> func("welcome", 1, true) # Calls method 4
"w"

julia> func("welcome", 1, 1) # Calls method 5
welcome: y and z are both of type Int64

This new method will be called
when y and z are both Integers
of the same type.

Type parameters are also useful
for constraining the types
contained in container types.
For example,
suppose we want a method
that operates on an Array
that contains only real numbers.
The following method signature
accomplishes this:

another_func(a::Array{T}) where T<:Real

If T isn’t used anywhere else,
the following method signature
works as well:

another_func(a::Array{<:Real})

Method Ambiguities

When adding different methods,
it’s possible to introduce
method ambiguities,
where, for a given set of input types,
there is no single most specific method.

Recall that method 3 of func
had the following method signature:

func(x::String, y::Integer)

Adding the following method
will introduce a method ambiguity
when calling func
with a String and an Int:

julia> function func(x, y::Int)
           println(x, ": ", y)
       end
func (generic function with 6 methods)

julia> func("hello", 2)
ERROR: MethodError: func(::String, ::Int64) is ambiguous.

Candidates:
  func(x::String, y::Integer)
    @ Main REPL[4]:1
  func(x, y::Int64)
    @ Main REPL[16]:1

Possible fix, define
  func(::String, ::Int64)

Notice the list of candidate methods
in the error message;
neither is more specific than the other.

• For the first argument,
  String is more specific than Any,
  so the first method is more specific.
• For the second argument,
  Int64 is more specific than Integer,
  so the second method is more specific.

To overcome this issue,
either remove one of the offending methods
or add the method suggested
in the error message.

Beware of Type Piracy

Another thing to be careful about
when defining methods
is type piracy.
Type piracy occurs when
you add a method to a function
that isn’t yours
(i.e., that you didn’t originally define)
using types that aren’t yours.

For example,
defining simple_func(x::String)
is fine because simple_func
is a new function,
so it’s fine to use String,
a type that we didn’t define,
in the method signature.

Similarly,
defining Base.sum(x::MyNewType)
is fine because we defined
(in this hypothetical scenario)
MyNewType ourselves,
so it’s fine to add this method
to Julia’s sum function.

But what’s wrong with adding a method like
Base.sum(x::Array)?
The problem occurs when someone else
tries to use your code.
If they call sum on any Arrays,
your new method will be called
instead of Julia’s built-in sum!
That’s a nasty bug waiting to happen.

(If you want to live on the edge,
try defining
Base.:+(a::Int, b::Int) = error("pirate invasion")
and then watch as Julia crashes fantastically.
It turns out that being able
to correctly add two integers
is necessary for Julia to work properly!)

Summary

In this post,
we learned about
multiple dispatch
in Julia.
We discussed how to utilize it
and how it compares to single dispatch,
typically used
in object-oriented languages.

Do you have any further questions
about multiple dispatch?
Let us know in the comments below!

Additional Links

• The Unreasonable Effectiveness of Multiple Dispatch
  • Popular talk by one of Julia’s co-creators, Stefan Karpinski.
• Wikipedia: Multiple Dispatch
  • Additional information about multiple dispatch.