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

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many new users find Julia's Lisp-style macros confusing. For people without experience using syntactic macros in another language, Julia's macros present several challenges: macros introduce multiple pieces of unfamiliar syntax (i.e. `@` and `$`); macros differ from functions in fairly subtle ways that make it unclear when to use which; and authoring macros requires a fairly deep understanding of Julia's syntax because Julia has a large range of expressions that can occur in normal code.\n",
    "\n",
    "The goal of this series of notebooks is to help users overcome those challenges so they can learn to write macros with confidence. By the end of the series, you should understand macros well enough to implement a DSL in Julia for yourself. In this first notebook, we won't implement any DSL's and will instead focus on writing simpler macros. But the second notebook will entirely focus on issues that arise in developing a DSL using macros.\n",
    "\n",
    "To avoid unhelpful redundancies with existing documentation, this document assumes that you've already read the [entire manual section on metaprogramming](https://docs.julialang.org/en/v1/manual/metaprogramming/). Although I assume you've read that section of the language manual, I also assume that you're reading this document because:\n",
    "\n",
    "1. You might not have fully understood some of the subtler points in the manual. For example, you might not be entirely sure that you understand how `$`, `esc` or `QuoteNode` work.\n",
    "2. You're not entirely comfortable writing macros on your own.\n",
    "\n",
    "To improve your understanding of the core concepts relevant to writing macros, we're going to proceed as follows:\n",
    "\n",
    "1. We'll review Julia's representations of quoted code and consider the kinds of expressions that you'll need to be able to reason about to produce reliable macros that work correctly across a broad range of inputs.\n",
    "2. We'll learn to distinguish quotation from quasiquotation to help us understand how `$` works in macros.\n",
    "3. We'll talk about writing functions over expressions, which should be used to make macro definitions easier to read.\n",
    "4. We'll discuss what hygiene means and understand how `esc` lets you tell Julia to not enforce hygiene.\n",
    "5. We'll contrast the order in which macros are expanded with the order in which functions are evaluated.\n",
    "6. We'll discuss when to use macros instead of functions.\n",
    "\n",
    "The approach we'll take is driven by focusing on examples that illustrate the core issues. Every time you see a snippet of code, think about what it does before executing it. Then execute it to check whether your understanding was correct. Keep thinking and checking until your own predictions about what should happen coincide with what happens.\n",
    "\n",
    "In addition to many executable examples, there are also several exercises in this notebook. You should try to complete as many of them as possible to solidify your grasp on the core concepts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a Macro?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At their core, macros are functions that:\n",
    "\n",
    "* Take in one or more pieces of quoted code as their arguments.\n",
    "* Produce one piece of quoted code as their return value.\n",
    "* Are evaluated exactly once at compile time. After evaluating the macro this one time, the returned quoted code is substituted in the calling code in place of the original macro call. Once this substitution occurs, there is no trace left behind of the macro's presence. (*Footnote: A few very exceptional macros generate source code that could never be written without using macros. You should assume that you will not be writing any such macros in the near future.*)\n",
    "\n",
    "Most of what makes writing macros challenging stems from a few subtleties related to these three issues. It is especially easy to be confused about:\n",
    "\n",
    "* How macro arguments are quoted before macro execution begins.\n",
    "* How the quoted code that your macro produces is munged/postprocessed by Julia to prevent accidentally creating or mutating any local variables.\n",
    "\n",
    "We'll therefore start by focusing on those two topics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quoting Code Produces More Types than Just Expr Objects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As noted earlier, a macro is, at core, a function that takes in quoted code as its arguments. As such, we need to be sure we understand how quoted code behaves in Julia. This is a little messy for two reasons:\n",
    "\n",
    "* Not every argument to a macro will be an instance of Julia's `Expr` type. Quoted code can consist of several types of values beyond the `Expr` type.\n",
    "* The way in which code is quoted before passing it as an argument to a macro is different than what can be achieved using the quotation mechanisms that are available for use outside of macros.\n",
    "\n",
    "To understand both issues, let's start by looking at a few examples of quoting code using the `:()` and `quote` operators that are built into Julia."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(:x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(1 + x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quote\n",
    "    1 + x\n",
    "    x + 1\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(:(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(:(:x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(:(1 + x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(\n",
    "    quote\n",
    "        1 + x\n",
    "        x + 1\n",
    "    end\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All of these snippets are examples of what I'll call quoted code going forward. But only `:(1 + x)` and the `quote` block produce objects of type `Expr`. The wide range of types produced by quoting code confuses many people who start metaprogramming in Julia because they assume that any piece of quoted code will be some kind of `Expr`. Other languages often wrap all quoted code to ensure that everything is some kind of `Expr` object. **Julia does not wrap all values in some kind of `Expr` object and so macros need to be ready to process non-`Expr` inputs.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Many Kinds of Expr Objects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to the diversity of types that be produced by quoting code, metaprogramming in Julia requires that you become familiar with the internal structure of the many kinds of `Expr` objects that exist. Unlike Lisp, in which there exists a small number of special forms, Julia's rich syntax generates many kinds of `Expr` objects and you unfortunately need to have some strategy for dealing with this complexity -- even if your strategy is just ignoring most kinds of expressions in the macros you write.\n",
    "\n",
    "To see the range of internal structures that occur in `Expr` objects, let's look at a few examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dump(:(1 + x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dump(:(sin(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dump(:(x == y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dump(\n",
    "    quote\n",
    "        let x = 1\n",
    "            x + 1\n",
    "        end\n",
    "    end\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This last example also illustrates that quoted blocks of multiple lines of code include `LineNumberNode` objects in addition to `Expr` objects that refer to the code itself. These `LineNumberNode` are important for error reporting, but are mostly a source of confusion when you first starting authoring macros. If you want to simplify things by ignoring these nodes, you can install the [MacroTools.jl](https://github.com/MikeInnes/MacroTools.jl) package and use the [`rmlines` function](https://mikeinnes.github.io/MacroTools.jl/stable/utilities/#MacroTools.rmlines), although I have the impression that `rmlines` doesn't apply itself recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import MacroTools: rmlines\n",
    "\n",
    "dump(\n",
    "    rmlines(\n",
    "        quote\n",
    "            let x = 1\n",
    "                x + 1\n",
    "            end\n",
    "        end\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To really master macros, it's good to have a basic sense of what kinds of `Expr` objects could come up. See [this gist](https://gist.github.com/johnmyleswhite/17d8e897e995874ce04f2fc102b59991) for the kinds of `Expr` objects that occur in Julia's base code along with their relative frequencies. See [ast.scm in Julia's parser](https://github.com/JuliaLang/julia/blob/a645d7f256c2d1634869fa927c90d4e282ff0a47/src/ast.scm#L75) for what seems to be an exhaustive list of what the parser understands."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to quoting code and examining the results, it's also valuable to spend some time constructing a few expressions manually and check that match the expressions you think they do. Some examples to get you started:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(x - y) == Expr(:call, :-, :x, :y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(sin(x)) == Expr(:call, :sin, :x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    ":(1 + sin(x)) == Expr(:call, :+, 1, Expr(:call, :sin, :x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "Now that we've discussed our first topic, it's time for you to do some exercises. To make sure you're familiar with Julia's `Expr` objects, try the following:\n",
    "\n",
    "1. Write out a `for` loop and quote it using `quote`, then print it out using `dump` to inspect its structure as an `Expr` object.\n",
    "2. Write out a `if` expression and inspect it.\n",
    "3. Write out an anonymous function (e.g. `x -> x + 1`) and inspect it.\n",
    "4. Take the code from [David Sanders for printing AST's as graphs](https://gist.github.com/dpsanders/5cc1acff2471d27bc583916e00d43387) and try it on a few expressions.\n",
    "5. Install the MacroTools package and read about the pattern matching macro called [`@capture`](https://mikeinnes.github.io/MacroTools.jl/stable/pattern-matching/) that can help you avoid dealing with the internal structure of `Expr` objects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quotation vs Quasiquotation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We mentioned earlier that Julia's built-in syntax for quotation (i.e. `:()` and `quote`) actually perform quotation in a different way than macros quote their arguments. In particular, macros employ true quotation whereas both `:()` and `quote` perform [quasiquotation](https://courses.cs.washington.edu/courses/cse341/04wi/lectures/14-scheme-quote.html). The distinction between these two kinds of quotation has to do with how [interpolation/splicing](https://docs.julialang.org/en/v1/manual/metaprogramming/#man-expression-interpolation-1) works.\n",
    "\n",
    "In quasiquotation, the unary `$` unary operator allows you to substitute a value inside of a quoted expression. In true quotation, you just see a call to the `$` unary operator without any interpolation.\n",
    "\n",
    "Let's see this in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(1 + x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(1 + $x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let y = :x\n",
    "    :(1 + y), :(1 + $y)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In contrast to the behavior of `:()`, true quotation would not perform interpolation where unary `$` occurs. Instead, we would capture the syntax that describes interpolation and produce something like the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(\n",
    "    :(1 + $x),                        # Quasiquotation\n",
    "    Expr(:call, :+, 1, Expr(:$, :x)), # True quotation\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, Julia does not provide built-in syntax for this operation, which is why we had to write out an `Expr` object by hand. But we can write a macro to perform true quotation. This will be our first macro, so let's get excited. Before we write our macro, we need to get familiar with `QuoteNode`, which is a way of representing something that's been truly quoted. To see why it exists at all, consider the following two examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":x, typeof(:(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ":(:x), typeof(:(:x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When applied to symbols, this `QuoteNode` wrapper might seem useless since it's unclear how wrapping a `Symbol` in a `QuoteNode` helps. But `QuoteNode` has clear value when it's used inside a macro to indicate that something should stay quoted even after the macro finishes executing. To see what this means, note how the following macro behaves:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro true_quote(e)\n",
    "    QuoteNode(e)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let y = :x\n",
    "    (\n",
    "        @true_quote(1 + $y),\n",
    "        :(1 + $y),\n",
    "    )\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why have we made such a big deal about all of this? We've focused on this seemingly obscure issue because Julia macros apply true quotation to their arguments before evaluating the macro body. They do not apply quasiquotation because interpolation/splicing is a fundamentally runtime concept that involves capturing runtime values.\n",
    "\n",
    "An important implication of this is that **you cannot write macros that use standard interpolation/splicing**. If you want that behavior, you need to take steps inside of your macro to simulate it. When you see macros like `@btime` from BenchmarkTools.jl encourage using `$`, [they are doing this simulation](https://discourse.julialang.org/t/interpolation-in-macro-calls/25530).\n",
    "\n",
    "On the flip side, the fact that macros apply true quotation rather than quasiquotation means that you can assign non-standard semantics to the interpolation/splice operator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "1. Read the code in [BenchmarkTools.jl](https://github.com/JuliaCI/BenchmarkTools.jl) to see how they make use of the splicing operator syntax to capture local variables without incurring performance penalties that would distort benchmarking results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions over Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Returning again to our earlier definition, a macro is essentially a function that maps input expressions into an output expression at compile time. Because macros behave like functions, it's often easier to write macros in terms of functions over expressions. In large part, this simplifies things because these functions behave the same way whether you're inside of a macro or not in one.\n",
    "\n",
    "To build up skills writing such functions, we're going to write a few now. We'll start by writing a function to count the number of arguments in an `Expr` object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nargs(e::Expr) = length(e.args)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nargs(:(1 + 2 + 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you're surprised by this result, use `dump` to look at the expression and count the arguments by hand. You'll see there's an argument there you might not be thinking about."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's do something a bit deeper and write a function that computes the maximum number of arguments in an expression recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maxargs(x::Any) = 0\n",
    "maxargs(e::Expr) = max(nargs(e), maximum(map(maxargs, e.args)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = quote\n",
    "    z = 1 + log(x + y)\n",
    "    exp(z)\n",
    "end\n",
    "\n",
    "maxargs(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notee that we had to define both `maxargs(x::Any)` and `maxargs(e::Expr)` here. Without the definition for `maxargs(x::Any)`, the recursive definition we've used would throw a missing method error whenever any of `e.args` is not an `Expr` object.\n",
    "\n",
    "In general, the diversity of kinds of quoted code means that we need to define functions over expressions and also over other types that might occur. Many functions over expressions will need to perform recursion over the arguments to an expression; to make this work, any functions we call need to be defined over `Expr` and also more broadly. I often default to using `Any` for the broader case and letting Julia's specificity rules apply the appropriate method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "Getting good at writing macros is fairly simple once you're good at writing functions over quoted code. So here's some exercises to practice that more foundational skill before you start writing macros:\n",
    "\n",
    "* Write a function, `symbols(e)`, that returns a `Set{Symbol}` containing all of the symbols in an expression. Remember that this requires descending the entire expression tree recursively.\n",
    "* Write a function, `free_vars(e)`, that returns a `Set{Symbol}` containing all of the symbols that are unbound in an anonymous function like `x -> x + y`. The output in that case should contain `:+` and `:y` because function names are themselves symbols. As a hint, try using the `symbols` function from the previous exercise.\n",
    "* Write a function, `function_names(e)`, that returns all of the symbols in an anonymous function definition that must refer to something callable because they are called in the expression. For example, `x -> sin(x)` should return something containing `:sin`. But note that `x -> Float64(x)` should return `Float64`, so the results of this function aren't necessarily object whose type is a function -- you're just finding symbols bound to callables. \n",
    "* Write a function, `math_eval(e)`, that evaluates a purely mathematical expression like `1 + sin(2.0)` and returns the result as a `Float64` value. Do not just call `eval`; walk the expression manually and call out to `+`, `*`, etc. manually."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Once you've written a few functions over `Expr` objects, it will be clear that a repeated pattern is recursively descending an AST while performing some action repeatedly. The MacroTools package captures this pattern in two functions: [prewalk](https://mikeinnes.github.io/MacroTools.jl/stable/pattern-matching/#Expression-Walking-1) and [postwalk](https://mikeinnes.github.io/MacroTools.jl/stable/pattern-matching/#Expression-Walking-1).**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Simplified Model of Macro Expansion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've discussed a few of the main issues that arise in writing macros, let's walk through a simplified model of how macros are expanded/executed.\n",
    "\n",
    "1. Treat all of the macro arguments as code and quote that code using true quotation rather than quasiquotation.\n",
    "2. Evaluate the macro body just like it was a normal function body, but (a) require that the output be quoted/quotable code and (b) execute this function body exactly once.\n",
    "3. Take the output quoted code and run a hygiene-enforcing pass on it. We'll define hygiene in the next section.\n",
    "4. Insert the hygiene-enforced quoted code in place of the macro call. This happens **exactly once** at compile time; once that time has passed, it is **impossible** to distinguish the result from code written without using a macro unless the macro generates code that could never be written without using macros."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make this last point clear, consider the following macro that might surprise a user:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro bad_macro()\n",
    "    x = rand()\n",
    "    :($x)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in 1:10\n",
    "    println((i, @bad_macro()))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why does `@bad_macro` have this behavior? Use `@macroexpand(@bad_macro())` to see for yourself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What's Hygiene?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The one core macro concept we've mentioned so far without explanation is hygiene. Let's try to understand hygiene now. Hygiene is a slightly tricky topic, so you'll likely want to reread this section a few times until you're sure you understand it.\n",
    "\n",
    "The problem of hygiene is this: if you're automatically generating code, it's possible that you will introduce variable names in your generated code that will clash with existing variable names in the scope in which a macro is called. These clashes might cause your generated code to read from or write to variables that you should not interacting with. **A macro is hygienic when it does not interact with existing variables; it is non-hygienic when it does.**\n",
    "\n",
    "Because you don't know (and can't know) which variables will be in scope when your macro is called, there is a non-trivial problem to be solved here. Julia's approach to solving this hygiene problem is too automatically enforce hygiene, but offer macro authors a mechanism for writing non-hygienic macros that intentionally clash with existing variables.\n",
    "\n",
    "To understand these issues, we're intentionally going to write an incorrect macro to develop an intuition for the problems that arise. Our macro is intended to be non-hygienic and to perform assign in the calling scope, but it will succeed because the Julia hygiene-enforcing pass will change our generated code before substituting it in place of our macro's call site."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro assign(name, e)\n",
    "    Expr(:(=), name, e)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@assign(z, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What went wrong? And why did the assignment expression produce a value even though the assignment seems to have not worked as we intended rather than throw an error?\n",
    "\n",
    "To debug these kinds of things, it's best to use the `@macroexpand` macro to see what the `@assign` macro is being expanded to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@macroexpand(@assign(z, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What's this strange variable name? It's the result of Julia's hygiene-enforcing pass, which is intended to prevent us from overwriting existing variables during macro expansion. This pass usually makes our macros safer, but it is also a source of confusion because it introduces a gap between the expressions we generate and the expressions that end up in the resulting source code.\n",
    "\n",
    "In particular, we generated the following expression when our macro executed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let name = :z, e = :(1)\n",
    "    Expr(:(=), name, e)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But the expression that is generated as the result of executing our `@assign` macro had hygiene enforced automatically before substituting it into the calling code. So Julia effectively wrote our expression as follows using the `gensym` function, which generates a new variable name that is guaranteed to not clash with any existing variable names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let name = :z, e = :(1)\n",
    "    Expr(:(=), gensym(name), e)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to prevent the hygiene-enforcing pass from changing the expression we generate, we need to use `esc` to wrap the expression in a special escape expression that tells the hygiene system to pass through the results without editing. Think of `esc` as the special all access pass you see staff use at airports that lets them skip through security screeening without undergoing a full security check. Arguably a more clear, but much longer, name for `esc` would be `no_hygiene`.\n",
    "\n",
    "Let's see what `esc` does outside of a macro and how it works to prevent the hygiene post-processing step from managling our macro's output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "esc(:x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "esc(:(1 + x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro assign(name, e)\n",
    "    Expr(:(=), esc(name), e)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@assign(z, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we can apply this escaping at many levels:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro assign(name, e)\n",
    "    esc(Expr(:(=), name, e))\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@assign(z, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, it's wise to apply the escaping mechanism to the smallest expression that requires escaping because the hygiene-enforcement mechanism is often useful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Macro Expansion Order vs Function Evaluation Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One final issue we'll discuss is the order in which macros are evaluated. To see this directly, let's consider these two macros that we'll compose:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "macro foo(e)\n",
    "    println(\"In foo\")\n",
    "    e\n",
    "end\n",
    "\n",
    "macro bar(e)\n",
    "    println(\"In bar\")\n",
    "    e\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@foo(@bar(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Contrast this with how functions are evaluated:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function foo(e)\n",
    "    println(\"In foo\")\n",
    "    e\n",
    "end\n",
    "\n",
    "function bar(e)\n",
    "    println(\"In bar\")\n",
    "    e\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "foo(bar(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I assure you that this issue will trip you up at some point if you rely on your intuitions from calling functions, so it's good to have it pointed out to you."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## When to Use Macros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we've noted repeatedly, macros are similar to functions in many ways. In general, you should use functions instead of macros whenever possible because they are easier to reason about and are more familiar to most Julia users.\n",
    "\n",
    "That said, the cases in which macros are required are outlined well in [Chapter 8 of Paul Graham's On Lisp](https://www.csee.umbc.edu/courses/undergraduate/331/resources/lisp/onLisp/08whenToUseMacros.pdf).\n",
    "\n",
    "In Julia, some broad classes of cases include:\n",
    "\n",
    "* You want to employ existing Julia syntax, but provide non-standard semantics that cannot be achieved through function overloading. Almost all DSL's fall under this category.\n",
    "* You want to provide a function that operates on expressions, but doesn't require the user to quote the expressions. Our `@true_quote` macro was a variant on this idea.\n",
    "* You want to force some computation to occur exactly once at compile-time. Our `@bac_macro` was a bad example of this.\n",
    "* You want to change the values bound to a variable in the caller's scope. Julia functions cannot do this, although they can mutate the contents of mutable values passed in to them as arguments. Our `@assign` macro was an example of this.\n",
    "* You want to write a function that does not evaluate all of its arguments eagerly. You'll write an example of this in the upcoming exercises.\n",
    "* You want to write a function that captures both an expression's value and the surface syntax in which it is written. This will come up in Part 2 of this series.\n",
    "\n",
    "So there are quite a few cases in which macros are useful. But it's worth remembering the limitations of macros as well:\n",
    "\n",
    "* Essentially every macro call gets translated into Julia code that does not make use of macros. The implication of this is that macros never allow you to express computations that you can't express without macros -- they are purely syntactic sugar. This makes them very different from concepts like structs, parametric types, etc. that are not immediately reducible to other existing language features. The few exceptions to this rule are macros that produce expressions as output that have no surface syntax in Julia. Our true quotation versus quasiquotation example is almost an example of this, except that there is surface syntax based on `Expr` constructors. The `@inbounds` macro in Julia is a better example in which the relevant `Expr` objects can be constructed, but could only be used in combination with `eval` to actually take effect and therefore cannot occur in normal Julia code (where normal is defined as not making use of `eval`). In general, you should assume you will write very few of these macros because they usually can't work without changes to the Julia compiler itself. As such, it is best to stick to the intuitive rule that **macros should be used to provide a more ergonomic solution to a problem than would be possible without them**.\n",
    "\n",
    "Some closing tips for writing macros:\n",
    "\n",
    "* Before you write a macro, write an example of the code you want to generate.\n",
    "* Do all of the important work in functions over expressions. This is especially important if you will hit hygiene issues because the macro will produce output that may surprise you, but the function will not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: A @loop Macro\n",
    "\n",
    "Write a `@loop` macro that translates:\n",
    "\n",
    "```\n",
    "@loop begin\n",
    "    [LOOP BODY]\n",
    "end\n",
    "```\n",
    "\n",
    "into:\n",
    "\n",
    "```\n",
    "while true\n",
    "    [LOOP BODY]\n",
    "end\n",
    "```\n",
    "\n",
    "This is a good example of how Julia's macros let you \"create new syntax\", but in a way that isn't as clean as first-class syntax because you have to employ a `begin` block. Once you've got something, think through the following design decision: should your macro throw an error if the loop body never contains a `break` expression that could end the infinite loop?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: An @and Macro\n",
    "\n",
    "Write a macro that behaves like the `&&` operator, which short-circuits evaluation and only evaluates the lefthand side if it evaluates to `false`. (This is the contrast with the `&` function, which allows evaluates both the lefthand and righthand sides.\n",
    "\n",
    "Your macro should translate something like:\n",
    "\n",
    "```\n",
    "@and(e1, e2)\n",
    "```\n",
    "\n",
    "into something like:\n",
    "\n",
    "```\n",
    "if !e1\n",
    "   false\n",
    "else\n",
    "   e2\n",
    "end\n",
    "```\n",
    "\n",
    "It's also valuable to convince yourself that you cannot write a function that behaves this way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Macros Generating Macro Calls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's possible for a macro to generate an expression that represents calling a macro. Use this ability to write an `@infinite_loop` macro that generates a call to itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@infinite_loop (macro with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macro infinite_loop()\n",
    "    Expr(:macrocall, esc(Symbol(\"@infinite_loop\")), LineNumberNode(0, nothing))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can verify this macro generates an infinite loop by running it:\n",
    "\n",
    "```\n",
    "@infinite_loop()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Three-Valued Logic Macro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia has a `missing` value that is meant to behave like the `NULL` value in SQL. In SQL, there is an extended version of Boolean logic called [three-valued logic](https://en.wikipedia.org/wiki/Three-valued_logic). To make this logic available in Julia is not possible without macros because the `&&` and `||` operators are not functions that can be overloaded to support three-valued logic. Instead, you'll need to write macro. It should take an expression like:\n",
    "\n",
    "```\n",
    "@tvl x && y || z\n",
    "```\n",
    "\n",
    "and generate something that computes the result using three-valued logic. This is quite challenging to do and you should expect this exercise will take you some time.\n",
    "\n",
    "To approach this, I suggest you implement helper macros for `@tvl_and` and `@tvl_or`. `@tvl_or` would generate something like the following:\n",
    "\n",
    "```\n",
    "let tmp1 = x\n",
    "    if !ismissing(tmp1)\n",
    "        if tmp1\n",
    "            true\n",
    "        else\n",
    "            tmp2 = y\n",
    "            if !ismissing(tmp2)\n",
    "                tmp2\n",
    "            else\n",
    "                missing\n",
    "            end\n",
    "        end\n",
    "    else\n",
    "        tmp2 = y\n",
    "        if !ismissing(tmp2)\n",
    "            if tmp2\n",
    "                true\n",
    "            else\n",
    "                tmp1\n",
    "            end\n",
    "        else\n",
    "            missing\n",
    "        end\n",
    "    end\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implementing just `@tvl_or` will be a good exercise in using `esc` and `$`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Topics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Getting really good at writing macros requires you to understand what information is available at macro expansion time and what information is missing. Explore the `__module__` and `__lineno__` arguments that implicitly passed to every macro to help you think about this issue. Investigate the `@isdefined` and `Base.@locals` macros as well.\n",
    "* Julia's string macros let you create custom string literals that can invoke arbitrary macros at compile time. Explore this topic by using `@macroexpand` to see how the `r\"x*\"` regex works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "* [Chapter 8 of Paul Graham's On Lisp](https://www.csee.umbc.edu/courses/undergraduate/331/resources/lisp/onLisp/08whenToUseMacros.pdf)\n",
    "* [Jeff Bezanson commeent on quotation versus quasiquotation at 51:00](https://www.youtube.com/watch?v=vfxS6_Sx1Pk&feature=youtu.be)\n",
    "* [Wikipedia on DSL's](https://en.wikipedia.org/wiki/Domain-specific_language)"
   ]
  }
 ],
 "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
}