{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "How to read this lecture…\n", "\n", "- If using QuantEcon lectures for the first time on a computer, execute `] add InstantiateFromURL` inside of a notebook or the REPL \n", "- For some notebooks, enable content with “Trust” on the command tab of Jupyter lab \n", "- Code should execute sequentially if run in a Jupyter notebook \n", "- Please direct feedback to [contact@quantecon.org](mailto:contact@quantecon.org\") or [discourse forum](http://discourse.quantecon.org/) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction to Types and Generic Programming" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Contents\n", "\n", "- [Introduction to Types and Generic Programming](#Introduction-to-Types-and-Generic-Programming) \n", " - [Overview](#Overview) \n", " - [Finding and Interpreting Types](#Finding-and-Interpreting-Types) \n", " - [The Type Hierarchy](#The-Type-Hierarchy) \n", " - [Deducing and Declaring Types](#Deducing-and-Declaring-Types) \n", " - [Creating New Types](#Creating-New-Types) \n", " - [Introduction to Multiple Dispatch](#Introduction-to-Multiple-Dispatch) \n", " - [Exercises](#Exercises) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Overview\n", "\n", "In Julia, arrays and tuples are the most important data type for working with numerical data\n", "\n", "In this lecture we give more details on\n", "\n", "- declaring types \n", "- abstract types \n", "- motivation for generic programming \n", "- multiple-dispatch \n", "- building user-defined types " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Setup" ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [], "source": [ "using InstantiateFromURL\n", "activate_github(\"QuantEcon/QuantEconLecturePackages\", tag = \"v0.3.1\") # activate the QuantEcon environment\n", "\n", "using LinearAlgebra, Statistics, Compat # load common packages" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Finding and Interpreting Types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Finding The Type\n", "\n", "As we have seen in the previous lectures, in Julia all values have a type, which can be queried using the `typeof` function" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(1) = Int64\n", "typeof(1.0) = Float64\n" ] } ], "source": [ "@show typeof(1)\n", "@show typeof(1.0);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The hard-coded values `1` and `1.0` are called literals in a programming language, and the compiler will deduce their types (`Int64` and `Float64` respectively in the example above)\n", "\n", "You can also query the type of a value" ] }, { "cell_type": "code", "execution_count": 119, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Int64" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = 1\n", "typeof(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Where the name `x` binds to the value `1`, created as a literal" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Parametric Types\n", "\n", "(See [parametric types documentation](https://docs.julialang.org/en/v1/manual/types/#Parametric-Types-1))\n", "\n", "The next two types use curly bracket notation to express the fact that they are *parametric*" ] }, { "cell_type": "code", "execution_count": 120, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(1.0 + 1im) = Complex{Float64}\n", "typeof(ones(2, 2)) = Array{Float64,2}\n" ] } ], "source": [ "@show typeof(1.0 + 1im)\n", "@show typeof(ones(2,2));" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will learn more details about [generic programming](generic_programming.html#) later, but the key is to interpret the curly brackets as swappable parameters for a given type\n", "\n", "For example, `Array{Float64, 2}` can be read as\n", "\n", "1. `Array` is a parametric type representing a dense array, where the first parameter is the type stored, and the 2nd is the number of dimensions \n", "1. `Float64` is a concrete type declaring that the data stored will be a particular size of floating point \n", "1. `2` is the number of dimensions of that array \n", "\n", "\n", "A concrete type is one which where values can be created by the compiler\n", "\n", "Values of a **parametric type** cannot be concretely constructed unless all of the parameters are given (themselves with concrete types)\n", "\n", "In the case of `Complex{Float64}`\n", "\n", "1. `Complex` is an abstract complex number type \n", "1. `Float64` is a concrete type declaring what the type of the real and imaginary parts of the value should store \n", "\n", "\n", "Another type to consider is the `Tuple` and `Named Tuple`" ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) = Tuple{Int64,Float64,String}\n" ] }, { "data": { "text/plain": [ "Tuple{Int64,Float64,String}" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = (1, 2.0, \"test\")\n", "@show typeof(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In that case, the `Tuple` is the parametric type, and the 3 parameters are a list of the types of each value stored in `x`\n", "\n", "For a named tuple" ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) = NamedTuple{(:a, :b, :c),Tuple{Int64,Float64,String}}\n" ] }, { "data": { "text/plain": [ "NamedTuple{(:a, :b, :c),Tuple{Int64,Float64,String}}" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = (a = 1, b = 2.0, c = \"test\")\n", "@show typeof(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The parametric `NamedTuple` type contains 2 parameters: first a list of names for each field of the tuple, and second the underlying `Tuple` type to store the values\n", "\n", "Anytime a value is prefixed by a colon, as in the `:a` above, the type is `Symbol`–a special kind of string used by the compiler" ] }, { "cell_type": "code", "execution_count": 123, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Symbol" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" } ], "source": [ "typeof(:a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remark:** Note that, by convention, type names use CamelCase — `Array`, `AbstractArray`, etc." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Variables, Types, and Values\n", "\n", "Since variables and functions are denoted in lower case, this can be used to easily identify types when reading code and output\n", "\n", "After assigning a variable name to an value, we can query the type of the\n", "value via the name" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) = Int64\n" ] } ], "source": [ "x = 42\n", "@show typeof(x);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Thus, `x` is just a symbol bound to an value of type `Int64`\n", "\n", "Indeed, we can *rebind* the symbol `x` to any other value, of the same type or otherwise" ] }, { "cell_type": "code", "execution_count": 125, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "42.0" ] }, "execution_count": 125, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = 42.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now `x` “points to” another value, of type `Float64`" ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Float64" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" } ], "source": [ "typeof(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, beyond a few notable exceptions (e.g. `nothing` used for [error handling](error_handling)), changing types is usually a symptom of poorly organized code–and it makes compiler [type inference](type_inference) more difficult" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Type Hierarchy\n", "\n", "Let’s discuss how types are organized" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Abstract vs Concrete Types\n", "\n", "(See [abstract types documentation](https://docs.julialang.org/en/v1/manual/types/#Abstract-Types-1))\n", "\n", "Up to this point, most of the types we have worked with (e.g., `Float64, Int64`) are examples of **concrete types**\n", "\n", "Concrete types are types that we can *instantiate* — i.e., pair with data in memory\n", "\n", "We will now examine types **abstract types** that cannot be instantiated, (e.g., `Real`, `AbstractFloat`)\n", "\n", "While you will never have a `Real` number directly in memory, the abstract types will help us organize and work with related concrete types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The Type Hierarchy\n", "\n", "How exactly do abstract types organize or relate different concrete types?\n", "\n", "The answer is that, in the Julia language specification, the types form a hierarchy\n", "\n", "You can check if a type is a subtype of another with the `<:` operator" ] }, { "cell_type": "code", "execution_count": 127, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Float64 <: Real = true\n", "Int64 <: Real = true\n", "Complex{Float64} <: Real = false\n", "Array <: Real = false\n" ] } ], "source": [ "@show Float64 <: Real\n", "@show Int64 <: Real\n", "@show Complex{Float64} <: Real\n", "@show Array <: Real;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the above, both `Float64` and `Int64` are **subtypes** of `Real`, whereas the `Complex` numbers are not\n", "\n", "They are, however, all subtypes of `Number`" ] }, { "cell_type": "code", "execution_count": 128, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Real <: Number = true\n", "Float64 <: Number = true\n", "Int64 <: Number = true\n", "Complex{Float64} <: Number = true\n" ] } ], "source": [ "@show Real <: Number\n", "@show Float64 <: Number\n", "@show Int64 <: Number\n", "@show Complex{Float64} <: Number;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`Number` in turn is a subtype of `Any`, which is a parent of all types" ] }, { "cell_type": "code", "execution_count": 129, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 129, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Number <: Any" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In particular, the type tree is organized with `Any` at the top and the concrete types at the bottom\n", "\n", "We never actually see *instances* of abstract types (i.e., `typeof(x)` never returns an abstract type)\n", "\n", "The point of abstract types is to categorize the concrete types, as well as other abstract types that sit below them in the hierarchy\n", "\n", "There are some further functions to help you explore the type hierarchy, such as `show_supertypes` which walks up the tree of types to `Any` for a given type" ] }, { "cell_type": "code", "execution_count": 130, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Int64 <: Signed <: Integer <: Real <: Number <: Any" ] } ], "source": [ "using Base: show_supertypes # import the function from the `Base` package\n", "\n", "show_supertypes(Int64)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And the `subtypes` which gives a list of the available subtypes for any packages or code currently loaded" ] }, { "cell_type": "code", "execution_count": 131, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "subtypes(Real) = Any[AbstractFloat, AbstractIrrational, FixedPoint, Dual, Integer, Rational]\n", "subtypes(AbstractFloat) = Any[BigFloat, Float16, Float32, Float64]\n" ] } ], "source": [ "@show subtypes(Real)\n", "@show subtypes(AbstractFloat);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Deducing and Declaring Types\n", "\n", "We will discuss this in detail in [this lecture](generic_programming.html#), but much of its performance gains and generality of notation comes from Julia’s type system\n", "\n", "For example, with" ] }, { "cell_type": "code", "execution_count": 132, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x1) = Array{Int64,1}\n", "typeof(x2) = Array{Float64,1}\n" ] }, { "data": { "text/plain": [ "Array{Float64,1}" ] }, "execution_count": 132, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x1 = [1, 2, 3]\n", "x2 = [1.0, 2.0, 3.0]\n", "@show typeof(x1)\n", "@show typeof(x2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These return `Array{Int64,1}` and `Array{Float64,1}` respectively, which the compiler is able to infer from the right hand side of the expressions\n", "\n", "Given the information on the type, the compiler can work through the sequence of expressions to infer other types" ] }, { "cell_type": "code", "execution_count": 133, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{Int64,1}:\n", " 2\n", " 4\n", " 6" ] }, "execution_count": 133, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# define some function\n", "f(y) = 2y\n", "\n", "# call with an integer array\n", "x = [1, 2, 3]\n", "z = f(x) # compiler deduces type" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Good Practices for Functions and Variable Types\n", "\n", "In order to keep many of the benefits of Julia, you will sometimes want to help the compiler ensure that it can always deduce a single type from any function or expression\n", "\n", "As an example of bad practice, is to use an array to hold unrelated types" ] }, { "cell_type": "code", "execution_count": 134, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{Any,1}:\n", " 1.0 \n", " \"test\"\n", " 1 " ] }, "execution_count": 134, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = [1.0, \"test\", 1] # typically poor style" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The type of this is `Array{Any,1}`, where the `Any` means the compiler has determined that any valid Julia types can be added to the array\n", "\n", "While occasionally useful, this is to be avoided whenever possible in performance sensitive code\n", "\n", "The other place this can come up is in the declaration of functions\n", "\n", "As an example, consider a function which returns different types depending on the arguments" ] }, { "cell_type": "code", "execution_count": 135, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "f(1) = 1.0\n", "f(-1) = 0\n" ] } ], "source": [ "function f(x)\n", " if x > 0\n", " return 1.0\n", " else\n", " return 0 # Probably meant 0.0\n", " end\n", "end\n", "@show f(1)\n", "@show f(-1);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The issue here is relatively subtle: `1.0` is a floating point, while `0` is an integer\n", "\n", "Consequently, given the type of `x`, the compiler cannot in general determine what type the function will return\n", "\n", "This issue, called **type stability** is at the heart of most Julia performance considerations\n", "\n", "Luckily, the practice of trying to ensure that functions return the same types is also the most consistent with simple, clear code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Manually Declaring Function and Variable Types\n", "\n", "(See [type declarations documentation](https://docs.julialang.org/en/v1/manual/types/#Type-Declarations-1))\n", "\n", "You will notice that in the lecture notes we have never directly declared any types\n", "\n", "This is intentional both for exposition and as a best practice for using packages (as opposed to writing new packages, where declaring these types is very important)\n", "\n", "It is also in contrast to some of the sample code you will see in other Julia sources, which you will need to be able to read\n", "\n", "To give an example of the declaration of types, the following are equivalent" ] }, { "cell_type": "code", "execution_count": 136, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 9.1\n", " 14.3" ] }, "execution_count": 136, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function f(x, A)\n", " b = [5.0, 6.0]\n", " return A * x .+ b\n", "end\n", "val = f([0.1, 2.0], [1.0 2.0; 3.0 4.0])" ] }, { "cell_type": "code", "execution_count": 137, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 9.1\n", " 14.3" ] }, "execution_count": 137, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function f2(x::Vector{Float64}, A::Matrix{Float64})::Vector{Float64} # argument and return types\n", " b::Vector{Float64} = [5.0, 6.0]\n", " return A * x .+ b\n", "end\n", "val = f2([0.1; 2.0], [1.0 2.0; 3.0 4.0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While declaring the types may be verbose, would it ever generate faster code?\n", "\n", "The answer is: almost never\n", "\n", "Furthermore, it can lead to confusion and inefficiencies since many things that behave like vectors and matrices are not `Matrix{Float64}` and `Vector{Float64}`\n", "\n", "To see a few examples where the first works and the second fails" ] }, { "cell_type": "code", "execution_count": 138, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "f([0.1; 2.0], [1 2; 3 4]) = [9.1, 14.3]\n", "f([0.1; 2.0], Diagonal([1.0, 2.0])) = [5.1, 10.0]\n" ] }, { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 5.1\n", " 10.0" ] }, "execution_count": 138, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@show f([0.1; 2.0], [1 2; 3 4])\n", "@show f([0.1; 2.0], Diagonal([1.0, 2.0]))\n", "\n", "#f2([0.1; 2.0], [1 2; 3 4]) # not a Float64\n", "#f2([0.1; 2.0], Diagonal([1.0, 2.0])) # not a Matrix{Float64}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Creating New Types\n", "\n", "(See [type declarations documentation](https://docs.julialang.org/en/v1/manual/types/#Type-Declarations-1))\n", "\n", "Up until now, we have used `NamedTuple` to collect sets of parameters for our models and examples\n", "\n", "There are many reasons to use that for the narrow purpose of maintaining values for model parameters, but you will eventually need to be able to read code that creates its own types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Syntax for Creating Concrete Types\n", "\n", "(See [composite types documentation](https://docs.julialang.org/en/v1/manual/types/#Composite-Types-1))\n", "\n", "While other sorts of types exist, we almost always use the `struct` keyword, which is for creation of composite data types\n", "\n", "- “composite” refers to the fact that the data types in question can be used as collection of named fields \n", "- the `struct` terminology is used in a number of programming languages to refer to composite data types \n", "\n", "\n", "Let’s start with a trivial example where the `struct` we build has fields named `a, b, c`, are not typed" ] }, { "cell_type": "code", "execution_count": 139, "metadata": {}, "outputs": [], "source": [ "struct FooNotTyped # immutable by default, use `mutable struct` otherwise\n", " a # BAD! Not typed\n", " b\n", " c\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And another where the types of the fields are chosen" ] }, { "cell_type": "code", "execution_count": 140, "metadata": {}, "outputs": [], "source": [ "struct Foo\n", " a::Float64\n", " b::Int64\n", " c::Vector{Float64}\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In either case, the compiler generates a function to create new values of the data type, called a “constructor”\n", "\n", "It has the same name as the data type but uses function call notion" ] }, { "cell_type": "code", "execution_count": 141, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(foo) = Foo\n", "foo.a = 2.0\n", "foo.b = 3\n", "foo.c = [1.0, 2.0, 3.0]\n" ] } ], "source": [ "foo_nt = FooNotTyped(2.0, 3, [1.0, 2.0, 3.0]) # new FooNotTyped\n", "foo = Foo(2.0, 3, [1.0, 2.0, 3.0]) # creates a new Foo\n", "@show typeof(foo)\n", "@show foo.a # get the value for a field\n", "@show foo.b\n", "@show foo.c;\n", "# foo.a = 2.0 # fails, since it is immutable" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You will notice two differences above for the creation of a `struct` compared to our use of `NamedTuple`\n", "\n", "- Types are declared for the fields, rather than inferred by the compiler \n", "- The construction of a new instance, has no named parameters to prevent accidental misuse by choosing the wrong order " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Issues with Type Declarations\n", "\n", "Was it necessary to manually declare the types `a::Float64` in the above struct?\n", "\n", "The answer, in practice, is usually yes\n", "\n", "Without a declaration of the type, the compiler is unable to generate efficient code, and the use of a `struct` declared without types could drop performance by orders of magnitude\n", "\n", "Moreover, it is very easy to use the wrong type, or unnecessarily constrain the types\n", "\n", "The first example, which is usually just as low-performance as no declaration of types at all, is to accidentally declare it with an abstract type" ] }, { "cell_type": "code", "execution_count": 142, "metadata": {}, "outputs": [], "source": [ "struct Foo2\n", " a::Float64\n", " b::Integer # BAD! Not a concrete type\n", " c::Vector{Real} # BAD! Not a concrete type\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second issue is that by choosing a type (as in the `Foo` above), you may be constraining what is allowed more than is really necessary" ] }, { "cell_type": "code", "execution_count": 143, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "FooNotTyped(2, 3, [1.0 2.0 3.0])" ] }, "execution_count": 143, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x) = x.a + x.b + sum(x.c) # use the type\n", "a = 2.0\n", "b = 3\n", "c = [1.0, 2.0, 3.0]\n", "foo = Foo(a, b, c)\n", "f(foo) # call with the foo, no problem\n", "\n", "# Some other typed for the values\n", "a = 2 # not a floating point, but f() would work\n", "b = 3\n", "c = [1.0, 2.0, 3.0]' # transpose is not a `Vector`. But f() would work\n", "# foo = Foo(a, b, c) # fails to compile\n", "\n", "# works with the NotTyped version, but low performance\n", "foo_nt = FooNotTyped(a, b, c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Declaring Parametric Types (Advanced)\n", "\n", "(See [type parametric types documentation](https://docs.julialang.org/en/v1/manual/types/#Parametric-Types-1))\n", "\n", "Motivated by the above, we can create a type which can adapt to holding fields of different types" ] }, { "cell_type": "code", "execution_count": 144, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "11.0" ] }, "execution_count": 144, "metadata": {}, "output_type": "execute_result" } ], "source": [ "struct Foo3{T1, T2, T3}\n", " a::T1 # could be any type\n", " b::T2\n", " c::T3\n", "end\n", "\n", "# Works fine\n", "a = 2\n", "b = 3\n", "c = [1.0, 2.0, 3.0]' # transpose is not a `Vector`. But f() would work\n", "foo = Foo3(a, b, c)\n", "f(foo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Of course, this is probably too flexible, and the `f` function might not work on an arbitrary set of `a, b, c`\n", "\n", "You could constrain the types based on the abstract parent type using the `<:` operator" ] }, { "cell_type": "code", "execution_count": 145, "metadata": {}, "outputs": [ { "ename": "ErrorException", "evalue": "invalid redefinition of constant Foo4", "output_type": "error", "traceback": [ "invalid redefinition of constant Foo4", "", "Stacktrace:", " [1] top-level scope at none:0" ] } ], "source": [ "struct Foo4{T1 <: Real, T2 <: Real, T3 <: AbstractVecOrMat{<:Real}}\n", " a::T1\n", " b::T2\n", " c::T3 # should check dimensions as well\n", "end\n", "foo = Foo4(a, b, c) # no problem, and high performance" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This ensure that\n", "\n", "- `a` and `b` are a subtype of `Real`, which ensures that the `+` in the definition of `f` works \n", "- `c` is a one dimensional abstract array of `Real` values \n", "\n", "\n", "The code works, and is equivalent in performance to a `NamedTuple`, but is becoming verbose and error prone" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Keyword Argument Constructors (Advanced)\n", "\n", "There is no way around the difficult creation of parametric types to achieve high performance code\n", "\n", "However, the other issue where constructor arguments are error-prone, can be remedied with the `Parameters.jl` library" ] }, { "cell_type": "code", "execution_count": 146, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "foo = Foo5\n", " a: Float64 0.1\n", " b: Int64 2\n", " c: Array{Float64}((3,)) [1.0, 2.0, 3.0]\n", "\n", "foo2 = Foo5\n", " a: Float64 2.0\n", " b: Int64 2\n", " c: Array{Float64}((3,)) [1.0, 2.0, 3.0]\n", "\n" ] }, { "data": { "text/plain": [ "8.1" ] }, "execution_count": 146, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using Parameters\n", "@with_kw struct Foo5\n", " a::Float64 = 2.0 # adds default value\n", " b::Int64\n", " c::Vector{Float64}\n", "end\n", "foo = Foo5(a = 0.1, b = 2, c = [1.0, 2.0, 3.0])\n", "foo2 = Foo5(c = [1.0, 2.0, 3.0], b = 2) # rearrange order, uses default values\n", "@show foo\n", "@show foo2\n", "\n", "function f(x)\n", " @unpack a, b, c = x # can use @unpack on any struct\n", " return a + b + sum(c)\n", "end\n", "f(foo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Tips and Tricks for Writing Generic Functions\n", "\n", "As discussed in the previous sections, there is major advantage to never declaring a type unless it is absolutely necessary\n", "\n", "The main place where it is necessary is designing code around [multiple dispatch](intro_multiple_dispatch)\n", "\n", "If you are careful in writing ensuring code that doesn’t unnecessarily assume a particular set of types, it will both have higher performance and let you seamlessly use a number of powerful libraries such as [auto-differentiation](https://github.com/JuliaDiff/ForwardDiff.jl), [static arrays](https://github.com/JuliaArrays/StaticArrays.jl), [GPUs](https://github.com/JuliaGPU/CuArrays.jl), [interval arithmetic and root finding](https://github.com/JuliaIntervals/IntervalRootFinding.jl), [arbitrary precision numbers](https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/index.html#Arbitrary-Precision-Arithmetic-1), and many more packages–including ones that have not even been written yet\n", "\n", "A few simple programming patterns will ensure that this is possible\n", "\n", "- Do not declare types when declaring variables or functions unless necessary " ] }, { "cell_type": "code", "execution_count": 147, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{Float64,1}:\n", " 6.0\n", " 7.0\n", " 3.1" ] }, "execution_count": 147, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# BAD\n", "x = [5.0, 6.0, 2.1]\n", "function g(x::Array{Float64, 1}) # not generic!\n", " y = zeros(length(x)) # not generic, hidden float!\n", " z = Diagonal(ones(length(x))) # not generic, hidden float!\n", " q = ones(length(x))\n", " y .= z * x + q\n", " return y\n", "end\n", "g(x)\n", "\n", "# GOOD\n", "function g2(x) # or x::AbstractVector\n", " y = similar(x)\n", " z = I\n", " q = ones(eltype(x), length(x)) # or fill(one(x), length(x))\n", " y .= z * x + q\n", " return y\n", "end\n", "g2(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "- Preallocate related vector with `similar` where possible, and use `eltype` or `typeof` " ] }, { "cell_type": "code", "execution_count": 148, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{BigInt,1}:\n", " 1\n", " 4" ] }, "execution_count": 148, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function g(x)\n", " y = similar(x)\n", " for i in eachindex(x)\n", " y[i] = x[i]^2 # of course, could broadcast\n", " end\n", " return y\n", "end\n", "g([BigInt(1), BigInt(2)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "- Use typeof or eltype when you need to declare a type " ] }, { "cell_type": "code", "execution_count": 149, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof([1.0, 2.0, 3.0]) = Array{Float64,1}\n", "eltype([1.0, 2.0, 3.0]) = Float64\n" ] } ], "source": [ "@show typeof([1.0, 2.0, 3.0])\n", "@show eltype([1.0, 2.0, 3.0]);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "- Beware of hidden floating points " ] }, { "cell_type": "code", "execution_count": 150, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(ones(3)) = Array{Float64,1}\n", "typeof(ones(Int64, 3)) = Array{Int64,1}\n", "typeof(zeros(3)) = Array{Float64,1}\n", "typeof(zeros(Int64, 3)) = Array{Int64,1}\n" ] } ], "source": [ "@show typeof(ones(3))\n", "@show typeof(ones(Int64, 3))\n", "@show typeof(zeros(3))\n", "@show typeof(zeros(Int64, 3));" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "- Use `one` and `zero` when you need to write generic code " ] }, { "cell_type": "code", "execution_count": 151, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(1) = Int64\n", "typeof(1.0) = Float64\n", "typeof(BigFloat(1.0)) = BigFloat\n", "typeof(one(BigFloat)) = BigFloat\n", "typeof(zero(BigFloat)) = BigFloat\n", "typeof(one(x)) = BigFloat\n", "typeof(zero(x)) = BigFloat\n" ] } ], "source": [ "@show typeof(1)\n", "@show typeof(1.0)\n", "@show typeof(BigFloat(1.0))\n", "@show typeof(one(BigFloat)) # gets multiplicative identity, passing in type\n", "@show typeof(zero(BigFloat))\n", "x = BigFloat(2)\n", "@show typeof(one(x)) # can call with a variable for convenience\n", "@show typeof(zero(x));" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This last example is a subtle, because of something called [type promotion](https://docs.julialang.org/en/v1/manual/conversion-and-promotion/#Promotion-1) \n", " \n", "- Assume reasonable type promotion exists for numeric types " ] }, { "cell_type": "code", "execution_count": 152, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(g(x)) = BigFloat\n" ] } ], "source": [ "# ACCEPTABLE\n", "function g(x::AbstractFloat)\n", " return x + 1.0 # Assumes that `1.0` can be converted to something compatible with typeof(x)\n", "end\n", "x = BigFloat(1.0)\n", "@show typeof(g(x)); # This has \"promoted\" the 1.0 to a BigFloat" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "But sometimes assuming promotion is not enough " ] }, { "cell_type": "code", "execution_count": 153, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(g2(x)) = BigFloat\n", "typeof(g2(x2)) = Nothing\n", "typeof(g3(x)) = BigFloat\n", "typeof(g3(x2)) = Nothing\n" ] } ], "source": [ "# BAD\n", "function g2(x::AbstractFloat)\n", " if x > 0.0 # can't efficiently call with x::Integer\n", " return x + 1.0 # ok. assumes can promote Float64 to the AbstractFloat\n", " otherwise\n", " return 0 # bad! Returns a Int64\n", " end\n", "end\n", "x = BigFloat(1.0)\n", "x2 = BigFloat(-1.0)\n", "@show typeof(g2(x))\n", "@show typeof(g2(x2)) # type unstable\n", "\n", "# GOOD\n", "function g3(x) #\n", " if x > zero(x) # any type with an additive identity\n", " return x + one(x) # More general, but less important of a change\n", " otherwise\n", " return zero(x)\n", " end\n", "end\n", "@show typeof(g3(x))\n", "@show typeof(g3(x2)); # type stable" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "These patterns are relatively straightforward, but think of generic programming as a Leontief production function: if *any* of the functions you write or call are not careful, then it may break the chain\n", "\n", "This is all the more reason to exploit carefully designed packages rather than a “do-it-yourself” approach to coding" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### A Digression on Style and Naming\n", "\n", "The previous section helps establishes some of the reasoning behind the key style choice in these lectures: “be aware of types, but avoid declaring them”\n", "\n", "The purpose of this is threefold\n", "\n", "- provide easy to read code with minimal “syntactic noise” and a clear correspondence to the math \n", "- ensure that code is sufficiently generic to exploit other packages and types \n", "- avoid common mistakes and unnecessary performance degradations \n", "\n", "\n", "This is just one of many decisions and patterns to ensure that your code is consistent and clear\n", "\n", "The best resource is to carefully read other peoples code, but a few sources to review are\n", "\n", "- [Julia Style Guide](https://docs.julialang.org/en/v1/manual/style-guide/) \n", "- [Julia Praxis Naming Guides](https://github.com/JuliaPraxis/Naming/tree/master/guides) \n", "- [QuantEcon Style Guide](https://github.com/QuantEcon/lecture-source-jl/blob/master/style.md) used in these lectures \n", "\n", "\n", "Now why would we emphasize naming as style as a crucial part of the lectures?\n", "\n", "Because it is an essential tool for creating research that is **reproducible** and [**correct**](https://en.wikipedia.org/wiki/Correctness_(computer_science))\n", "\n", "Some helpful ways to think about this are\n", "\n", "- **Clearly written code is easier to review for errors**: The first-order concern of any code is that it correctly implements the whiteboard math \n", "- **Code is read many more times than it is written**: Saving a few keystrokes in typing a variable name is never worth it, nor is a divergence from the mathematical notation where a single symbol for a variable name would map better to the model \n", "- **Write code to be read in the future, not today**: If you are not sure anyone else will read the code, then write it for an ignorant future version of your self who may have forgotten everything, and is likely to misuse the code \n", "- **Maintain the correspondence between the whiteboard math and the code**: For example, if you change notation in your model, then immediately update all variables in the code to reflect it " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Commenting Code\n", "\n", "One common mistake people make when trying to apply these goals is to add in a large number of comments\n", "\n", "Over the years, developers have found that excess comments in code (and *especially* big comment headers used before every function declaration) can make code *harder* to read\n", "\n", "The issue is one of syntactic noise: if most of the comments are redundant given clear variable and function names, then the comments make it more difficult to mentally parse and read the code\n", "\n", "If you examine Julia code in packages and the core language, you will see a great amount of care taken in function and variable names, and comments are only added where helpful\n", "\n", "For creating packages that you intend others to use, instead of a comment header, you should use [docstrings](https://docs.julialang.org/en/v1/manual/documentation/index.html#Syntax-Guide-1)\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction to Multiple Dispatch\n", "\n", "One of the defining features of Julia is **multiple dispatch**, whereby the same function name can do different things depending on the underlying types\n", "\n", "Without realizing it, in nearly every function call within packages or the standard library you have used this features\n", "\n", "To see this in action, consider the absolute value function `abs`" ] }, { "cell_type": "code", "execution_count": 154, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "abs(-1) = 1\n", "abs(-1.0) = 1.0\n", "abs(0.0 - 1.0im) = 1.0\n" ] } ], "source": [ "@show abs(-1) # Int64\n", "@show abs(-1.0) # Float64\n", "@show abs(0.0 - 1.0im); # Complex{Float64}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In all of these cases, the `abs` function has specialized code depending on the type passed in\n", "\n", "To do this, a function specifies different **methods** which operate on a particular set of types\n", "\n", "Unlike most cases we have seen before, this requires a type annotation\n", "\n", "To rewrite the `abs` function" ] }, { "cell_type": "code", "execution_count": 155, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ourabs(-1) = 1\n", "ourabs(-1.0) = 1.0\n", "ourabs(1.0 - 2.0im) = 2.23606797749979\n" ] } ], "source": [ "function ourabs(x::Real)\n", " if x > zero(x) # note, not 0!\n", " return x\n", " else\n", " return -x\n", " end\n", "end\n", "\n", "function ourabs(x::Complex)\n", " sqrt(real(x)^2 + imag(x)^2)\n", "end\n", "\n", "@show ourabs(-1) # Int64\n", "@show ourabs(-1.0) # Float64\n", "@show ourabs(1.0 - 2.0im); # Complex{Float64}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that in the above, `x` works for any type of `Real`, including `Int64`, `Float64`, and ones you may not have realized exist" ] }, { "cell_type": "code", "execution_count": 156, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) = Rational{Int64}\n", "ourabs(x) = 2//3\n" ] } ], "source": [ "x = -2//3 # a Rational number, -2/3\n", "@show typeof(x)\n", "@show ourabs(x);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You will also note that we used an abstract type, `Real`, and an incomplete parametric type `Complex` when defining the above Functions\n", "\n", "Unlike the creation of `struct` fields, there is no penalty in using absract types when you define function parameters, as they are used purely to determine which version of a function to use" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Multiple Dispatch in Algorithms (Advanced)\n", "\n", "If you want an algorithm to have specialized versions when given different input types, you need to declare the types for the function inputs\n", "\n", "As an example where this could come up, assume that we have some grid `x` of values, the results of a function `f` applied at those values, and want to calculate an approximate derivative using forward differences\n", "\n", "In that case, given $ x_n, x_{n+1}, f(x_n) $ and $ f(x_{n+1}) $, the forward-difference approximation of the derivative is\n", "\n", "$$\n", "f'(x_n) \\approx \\frac{f(x_{n+1}) - f(x_n)}{x_{n+1} - x_n}\n", "$$\n", "\n", "To implement this calculation for a vector of inputs, we notice that there is a specialized implementation if the grid is uniform\n", "\n", "The uniform grid can be implemented using an `AbstractRange`, which we can analyze with `typeof, supertype` and `show_supertypes`" ] }, { "cell_type": "code", "execution_count": 157, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) = StepRangeLen{Float64,Base.TwicePrecision{Float64},Base.TwicePrecision{Float64}}\n", "typeof(x_2) = StepRange{Int64,Int64}\n", "supertype(typeof(x)) = AbstractRange{Float64}\n" ] }, { "data": { "text/plain": [ "AbstractRange{Float64}" ] }, "execution_count": 157, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = range(0.0, 1.0, length = 20)\n", "x_2 = 1:1:20 # if integers\n", "@show typeof(x)\n", "@show typeof(x_2)\n", "@show supertype(typeof(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To see the entire tree about a particular type, use `show_supertypes`" ] }, { "cell_type": "code", "execution_count": 158, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "StepRangeLen{Float64,Base.TwicePrecision{Float64},Base.TwicePrecision{Float64}} <: AbstractRange{Float64} <: AbstractArray{Float64,1} <: Any" ] } ], "source": [ "show_supertypes(typeof(x)) # or typeof(x) |> show_supertypes" ] }, { "cell_type": "code", "execution_count": 159, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "StepRange{Int64,Int64} <: OrdinalRange{Int64,Int64} <: AbstractRange{Int64} <: AbstractArray{Int64,1} <: Any" ] } ], "source": [ "show_supertypes(typeof(x_2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The types of the range objects can be very complicated, but are both subtypes of `AbstractRange`" ] }, { "cell_type": "code", "execution_count": 160, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(x) <: AbstractRange = true\n", "typeof(x_2) <: AbstractRange = true\n" ] } ], "source": [ "@show typeof(x) <: AbstractRange\n", "@show typeof(x_2) <: AbstractRange;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While you may not know the exact concrete type, any `AbstractRange` has an informal set of operations that are available" ] }, { "cell_type": "code", "execution_count": 161, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "minimum(x) = 0.0\n", "maximum(x) = 1.0\n", "length(x) = 20\n", "step(x) = 0.05263157894736842\n" ] } ], "source": [ "@show minimum(x)\n", "@show maximum(x)\n", "@show length(x)\n", "@show step(x);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Similarly, there are a number of operations available for any `AbstractVector`, such as `length`" ] }, { "cell_type": "code", "execution_count": 162, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(f_x) = Array{Float64,1}\n", "supertype(typeof(f_x)) = DenseArray{Float64,1}\n", "supertype(supertype(typeof(f_x))) = AbstractArray{Float64,1}\n", "length(f_x) = 20\n" ] } ], "source": [ "f(x) = x^2\n", "f_x = f.(x) # calculating at the range values\n", "@show typeof(f_x)\n", "@show supertype(typeof(f_x))\n", "@show supertype(supertype(typeof(f_x))) # walk up tree again!\n", "@show length(f_x); # and many more" ] }, { "cell_type": "code", "execution_count": 163, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Array{Float64,1} <: DenseArray{Float64,1} <: AbstractArray{Float64,1} <: Any" ] } ], "source": [ "show_supertypes(typeof(f_x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are also many functions that can use any `AbstractArray`, such as `diff`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```julia\n", "?diff\n", "\n", "search: diff symdiff setdiff symdiff! setdiff! Cptrdiff_t\n", "\n", "diff(A::AbstractVector)\n", "diff(A::AbstractMatrix; dims::Integer)\n", "Finite difference operator of matrix or vector A. If A is a matrix, specify the dimension over which to operate with the dims keyword argument.\n", "```\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Hence, we can call this function for anything of type `AbstractVector`\n", "\n", "Finally, we can make a high performance specialization for any `AbstractVector` and `AbstractRange`" ] }, { "cell_type": "code", "execution_count": 164, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "derivatives (generic function with 3 methods)" ] }, "execution_count": 164, "metadata": {}, "output_type": "execute_result" } ], "source": [ "derivatives(f::AbstractVector, x::AbstractRange) = diff(f)/step(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can use auto-differentiation to compare the results" ] }, { "cell_type": "code", "execution_count": 165, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "\n", "1\n", "\n", "\n", "2\n", "\n", "\n", "3\n", "\n", "\n", "4\n", "\n", "\n", "-1.0\n", "\n", "\n", "-0.5\n", "\n", "\n", "0.0\n", "\n", "\n", "0.5\n", "\n", "\n", "1.0\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "q' with AD\n", "\n", "\n", "\n", "q'\n", "\n", "\n" ] }, "execution_count": 165, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using Plots, ForwardDiff\n", "# operator to get the derivative of this function using AD\n", "D(f) = x -> ForwardDiff.derivative(f, x)\n", "\n", "q(x) = sin(x)\n", "x = 0.0:0.1:4.0\n", "q_x = q.(x)\n", "D_q_x = derivatives(q_x, x)\n", "\n", "plot(x[1:end-1], D(q).(x[1:end-1]), label = \"q' with AD\")\n", "plot!(x[1:end-1], D_q_x, label = \"q'\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider a variation where we pass a function instead of an `AbstractArray`" ] }, { "cell_type": "code", "execution_count": 166, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "typeof(q) <: Function = true\n", "d_q[1] = 0.9983341664682815\n" ] } ], "source": [ "derivatives(f::Function, x::AbstractRange) = diff(f.(x))/step(x) # broadcast function\n", "\n", "@show typeof(q) <: Function\n", "d_q = derivatives(q, x)\n", "@show d_q[1];" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, if `x` was an `AbstractArray` and not an `AbstractRange` we can no longer use a uniform step" ] }, { "cell_type": "code", "execution_count": 167, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "d_f[1] = 1.0000000000000009\n" ] } ], "source": [ "derivatives(f::Function, x::AbstractArray) = diff(f.(x))./diff(x) # broadcasts over the diff\n", "\n", "d_f = derivatives(f, x)\n", "@show d_f[1];" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the final example, we see that it is able to use specialized implementations over both the `f` and the `x` arguments\n", "\n", "This is the “multiple” in multiple-dispatch" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1\n", "\n", "Explore the package [StaticArrays.jl](https://github.com/JuliaArrays/StaticArrays.jl)\n", "\n", "- Describe 2 abstract types and the hierarchy of 3 different concrete types \n", "- Benchmark the calculation of some simple linear algebra with a static array compared to the following for a dense arrays for `N=3` and `N=15` " ] }, { "cell_type": "code", "execution_count": 168, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 89.133 ns (1 allocation: 112 bytes)\n", " 867.936 ns (5 allocations: 1.98 KiB)\n" ] }, { "data": { "text/plain": [ "3×3 Array{Float64,2}:\n", " 3.4428 -2.02391 0.138267\n", " 3.84254 -3.97494 1.8532 \n", " -2.81781 2.82176 -0.231472" ] }, "execution_count": 168, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using BenchmarkTools\n", "N = 3\n", "A = rand(N, N)\n", "x = rand(N)\n", "@btime $A * $x # the $ in front of variable names is sometimes important\n", "@btime inv($A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2\n", "\n", "A key step in the calculation of the Kalman Filter is calculation of the Kalman gain, as can be seen with the following example using dense matrices from [this lecture](kalman)\n", "\n", "Using what you learned from Exercise 1, benchmark this using Static Arrays" ] }, { "cell_type": "code", "execution_count": 169, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 910.379 ns (10 allocations: 1.94 KiB)\n" ] }, { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " 0.666667 1.11022e-16\n", " 1.11022e-16 0.666667 " ] }, "execution_count": 169, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Σ = [0.4 0.3;\n", " 0.3 0.45]\n", "G = I\n", "R = 0.5 * Σ\n", "\n", "gain(Σ, G, R) = Σ * G' * inv(G * Σ * G' + R)\n", "@btime gain($Σ, $G, $R)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How many times faster are static arrays in this example?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3\n", "\n", "The [Polynomial.jl](https://github.com/JuliaMath/Polynomials.jl) provides a package for simple univariate Polynomials" ] }, { "cell_type": "code", "execution_count": 170, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = Poly(2 - 5*x + 2*x^2)\n", "(p(0.1), p′(0.1)) = (1.52, -4.6)\n", "roots(p) = [2.0, 0.5]\n" ] } ], "source": [ "using Polynomials\n", "p = Poly([2, -5, 2], :x) # :x just gives a symbol for display\n", "@show p\n", "p′ = polyder(p) # gives the derivative of p, another polynomial\n", "@show p(0.1), p′(0.1) # call like a function\n", "@show roots(p); # find roots such that p(x) = 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Plot both `p(x)` and `p′(x)` for $ x \\in [-2, 2] $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4\n", "\n", "Using your solution to Exercise 8(a/b) in the [Julia By Example Lecture](julia_by_example) to create a specialized version of Newton’s method for Polynomials, using the `polyder` function\n", "\n", "The signature of the function should be `newtonsmethod(p::Poly, x_0; tolerance = 1E-7, maxiter = 100)`, where the `p::Poly` ensure that this version of the function will be used anytime a polynomial is passed (i.e. dispatch)\n", "\n", "Compare the results of this function to the built in `roots(p)`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5 (Advanced)\n", "\n", "The [trapezoidal rule](https://en.wikipedia.org/wiki/Trapezoidal_rule) approximate an integral with\n", "\n", "$$\n", "\\int_\\underline{x}^\\bar{x} f(x) \\, dx \\approx \\sum_{n=1}^N \\frac{f(x_{n-1}) + f(x_n)}{2} \\Delta x_n\n", "$$\n", "\n", "where $ x_0 = \\underline{x},\\, x_N = \\bar{x} $, and $ \\Delta x_n \\equiv x_{n-1} - x_n $\n", "\n", "Given an `x` and a function `f`, implement a few variations of the trapezoidal rule using multiple-dispatch\n", "\n", "- `trapezoidal(f, x)` for any `typeof(x) = AbstractArray` and `typeof(f) == AbstractArray` where `length(x) = length(f)` \n", "- `trapezoidal(f, x)` for any `typeof(x) = AbstractRange` and `typeof(f) == AbstractArray` where `length(x) = length(f)`\n", " * exploit the fact that `AbstractRange` have constant step sizes to specialize the algorithm \n", "- `trapezoidal(f, x̲, x̄, N)` where `typeof(f) = Function`, and the other arguments are `Real`\n", " * for this, build a uniform grid with `N` points on `[x̲,x̄]`, call the `f` function at those grid points, and use the existing `trapezoidal(f, x)` from the implementation \n", "\n", "\n", "With these,\n", "1. Test each variation of the function with $ f(x) = x^2 $ with $ \\underline{x}=0,\\, \\bar{x} = 1 $\n", "2. From the analytical solution of the function, plot the error of `trapezoidal(f, x̲, x̄, N)` relative to the analytical solution for a grid of different `N` values\n", "3. Consider trying different functions for $ f(x) $ and comparing the solutions for various `N`\n", "\n", "When trying different functions, instead of integrating by hand consider using a high-accuracy library for numerical integration such as [QuadGK.jl](https://juliamath.github.io/QuadGK.jl/latest/)" ] }, { "cell_type": "code", "execution_count": 171, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1.5, 0.0)" ] }, "execution_count": 171, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using QuadGK\n", "f(x) = x^2\n", "value, accuracy = quadgk(f, 0.0, 1.0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 6 (Advanced)\n", "\n", "Take a variation of your code in Exercise 5 which implements the trapezoidal rule for the uniform grid\n", "\n", "Use auto-differentiation to calculate the following derivative for the example functions\n", "\n", "$$\n", "\\frac{d}{d \\bar{x}}\\int_\\underline{x}^\\bar{x} f(x) \\, dx\n", "$$\n", "\n", "Hint: See the following code for the general pattern, and be careful to follow the [rules for generic programming](_generic_tips_tricks)" ] }, { "cell_type": "code", "execution_count": 172, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "f(0.0, 3.0) = 1.5\n", "f(0.0, 3.1) = 1.55\n" ] }, { "data": { "text/plain": [ "0.5" ] }, "execution_count": 172, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function f(a, b; N = 50)\n", " r = range(a, b, length=N) # one\n", "return mean(r)\n", "end\n", "Df(x) = ForwardDiff.derivative(y -> f(0.0, y), x)\n", "\n", "using ForwardDiff\n", "@show f(0.0, 3.0)\n", "@show f(0.0, 3.1)\n", "Df(3.0)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "filename": "introduction_to_types.rst", "kernelspec": { "display_name": "Julia 1.0.1", "language": "julia", "name": "julia-1.0" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.0.1" }, "title": "Introduction to Types and Generic Programming" }, "nbformat": 4, "nbformat_minor": 2 }