How to read this lecture...

Code should execute sequentially if run in a Jupyter notebook

Types, Methods and Dispatch

Overview

In this lecture we delve more deeply into the structure of Julia, and in particular into

  • the concept of types
  • methods and multiple dispatch
  • building user-defined types

These concepts relate to the way that Julia stores and acts on data

Understanding them will help you

  • Write “well organized” Julia code that’s easy to read, modify, maintain and debug
  • Improve the speed at which your code runs
  • Read Julia code written by other programmers

Types and Multiple Dispatch

Common Types

In Julia all objects have a type, which can be queried using the typeof() function

typeof(0.5)
Float64
typeof(5)
Int64
typeof("foo")
String
typeof('c')
Char

The next two types use curly bracket notation to express the fact that they are parametric

typeof(1 + 1im)
Complex{Int64}
typeof(eye(2))
Array{Float64,2}

We’ll return to parametric types later in this lecture

Remark: Note that, by convention, type names use CamelCase — FloatingPoint, Array, AbstractArray, etc.

Variables and Type

After assigning a variable name to an object, we can query the type of the object via the name

x = 42
42
typeof(x)
Int64

The type resides with the object itself, not with the name x

Thus, x is just a symbol bound to an object of type Int64

Indeed, we can rebind the symbol x to any other object, of the same type or otherwise

x = 42.0
42.0

Now x “points to” another object, of type Float64

typeof(x)
Float64

Multiple Dispatch

When we process data with a computer, the precise data type is important — sometimes more than we realize

For example, on an abstract mathematical level we don’t distinguish between 1 + 1 and 1.0 + 1.0

But for a CPU, integer and floating point addition are different things, using a different set of instructions

Julia handles this problem by storing multiple, specialized versions of functions like addition, one for each data type or set of data types

These individual specialized versions are called methods

When an operation like addition is requested, the Julia runtime environment inspects the type of data to be acted on and hands it out to the appropriate method

This process is called multiple dispatch

Example 1

In Julia, 1 + 1 has the alternative syntax +(1, 1)

+(1, 1)
2

This operator + is itself a function with multiple methods

We can investigate them using the @which macro, which shows the method to which a given call is dispatched

x, y = 1.0, 1.0
@which +(x, y)
+(x::Float64, y::Float64) at float.jl:240

We see that the operation is sent to the + method that specializes in adding floating point numbers

Here’s the integer case

x, y = 1, 1
@which +(x, y)
+{T<:Union{Int128, Int32, Int64, ...}}(x::T, y::T) at int.jl:32

This (slightly edited) output says that the call has been dispatched to the + method responsible for handling integer values

(We’ll learn more about the details of this syntax below)

Here’s another example, with complex numbers

x, y = 1.0 + 1.0im, 1.0 + 1.0im
@which +(x, y)
+(z::Complex, w::Complex) at complex.jl:125

Again, the call has been dispatched to a + method specifically designed for handling the given data type

Example 2

The isless function also has multiple methods

isless(1.0, 2.0)  # Applied to two floats
true
@which isless(1.0, 2.0)
isless(x::Float64, y::Float64) at float.jl:283

Now let’s try with integers

@which isless(1, 2)
isless(x::Real, y::Real) at operators.jl:75

The Real data type we haven’t met yet — it’s an example of an abstract type, and encompasses both floats and integers

We’ll learn more about abstract types below

Example 3

The function isfinite() has multiple methods too

@which isfinite(1) # Call isfinite on an integer
isfinite(x::Integer) at float.jl:360
@which isfinite(1.0) # Call isfinite on a float
isfinite(x::AbstractFloat) at float.jl:358

Here AbstractFloat is another abstract data type, this time encompassing all floats

We can list all the methods of isfinite as follows

methods(isfinite)
9 methods for generic function isfinite:
isfinite(x::BigFloat) at mpfr.jl:799
isfinite(x::Float16) at float16.jl:119
isfinite(x::AbstractFloat) at float.jl:358
isfinite(x::Integer) at float.jl:360
isfinite(::Irrational) at irrationals.jl:82
isfinite(x::Real) at float.jl:359
isfinite(z::Complex) at complex.jl:57
isfinite{T<:Number}(x::AbstractArray{T,N<:Any}) at operators.jl:555
isfinite{T<:Base.Dates.TimeType}(::Union{T,Type{T}}) at dates/types.jl:218

