3. Metaprogramming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Metaprogramming: \"Code that creates code\" "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia has strong metaprogramming capabilities, i.e. we can use Julia to manipulate objects in Julia that represent Julia code. In this way, we can produce code in an automatic way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since this is rather abstract, let's consider a very concrete 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 their eigenvalues 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 explicitly:"
   ]
  },
  {
   "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": [
    "$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. Of course, one possible definition uses a `for` loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "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 have the actual function object $p_n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wilkinson(n) = x -> wilkinson(n, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, as we have seen, currently \"anonymous functions are slow\". It seems like it should be possible to use the original definition of the function by \"unrolling the loop\" and writing a loop that writes *the code to generate the function*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expressions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In other languages, e.g. Python, code is manipulated as strings. Julia takes a different approach. Consider the string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s = \"(x-1) * (x-2)\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To convert this into an object that represents Julia code, we **parse** it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex = parse(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "typeof(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`ex` is a Julia *expression object*. It can be thought of as a representation of the \"abstract syntax tree\" (AST) representing the internal structure of the expression. We can see this in two ways, using `dump`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dump(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which shows everything in detail, or "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Meta.show_sexpr(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which gives a compact version."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that `Expr`s have a hierarchical format that represents the code. Since they are simply Julia objects, e.g. `Array`s, we *can use Julia to manipulate them*.\n",
    "\n",
    "The object `:x` is of type Symbol, and represents the unevaluated object `:x`. This is basically a special type of string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Write a function that takes an expression object and replaces all the `:x`s by `:z`s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our case, we do not need to mess with the internal structure of code, but rather build up code from preexisting bits. We can do this as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex = :(x-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex = :(($ex) * (x-2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, in the same way as in string interpolation, we have inserted the current *value* of `ex` into the expression!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex = :(($ex) * (x-3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can make our loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "ex = :(x-1)\n",
    "for i in 2:n\n",
    "    ex = :( ($ex) * (x-i) )\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This did not work, since we did not want \"the code '`i`'\", but rather the value of `i`. So:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "ex = :(x-1)\n",
    "for i in 2:n\n",
    "    ex = :( ($ex) * (x-$i) )\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to produce the name of the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "name = symbol(string(\"W_\", n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[In Julia v0.4, this can be written more simply as `symbol(\"W_\", n)`.]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the code that we would like is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "code = :( $name(x) = $ex )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we wish to evaluate this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "eval(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This creates a function with the name `W_10` that does (almost) exactly 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": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "f1(range) = [W_10(x) for x in range]\n",
    "f2(range) = [wilkinson(10, x) for x in range]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "range = -10:0.000001:10\n",
    "@time f1(range);\n",
    "@time f2(range);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the generated code with the unrolled loop is twice as fast as the naive `for` loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code generation like this is used frequently in Julia code when repetitive code is required."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Macros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The things that feel like functions whose names start with `@` that we have been using, such as `@time`, `@which`, etc., are not functions in the standard sense, but rather are **macros**. These are \"super-functions\" whose arguments are code expressions, and which transform one code expression into another. This new code expression is then evaluated as if the new code had been typed directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand what is going on, let's define a simple macro:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "macro simple(expr)\n",
    "    @show expr\n",
    "    0  # for the moment\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@simple x+y"
   ]
  },
  {
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "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": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@simple x+y"
   ]
  },
  {
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "macro replace!(expr)\n",
    "    replace(expr)\n",
    "    @show expr\n",
    "    expr\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@replace! 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": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote  # util.jl, line 53:\n",
       "    local #464#b0 = Base.gc_bytes() # line 54:\n",
       "    local #465#t0 = Base.time_ns() # line 55:\n",
       "    local #466#g0 = Base.gc_time_ns() # line 56:\n",
       "    local #467#val = sin(10) # line 57:\n",
       "    local #468#g1 = Base.gc_time_ns() # line 58:\n",
       "    local #469#t1 = Base.time_ns() # line 59:\n",
       "    local #470#b1 = Base.gc_bytes() # line 60:\n",
       "    Base.time_print(Base.-(#469#t1,#465#t0),Base.-(#470#b1,#464#b0),Base.-(#468#g1,#466#g0)) # line 61:\n",
       "    #467#val\n",
       "end"
      ]
     },
     "execution_count": 11,
     "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": true
   },
   "outputs": [],
   "source": [
    "Pkg.add(\"ValidatedNumerics\")\n",
    "Pkg.checkout(\"ValidatedNumerics\", \"master\")  # checkout the master branch [\"master\" is not necessary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using ValidatedNumerics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.09999999999999999, 0.1]"
      ]
     },
     "execution_count": 13,
     "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": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(ValidatedNumerics.make_interval(interval_parameters.precision_type,0.1))"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macroexpand(:(@interval(0.1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0798999944880696, 1.07989999448807]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@interval sin(0.1) + cos(0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(ValidatedNumerics.+(sin(ValidatedNumerics.make_interval(interval_parameters.precision_type,0.1)),cos(ValidatedNumerics.make_interval(interval_parameters.precision_type,0.2))))"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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"
   ]
  }
 ],
 "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
}