Code should execute sequentially if run in a Jupyter notebook

- See the set up page to install Jupyter, Julia and all necessary libraries
- Please direct feedback to contact@quantecon.org or the discourse forum

# Types, Methods and Dispatch¶

Contents

## 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

### 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

`(Float64, Int64)`

pairs`(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¶

To create a new data type we use the keyword `type`

followed by the name

By convention, type names use CamelCase — `FloatingPoint`

, `Array`

, `AbstractArray`

, etc.

Let’s start with a trivial example

```
type 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

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

```
type AR1
a
b
sigma
phi
end
```

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

```
type AR1_explicit
a::Float64
b::Float64
sigma::Float64
phi::Distribution
end
```

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

```
type 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

```
type 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`

### Exercise 2¶

The term **universal function** is sometimes applied to functions which

- when called on a scalar return a scalar
- when called on an array of scalars return an array of the same length by acting elementwise on the scalars in the array

For example, `sin()`

has this property in Julia

```
sin(pi)
```

```
1.2246467991473532e-16
```

```
sin([pi, 2pi])
```

```
2-element Array{Float64,1}:
1.22465e-16
-2.44929e-16
```

Write a universal function `f`

such that

`f(k)`

returns a chi-squared random variable with`k`

degrees of freedom when`k`

is an integer`f(k_vec)`

returns a vector where`f(k_vec)[i]`

is chi-squared with`k_vec[i]`

degrees of freedom

Hint: If we take `k`

independent standard normals, square them all and sum we get a chi-squared with `k`

degrees of freedom

## Solutions¶

### Exercise 1¶

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

```
using Distributions
type 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
pyplot()
```

```
plot(X, legend=:none)
```

### Exercise 2¶

Here’s the function to act on integers

```
function f_ex2(k::Integer)
@assert k > 0 "k must be a natural number"
z = randn(k)
return sum(z.^2)
end
```

```
f_ex2 (generic function with 1 method)
```

```
f_ex2(3)
```

```
1.5841392760511817
```

Calls with non-integer arguments will raise a “no matching method” error

```
f_ex2(3.5)
```

```
MethodError: no method matching f_ex2(::Float64)
Closest candidates are:
f_ex2(::Integer) at In[89]:2
```

Calls with integers less than 1 will trigger an assertion failure inside the function body

```
f_ex2(-2)
```

```
AssertionError: k must be a natural number
in f_ex2(::Int64) at ./In[89]:2
```

Now let’s add the version that works on vectors. The notation we’ll use
is slightly different to what we saw in the lectures. We are using
parametric types to indicate that f will act on vectors of the form
`Array{T, 1}`

where `T`

is a subtype Integer

```
function f_ex2{T <: Integer}(k_vec::Array{T, 1})
for k in k_vec
@assert k > 0 "Each integer must be a natural number"
end
n = length(k_vec)
draws = Array{Float64}(n)
for i in 1:n
z = randn(k_vec[i])
draws[i] = sum(z.^2)
end
return draws
end
```

```
f_ex2 (generic function with 2 methods)
```

```
f_ex2([2, 4, 6])
```

```
3-element Array{Float64,1}:
0.992351
3.03434
3.29578
```

The first version of f continues to work as before when we call it on scalars

```
f_ex2(2)
```

```
2.1306420882546395
```

```
@which(f_ex2(2))
```

```
f_ex2(k::Integer) at In[89]:2
```

```
@which(f_ex2([2,3]))
```

```
f_ex2{T<:Integer}(k_vec::Array{T,1}) at In[93]:2
```