Introduction to metaprogramming: "Code that creates code"

Julia has strong metaprogramming capabilities. What does this mean?

meta: something on a higher level

metaprogramming = "higher-level programming"

i.e. writing code (a program) to manipulate not data, but code (that itself manipulates data)

Motivating example: Interact.jl

Exercise 1

  1. Install the Interact.jl package.
  1. Run the following code
In [3]:
for i in 1:10
    j = i^2
    println("The square of $i is $(j)")
end
The square of 1 is 1
The square of 2 is 4
The square of 3 is 9
The square of 4 is 16
The square of 5 is 25
The square of 6 is 36
The square of 7 is 49
The square of 8 is 64
The square of 9 is 81
The square of 10 is 100
In [1]:
using Interact

@manipulate for i in 1:10
    j = i^2
    "The square of $i is $(j)"
end
Unable to load WebIO. Please make sure WebIO works for your Jupyter client.
┌ Warning: Accessing `scope.id` is deprecated, use `scopeid(scope)` instead.
│   caller = ip:0x0
└ @ Core :-1
Out[1]:
In [ ]:

You should see a slider appear with the label i. When you manipulate the slider, the caption should show the value of i and its square, and should update when you move the slider.

What happened here? A for loop iterates over its values. Somehow the @manipulate command, which is a macro, took the object "code for the for loop" and replaced it with "code for a slider with the same range"; in other words, @manipulate operated on code to produce some different code that did something useful -- it took in a program and replaced it by a different program.

We can see the result of the @manipulate by "expanding" the effect of the macro using @macroexpand. To make it easier to read, we will suppress some line information using the MacroTools package:

In [4]:
code = @macroexpand @manipulate for i in 1:10
    j = i^2
    "The square of $i is $j"
end;

