2. Making new types.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example: Modelling a gas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that I want to simulate a gas, i.e. a collection of particles in a two-dimensional box that move around.\n",
    "A particle has a position, which is a 2D vector, a velocity, which is another 2D vector, and a mass, that is a real number. How can I represent this in Julia?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# User-defined types "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we have started to see, the basic types in Julia, such as `Complex`, are defined in Julia code.\n",
    "They are treated on the same footing as types defined by the user.\n",
    "\n",
    "Composite types in Julia are just boxes that hold data and provide constructor functions for making new objects of that type. They *do not contain methods (functions)* (as would be the case in many other object-oriented languages); rather, the methods are defined using multiple dispatch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Fixed-size vectors "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Currently, there are no fixed-size vectors in base Julia (although these are available, for example, in the `ImmutableArrays` and `FixedSizeVectors` packages). For many applications, fixed-size vectors are useful, for example for representing positions of particles moving in 2D or 3D space. We can define our own type that may prove to be more efficient than Julia's `Array` type."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic syntax for defining a composite type is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "type Vector2D\n",
    "    x::Float64\n",
    "    y::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The double colon (`::`) is a **type annotation** that specifies the type of `x` and `y`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's  check which methods have been defined:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "methods(Vector2D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Vector2D(3.5, 4.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Vector2D(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v = Vector2D(3, 4)\n",
    "w = Vector2D(5, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens if we try to add two `Vector2D`s?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v + w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia confirms that it has no idea how to do so. So let's just try defining it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "+(a::Vector2D, b::Vector2D) = Vector2D(a.x+b.x, a.y+b.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v + w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suddenly, it works! This is Julia's version of operator overloading -- just add a new method to the relevant operator that acts on objects of your new type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dot(a::Vector2D, b::Vector2D) = a.x*b.x + a.y+b.y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia has certain Unicode operators defined, for example `\\cdot<TAB>`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "⋅"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that this operator is just an alias for the `dot` function, but that is parsed as in infix operator. So we can now write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v ⋅ w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It doesn't work. What's the matter? The signal was given by Julia when we defined `dot`: it said there was only 1 method. But `\\cdot<TAB>` has 7 methods. So they are different functions. The solution is that the name `dot` refers to Julia's built-in `dot` function, which is defined in Julia's standard library, called `Base`. So the true name of the function is `Base.dot`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Base.dot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We thus need to *extend* this function instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Base.dot(a::Vector2D, b::Vector2D) = a.x*b.x + a.y+b.y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v ⋅ w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia provides an `import` keyword to make this simpler when we are defining different methods for the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import Base.dot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This must be done *before* defining `dot`. To clear our current namespace we can use `workspace`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "workspace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "type Vector2D\n",
    "    x::Float64\n",
    "    y::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import Base.dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dot(a::Vector2D, b::Vector2D) = a.x*b.x + a.y+b.y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v = Vector2D(1, 2)\n",
    "w = Vector2D(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v ⋅ w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parametrised types "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may wish to define different kinds of `Vector2D` that contain different types. We can *define them all at once* by using a **type parameter**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "workspace()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "immutable Vector2D{T}\n",
    "    x::T\n",
    "    y::T\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have replaced the keyword `type` by `immutable`; this permits the compiler to store the object more efficiently. The `{T}` indicates that `T` can now be any type, and `x` and `y` are both of the *same* type `T`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Create vectors of different types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functions may also be parametrised:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "+{T}(a::Vector2D{T}, b::Vector2D{T}) = Vector2D{T}(a.x+b.x, a.y+b.y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining a particle "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Define a particle type and create a couple of particles. Define a function `move!` that moves a particle in its current direction for a small time $\\delta t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining a gas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Define a gas that contains a certain number of particles, $N$, and the particles themselves. Define `move!` for the gas. (A gas should also have a box in which it lives -- exercise.) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Example: Automatic differentiation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in other languages, a type's behaviour is determined both by its fields and by the methods that act on the types; the only difference, once again, is that in Julia the methods are defined outside the definition of the type itself.\n",
    "\n",
    "We will now define another type that has two fields but that behaves very differently, to permit [**automatic** (or **algorithmic**) **differentiation**](https://en.wikipedia.org/wiki/Automatic_differentiation).\n",
    "\n",
    "The idea is that to differentiation a complicated function, say\n",
    "\n",
    "$f(x) := \\sin[(x-1)(x^2+2)],$\n",
    "\n",
    "the function is decomposed into elementary functions that we know how to differentiate.\n",
    "\n",
    "For example, suppose that we know how to differentiate the functions $g(x) := x-1$ and $h(x) := x^2 + 2$ at $x=a$. Then the derivative of their product is given by\n",
    "\n",
    "$[g \\cdot h]'(a) = g(a) h'(a) + g'(a) h(a)$.\n",
    "\n",
    "Similarly, to differentiate *any* function at $a$, it is sufficient to know the value and the derivative of each subpart of the function at the same point $a$.\n",
    "\n",
    "We thus represent a function $f$ by the pair $(f(a), f'(a))$, which we can regard as a mathematical object called a [**jet**](https://en.wikipedia.org/wiki/Jet_(mathematics)), i.e. the collection [equivalence class] of all functions that have the same value and the same derivative at the point $a$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "immutable Jet\n",
    "    value::Float64\n",
    "    deriv::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The operations on `Jet`s should correspond to the operations on those functions to give new functions. For example, we have"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "+(f::Jet, g::Jet) = Jet(f.value+g.value, f.deriv+g.deriv)\n",
    "*(f::Jet, g::Jet) = Jet(f.value*g.value, f.value*g.deriv + f.deriv*g.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A constant function $c(x) := c$  for all $x$ has derivative $0$, so `c` corresponds to the jet `Jet(c, 0)`.\n",
    "The identity function $\\mathrm{id}(x)$ has the value $id(a)=a$ at the point $x=a$ and derivative $1$, and so corresponds to the Jet `Jet(a, 1)`.\n",
    "\n",
    "We can now do simple derivatives. Let's calculate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = 3\n",
    "xx = Jet(a, 1)\n",
    "\n",
    "f(x) = x*x + x  # we haven't yet defined ^ for a Jet!\n",
    "f′(x) = 2x + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@show f(a) \n",
    "@show f′(a)\n",
    "@show f(xx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This correctly calculates, *automatically*, the value and derivative of the function at $a$!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Promotion and conversion "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we now try to do "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "xx + 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia does not know how to add a jet and an integer -- because we defined addition only for two jets.\n",
    "One (painful) solution would be to explicitly define `+(a::Jet, b::Number)`, `+(a::Number, b::Jet)`, and the same for all the other operations.\n",
    "\n",
    "Julia provides a better solution: a system for promotion and conversion of types from one type to another. Nothing is \"automatic\", though, it's all coded in rules. For example, what does Julia do when we try to add an integer and a float?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@which 3 + 4.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that it calls a very generic function that adds two `Number`s. We copy here the code for convenience:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "+(x::Number, y::Number) = +(promote(x,y)...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does this call to `promote` do?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "promote(3, 4.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It returns both numbers, converted to the same type. How does it work?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@which promote(3, 4.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That code is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "function promote{T,S}(x::T, y::S)\n",
    "    (convert(promote_type(T,S),x), convert(promote_type(T,S),y))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It uses the function `convert` that converts between types, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "convert(Float64, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@which convert(Float64, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That code calls out the `sitofp` LLVM intrinsic function that converts a signed integer to a floating point number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does `promote_type` do?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "promote_type(Float64, Int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@which promote_type(Float64, Int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "promote_type{T,S}(::Type{T}, ::Type{S}) =\n",
    "    promote_result(T, S, promote_rule(T,S), promote_rule(S,T))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally, "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "promote_rule(Float64, Int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@which promote_rule(Float64, Int64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This specifies what the result of the promotion of those two types should be."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining our own conversions and promotions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can \"hook in\" to this mechanism if we think of a `Jet` as a *type of `Number`*. We can specify that `Jet` is a new type in the type hierarchy below `Number` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "workspace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "immutable Jet <: Number\n",
    "    value::Float64\n",
    "    deriv::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Base.convert(::Type{Jet}, c::Real) = Jet(c, 0)\n",
    "Base.promote_rule{S<:Real}(::Type{Jet}, ::Type{S}) = Jet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "+(f::Jet, g::Jet) = Jet(f.value+g.value, f.deriv+g.deriv)\n",
    "*(f::Jet, g::Jet) = Jet(f.value*g.value, f.value*g.deriv + f.deriv*g.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now operations with constants work \"magically\" (without any magic at all, i.e. with everything being completely explicit and traceable in the code):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "j = Jet(3, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "j + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "j * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "2 * j"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we can differentiate more complicated functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "f(x) = 3x^2 + 2.3x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = 3\n",
    "xx = Jet(a, 1)\n",
    "f(xx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Define `^` for jets and check that you can differentiate polynomials. Define `exp` for a jet and differentiate functions involving exponentials. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that several [implementations](http://www.juliadiff.org/) of automatic differentiation are available.\n",
    "An implementation along the lines presented here is available in [`ValidatedNumerics.jl`](https://github.com/dpsanders/ValidatedNumerics.jl)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.3.10-pre",
   "language": "julia",
   "name": "julia-0.3"
  },
  "language_info": {
   "name": "julia",
   "version": "0.3.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}