Julias Type System

Author

Marcel Angenvoort

Published

January 12, 2025

Abstract

Last week we started programming with Julia, covering basic control flow, functions and strings. In this video we will learn about Julias type system and a very powerful mechanism called “multiple dispatch”. We will also talk about important data structures such as arrays, sets and dictionaries.

Keywords

julia, programming, scientific computing

Types in Julia

There are two types of programming languages: Statically typed systems such as C++, where each variable must be of a particular type before execution, and dynamically typed systems, where the type is not known until runtime. Julia is a dynamically typed language, but still has the ability to specify certain types for better efficiency.

. . .

Recall that you can specify the type of a variable either by calling its constructor, or via using the :: operator:

julia> x::Float64 = 8
8

julia> typeof(x)
Float64

We can determine the type of a variable with the typeof() function.

Types in Julia are organised in a hierarchy, which is very similar to inheritance in object-oriented languages such as C++, except that it also works for primitive types. Each type has exactly one parent type and possibly several child types, which can be determined using the supertype and subtype cmmands.

. . .

julia> subtypes(Real)
4-element Vector{Any}:
 AbstractFloat
 AbstractIrrational
 Integer
 Rational

julia> supertype(Float64)
AbstractFloat

For example, Real is an abstract type representing real numbers, which has subtypes for rational, integer, and floating-point types.

This way we can display the complete type tree:

Types in Julia. This figure was created with draw.io and is hereby licensed under Public Domain (CC0 1.0)

Types in Julia.
This figure was created with draw.io and is hereby licensed under Public Domain (CC0 1.0)

As you can see, each type is a subtype of the type Any. We can check whether a type is a subtype of another using the <: operator.

julia> Float64 <: Any
true

. . .

Concrete types such as Float64 or Int64 can be instantiated, whereas abstract types exist only in the type hierarchy.

julia> isconcretetype(Float64)
true

julia> isabstracttype(AbstractFloat)
true

. . .

There are also composite types, which are made up of many smaller types.

struct Person
  name::String
  age::Int
  married::Bool
end

. . .

ImportantImportant

Composite types in Julia are not the same as classes in other languages. They don’t support inheritance and can’t have member functions.

. . .

To instantiate a variable of that type, we call it’s constructor.

julia> author = Person("Marcel", 29, false)
Person("Marcel", 29, false)

julia> typeof(author)
Person

As usual, we can access the member variables of a composite type using the . notation.

julia> author.name
"Marcel"

julia> author.age
29

julia> author.married
false

. . .

By default, composite types are immutable, meaning they cannot be changed. However, an immutable object can contain mutable fields, such as arrays, which remain mutable.

To define a mutable type, use the mutable keyword. If you want to ensure that a particular field remains constant in an otherwise mutable object, you can do this using the const keyword.

mutable struct Triple
  a::Int
  b::Real
  const c::Char
end

julia> X = Triple(8, 3.7, 'K')
Triple(8, 3.7, 'K')

julia> X.a = 5
5

julia> X.c = 'M'
ERROR: setfield!: const field .c of type Triple cannot be changed
Stacktrace:
[...]

TODO: Ist das wichtig?

Abstract, primitive and composite types are all instances of the same concept, DataType, which is the type of these types.

julia> typeof(Real)
DataType

julia> typeof(Person)
DataType

julia> typeof(DataType)
DataType

Type Unions

What if you want to specify that a function accepts signed and unsigned integers, but not bool? You can use a union type.

The concept is similar in other programming languages.

IntOrString = Union{Int, AbstractString}

x = 8::IntOrString
x = "Hello!"

println(x)
using IntOrString = std::variant<int, std::string>;

auto x = IntOrString(8);
x = "Hello!";

std::println(std::get<std::string>(x));

A particularly useful case of a Union type is Union{T, Nothing}, which would be equivalent to std::optional in C++.

Parametric Types

Types in Julia can take parameters, so type declarations introduce a whole family of types. This concept is known in other programming languages as generic programming.

struct Point{T}
    x::T
    y::T
end

P = Point{Float64}(5, 8)
template <typename T>
stuct Point {
  T x;
  T y;
}

auto P = Point<double>(5, 8)
WarningWarning

Note that although Float64 is a subtype of Real, we do NOT have:

julia> Point{Float64} <: Point{Real}
false

In other words, Julia’s type parameters are invariant.

. . .

Let’s say we want to write a generic function that can take Point{Float64} as an argument. The following method won’t work:

function norm(p::Point{Real})
    sqrt(p.x^2 + p.y^2)