We’ll discuss some of the more complicated data types you see here later on

Adding Methods

It’s straightforward to add methods to existing functions

For example, we can’t at present add an integer and a string in Julia

+(100, "100")
MethodError: no method matching +(::Int64, ::String)
  ...

This is sensible behavior, but if you want to change it there’s nothing to stop you:

importall Base.Operators  #  Gives access to + so that we can add a method

+(x::Integer, y::String) = x + parse(Int, y)
+ (generic function with 164 methods)
+(100, "100")
200
100 + "100"
200

Dispatch and User-Defined Functions

You can exploit multiple dispatch in user-defined functions

Here’s a trivial example (we’ll see many realistic examples later)

function h(a::Float64)
    println("You have called the method for handling Float64s")
end

function h(a::Int64)
    println("You have called the method for handling Int64s")
end

The h that gets invoked depends on the data type that you call it with:

h(1.0)
You have called the method for handling Float64s
h(1)
You have called the method for handling Int64s

Actually, as we’ll see when we discuss JIT compilation, this process is partly automated

For example, if we write a function that can handle either floating point or integer arguments and then call it with floating point arguments, a specialized method for applying our function to floats will be constructed and stored in memory

  • Inside the method, operations such as addition, multiplication, etc. will be specialized to their floating point versions

If we next call it with integer arguments, the process will be repeated but now specialized to integers

  • Inside the method, operations such as addition, multiplication, etc. will be specialized to their integer versions

Subsequent calls will be routed automatically to the most appropriate method

Comments on Efficiency

Julia’s multiple dispatch approach to handling data differs from the approach used by many other languages

It is, however, well thought out and well suited to scientific computing

The reason is that many methods, being specialized to specific data types, are highly optimized for the kind of data that they act on

We can likewise build specialized methods and hence generate fast code

We’ll see how this enables Julia to easily generate highly efficient machine code in later on

The Type Hierarchy

Let’s discuss how types are organized in Julia

Abstract vs Concrete Types

We saw above that Float64 is the standard type for representing a 64 bit floating point number

But we’ve also seen references to types such as Real and AbstractFloat

The former (i.e., Float64) is an example of a concrete type, as is Int64 or Float32

The latter (i.e., Real, AbstractFloat) are examples of so-called abstract types

Concrete types are types that we can instantiate — i.e., pair with data in memory

On the other hand, abstract types help us organize and work with related concrete types

The Type Hierarchy

How exactly do abstract types organize or relate different concrete types?

The answer is that, in the Julia language specification, the types form a hierarchy

For example, Float64 and Int64 are subtypes of Real

Float64 <: Real
true
Int64 <: Real
true

On the other hand, 64 bit complex numbers are not reals

Complex64 <: Real
false

They are, however, subtypes of Number

Complex64 <: Number
true

Number in turn is a subtype of Any, which is a parent of all types

Number <: Any
true

In particular, the type tree is organized with Any at the top and the concrete types at the bottom

We never actually see instances of abstract types (i.e., typeof(x) never returns an abstract type)

The point of abstract types is to categorize the concrete types, as well as other abstract types that sit below them in the hierarchy

Back to Multiple Dispatch

We can now be a little bit clearer about what happens when you call a function on given types

Suppose we execute the function call f(a, b) where a and b are of concrete types S and T respectively

The Julia interpreter first queries the types of a and b to obtain the tuple (S, T)

It then parses the list of methods belonging to f, searching for a match

If it finds a method matching (S, T) it calls that method

If not, it looks to see whether the pair (S, T) matches any method defined for immediate parent types

For example, if S is Float64 and T is Complex64 then the immediate parents are AbstractFloat and Number respectively

supertype(Float64)
AbstractFloat
supertype(Complex64)
Number

Hence the interpreter looks next for a method of the form f(x::AbstractFloat, y::Number)

If the interpreter can’t find a match in immediate parents (supertypes) it proceeds up the tree, looking at the parents of the last type it checked at each iteration

  • If it eventually finds a matching method it invokes that method
  • If not, we get an error

This is the process that leads to the following error

+(100, "100")
MethodError: no method matching +(::Int64, ::String)
  ...

Because the dispatch procedure starts from concrete types and works upwards, dispatch always invokes the most specific method available

For example, if you have methods for function f that handle

  1. (Float64, Int64) pairs
  2. (Number, Number) pairs

and you call f with f(0.5, 1) then the first method will be invoked