using MacroTools
MacroTools.striplines(code)
Out[4]:
quote
    local #64#children = (Widgets.OrderedDict)(:i => (i = (Widgets.widget)(1:10, label="i")))
    local #65#output = begin
                #66###364 = ((i,)->begin
                            j = i ^ 2
                            "The square of $(i) is $(j)"
                        end)
                (Widgets.map)(#66###364, i)
            end
    local #67#layout = (Widgets.manipulatelayout)((Widgets.get_backend)())
    (Widgets.Widget){:manipulate}(#64#children, output=#65#output, layout=#67#layout)
end

We see that the for loop has been replaced by code for manipulating a widget. The information about the variable name i, the range 1:10 and and the code inside the for loop have been preserved, but they have been embedded in a certain way into a new piece of code.

In order to carry out a code transformation like this, Julia allows us to manipulate Julia code from within Julia: we need to be able to get inside a piece of Julia code and modify it, before that code reaches the Julia compiler.

Finally we need to see how to wrap the result up into a macro.

Expressions

In [6]:
i
Out[6]:
In [5]:
j = i^2
MethodError: no method matching ^(::Widget{:slider,Int64}, ::Int64)
Closest candidates are:
  ^(!Matched::Float16, ::Integer) at math.jl:795
  ^(!Matched::Missing, ::Integer) at missing.jl:124
  ^(!Matched::Missing, ::Number) at missing.jl:97
  ...

Stacktrace:
 [1] macro expansion at ./none:0 [inlined]
 [2] literal_pow(::typeof(^), ::Widget{:slider,Int64}, ::Val{2}) at ./none:0
 [3] top-level scope at In[5]:1

Let's start with just the part j = i^2. If we type this code into a fresh Julia session, we get the following error:

julia> j  = i^2
ERROR: UndefVarError: i not defined
Stacktrace:
 [1] top-level scope at none:0

since Julia is trying to evaluate the code using the values for the variables i and j, which are not defined.

[If instead we type this after running the above @manipulate command, i is interpreted as a slider and we get a different error.]

For metaprogramming purposes, we do not wish to evaluate the code; instead, we just want to treat the code as unevaluated symbolic expressions, which will gain meaning only later. Julia allows us to construct unevaluated pieces of code as follows:

In [7]:
quote 
    j = i^2
end
Out[7]:
quote
    #= In[7]:2 =#
    j = i ^ 2
end

or with the following shorthand syntax:

In [8]:
:(j = i^2)
Out[8]:
:(j = i ^ 2)

Exercise 2

  1. Define a variable code to be :(j = i^2).
  1. What type is the object code? Note that code is just a normal Julia variable, of a particular special type.
  1. Use the dump function to see what there is inside code. Remembering that code is just a particular kind of Julia object, use the Julia to play around interactively, seeing how you can extract pieces of the code object.
  1. How is the operation i^2 represented? What kind of object is that subpiece?
  1. Copy code into a variable code2. Modify this to replace the power 2 with a power 3. Make sure that the original code variable is not also modified.
  1. Copy code2 to a variable code3. Replace i with i + 1 in code3.
  1. Define a variable i with the value 4. Evaluate the different code expressions using the eval function and check the value of the variable j.
In [10]:
code = Meta.parse("j = i^2")
Out[10]:
:(j = i ^ 2)
In [11]:
typeof(code)
Out[11]:
Expr
In [13]:
dump(code)
Expr
  head: Symbol =
  args: Array{Any}((2,))
    1: Symbol j
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol ^
        2: Symbol i
        3: Int64 2
In [14]:
code.head
Out[14]:
:(=)
In [15]:
typeof(ans)
Out[15]:
Symbol
In [17]:
:+
Out[17]:
:+
In [19]:
typeof(ans)
Out[19]:
Symbol
In [20]:
+
Out[20]:
+ (generic function with 171 methods)
In [21]:
code.args
Out[21]:
2-element Array{Any,1}:
 :j      
 :(i ^ 2)
In [22]:
typeof(code.args)
Out[22]:
Array{Any,1}
In [23]:
code.args[1]
Out[23]:
:j
In [26]:
typeof(code.args[1])
Out[26]:
Symbol
In [24]:
code.args[2]
Out[24]:
:(i ^ 2)
In [25]:
typeof(code.args[2])
Out[25]:
Expr
In [29]:
code.args[2].head
Out[29]:
:call
In [30]:
code.args[2].args
Out[30]:
3-element Array{Any,1}:
  :^
  :i
 2  
In [31]:
code.args[2].args[3]
Out[31]:
2
In [32]:
code.args[2].args[3] = 3
Out[32]:
3
In [33]:
code
Out[33]:
:(j = i ^ 3)
In [35]:
code.args[2].args[2] = :(i + 1)
Out[35]:
:(i + 1)
In [36]:
code
Out[36]:
:(j = (i + 1) ^ 3)
In [37]:
dump(ans)
Expr
  head: Symbol =
  args: Array{Any}((2,))
    1: Symbol j
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol ^
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol +
            2: Symbol i
            3: Int64 1
        3: Int64 3

We have just taken a (very simple) program, represented by code, and produced two new programs, code2 and code3, which we ran using eval. This is the basis of all metaprogramming: taking in a piece of code, and modifying it to produce a new piece of code.

In [ ]:

Walking a syntax tree

In the previous exercise, we modified a single i to i + 1. But in general we might have a more complicated expression like i^2 + (i * (i - 3)) and we may wish to modify all of the is in the expression to (i+1)s or to ks to produce the new expression. The problem is that they may be buried arbitrarily deeply. We thus need to find a way of walking through the whole expression to examine each subpiece of it.

In [38]:
code = :( i^2 + (i * (i - 3)) )
Out[38]:
:(i ^ 2 + i * (i - 3))
In [39]:
dump(code)
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol +
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol ^
        2: Symbol i
        3: Int64 2
    3: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol *
        2: Symbol i
        3: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol -
            2: Symbol i
            3: Int64 3

Exercise 3

  1. Write a function walk! that takes an expression object and replaces all of the :xs by :zs.

    Hint: This function should be recursive: at some point it will need to call itself if it finds that a piece of the expression is itself an Expr.

  1. Make this function into a more general pattern matcher that looks for a given sub-expression and replaces it by another.
In [40]:
3 isa Expr
Out[40]:
false
In [41]:
3 isa Symbol
Out[41]:
false
In [42]:
3 isa Number
Out[42]:
true
In [43]:
:x isa Expr
Out[43]:
false
In [44]:
:x isa Symbol
Out[44]:
true
In [45]:
:(x + 1) isa Expr
Out[45]:
true
In [50]:
function walk!(ex::Expr)
    for arg in ex.args
        @show arg
        if arg == :x
            arg = :z
        end
        
        if arg isa Expr
            walk!(arg)
        end
    end
end
Out[50]:
walk! (generic function with 1 method)
In [51]:
ex = :(x*x + x)
Out[51]:
:(x * x + x)
In [52]:
walk!(ex)
arg = :+
arg = :(x * x)
arg = :*
arg = :x
arg = :x
arg = :x
In [49]:
ex
Out[49]:
:(x * x + x)
In [82]:
function walk!(ex::Expr)
    
    args = ex.args
    
    for i in 1:length(args)

        if args[i] == :x
            args[i] = :z
        end
        
        if args[i] isa Expr
            walk!(args[i])
        end
    end
    
    return ex
end
Out[82]:
walk! (generic function with 1 method)
In [62]:
walk!(ex)
In [64]:
ex
Out[64]:
:(z * z + z)
In [ ]:

Exercise 4

Julia by default uses standard 64-bit (or 32-bit) integers, which leads to surprising overflow behaviour, e.g.

In [76]:
2^32 * 2^31
Out[76]:
-9223372036854775808

No warning is given that there was an overflow in this calculation.

However, in Base there are checked operations, such as checked_mul, which do throw an exception on overflow:

In [65]:
Base.checked_mul(2^60, 2^60)
OverflowError: 1152921504606846976 *y overflowed for type Int64

Stacktrace:
 [1] throw_overflowerr_binaryop(::Symbol, ::Int64, ::Int64) at ./checked.jl:154
 [2] checked_mul(::Int64, ::Int64) at ./checked.jl:288
 [3] top-level scope at In[65]:1
  1. Write a function make_checked that replaces standard functions (-, +, *, /) in an expression by their corresponding checked counterparts.
In [66]:
code
Out[66]:
:(i ^ 2 + i * (i - 3))
In [67]:
ex = :(x + x * x)
Out[67]:
:(x + x * x)
In [68]:
eval(ex)
UndefVarError: x not defined

Stacktrace:
 [1] top-level scope at none:0
 [2] eval at ./boot.jl:328 [inlined]
 [3] eval(::Expr) at ./client.jl:404
 [4] top-level scope at In[68]:1
In [69]:
x = 3
Out[69]:
3
In [70]:
eval(ex)
Out[70]:
12
In [71]:
walk!(ex)
In [72]:
ex
Out[72]:
:(z + z * z)
In [73]:
eval(z)
UndefVarError: z not defined

Stacktrace:
 [1] top-level scope at In[73]:1
In [74]:
z = 5
Out[74]:
5
In [75]:
eval(z)
Out[75]:
5

Generating repetitive code

One common application of basic metaprogramming in Julia is generating repetitive code. For example, there are situations in which it's useful to wrap on object of one type into a user-defined type in order to modify its behaviour in some way.

e.g. Let's define a wrapper type MyFloat of Float64:

In [42]:
struct MyFloat
    x::Float64
end

We can generate objects of this type:

In [43]:
a = MyFloat(3)
b = MyFloat(4)
Out[43]:
MyFloat(4.0)

But arithmetic operations are not defined:

In [44]:
a + b
MethodError: no method matching +(::MyFloat, ::MyFloat)
Closest candidates are:
  +(::Any, ::Any, !Matched::Any, !Matched::Any...) at operators.jl:502

Stacktrace:
 [1] top-level scope at In[44]:1

We can define them in the natural way:

In [45]:
import Base: +, -, *, /

+(a::MyFloat, b::MyFloat) = a.x + b.x
-(a::MyFloat, b::MyFloat) = a.x - b.x
Out[45]:
- (generic function with 188 methods)

But this will quickly get dull, and we could easily make a mistake. As usual, whenever we are repeating something more than twice, we should try to automate it.

We have some code of the form

op(a::MyFloat, b::MyFloat) = op(a.x, b.x)

where op denotes the operator. Julia allows us to do this almost literally; we just need to substitute in the value of the variable op!

Exercise 5

  1. Let op be the symbol :+, which is an unevaluated version of the + operator.
  1. Let code be the expression corresponding to op(a::MyFloat, b::MyFloat) = op(a.x, b.x).
  1. Substitute the value of op by replacing op by $(op). Check that code contains the correct result.
  1. Evaluate the code in order to generate the new method. Check that the method works for objects of type MyFloat.
  1. We can replace the two steps "define code" and "evaluate code" by one step, @eval of the expression that defines code.
  1. Write a loop over the operations +, -, * and / to define them all for our wrapper type.

Finally we need to evaluate the code. The combination of eval and :(...) that we used above can be abbreviated to @eval:

Macros

Finally let's return to macros. Recall that macros begin with @ and behave like "super-functions", which take in a piece of code and replace it with another piece of code. In fact, the effect of a macro call will be to insert the new piece of code in place of the old code, which is consequently compiled by the Julia compiler.

Note that the user does not need to explicitly pass an Expression object; Julia turns the code that follows the macro call into an expression.

To see this, let's define the simplest macro:

In [89]:
macro simple(expr)
    @show expr, typeof(expr)
    nothing   # return nothing for the moment
end
Out[89]:
@simple (macro with 1 method)

and run it with the following simple code:

In [91]:
result = @simple yy = xx^2
(expr, typeof(expr)) = (:(yy = xx ^ 2), Expr)
In [92]:
result
In [86]:
macro walk!(expr)
    @show expr
    result = walk!(expr)
    @show result
    return result
end
Out[86]:
@walk! (macro with 1 method)
In [87]:
@walk! x + x
expr = :(x + x)
result = :(z + z)
Out[87]:
10
In [88]:
@macroexpand @walk! x + x
expr = :(x + x)
result = :(z + z)
Out[88]:
:(Main.z + Main.z)

We see that the Julia code that follows the macro call is passed to the macro, already having been parsed into an Expr object.

Exercise 6

  1. Define a macro @simple2 that returns the expression that was passed to it.
  1. What happens when you call @simple2 yy = xx^2?
  1. Define a variable xx with the value 3. Does the macro work now?
  1. Does the variable xx now exist?
  1. To see what's happening, use @macroexpand.
In [93]:
macro simple2(expr)
    return expr
end
Out[93]:
@simple2 (macro with 1 method)
In [94]:
@simple2 yy = xx^2
UndefVarError: xx not defined

Stacktrace:
 [1] top-level scope at In[94]:1
In [95]:
xx = 10
Out[95]:
10
In [96]:
@simple2 yy = xx^2
Out[96]:
100
In [97]:
yy
UndefVarError: yy not defined

Stacktrace:
 [1] top-level scope at In[97]:1
In [98]:
@macroexpand @simple2 yy = xx^2
Out[98]:
:(#79#yy = Main.xx ^ 2)

You should find that the variable yy does not now exist, even though it seems like it should, since the code yy = xx^2 was evaluated. However, macros by default do not "touch" variables in the context from where they are called, since this may have unintended consequences. We refer to macro hygiene (they do not "infect" code where they are not welcome).

Nonetheless, often we may wish them to modify variables in the context from which they are called, in which case we can "escape" from this hygiene using esc:

In [109]:
op = :+
Out[109]:
:+
In [110]:
code = :($op(x, y))
Out[110]:
:(x + y)
In [ ]:

In [103]:
macro simple3(expr)
    return :($(esc(expr)))
end
Out[103]:
@simple3 (macro with 1 method)
In [104]:
@simple3 yy = xx^2
Out[104]:
100
In [105]:
yy
Out[105]:
100
In [107]:
@macroexpand @simple3 yy = xx^2
Out[107]:
:(yy = xx ^ 2)

Note that once again the macro must return an expression.

Exercise 7

  1. Check that @simple3 does create a variable yy.
In [ ]:

When writing macros, it is common to treat the macro as simply a wrapper around a function that does the hard work of transforming one Expr into another`:

Exercise 8

  1. Write a macro @walk! that uses the function walk! defined above to replace terms in an expression. Apply it to yy = xx^2, replacing xx by xx + 1.
  1. Write a macro @checked that replaces all arithmetic operations with checked operations.