end

Since Point{Float64} is not a subtype of Point{Real}, the function can’t take Point{Float64} as an argument.

. . .

Important

The correct way to define a method that accepts all arguments of type Point{T} where T is a subtype of Real is:

function norm(p::Point{T}) where T<:Real;
    sqrt(p.x^2 + p.y^2)
end

Alternatively, one could also write

function norm(p::Point{<:Real})
    sqrt(p.x^2 + p.y^2)
end

. . .

NoteExercise

Implement a parametric type for rational numbers.

struct Rational{T<:Integer} <: Real
    num::T
    den::T
end

Arrays

Arrays are data structures that allow random access to elements. Arrays often represent vectors and matrices. Julia has built-in support for arrays, with indexing and slicing syntax similar to Python or MATLAB. A (column)-vector in Julia can be constructed directly using square brackets and a comma (or semicolon) as separators.

julia> v = [4, 8, 15, 16, 23, 42]
6-element Vector{Int64}:
  4
  8
 15
 16
 23
 42

. . .

There are built-in functions for constructing common matrices:

julia> zeros(Int8, (2, 3))
2×3 Matrix{Int8}:
 0  0  0
 0  0  0

julia> A = rand(2, 2)
×2 Matrix{Float64}:
0.380141  0.81997
0.93474   0.0321379

julia> Matrix{Float64}(I, 3, 3)
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0
>>> A = np.zeros( (2, 3), dtype=int)
array([[0, 0, 0],
       [0, 0, 0]])

>>> np.random.rand( 2, 2)
array([[0.46581219, 0.93757536],
       [0.97690228, 0.72186734]])

>>> np.identity(3)
array([[1., 0., 0.],
       [0., 1., 0.],
       [0., 0., 1.]])

. . .

Note that ranges in Julia are closed, i.e. they include the endpoint.

julia> collect(range(1, 5))
1:5

julia> range(0, 2*pi, length=10)
0.0:0.6981317007977318:6.283185307179586
>>> np.arange(0, 5)
array([0, 1, 2, 3, 4])
>>> np.linspace(0, 2*np.pi, num=10, endpoint=True)
array([0.        , 0.6981317 , 1.3962634 , 2.0943951 , 2.7925268 ,
       3.4906585 , 4.1887902 , 4.88692191, 5.58505361, 6.28318531])

. . .

You can basic information about the data type, dimension and size of the matrix:

julia> eltype(A)
Float64

julia> ndims(A)
2

julia> size(A)
(2, 2)

julia> length(A)
4
>>> A.dtype
dtype('int64')
>>> A.ndim
2
>>> A.shape
(2, 3)
>>> A.size
6

Indexing and Slicing works very similar to MATLAB/Python:

Array Slicing in Julia This image was created using draw.io and is hereby released into the public domain (CC0 1.0)

Array Slicing in Julia
This image was created using draw.io and is hereby released into the public domain (CC0 1.0)
A = transpose(reshape(1:25, 5, 5))

red = A[:, 2:2:end]
blue = A[2:2:end, 1:2:3]
yellow = A[end, :]
A = np.arange(1, 26).reshape((5,5))

red = A[:, 1::2]
blue = A[1::2, 0:3:2]
yellow = A[-1, :]

By default, indexing and slicing return copies of the array. For performance reasons, it may sometimes be better to just get a view:

julia> B = @view A[2, :]
3-element view(::Matrix{Int64}, 2, :) with eltype Int64:
  8
 42
 69

julia> B[2] = -5
-5

julia> A
3×3 Matrix{Int64}:
 1   2    3
 8  -5   69
 5  25  100
>>> B = A[:, 1]
>>> B[1] = -5

>>> A
array([[  1,   2,   3],
       [  8,  -5,  69],
       [  5,  25, 100]])

As you can see, changing the second element of B causes the corresponding element of A to change as well.

To use logical indexing (masking) in Julia, you must first map a lambda function to each element to create a mask. Alternatively, you can use dot syntax to vectorise a particular function.

julia> mask = map( x -> (x > 3), A)
3×3 Matrix{Bool}:
 0  0  0
 1  0  1
 1  1  1

julia> A[mask]
5-element Vector{Int64}:
   8
   5
  25
  69
 100

julia> A[A.>3]
5-element Vector{Int64}:
   8
   5
  25
  69
 100
>>> A > 3
array([[False, False, False],
       [ True, False,  True],
       [ True,  True,  True]])

>>> A[A>3]
array([  8,  69,   5,  25, 100])

You can use hcat and to combine multiple arrays:

Array concatenation in Julia This image was created with draw.io and is hereby release into the public domain (CC0 1.0).

Array concatenation in Julia
This image was created with draw.io and is hereby release into the public domain (CC0 1.0).
julia> hcat(A, B)
2×6 Matrix{Int64}:
 1  2  3  42  69  100
 4  5  6  73  13   25

julia> vcat(A, B)
4×3 Matrix{Int64}:
  1   2    3
  4   5    6
 42  69  100
 73  13   25
>>> np.hstack( (A, B) )
array([[  1,   2,   3,  42,  69, 100],
       [  4,   5,   6,  73,  13,  25]])
>>> np.vstack( (A,B) )
array([[  1,   2,   3],
       [  4,   5,   6],
       [ 42,  69, 100],
       [ 73,  13,  25]])

Broadcasting also works in Julia, but you have to explicitly use the broadcast function, so the syntax is a bit more verbose. That way, broadcasting cannot happen by accident.

julia> A = randn(2,2)
2×2 Matrix{Float64}:
 -0.805994   0.887138
  0.630169  -0.70303

julia> b = [5; 3]
2-element Vector{Int64}:
 5
 3

julia> broadcast(+, A, b)
2×2 Matrix{Float64}:
 4.19401  5.88714
 3.63017  2.29697
>>> A = np.random.randn(2, 2)
>>> A
array([[ 0.22867558,  0.50563247],
       [-0.21137373, -1.31592931]])
>>> b = np.array([[5, 3]]).T
>>> b
array([[5],
       [3]])
>>> A + b
array([[5.22867558, 5.50563247],
       [2.78862627, 1.68407069]])

Constructors

Constructors are functions that create new instances of composite types. When a user defines a new composite type, Julia creates the default constructors. However, in some cases constructors need additional functionality, for example to enforce constraints (called invariants) through argument checking or transformation.

Here’s a simple example illustrating the use of constructors in Julia:

struct Rectangle{T <: Real}
   width::T
   height::T

   # Inner constructor
   function Rectangle(width::Real, height::Real)
       @assert width >= 0 "Width must be non-negative!"
       @assert height >= 0 "Height must be non-negative!"
       promoted_type = promote_type(typeof(width), typeof(height))
       new{promoted_type}(width, height)
   end

   # Default Constructor
   Rectangle() = Rectangle(1.0, 1.0)
end

. . .

That way, you can construct a Rectangle via

rect1 = Rectangle(5.0, 3.0)     # Float64
rect2 = Rectangle(5, 3)         # Int64
rect3 = Rectangle(5.0, 3)       # Float64 (via type promotion)
rect4 = Rectangle()             # default: Float64

but calling it with negative arguments results in an error:

rect = Rectangle(5.0, -3.0)    # error

Sometimes it can be useful to define a struct with some default values. This can be achieved either by using default arguments in the constructor,

struct MyType
        a::Int # required keyword
        b::Float64 # optional
        
        MyType(a::Int) = new(a, 2.3)
        MyType(a::Int, b::Float64) = new(a, b)
end

. . .

or by using the Base.@kwdef macro:

Base.@kwdef struct MyType
    a::Int # required keyword
    b::Float64 = 2.3
    c::String = "hello"
end

. . .

If you omit any of the optional parameters, the values must be passed as keyword arguments:

julia> MyType(1, 2.3, "aaa")
MyType(1, 2.3, "aaa")

julia> MyType(; a = 3)
MyType(3, 2.3, "hello")

TODO: Explain functors, make comparison with C++

Base.@kwdef struct Gauss
    μ::Float64 = 0.0
    σ::Float64 = 1.0
    
    function Gauss(mu::Real, sigma::Real)
        @assert sigma > 0 "sigma must be positive"
        new(mu, sigma)
    end
end     

# Function to compute the normal distribution
(d::Gauss)(x::Real) = 1/(d.σ * sqrt(2π)) * exp(-1/2((x-d.μ)/d.σ)^2)

Method Overloading

A function in Julia can consist of multiple methods. When a user calls a function, the method that is actually executed depends on the type and number of arguments. This is very similar to function overloading in C++.

julia> f(x::Float64, y::Float64) = 2x - y
f (generic function with 2 methods)

julia> f(x::Int64, y::Int64) = 2x - y
f (generic function with 2 methods)
double f(double x, double y) {
    return 2*x - y;
}

long f(long x, long y) {
    return 2*x - y;
}

. . .

You can use the methods function to get a list of the methods for a given function.