This makes sense because (hopefully) the first method is optimized for exactly this kind of data

The second method is probably more of a “catch all” method that handles other data in a less optimal way

Here’s another simple example, involving a user-defined function

function f(x)
    println("Generic function invoked")
end

function f(x::Number)
    println("Number method invoked")
end

function f(x::Integer)
    println("Integer method invoked")
end

Let’s now run this and see how it relates to our discussion of method dispatch above

f(3)
Integer method invoked
f(3.0)
Number method invoked
f("foo")
Generic function invoked

Since

  • 3 is an Int64 and Int64 <: Integer <: Number

the call f(3) proceeds up the tree to Integer and invokes f(x::Integer)

On the other hand, 3.0 is a Float64, which is not a subtype of Integer

Hence the call f(3.0) continues up to f(x::Number)

Finally, f("foo") is handled by the generic function, since String is not a subtype of Number

User-Defined Types

Let’s have a look at defining our own data types

Motivation

At our respective homes we both have draws full of fishing gear

Of course we have draws full of other things too, like kitchen utensils, or clothes

Are these draws really necessary?

Perhaps not, but who wants to search the whole house for their fishing reel when the fish are biting?

Certainly not us

Just as it’s convenient to store household objects in draws, it’s also convenient to organize the objects in your program into designated “containers”

The first step is to design and build the containers

We do this by declaring and using our own types

For example,

  • a Firm type might store parameters for objects that represent firms in a given model
  • an EstimationResults type might store output from some statistical procedure, etc.

Once those types are declared, we can create instances of the type

For example,

results = EstimationResults(y, X)

might create an instances of EstimationResults that stores estimated coefficients and other information from a given regression exercise involving data y, X

Syntax

While there are multiple ways to create new types, we almost always use the struct keyword, which is for creation of composite data types

Notes:

  • “composite” refers to the fact that the data types in question can be used as “containers” that hold a variety of data
  • the struct terminology is used in a number of programming languages to refer to composite data types

Let’s start with a trivial example where the struct we build is empty

struct Foo  # A useless data type that stores no data
end

When a new data type is defined in this way, the interpreter also creates a default constructor for the data type

This constructor is a function for generating new instances of the data type in question

It has the same name as the data type but uses function call notion:

foo = Foo()  # Call default constructor, make a new Foo

A new instance of type Foo is created and the name foo is bound to that instance

typeof(foo)
Foo

Adding Methods

We can now create functions that act on instances of Foo

foofunc(x::Foo) = "onefoo"
foofunc (generic function with 1 method)
foofunc(foo)
"onefoo"

Or we can add new methods for acting on Foos to existing functions, such as +

+(x::Foo, y::Foo) = "twofoos"
+ (generic function with 165 methods)
foo1, foo2 = Foo(), Foo()  # Create two Foos
(Foo(),Foo())
+(foo1, foo2)
"twofoos"

A Less Trivial Example

Let’s say we are doing a lot of work with AR(1) processes, which are random sequences \(\{X_t\}\) that follow the law of motion

(1)\[X_{t+1} = a X_t + b + \sigma W_{t+1}\]

Here

  • \(a\), \(b\) and \(\sigma\) are scalars and
  • \(\{W_t\}\) is an iid sequence of shocks with some given distribution \(\phi\)

Let’s take these primitives \(a\), \(b\), \(\sigma\) and \(\phi\) and organize them into a single entity like so

mutable struct AR1
    a
    b
    sigma
    phi
end

Here mutable means that we can change (mutate) data while the object is live in memory – see below

For the distribution phi we’ll assign a Distribution from the Distributions package

using Distributions
m = AR1(0.9, 1, 1, Beta(5, 5))
AR1(0.9,1,1,Distributions.Beta{Float64}(α=5.0, β=5.0))

In this call to the constructor we’ve created an instance of AR1 and bound the name m to it

We can access the fields of m using their names and “dotted attribute” notation

m.a
0.9
m.b
1
m.sigma
1
m.phi
Distributions.Beta{Float64}(α=5.0, β=5.0)

For example, the attribute m.phi points to an instance of Beta, which is in turn a subtype of Distribution as defined in the Distributions package

typeof(m.phi)
Distributions.Beta{Float64}
typeof(m.phi) <: Distribution
true

We can reach into m and change this if we want to

m.phi = Exponential(0.5)
Distributions.Exponential{Float64}(θ=0.5)

