2. Metaprogramming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to metaprogramming: \"Code that creates code\" "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia has strong **metaprogramming** capabilities. What does this mean?\n",
    "\n",
    "> **meta**: something on a higher level\n",
    "\n",
    "**metaprogramming** = \"higher-level programming\"\n",
    "\n",
    "i.e. writing code (a program) to manipulate not data, but code (that itself manipulates data)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivating example\n",
    "\n",
    "Metaprogramming has many different uses, several of which we will explore. It is often a way to add, or change, the syntax of Julia, to write a \"domain-specific language\" (DSL), that converts a simple syntax (but that is not standard Julia syntax) into true Julia code.\n",
    "\n",
    "As a motivating example, we might like to be able to write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: ∑_ not defined\nwhile loading In[2], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: ∑_ not defined\nwhile loading In[2], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "∑_{i ≠ j}, 1/(λ_i - λ_j)  # NOT JULIA SYNTAX!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and have it *automatically converted* into something like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "total = zero(λ[1])\n",
    "\n",
    "for i in 1:N\n",
    "    j == i && continue\n",
    "    \n",
    "    total += 1 / (λ[i] - λ[j])\n",
    "end\n",
    "\n",
    "total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A simpler example "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is too hard [**exercise**: write this functionality and make it into a package!], let's start out with a simpler example: Wilkinson-type polynomials.\n",
    "The [Wilkinson polynomial](https://en.wikipedia.org/wiki/Wilkinson's_polynomial) is\n",
    "\n",
    "$$p_{20}(x) := (x-1) \\cdot (x-2) \\cdot \\cdots \\cdot (x-20) = \\prod_{i=1}^{20} (x-i).$$\n",
    "\n",
    "[Polynomials like this are interesting, since the eigenvalues of the associated \"companion matrix\", which are used to find the roots of the polynomial, are very sensitive to perturbations of the coefficients of the polynomial.]\n",
    "\n",
    "Suppose we wish to define this polynomial in Julia. The simple way would be to write it out explicitly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "p_5 (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_5(x) = (x-1) * (x-2) * (x-3) * (x-4) * (x-5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$p_{10}$ is already a pain to type by hand, $p_{20}$ more so, and $p_{100}$ is basically impossible. But this is just a case of repetition, and computers are designed for that. One possible definition uses a `for` loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "wilkinson (generic function with 1 method)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function wilkinson(n, x)\n",
    "    result = x - 1\n",
    "    \n",
    "    for i in 2:n\n",
    "        result *= (x - i)\n",
    "    end\n",
    "    \n",
    "    result\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use an anonymous function to define the function $p_n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "p (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p(n) = x -> wilkinson(n, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-0.20790000000000022"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p(4)(3.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[In Julia 0.4, anonymous functions have a performance penalty, although they no longer do in 0.5.]\n",
    "\n",
    "It seems, though, that it should be possible to use the original definition of the function to write the equivalent of"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p_5(x) = (x-1)*(x-2)*(x-3)*(x-4)*(x-5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "for $n=100$.\n",
    "In other languages, this would often be accomplished by manipulating strings that represent the \"surface syntax\", i.e. the string of characters that you would actually type, and then evaluate this string. However, in Julia\n",
    "**we never use strings for this**, since Julia has a way to **refer to Julia code objects within Julia**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expressions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Let's take the simplest polynomial, that we write as `(x-1) * (x-2)`. We can view this as a piece of Julia code, called an **expression**, and can tell Julia this as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote  # In[7], line 2:\n",
       "    (x - 1) * (x - 2)\n",
       "end"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = quote   \n",
    "        (x - 1) * (x - 2)\n",
    "    end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For small pieces of code like this, an alternative syntax uses the `:( ... )`  operator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :( (x-1) * (x-2) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does Julia think this is?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Expr"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that Julia has a type `Expr` that represents an **expression object**, that we can think of as a \"Julia code snippet\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to be able to execute this code; we can do so with `eval` (\"evaluate\"):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: x not defined\nwhile loading In[11], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: x not defined\nwhile loading In[11], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "eval(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that `x` is not defined, since Julia is trying to do the same as if we had written the following straight at the prompt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: x not defined\nwhile loading In[12], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: x not defined\nwhile loading In[12], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "(x-1) * (x-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we give `x` a value first, then it works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.75"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 3.5\n",
    "(x-1) * (x-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And so hence does the `eval`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.75"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, we can try to write a simple formula evaluator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"3x^2 + 4x - 3sin(x)\""
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "formula = \"3x^2 + 4x - 3sin(x)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"3x\""
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(formula)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This does not do what we expect, since we have a string, not a Julia expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ASCIIString"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(formula)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To convert this string into an expression, we use `parse`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(3x)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "formula2 = parse(formula)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.5"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(formula2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((3 * x ^ 2 + 4x) - 3 * sin(x))"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = parse(\"3x^2 + 4x - 3sin(x)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51.80234968306886"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "f(x) = 3x^2 + 4x - 3sin(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the really hard work, that of parsing the expression, i.e. converting it into an internal representation in terms of a tree, has already been done for us by Julia. It is thus, happily, usually not necessary for us to write our own parser; we just leverage Julia's own! This is one of many ways in which Julia minimises the work that we need to do, compared to other languages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structure of `Expr`essions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An expression object of type `Expr` has an internal structure that corresponds to the **abstract syntax tree** (AST) of the expression, i.e. a tree, whose nodes are operations, and whose children are subtrees.\n",
    "We can see this in two ways, using `dump`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expr \n",
      "  head: Symbol call\n",
      "  args: Array(Any,(3,))\n",
      "    1: Symbol -\n",
      "    2: Expr \n",
      "      head: Symbol call\n",
      "      args: Array(Any,(3,))\n",
      "        1: Symbol +\n",
      "        2: Expr \n",
      "          head: Symbol call\n",
      "          args: Array(Any,(3,))\n",
      "          typ: Any\n",
      "        3: Expr \n",
      "          head: Symbol call\n",
      "          args: Array(Any,(3,))\n",
      "          typ: Any\n",
      "      typ: Any\n",
      "    3: Expr \n",
      "      head: Symbol call\n",
      "      args: Array(Any,(3,))\n",
      "        1: Symbol *\n",
      "        2: Int64 3\n",
      "        3: Expr \n",
      "          head: Symbol call\n",
      "          args: Array(Any,(2,))\n",
      "          typ: Any\n",
      "      typ: Any\n",
      "  typ: Any\n"
     ]
    }
   ],
   "source": [
    "dump(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which shows everything [up to a pre-determined depth] in detail, or "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(:call, :-, (:call, :+, (:call, :*, 3, (:call, :^, :x, 2)), (:call, :*, 4, :x)), (:call, :*, 3, (:call, :sin, :x)))"
     ]
    }
   ],
   "source": [
    "Meta.show_sexpr(ex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :((x-1) * (x-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expr \n",
      "  head: Symbol call\n",
      "  args: Array(Any,(3,))\n",
      "    1: Symbol *\n",
      "    2: Expr \n",
      "      head: Symbol call\n",
      "      args: Array(Any,(3,))\n",
      "        1: Symbol -\n",
      "        2: Symbol x\n",
      "        3: Int64 1\n",
      "      typ: Any\n",
      "    3: Expr \n",
      "      head: Symbol call\n",
      "      args: Array(Any,(3,))\n",
      "        1: Symbol -\n",
      "        2: Symbol x\n",
      "        3: Int64 2\n",
      "      typ: Any\n",
      "  typ: Any\n"
     ]
    }
   ],
   "source": [
    "dump(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which gives a compact version (similar to an [S-expression](https://en.wikipedia.org/wiki/S-expression) in Lisp, whence the name of the function, which is in the `Meta` submodule in `Base`). They both give representations of the syntax tree describing the hierarchical structure of the expression.\n",
    "\n",
    "The point is that since an `Expr`ession is a **standard Julia objects**, we can **use standard Julia commands to manipulate it**! \n",
    "\n",
    "As usual, doing `ex.<TAB>` gives a list of the fields in the type `Expr`, or we can use `fieldnames(ex)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Symbol,1}:\n",
       " :head\n",
       " :args\n",
       " :typ "
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fieldnames(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and then examine the fields:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":call"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tells us that the expression represents a function call, whose arguments are the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Any,1}:\n",
       " :*      \n",
       " :(x - 1)\n",
       " :(x - 2)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`ex.typ` is not useful for the user.]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first element of the array `ex.args` is the function to be called:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":*"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and the second element is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(x - 1)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "that is, it is itself an `Expr`ession:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Expr"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus the structure of `Expr`essions is fundamentally recursive, and so lends itself naturally to recursive algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can dive, in turn, into the structure of each element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(=)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2 = :(a = b + c)\n",
    "ex2.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":call"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(x - 1)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":-"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[2].args[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":x"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[2].args[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is this `:x`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Symbol"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(ex.args[2].args[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that it has a special `Symbol` type, which represents the atoms (smallest parts) of an expression."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modifying expressions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, what happens if we **modify** this?  Let's make a copy of the expression first so that we can compare the two."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :((x - 1) * (x - 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2 = copy(ex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":z"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2.args[2] = :z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(z * (x - 2))"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":x"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2.args[2].args[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":z"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2.args[2].args[2] = :z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have changed something inside the object `ex2`, so let's look at it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((z - 1) * (x - 2))"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The original expression has, indeed, changed! That is, we have taken a piece of Julia code, and used Julia itself to manipulate it into a different piece of Julia code. This is one of the simplest examples of metaprogramming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can define `x` and `z` and evaluate the expressions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.5"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 3.5; z = 4.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3.75,6.75)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ex), eval(ex2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Walking a syntax tree "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What if we wanted to replace *all* of the `x`s in a given expression. The problem is that they may be buried arbitrarily deeply in the nested syntax tree. So we have to traverse the tree, in order to visit each piece of it and check if it is an `:x`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Write a function that takes an expression object and replaces **all** of the `:x`s by `:z`s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Tuple{Int64,Int64},1}:\n",
       " (1,4)\n",
       " (2,5)\n",
       " (3,6)"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = [4, 5, 6]\n",
    "collect(enumerate(v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "traverse! (generic function with 1 method)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function traverse!(ex::Expr)\n",
    "    for i in 1:length(ex.args) # enumerate(ex.args)\n",
    "        \n",
    "        if ex.args[i] == :x\n",
    "            #ex.args[i] = :z   # we cannot use arg here, since it is a copy, not a reference\n",
    "            ex.args[i] = :z\n",
    "        end\n",
    "        \n",
    "        if isa(ex.args[i], Expr)\n",
    "            traverse!(ex.args[i])\n",
    "        end\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :((x-1)*(x-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((z - 1) * (z - 2))"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traverse!(ex)\n",
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, we can now make this potentially more useful by generalising the function, allowing us to replace one sub-expression by another:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "traverse! (generic function with 2 methods)"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function traverse!(ex::Expr, find, replace)\n",
    "    for (i, arg) in enumerate(ex.args)\n",
    "        \n",
    "        if arg == find\n",
    "            ex.args[i] = replace   # we cannot use arg here, since it is a copy, not a reference\n",
    "        end\n",
    "        \n",
    "        if isa(arg, Expr)\n",
    "            traverse!(arg, find, replace)   # recursive\n",
    "        end\n",
    "    end\n",
    "    \n",
    "    ex\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 10) * (x - 2))"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traverse!( :( (x-1) * (x-2) ), :(x-1), :(x-10) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((z - 1) * (z - 2))"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traverse!( :( (x-1) * (x-2) ), :(x), :(z) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is, of course, not general enough - for example, we cannot replace something of the form `:(x - a)` with `:(x - 2a)` with the current version; this would require more sophisticated pattern matching capabilities - but it demonstrates the basic idea."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Julia by default uses standard 64-bit (or 32-bit) integers, which leads to surprising behaviour, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-9223372036854775808"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2^32 * 2^31"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No warning is given that there was an overflow in this calculation. \n",
    "\n",
    "However, in `Base` there are *checked* operations, such as `checked_mul`, which do throw an exception on overflow:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: OverflowError()\nwhile loading In[77], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: OverflowError()\nwhile loading In[77], in expression starting on line 1",
      "",
      " in checked_mul at int.jl:514"
     ]
    }
   ],
   "source": [
    "Base.checked_mul(2^60, 2^60)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Write a function `checked` that replaces standard functions (`-`, `+`, `*`, `/`) in an expression by their corresponding checked counterparts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's return to the original question: how to create a long polynomial expression. \n",
    "So far, we have not seen how to *add* code, only *change* code that is already there. \n",
    "\n",
    "A natural idea is to build the code up step by step; this is known as **code generation**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's start again from the first term:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(x - 1)"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(x-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Expr"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to take what we have and create code that is \"what we have multiplied by `:(x-2)`\". Let's try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(ex * (x - 2))"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex_new = :(ex * (x-2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This doesn't work, since `ex` is treated as a symbol, whereas we need the *value* contained in the *variable* called `ex`. This is obtained using the `$` operator, a procedure called **interpolation**. (Compare this to string interpolation.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"Hello David\""
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "name = \"David\"\n",
    "s = \"Hello $name\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x - 1) * (x - 2))"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :( $ex * (x-2) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Now we can continue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(((x - 1) * (x - 2)) * (x - 3))"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :( $ex * (x-3) ) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we see how to construct our loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "ex = :(x-1)\n",
    "\n",
    "for i in 2:n\n",
    "    ex = :( $ex * (x - i) )\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((((((((((x - 1) * (x - 2)) * (x - 3)) * (x - 4)) * (x - 5)) * (x - 6)) * (x - 7)) * (x - 8)) * (x - 9)) * (x - 10))"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This did not work, since once again we did not want \"the code '`i`'\", but rather the value of the variable `i`. So:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "\n",
    "ex = :(x-1)\n",
    "\n",
    "for i in 2:n\n",
    "    ex = :( $ex * (x - $i) )\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((((((((((x - 1) * (x - 2)) * (x - 3)) * (x - 4)) * (x - 5)) * (x - 6)) * (x - 7)) * (x - 8)) * (x - 9)) * (x - 10))"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is almost what we would write by hand, except for the large number of parentheses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to produce the name of the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"p_10\""
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "string(\"p_\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":p_10"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "name = symbol(\"p_\", n)   # use `Symbol` instead of `symbol` in Julia v0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code is then"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(p_10(x) = begin  # In[101], line 1:\n",
       "            (((((((((x - 1) * (x - 2)) * (x - 3)) * (x - 4)) * (x - 5)) * (x - 6)) * (x - 7)) * (x - 8)) * (x - 9)) * (x - 10)\n",
       "        end)"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code = :( $name(x) = $ex )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can wrap this in a function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "make_wilkinson (generic function with 1 method)"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function make_wilkinson(n)\n",
    "    \n",
    "    ex = :(x-1)\n",
    "\n",
    "    for i in 2:n\n",
    "        ex = :( $ex * (x - $i) )\n",
    "    end\n",
    "    \n",
    "    name = symbol(\"p_\", n) \n",
    "    code = :( $name(x) = $ex )\n",
    "    \n",
    "    eval(code)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we evaluate this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "p_10 (generic function with 1 method)"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_wilkinson(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "p_100 (generic function with 1 method)"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_wilkinson(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This creates a function with the name `p_10` that does what we would write by hand."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compare the two options by evaluating the function on a grid of values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "f2 (generic function with 1 method)"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f1(range)\n",
    "    total = 0.0\n",
    "    for x in range\n",
    "        total += p_100(x)\n",
    "    end\n",
    "    return total\n",
    "end\n",
    "\n",
    "function f2(range)\n",
    "    total = 0.0\n",
    "    for x in range\n",
    "        total += wilkinson(100, x)\n",
    "    end\n",
    "    return total\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.2080035401369522"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range = -10:0.000001:10\n",
    "t1 = @elapsed f1(range);\n",
    "t2 = @elapsed f2(range);\n",
    "t2 / t1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the generated code with the unrolled loop is 10% faster than the naive loop with 100 terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Starting from empty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In some cases, it is useful to start from something empty and add statements to it.\n",
    "To do this, we can do, for example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote \n",
       "end"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code = quote end   # empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expr \n",
      "  head: Symbol block\n",
      "  args: Array(Any,(0,))\n",
      "  typ: Any\n"
     ]
    }
   ],
   "source": [
    "dump(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Note that in Julia 0.5, this is not \"empty\", since it has a `:line` line-number node.]\n",
    "\n",
    "We can add statements using the standard Julia `push!`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote \n",
       "    a = 1\n",
       "    b = a + 1\n",
       "end"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Base.push!(code.args, :(a = 1))\n",
    "Base.push!(code.args, :(b = a + 1))\n",
    "code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expr \n",
      "  head: Symbol call\n",
      "  args: Array(Any,(4,))\n",
      "    1: Symbol *\n",
      "    2: Symbol a\n",
      "    3: Symbol b\n",
      "    4: Symbol c\n",
      "  typ: Any\n"
     ]
    }
   ],
   "source": [
    "dump(:(a * b * c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Build up the Wilkinson example using this technique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Repetitive code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code generation is used frequently in Julia code when repetitive code is required. For example, let's return to the idea of wrapping a type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type OurFloat\n",
    "    x::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can generate objects of this type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OurFloat(4.0)"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = OurFloat(3)\n",
    "b = OurFloat(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But arithmetic operations are not defined:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: MethodError: `+` has no method matching +(::OurFloat, ::OurFloat)\nClosest candidates are:\n  +(::Any, ::Any, !Matched::Any, !Matched::Any...)\nwhile loading In[124], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: MethodError: `+` has no method matching +(::OurFloat, ::OurFloat)\nClosest candidates are:\n  +(::Any, ::Any, !Matched::Any, !Matched::Any...)\nwhile loading In[124], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can define them in the natural way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- (generic function with 205 methods)"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import Base: +, -, *, /\n",
    "+(a::OurFloat, b::OurFloat) = a.x + b.x\n",
    "-(a::OurFloat, b::OurFloat) = a.x - b.x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But this will quickly get dull, and we could easily make a mistake. \n",
    "As usual, whenever we are repeating something more than twice, we should try to automate it.\n",
    "\n",
    "We have some code of the form\n",
    "\n",
    "    *op*(a::OurFloat, b::OurFloat) = a.x *op* b.x\n",
    "    \n",
    "where `*op*` is supposed to represent the operator. Julia allows us to do this almost literally; we just need to substitute in the *value* of the *variable* `op`! This is an **exercise**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "op = :+\n",
      "code = :(a::OurFloat + b::OurFloat = begin  # In[127], line 3:\n",
      "            a.x + b.x\n",
      "        end)\n",
      "op = :-\n",
      "code = :(a::OurFloat - b::OurFloat = begin  # In[127], line 3:\n",
      "            a.x - b.x\n",
      "        end)\n",
      "op = :*\n",
      "code = :(a::OurFloat * b::OurFloat = begin  # In[127], line 3:\n",
      "            a.x * b.x\n",
      "        end)\n",
      "op = :/\n",
      "code = :(a::OurFloat / b::OurFloat = begin  # In[127], line 3:\n",
      "            a.x / b.x\n",
      "        end)\n"
     ]
    }
   ],
   "source": [
    "for op in (:+, :-, :*, :/)\n",
    "    @show op\n",
    "    code = :( $(op)(a::OurFloat, b::OurFloat) = $(op)(a.x, b.x) )\n",
    "    @show code\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we need to evaluate the code. The combination of `eval` and `:(...)` that we used above can be abbreviated to `@eval`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for op in (:+, :-, :*, :/)\n",
    "    @eval $(op)(a::OurFloat, b::OurFloat) = $(op)(a.x, b.x) \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.0"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "*(a::<b>OurFloat</b>, b::<b>OurFloat</b>) at In[128]:2"
      ],
      "text/plain": [
       "*(a::OurFloat, b::OurFloat) at In[128]:2"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which a*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "sin(x::<b>Float64</b>) at <a href=\"https://github.com/JuliaLang/julia/tree/2e358ce975029ec97aba5994c17d4a2169c3b085/base/math.jl#L137\" target=\"_blank\">math.jl:137</a>"
      ],
      "text/plain": [
       "sin(x::Float64) at math.jl:137"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@which sin(3.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Macros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is very common in Julia to use things that look like functions but whose names start with `@`, e.g. `@time`, `@which`, etc. These are not functions in the standard sense, but rather are a kind of \"super-function\", called **macros**. \n",
    "\n",
    "A macro takes a **piece of Julia code** (`Expr`ession object) as its argument, manipulates that code to turn it into a new one, and **returns a new piece of code** as its output. The effect of a macro call is to insert that new piece of code in place of the old code, which is consequently compiled by the Julia compiler. \n",
    "\n",
    "Note that the user *does not need to explicitly pass an `Expr`ession object, since this is done automatically*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see this, let's define a simple macro:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "macro simple(expr)\n",
    "    @show expr\n",
    "    nothing   # return nothing for the moment\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: ≲ not defined\nwhile loading In[137], in expression starting on line 3",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: ≲ not defined\nwhile loading In[137], in expression starting on line 3",
      ""
     ]
    }
   ],
   "source": [
    "x = 3\n",
    "y = 4\n",
    "x ≲ y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expr = :((3 * x ^ 2 + 4x) - 2)\n"
     ]
    }
   ],
   "source": [
    "@simple 3x^2 + 4x - 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the Julia code that follows the macro call is passed to the macro *already having been parsed into an `Expr` object*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we redefine the macro as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "macro simple(expr)\n",
    "    @show expr\n",
    "    expr  # returns expr\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we get"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expr = :(w + z)\n"
     ]
    },
    {
     "ename": "LoadError",
     "evalue": "LoadError: UndefVarError: w not defined\nwhile loading In[140], in expression starting on line 1",
     "output_type": "error",
     "traceback": [
      "LoadError: UndefVarError: w not defined\nwhile loading In[140], in expression starting on line 1",
      ""
     ]
    }
   ],
   "source": [
    "@simple w + z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is happening here is that the macro returns the expression `:(x+y)`, and this is then evaluated using `eval`.\n",
    "The result is that Julia tries to calculate the value of the expression `x+y`, but the variable `x` is not defined. Let's define `y` and `z`, but not `x`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "y = 3; z = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@simple x+y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's define a new macro `@replace` that uses our previous `replace` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "macro traverse(expr)\n",
    "    traverse!(expr)\n",
    "    @show expr\n",
    "    #Meta.quot(expr)\n",
    "    expr\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expr = :(z + y)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8.5"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@traverse x + y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `macroexpand`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can discover what a macro does using the `macroexpand` function which takes a code expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.000003 seconds (5 allocations: 176 bytes)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-0.5440211108893698"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@time sin(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(sin(10))"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(sin(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote  # util.jl, line 153:\n",
       "    local #101#stats = Base.gc_num() # util.jl, line 154:\n",
       "    local #103#elapsedtime = Base.time_ns() # util.jl, line 155:\n",
       "    local #102#val = sin(10) # util.jl, line 156:\n",
       "    #103#elapsedtime = Base.-(Base.time_ns(),#103#elapsedtime) # util.jl, line 157:\n",
       "    local #104#diff = Base.GC_Diff(Base.gc_num(),#101#stats) # util.jl, line 158:\n",
       "    Base.time_print(#103#elapsedtime,#104#diff.allocd,#104#diff.total_time,Base.gc_alloc_count(#104#diff)) # util.jl, line 160:\n",
       "    #102#val\n",
       "end"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macroexpand(:(@time sin(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example of the use of a macro, let's look at the `@interval` macro from the [`ValidatedNumerics.jl` package](https://github.com/dpsanders/ValidatedNumerics.jl):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Pkg.add(\"ValidatedNumerics\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "using ValidatedNumerics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.0999999, 0.100001]"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@interval(0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Floating-point calculations are not precise. Interval arithmetic is a way to provide a guaranteed *enclosure* of a result, i.e. an interval that contains the true result. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(ValidatedNumerics.convert(Interval{parameters.precision_type},0.1))"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macroexpand(:(@interval(0.1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.07989, 1.0799]"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@interval sin(0.1) + cos(0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(ValidatedNumerics.+(sin(ValidatedNumerics.convert(Interval{parameters.precision_type},0.1)),cos(ValidatedNumerics.convert(Interval{parameters.precision_type},0.2))))"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hello = macroexpand(:(@interval sin(0.1) + cos(0.2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This has the structure `sin(interval(0.1)) + cos(interval(0.2))` (although the details are a bit more complicated).\n",
    "\n",
    "So basically the `@interval` macro does something very similar to our `replace!` macro: it walks the tree of the expression; finds parts of it that are of a certain type (numeric literals); and wraps those in the `make_interval` function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a `@checked` macro that uses the `check_arithmetic` function from a previous exercise to wrap convert a piece of code that uses arithmetic operations into the corresponding code that uses the checked versions instead."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Macro hygiene"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An important, but slippery topic with macros is so-called \"hygiene\". This refers to where variables are considered to be defined: inside the macro itself, or where the code that the macro creates is evaluated. We unfortunately do not have time to give this topic a detailed discussion. \n",
    "\n",
    "Basically, we need to allow variables to \"escape\" from the environment of the macro into the surrounding code, when the code returned by a macro refers to these external variables, rather than variables internal to the macro. This is done using `esc`; see the corresponding [Julia documentation](http://docs.julialang.org/en/release-0.4/manual/metaprogramming/#hygiene), and perhaps books on Lisp."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.4.6",
   "language": "julia",
   "name": "julia-0.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.4.6"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}