3. Case study of metaprogramming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Case study of metaprogramming: interval constraint propagation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perhaps the best way to learn metaprogramming is through an example. \n",
    "Let's look at **interval constraint propagation**, as implemented in the author's\n",
    "[`IntervalConstraintProgramming.jl`](https://github.com/dpsanders/IntervalConstraintProgramming.jl) package.\n",
    "\n",
    "This is less complicated than it sounds. The idea is to find a way of taking a declarative **constraint**, like `x^2 + y^2 <= 1`, representing a set `S`, and **turning it into actual code** that operates on interval variables `x` and `y` representing a box `B` in the plane, and *contracts* it (squashes it down) to a smaller subbox `B'` that still contains the part of `B` that is inside `S`.\n",
    "\n",
    "The method takes the AST (Abstract Syntax Tree) of the expression, and unfolds it in two directions: first \"forward\", from the leaves of the tree towards the root, and then backwards, incorporating the constraints. We will present a simplified version of the code at https://github.com/dpsanders/IntervalConstraintProgramming.jl/blob/master/src/contractor.jl"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take the example of the expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(x ^ 2 + y ^ 2)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(x^2 + y^2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to introduce new variables at each node in the tree, from the \"bottom\" (i.e. the leaves) up, giving the result\n",
    "\n",
    "    z1 = x^2\n",
    "    z2 = y^2\n",
    "    z3 = z1 + z2\n",
    "    \n",
    "These variables will be used later in the backwards pass to pass back information about the constraint that `z3` must be in the interval `[0,1]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we define an expression, Julia parses it into its AST:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(:call, :+, (:call, :^, :x, 2), (:call, :^, :y, 2))"
     ]
    }
   ],
   "source": [
    "Meta.show_sexpr(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Forward pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "workspace()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We first write a function to generate new unique symbols. (We could use `gensym()` from `Base`, but the result is unreadable for humans):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: redefining constant _variable_number_\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "makesymbol (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const _variable_number_ = [0]\n",
    "\n",
    "makesymbol() = symbol(\"_z_\", _variable_number_[1]+=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":_z_1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "makesymbol()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":_z_2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "makesymbol()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will make a recursive function that takes a sub-expression and returns two things: (i) the new variable at the top of that subexpression; and (ii) the code that has been generated so far."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "unfold (generic function with 2 methods)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unfold(ex) = (ex, quote end)  # catch-all for symbols and constants\n",
    "\n",
    "\n",
    "function unfold(ex::Expr)\n",
    "\n",
    "    ex.head != :call && throw(ArgumentError(\"Unknown expression type: $ex\"))\n",
    "    \n",
    "    new_code = quote end   # empty expression\n",
    "\n",
    "    op = ex.args[1]\n",
    "    \n",
    "    # do child nodes *first*:\n",
    "    var1, code1 = unfold(ex.args[2])\n",
    "    var2, code2 = unfold(ex.args[3])\n",
    "        \n",
    "    new_var = makesymbol()\n",
    "    new_line = :($new_var = $op($var1, $var2))   \n",
    "    \n",
    "    append!(new_code.args, code1.args)\n",
    "    append!(new_code.args, code2.args)\n",
    "    push!(new_code.args, new_line)\n",
    "    \n",
    "    return new_var, new_code\n",
    "\n",
    "end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backward pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The top-level variable must now be constrained:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:_z_5,quote \n",
       "    _z_3 = x ^ 2\n",
       "    _z_4 = y ^ 2\n",
       "    _z_5 = _z_3 + _z_4\n",
       "end)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(x^2 + y^2)\n",
    "var, code = unfold(ex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "intersect (generic function with 15 methods)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "∩"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Array{Any,1}:\n",
       " :(_z_3 = x ^ 2)               \n",
       " :(_z_4 = y ^ 2)               \n",
       " :(_z_5 = _z_3 + _z_4)         \n",
       " :(_z_5 = _z_5 ∩ Interval(0,1))\n",
       " :(_z_5 = _z_5 ∩ Interval(0,1))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "interval = :(Interval(0,1))\n",
    "\n",
    "constraint_code = :($var = $var ∩ $interval)\n",
    "push!(code.args, constraint_code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we wish to go backwards through the generated code, and use reverse-mode functions to propagate the constraints.\n",
    "For example, if `z5 = z3 + z4`, then `z3 = z5 - z4`, so we can *constrain* `z3` accordingly by\n",
    "\n",
    "    z3 = z3 ∩ (z5 - z4)\n",
    "    \n",
    "Here, ∩ is an operation defined on intervals in the [`ValidatedNumerics.jl package`](https://github.com/dpsanders/ValidatedNumerics.jl)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will assume that there are so-called \"reverse mode\" functions defined that do these operations; see https://github.com/dpsanders/IntervalConstraintProgramming.jl/blob/master/src/reverse_mode.jl\n",
    "\n",
    "We will then replace `z5 = z3 + z4` by `(z5,z3,z4) = reverse_add(z5, z3, z4)` with the following function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To find out how to do this, we do"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ex = :(z = x + y)\n",
    "dump(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tells us which elements to use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "var1 = ex.args[1]\n",
    "op = ex.args[2].args[1]\n",
    "var2, var3 = ex.args[2].args[2:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Dict{Symbol,Symbol} with 2 entries:\n",
       "  :+ => :reverse_add\n",
       "  :- => :reverse_sub"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const reverse_ops = Dict(:+ => :reverse_add,\n",
    "                            :- => :reverse_sub)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "make_reverse (generic function with 1 method)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function make_reverse(ex)\n",
    "    # a = b op c\n",
    "    \n",
    "    var1 = ex.args[1]\n",
    "    op = ex.args[2].args[1]\n",
    "    var2, var3 = ex.args[2].args[2:3]\n",
    "    \n",
    "    reverse_op = reverse_ops[op]\n",
    "    \n",
    "    return :( ($var1, $var2, $var3) = $reverse_op($var1, $var2, $var3) )\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(z = x + y)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(z = x+y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((z,x,y) = reverse_add(z,x,y))"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_reverse(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MacroTools.jl \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The extraction of the variables was pretty ugly. There is a solution to this: the `MacroTools.jl` package."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using MacroTools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(z = x + y)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(:+,:z,:x,:y)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(op, var1, var2, var3) = @match ex begin\n",
    "    (var1_ = op_(var2_, var3_)) => (op, var1, var2, var3)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Finish writing the backwards pass."
   ]
  }
 ],
 "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
}