Specifying Field Types

In our type definition we can be explicit that we want phi to be a Distribution and the other elements to be floats

struct AR1_explicit
    a::Float64
    b::Float64
    sigma::Float64
    phi::Distribution
end

(In this case, mutable is removed since we do not intend to make any changes to the elements of AR1_explicit)

Now the constructor will complain if we try to use the wrong data type

m = AR1_explicit(0.9, 1, "foo", Beta(5, 5))
MethodError: Cannot `convert` an object of type String to an object of type Real

This can be useful in terms of failing early on incorrect data, rather than deeper into execution

At the same time, AR1_explicit is not as generic as AR1, and hence less flexibile

For example, suppose that we want to allow a, b and sigma to take any value that is <: Real

We could achieve this by the new definition

struct AR1_real
    a::Real
    b::Real
    sigma::Real
    phi::Distribution
end

But it turns out that using abstract types inside user-defined types adversely affects performance — more about that soon

Fortunately, there’s another approach that both

  • preserves the use of concrete types for internal data and
  • allows flexibility across multiple concrete data types

This approach uses type parameters, a topic we turn to now

Type Parameters

Consider the following output

typeof([10, 20, 30])
Array{Int64,1}

Here Array is one of Julia’s predefined types (Array <: DenseArray <: AbstractArray <: Any)

The Int64,1 in curly brackets are type parameters

In this case they are the element type and the dimension

Many other types have type parameters too

typeof(1.0 + 1.0im)
Complex{Float64}
typeof(1 + 1im)
Complex{Int64}

Types with parameters are therefore in fact an indexed family of types, one for each possible value of the parameter

We can use parametric types in our own type definitions, as the next example shows

Back to the AR1 Example

Recall our AR(1) example, where we considered different restrictions on internal data

For the coefficients a, b and sigma we considered

  • allowing them to be any type
  • forcing them to be of type Float64
  • allowing them to be any Real

The last option is a nice balance between specific and flexible

For example, using Real in the type definition tells us that, while these values should be scalars, integer values and floats are both OK

However, as mentioned above, using abstract types for fields of user-defined types impacts negatively on performance

For now it suffices to observe that we can achieve flexibility and eliminate abstract types on a, b and sigma by the following declaration

struct AR1_best{T <: Real}
    a::T
    b::T
    sigma::T
    phi::Distribution
end

If we create an instance using Float64 values then the instance has type AR1_best{Float64}

m = AR1_best(0.9, 1.0, 1.0, Beta(5, 5))
AR1_best{Float64}(0.9,1.0,1.0,Distributions.Beta{Float64}(α=5.0, β=5.0))

Exercises

Exercise 1

Write a function with the signature simulate(m::AR1, n::Integer, x0::Real) that takes as arguments

  • an instance m of AR1 (see above)
  • an integer n
  • a real number x0

and returns an array containing a time series of length n generated according to (1) where

  • the primitives of the AR(1) process are as specified in m
  • the initial condition \(X_0\) is set equal to x0

Hint: If d is an instance of Distribution then rand(d) generates one random draw from the distribution specified in d

Solutions

Exercise 1

Let’s start with the AR1 definition as specified in the lecture

using Distributions

struct AR1_ex1{T <: Real}
    a::T
    b::T
    sigma::T
    phi::Distribution
end

Now let’s write the function to simulate AR1s

function simulate(m::AR1_ex1, n::Integer, x0::Real)
    X = Array{Float64}(n)
    X[1] = x0
    for t in 1:(n-1)
        X[t+1] = m.a * X[t] + m.b + rand(m.phi)
    end
    return X
end

Let’s test it out on the AR(1) process discussed in the lecture

m = AR1_ex1(0.9, 1.0, 1.0, Beta(5, 5))
X = simulate(m, 100, 0.0)
100-element Array{Float64,1}:
  0.0
  1.43703
  2.75257
  4.07441
  5.08574
  6.24482
  7.19393
  7.9938
  8.49046
  9.12257
  9.77304
 10.0554
 10.3597
  ⋮
 14.8071
 14.4791
 14.3067
 14.4508
 14.7374
 14.854
 14.7483
 14.8965
 14.6211
 14.7057
 14.6627
 14.7309

Next let’s plot the time series to see what it looks like

using Plots

plot(X, legend=:none)
../_images/types_methods_solutions_ex1_jl.png