julia> methods(f)
# 2 methods for generic function "f" from Main:
 [1] f(x::Int64, y::Int64)
     @ REPL[5]:1
 [2] f(x::Float64, y::Float64)
     @ REPL[4]:1

We can call this function in the usual way:

julia> f(2, 3)
1

julia> f(2.0, 3.0)
1.0

. . .

If there is no method available for the given arguments, this will result in a MethodError:

julia> f(2, 3.7)
ERROR: MethodError: no method matching f(::Int64, ::Float64)
The function `f` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  f(::Int64, ::Int64)
   @ Main REPL[5]:1
  f(::Float64, ::Float64)
   @ Main REPL[4]:1

Stacktrace:
[...]

Providing a method for every possible combination of types can quickly get out of hand; it is more useful to define general methods where the parameters are abstract:

julia> f(x::Number, y::Number) = 2x - y
f (generic function with 2 methods)

julia> f(2.0, 3)
1.0

This function will work for any numeric type; non-numeric types will throw an error as expected.

julia> f(2, 3)
7

julia> f(2.0, 3.0)
7.0

julia> f(2.0, 3)
7.0

julia> f("2.0", 3)
ERROR: MethodError: no method matching f(::String, ::Int64)

Care should be taken to ensure that there are no conflicting methods for the same function. If more than one method is applicable to a particular combination of arguments, the function call is ambiguous and an error will occur.

julia> g(x::Float64, y) = 2x + y
g (generic function with 1 method)

julia> g(x, y::Float64) = x + 2y
g (generic function with 2 methods)

julia> g(2.0, 3)
7.0

julia> g(2, 3.0)
8.0

julia> g(2.0, 3.0)
ERROR: MethodError: g(::Float64, ::Float64) is ambiguous.
[...]

Polymorphism

In order to understand Multiple Dispatch, we first need to talk about Polymorphism.

. . .

Polymorphism, meaning “many forms,” is a fundamental concept in object-oriented programming (OOP) that allows objects of different classes to be treated as objects of a common type. It enables you to design code that is more flexible, extensible, and reusable.

. . .

#include <vector>
#include <iostream>
#include <memory>

class Animal {
  public:
    virtual void sound() const {
      std::cout << "FALLBACK\n" << std::endl;
    }
    virtual ~Animal() = default;
};

class Dog : public Animal {
  public:
    void sound() const override {
      std::cout << "bark\n";
    }
};

class Cat : public Animal {
  public:
    void sound() const override {
      std::cout << "miau\n";
    }
};



int main()
{
  auto ein = std::make_unique<Dog>();
  auto sphinx = std::make_unique<Cat>();

  ein->sound();
  sphinx->sound();
}
using System;

public class Animal
{
  public virtual void Sound()
  {
    Console.WriteLine("FALLBACK");
  }
}

public class Dog : Animal
{
  public override void Sound()
  {
    Console.WriteLine("bark");
  }
}

public class Cat : Animal
{
  public override void Sound()
  {
    Console.WriteLine("miau");
  }
}

public class Program
{
  public static void Main(string[] args)
  {
    Animal ein = new Dog();
    Animal sphinx = new Cat();

    ein.Sound();
    sphinx.Sound();
  }
}

As Julia is not an object-oriented language, the only way to achieve something similar is as follows:

abstract type Animal end
struct Cat <: Animal end
struct Dog <: Animal end
struct Bird <: Animal end

make_sound(cat::Cat) = println("miau!")
make_sound(dog::Dog) = println("wuff!")
make_sound(bird::Bird) = println("chierp!")

ein = Dog()
shinx = Cat()

make_sound(ein)
make_sound(cat)

This isn’t very spectacular yet; it looks like normal operator overloading. Things get more interesting when the functions have more arguments.

Multiple Dispatch

Multi-dispatch is the ability to choose which version of a function to call based on the runtime type of all arguments passed to the function call.

abstract type Pet end
struct Dog <: Pet; name::String end
struct Cat <: Pet; name::String end

function encounter(a::Pet, b::Pet)
    verb = meets(a, b)
    println("$(a.name) meets $(b.name) and $verb")
end

meets(a::Dog, b::Dog) = "sniffs"
meets(a::Dog, b::Cat) = "chases"
meets(a::Cat, b::Dog) = "hisses"
meets(a::Cat, b::Cat) = "slinks"

fido = Dog("Fido")
rex = Dog("Rex")
whiskers = Cat("Whiskers")
spots = Cat("Spots")

