From Macros to DSLs in Julia - Part 2 - DSLs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building Simple DSL's"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you've worked through Part 1 of this tutorial, it's time to start putting your newly acquired knowledge to use by solving more interesting problems. To that end, we'll be writing substantially more complicated macros going forward. As macros get more complicated, they often start to resemble simple [domain-specific languages](https://en.wikipedia.org/wiki/Domain-specific_language), which I'll always refer to as DSL's going forward.\n",
    "\n",
    "Macros that operate on Julia expressions can be used to write [embedded DSL's](https://en.wikipedia.org/wiki/Domain-specific_language#External_and_Embedded_Domain_Specific_Languages) that provide alternative semantics for existing Julia syntax, even though these DSL's must still strictly conform to Julia's existing syntax rules. If you want to provide novel syntax that isn't present in Julia, you can do so by writing a macro that takes in one or more strings as inputs. Julia's [non-standard string literals](https://docs.julialang.org/en/v1/manual/metaprogramming/#Non-Standard-String-Literals-1) are examples of this approach that come with additional syntactic sugar to make them seem closely integrated into the rest of the language. This approach to custom syntax via macros that take in strings instead of AST's is closely related to [reader macros in Lisp](https://letoverlambda.com/index.cl/guest/chap4.html). We won't discuss string macros in depth here, although there's an exercise at the end that you can do to experiment with them.\n",
    "\n",
    "In what follows, you're going to implement several DSL's. To make it easier to handle the complexity of writing DSL's from scratch, we'll generally construct a sequence of increasingly complicated DSL's that are nested inside of each other. Adding complexity incrementality is a good way to make macro authoring tractable since handling the entirety of Julia's syntax by default can be overwhelming.\n",
    "\n",
    "Note that these DSL's are not formally specified because we won't spell out a formal grammar or specification. This is common practice for Julia DSL's, although it also accounts for many cases in which Julia DSL's have surprising edge cases that were not considered by the DSL creators. Because these DSL's are just regular macros, they conceivably could be passed arbitrarily complicated quoted code, but they often won't be capable of processing such code. Providing good error messages is one of the tricks to writing great macros, but we won't go into it in detail. The provided solutions to some of the exercises demonstrate a few approaches to producing usable error messages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Our First DSL: Graph Literals\n",
    "\n",
    "Programming languages typically offer literals for many of their primitive types; Julia offers literals integers (`1`), floating point numbers (`1.0`), strings (`\"foo\"`), symbols (`:foo`) and more. Using these literals can make code more readable; to see why you benefit from them, imagine a language that only had string literals and required you to write `1` as something like `parse(Int, \"1\")`. You would probably find this pretty tedious.\n",
    "\n",
    "Macros provide one mechanism for defining something like literals for more complex types. We're going to explore this topic by writing a macro that lets users write out graphs as macro calls. For example, we want something like:\n",
    "\n",
    "```\n",
    "@graph begin\n",
    "    1 -> 2\n",
    "    2 -> 3\n",
    "end\n",
    "```\n",
    "\n",
    "to expand to the following substantially more verbose graph constructor:\n",
    "\n",
    "\n",
    "```\n",
    "let edges = ((1, 2), (2, 3)), g = LightGraphs.SimpleDiGraph(3)\n",
    "    for e in edges\n",
    "        LightGraphs.add_edge!(g, e[1], e[2])\n",
    "    end\n",
    "    g\n",
    "end\n",
    "```\n",
    "\n",
    "We'll also want to support undirected graphs like the following:\n",
    "\n",
    "```\n",
    "@graph begin\n",
    "    1 - 2\n",
    "    2 - 3\n",
    "end\n",
    "```\n",
    "\n",
    "We won't support mixed graphs that contain both directed and undirected edges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation Stragegy\n",
    "\n",
    "To get started, we'll restrict our focus to directed graphs and then cycle back to support undirected graphs. The high-level approach will be:\n",
    "\n",
    "1. Assume we're being passed a block in which each expression is a directed edge. Anything else will be an error on the user's part, so we'll throw an error if it occurs.\n",
    "2. Given each of directed edge expressions, we'll transform it into a form that only contains information needed for the semantics of defining a graph. In our case, `:(1 -> 2)` will be transformed into the tuple `(1, 2)` assuming background information about the edge being directed.\n",
    "3. Given all of the edges represented as tuples, we'll generate the suggested graph constructor expression based on the specified edges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: Processing a Block\n",
    "\n",
    "We'll do the bare minimum needed to get something working and then suggest improvements in the exercises. To start, we'll write code to process a full graph as a block expression:\n",
    "\n",
    "1. We'll assert the passed in block really is a block.\n",
    "2. We'll output the edges and nodes as `Vector{NTuple{2, Int}}` and `Set{Int}` respectively.\n",
    "3. We'll just ignore line numbers.\n",
    "4. We'll assume the block only contains valid directed edge expressions.\n",
    "5. We'll extract the edge from the expression.\n",
    "6. We'll return the edges and nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "extract_graph (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function extract_graph(e::Expr)\n",
    "    @assert e.head == :block\n",
    "    edges = NTuple{2, Int}[]\n",
    "    nodes = Set{Int}()\n",
    "    for ex in e.args\n",
    "        if isa(ex, LineNumberNode)\n",
    "            continue\n",
    "        end\n",
    "        edge = extract_edge(ex)\n",
    "        push!(edges, edge)\n",
    "        push!(nodes, edge[1])\n",
    "        push!(nodes, edge[2])\n",
    "    end\n",
    "    edges, nodes\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2: Processing an Edge\n",
    "\n",
    "To make `extract_graph` work, we need to implement `extract_edge`. This is fairly simple code that mostly requires dealing with the specific format of `Expr` objects that represent anonymous functions. Because we need to make many assumptions, we'll include a lot of `@assert` calls that should be turned into proper error messages that users could use to fix their code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "extract_edge (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function extract_edge(e::Expr)\n",
    "    @assert e.head == :->\n",
    "    @assert isa(e.args[1], Integer)\n",
    "    e′ = e.args[2]\n",
    "    @assert e′.head == :block\n",
    "    @assert length(e′.args) == 2\n",
    "    @assert isa(e′.args[2], Integer)\n",
    "    (e.args[1], e′.args[2])\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test our code on a few cases to see that it can handle the simplest examples we can think of:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_edge(:(1 -> 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 3)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_edge(:(1 -> 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 1)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_edge(:(2 -> 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([(1, 2), (2, 3)], Set([2, 3, 1]))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_graph(:(\n",
    "    begin\n",
    "        1 -> 2\n",
    "        2 -> 3\n",
    "    end\n",
    "))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: Write the Macro\n",
    "\n",
    "Now that we have the core logic in place for transforming a block expression representing a graph into a condensed form, writing the `@graph` macro is very simple. To make the macro easier to read, we produce our final expression using quasiquotation splicing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@graph (macro with 1 method)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macro graph(e)\n",
    "    edges, nodes = extract_graph(e)\n",
    "    n = length(nodes)\n",
    "    quote\n",
    "        import LightGraphs\n",
    "        let edges = $edges, g = LightGraphs.SimpleDiGraph($n)\n",
    "            for e in edges\n",
    "                LightGraphs.add_edge!(g, e[1], e[2])\n",
    "            end\n",
    "            g\n",
    "        end\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can confirm that our macro works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3, 2} directed simple Int64 graph"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@graph begin\n",
    "    1 -> 2\n",
    "    2 -> 3\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "1. Extend the DSL to support multiple edges per line like the following:\n",
    "\n",
    "```\n",
    "1 -> 2 -> 3\n",
    "```\n",
    "\n",
    "2. Support writing edges in the other direction:\n",
    "\n",
    "```\n",
    "1 <- 2\n",
    "```\n",
    "\n",
    "3. Mix multiple edges per line with support for both left and right directed edges:\n",
    "\n",
    "```\n",
    "1 <- 2 -> 3\n",
    "```\n",
    "\n",
    "4. Suppport undirected graphs using `1 - 2` to represent an edge instead of `1 -> 2`.\n",
    "\n",
    "5. Think through the issues for and against allowing the macro to decide for itself whether the output graph is directed or undirected. Instead of allowing the macro to decide, do you want to use two distinct macros called `@graph` and `@digraph`? Does type stability matter for macros that act like literals? Why or why not?\n",
    "\n",
    "6. Ensure that your macro emits useful error information. At the least, provide error messages that describe which expression caused an error, what kind of error was encountered and what was expected to occur in that expression. Even better, add line numbers to improve reporting.\n",
    "\n",
    "7. Much more ambitious exercise: make `@graph` into a string macro that processes raw strings that you parse with a custom parser. Invent a piece of graph syntax that Julia's normal syntax doesn't support.\n",
    "\n",
    "8. Convince yourself `@graph` can't be a function unless you pass in strings. What are some of the reasons that something like the following wouldn't work?\n",
    "\n",
    "```\n",
    "graph(1 -> 2, 2 -> 3)\n",
    "```\n",
    "\n",
    "8. (Cont.) What problems would we hit if we tried this instead?\n",
    "\n",
    "```\n",
    "graph(1 => 2, 2 => 3)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Named Tuple Rand"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've built our first simple DSL, let's explore a richer space. In what follows, we'll build a DSL that lets users describe a probabilistic model using the notation found in probabistic programming languages (aka PPL's) like BUGS, JAGS, Stan or Turing. But, unlike a true PPL, we're only going to use this model specification to generate a single sample from the model, which we'll return as a named tuple.\n",
    "\n",
    "Just this simplified topic is very deep and we'll explore only a piece of it in what follows; there's essentially no limit to how rich the modeling language could be made if you decided to invest more time into it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1: Named Tuple RNG without Dependencies\n",
    "\n",
    "To get started write a macro `@rng` that takes in a simple model with no dependencies between variables and generates a named tuple. For example, the following model:\n",
    "\n",
    "```\n",
    "@rng begin\n",
    "    mu ~ Normal(0, 1)\n",
    "    sigma ~ Gamma(1, 1)\n",
    "end\n",
    "```\n",
    "\n",
    "should generate the following named tuple:\n",
    "\n",
    "```\n",
    "(\n",
    "    mu = rand(Distributions.Normal(0, 1)),\n",
    "    sigma = rand(Distributions.Gamma(1, 1)),\n",
    ")\n",
    "```\n",
    "\n",
    "Do this for yourself. The logic here is quite similar to the graph literals in the previous section. If you get stuck, consult the [solutions](https://github.com/johnmyleswhite/julia_tutorials/tree/master/solutions/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2: Named Tuple RNG with Dependencies\n",
    "\n",
    "Now that you have something simple working, let's introduce dependencies between variables. To make things simpler for now, you can assume that the model block is written in the order in which calls to `rand` must happen:\n",
    "\n",
    "```\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "x ~ Normal(mu, sigma)\n",
    "```\n",
    "\n",
    "Note that you'll need to deal with scoping issues here because named tuples can't refer to previous tuple elements (unlike keyword arguments)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3: Named Tuple RNG with Out-of-Order Dependencies\n",
    "\n",
    "Once you've finished Exercise 2, modify your code to support a block in which variables are defined in an arbitrary order, requiring you, the macro author, to topologically sort them before emitting calls to `rand`.\n",
    "\n",
    "```\n",
    "x ~ Normal(mu, sigma)\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4: Support Expressions as Distribution Parameters\n",
    "\n",
    "None of the examples so far passed in expressions as arguments to the distribution constructors. Add support for things like:\n",
    "\n",
    "```\n",
    "x ~ Normal(mu + 1, sigma)\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5: Introducing Branches\n",
    "\n",
    "Enrich your modeling language by support `if`/`else` expressions:\n",
    "\n",
    "```\n",
    "x ~ Bernoulli(0.5)\n",
    "if x == 1\n",
    "    y ~ Normal(+1, 1.0)\n",
    "else\n",
    "    y ~ Normal(-1, 1.0)\n",
    "end\n",
    "```\n",
    "\n",
    "Sometimes this can be done trivially using existing dependencies if the parameters of a distribution are arbitrary expressions (as in the following example), but this is not sufficient in the distribution itself varies across the branches of the `if`/`else` expression:\n",
    "\n",
    "```\n",
    "x ~ Bernoulli(0.5)\n",
    "y ~ Normal(+1 * x + -1 * (1 - x), 1.0)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6: Support Statically Bounded For Loops\n",
    "\n",
    "Further enrich your language by adding support for static for loops whose loop bounds are known at macro expansion time like the following example in which the bounds are statically known to be `1` and `10`:\n",
    "\n",
    "```\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "for i in 1:10\n",
    "    x[i] ~ Normal(mu, sigma)\n",
    "end\n",
    "```\n",
    "\n",
    "You should decide whether you want to generate elements of the tuple like `Symbol(\"x[1]\")` or whether `x` should be a vector. What are arguments for and against each approach?\n",
    "\n",
    "There's also an interesting question here about the kind of code you want to emit: do you want to emit code uses for loops? Or do you want to emit code in which each variable defined over the course of the loop generates its own expression? The latter is called [unrolling a loop](https://en.wikipedia.org/wiki/Loop_unrolling)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7: Support Dynamically Bounded For Loops\n",
    "\n",
    "Go a step further and support dynamic for loops whose bounds are **not** known at macro expansion time like the following in which the uppper loop bound is a variable:\n",
    "\n",
    "```\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "for i in 1:n\n",
    "    x[i] ~ Normal(mu, sigma)\n",
    "end\n",
    "```\n",
    "\n",
    "Because this computation depends on information that cannot be known at compile time, you need to produce a function of `n` that evaluates to a named tuple; this is introduces a breaking change relative to your previous work.\n",
    "\n",
    "Note that this kind of dynamic bounds completely rules out manual unrolling at macro compile time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 8: Non-IID Loops\n",
    "\n",
    "So far all of the loops we've considered (whether statically bound or dynamically bound) have not introduced dependencies between the output values generated by the loop. Extend your language (if necessary) to support dependencies like the following one:\n",
    "\n",
    "```\n",
    "mu ~ Normal(0, 1)\n",
    "sigma ~ Gamma(1, 1)\n",
    "x[1] ~ Normal(mu, sigma)\n",
    "for i in 2:n\n",
    "    x[i] ~ x[i - 1] + Normal(mu, sigma)\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More Ideas for Macros and DSL's to Implement\n",
    "\n",
    "If you're worked through these DSL's and want to work on more projects, here's a few to consider. Some of these are really just more complicated macros rather than DSL's.\n",
    "\n",
    "1. **Symbolic Differentiation**\n",
    "\n",
    "Write a macro that uses [Calculus.jl](https://github.com/JuliaMath/Calculus.jl) to perform symbolic differentiation on expressions to generate their derivatives. Your macro should look something like:\n",
    "\n",
    "```\n",
    "@derivative(x + sin(exp(x)))\n",
    "```\n",
    "\n",
    "and it should generate output like:\n",
    "\n",
    "```\n",
    "x -> 1 + cos(exp(x)) * exp(x)\n",
    "```\n",
    "\n",
    "2. **Embedded Lisp**\n",
    "\n",
    "As noted earlier, you can support novel syntax using string macros. Based on ideas [from Peter Norvig's blog](https://norvig.com/lispy.html), implement a basic version of Lispy using a Julia string macro:\n",
    "\n",
    "```\n",
    "lisp\"(+ 1 (* 2 3))\"\n",
    "```\n",
    "\n",
    "3. **Curve Plotting**\n",
    "\n",
    "Write a macro that plots a curve specified in terms of the assumed variable `x`. Make sure that you both make use of the expression as a function while also representing the expression incorrectly in the axis labels for your plot. For example, be sure the labels for these two calls produce different outputs even though they define the same functions:\n",
    "\n",
    "```\n",
    "@curve(sin(x + y), xlim = (-1, 1), ylim = (-1, 1))\n",
    "```\n",
    "\n",
    "```\n",
    "@curve(sin(y + x), xlim = (-1, 1), ylim = (-1, 1))\n",
    "```\n",
    "\n",
    "4. **Model Transformer DSL**\n",
    "\n",
    "One of the main uses of [non-standard evaluation](http://adv-r.had.co.nz/Computing-on-the-language.html) in the R programming language is to support [Wilkinson notation](https://www.jstor.org/stable/2346786?seq=1) for transforming tabular data into design matrices for modeling. Implement something like:\n",
    "\n",
    "```\n",
    "@transformer(z ~ 1 + x + factor(y))\n",
    "```\n",
    "\n",
    "This should generate a transformer object that, when applied to a DataFrame, would generate the appropriate matrix. If you're unfamiliar with linear models, you should probably skip this exercise as the modeling issues are much deeper than the macro authoring issues."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.4.1",
   "language": "julia",
   "name": "julia-1.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.4.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}