encounter(fido, rex)
encounter(fido, whiskers)
encounter(whiskers, rex)
encounter(whiskers, spots)
Fido meets Rex and sniffs
Fido meets Whiskers and chases
Whiskers meets Rex and hisses
Whiskers meets Spots and slinks
#include <iostream>
#include <string>

class Pet {
    public:
        std::string name{};
};

class Dog : public Pet{};
class Cat : public Pet{};

std::string meets(Dog a, Dog b) { return "sniffs"; }
std::string meets(Dog a, Cat b) { return "chases"; }
std::string meets(Cat a, Dog b) { return "hisses"; }
std::string meets(Cat a, Cat b) { return "slinks"; }

std::string meets(Pet a, Pet b) {
    return "FALLBACK";
}

void encounter(Pet a, Pet b) {
    auto verb = meets(a, b);
    std::cout << a.name << " meets "
        << b.name << " and " << verb << std::endl;
}

int main() {
    Dog fido{"Fido"};
    Dog rex{"Rex"};
    Cat whiskers{"whiskers"};
    Cat spots{"spots"};

    encounter(fido, rex);
    encounter(fido, whiskers);
    encounter(whiskers, rex);
    encounter(whiskers, spots);
}
Fido meets Rex and FALLBACK
Fido meets whiskers and FALLBACK
whiskers meets Rex and FALLBACK
whiskers meets spots and FALLBACK

Doing something like this in C++ is not possible.

. . .

See also:

Functional Programming

Functional programming is a programming paradigm where programs are constructed by applying and composing functions. It’s a declarative style of programming, meaning you describe what you want to achieve rather than how to achieve it (which is more typical of imperative programming)

. . .

The core concepts and characteristics of functional programming are as follows:

  1. Functions are first-class objects, meaning they can be passed around and stored like variables.
  2. Higher order functions: functions can take other functions as arguments, or return a function as a result
  3. Immutability: Data, once created, cannot be changed. Instead of modifying existing data structures, you create new ones with the desired changes.
  4. Declarative style programming: Using map, filter and reduce instead of for loops to iterate over an array.

Map, Filter, Reduce

  • map: Transforms each element in a collection by applying a function to it, returning a new collection of the same size.
  • filter: Creates a new collection containing only elements that satisfy a given predicate function.
  • reduce: Reduces a collection to a single value by iteratively applying a function that combines elements.

Normal Distribution

\[ \mathcal{N}(x | \mu, \sigma) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left({- \frac{1}{2} \biggl( \frac{x - \mu}{\sigma} \biggr)^2 }\right) \] \[ \mathcal{N}(x | \mu, \sigma) = \frac{1}{\sqrt{2\pi}\sigma} \, e^{- \frac{1}{2} \left( \frac{x - \mu}{\sigma} \right)^2 } \]

Closure:

function normal_distribution(μ::Real = 0, σ::Real = 1)
  return x -> 1 / (sqrt(2π) * σ) * exp(-1/2 * ((x - μ)/σ)^2) 
end

f = normal_distribution(5, 2)
println(f(7.5))
#include <cmath>
#include <functional>
#include <iostream>
#include <numbers>

std::function<double(double)> normal_distribution(double mu=0.0, double sigma=1.0) {
  return [=](double x) {
    return 1 / (std::sqrt(2 * std::numbers::pi) * sigma) * std::exp( -1/2 * std::pow( (x - mu) / sigma, 2));
  };
}

int main()
{
  auto f = normal_distribution(5.0, 2.0);
  std::cout << f(7.5) << std::endl;
}

LeetCode Example

Let’s say we want to solve LeetCode problem 557 (Reverse Words in a String III). Given a string str, reverse the characters in each word while still preserving the initial word order.

Example:

str = "The quick brown fox jumps over the lazy dog"
--> "ehT kciuq nworb xof spmuj revo eht yzal god"

. . .

This problem can be solved in a very elegant way using functional programming:

  1. split the string at the space (’ ’) character
  2. map the reverse function to each element
  3. join everything back together

. . .

function reverse_word(str::String)
  return join(map(reverse, split(str, " ")), " ")
end
#include <string>
#include <ranges>
#include <string_view>

std::string reverseWords(std::string_view str) {
  return str | std::views::split(' ')
             | std::views::transform([](auto&& word) {
                  return word | std::views::reverse;
                })
              | std::views::join_with(' ')
              | std::ranges::to<std::string>();
}

Alternatively, you can do this with the pipe operator:

function reverse_word(str::String)
  return str |> x -> split(x, " ") |>
  x -> map(reverse, x) |>
  x -> join(x, " ")
end

TODO: