I recently completed all 25 days of Advent of Code 2017, an annual
series of recreational programming puzzles. Each day describes a programming
puzzle and illustrates a handful of simple examples of the problem. The puzzle
then requires the participant to solve a much, much larger form of the problem.
For five or so of the puzzles, I used nonstandard evaluation to implement my
solution. As I previously wrote, nonstandard evaluation is a way of
bottling up magic spells (lines of R code) and changing how or where they are
cast (evaluated). I chose to use special evaluation not because it was the
easiest or most obvious solution but because I wanted to develop my skills with
computing on the language. In this post, I work through one of the examples
where I used nonstandard evaluation to write an interpreter for a simple machine.
Puzzle description
Day 8 requires us to simulate the state of a register machine as it receives a series of instructions.
Each instruction consists of several parts: the register to modify, whether to
increase or decrease that register’s value, the amount by which to increase or
decrease it, and a condition. If the condition fails, skip the instruction
without modifying the register. The registers all start at 0. The instructions
look like this:
b inc 5 if a __ 1
a inc 1 if b __ 5
c dec -10 if a __= 1
c inc -20 if c == 10
[…]
You might also encounter 1
b 1) b + 5 else b
# a inc 1 if b __ 5
a [1] 1000
head(full_input)
#__ [1] &quot;kd dec -37 if gm 3&quot; #__ [5] &quot;f dec -385 if msg __ -3&quot; &quot;kd dec -456 if ic |=||=| 1&quot;
stringr::str_match(text, re)
#__ [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#__ [1,] &quot;b inc 5 if a __ 1&quot; &quot;b&quot; &quot;inc&quot; &quot;5&quot; &quot;a __ 1&quot; &quot;a&quot; &quot;__&quot; &quot;1&quot;
# Column 5 matches the subgroups in columns 6, 7 and 8 as a single # group because of the extra grouping parentheses after the `if`.
We can package this step into a function that takes an instruction’s
text and returns a list with the labelled parts of that instruction.
parse_instruction % stringr::str_match(re) %__% as.list() %__% setNames(c(&quot;instruction&quot;, &quot;target&quot;, &quot;verb&quot;, &quot;num1&quot;,
&quot;cond&quot;, &quot;s1&quot;, &quot;op&quot;, &quot;num2&quot;))
}
str(parse_instruction(text))
#__ List of 8
#__ $ instruction: chr &quot;b inc 5 if a __ 1&quot;
#__ $ target : chr &quot;b&quot;
#__ $ verb : chr &quot;inc&quot;
#__ $ num1 : chr &quot;5&quot;
#__ $ cond : chr &quot;a __ 1&quot;
#__ $ s1 : chr &quot;a&quot;
#__ $ op : chr &quot;__&quot;
#__ $ num2 : chr &quot;1&quot;
Creating R code
Next, we need to convert some strings into R code. We can do this with rlang::parse_expr(). It takes a string and creates an R expression, something I’ve described as a kind of bottled up magic spell: An expression captures magic words (code) allow us to manipulate or cast (evaluate)
them.
code print(&quot;hello&quot;)
code if (a __ 1) b + 5 else b
The format of the instructions is relatively straightforward. We can fill
in a template with the parts of the parsed line. Because inc/dec are just
addition and subtraction, we replace them with the appropriate math operations.
create_r_instruction if (a __ 1) b + 5 else b
Create the register machine
We have to figure out where we want to evaluate the generated R code. We
create a register object to hold the values. The object will just be a list()
with some extra metadata. This object will be the location where the R code is evaluated.
create_register_machine List of 3
#__ $ a : num 0
#__ $ b : num 0
#__ $ .metadata: list()
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
Evaluating code inside of the machine
So far, we have:
A way to analyze register instructions and convert them into R code
An object that holds register values
Now, we need to evaluate an expression inside of the register. We will usetidy evaluation; the function eval_tidy() lets us evaluate an
R expression inside of a data object.
r_code
#__ if (a __ 1) b + 5 else b
# b + 5
r [1] 12
# just b
r [1] 7
Now, we need to actually do something. We need to update the register machine
using the value from the evaluated instruction. Otherwise, the machine will just
read expressions and forget everything it’s read.
To update the machine, we have to determine the register to update. Fortunately,
our generated code always ends with an else branch that has the target register.
r_code
#__ if (a __ 1) b + 5 else b
If we can pull out that symbol after the else, we will have the name of
register to update in the machine. Because the code is so formulaic, we can just
extract the symbol directly using the code’s abstract syntax tree (AST). pryr::call_tree() shows the AST for an expression.
pryr::call_tree(r_code)
#__ \- ()
#__ \- `if
#__ \- ()
#__ \- `__
#__ \- `a
#__ \- 1
#__ \- ()
#__ \- `+
#__ \- `b
#__ \- 5
#__ \- `b
We can extract elements from the tree like elements in a list by selecting indices.
# The numbers match one of the slashs at the first level of indentation
r_code[[1]]
#__ `if`
r_code[[2]]
#__ a __ 1
# We can crawl down subtrees too
r_code[[2]][[2]]
#__ a
# But what we want is the last branch from the `if` level
r_code[[4]]
#__ b
If we convert the symbol into a string, we can look it up in the register using
the usual list lookup syntax.
r $ a : num 4
#__ $ b : num 12
#__ $ .metadata: list()
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
Let’s wrap these steps into a function.
eval_instruction $ a : num 2
#__ $ b : num 5
#__ $ .metadata: list()
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
create_register_machine(a = 2, b = 0) %__% # For quick testing, we pass in quoted expressions
eval_instruction(quote(if (a __ 1) b - 100 else b)) %__% # Should not run
eval_instruction(quote(if (a % # Should run
eval_instruction(quote(if (a __ 1) a + 10 else a))
#__ List of 3
#__ $ a : num 12
#__ $ b : num -100
#__ $ .metadata: list()
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
Time for some extra nonstandard evaluation
The code so far only works if the machine already has registers that match the
registers in an instruction. Otherwise, we raise an error.
create_register_machine() %__% eval_instruction(quote(if (a __ 1) b - 100 else b))
#__ Error in overscope_eval_next(overscope, expr): object 'a' not found
# &quot;Overscope&quot; is the tidy evaluation term for the data context, so failing to
# find the name in the data is failing to find the name in the overscope.
To solve the problem, we could study the 1,000 lines of input beforehand,
extract the register names, initialize them to 0 and then evaluate the
instructions.1 Or… or… we could procrastinate and only
initialize a register name to 0 when the machine encounters a name it doesn’t
recognize. If, for some reason, our machine received instructions one at a time, like over a network connection, then the procrastinated approach
seems even more reasonable.
This latter strategy will involve some very nonstandard evaluation. I
emphasize the “very” because we are changing one of the fundamental rules of R
evaluation :smiling_imp:. R throws an error if you ask it to evaluate the name
of a variable that doesn’t exist. But here we are going to detect those missing
variables and set them to 0 before they get evaluated.
To find the brand-new register names, we can inspect the call tree and find the
names of the registers. We already know where the target is. The other place where names show up is in the condition of the if statement.
pryr::call_tree(r_code)
#__ \- ()
#__ \- `if
#__ \- ()
#__ \- `__
#__ \- `a
#__ \- 1
#__ \- ()
#__ \- `+
#__ \- `b
#__ \- 5
#__ \- `b
extract_register_names List of 2
#__ $ target : chr &quot;b&quot;
#__ $ registers: chr [1:2] &quot;b&quot; &quot;a&quot;
# Just returns unique names
extract_register_names(quote(if (b __ 1) b - 100 else b)) %__% str()
#__ List of 2
#__ $ target : chr &quot;b&quot;
#__ $ registers: chr &quot;b&quot;
We can define a helper function which checks for missing names—names that
yield NULL values when we try to retrieve them—and initializes them to 0.
initialize_new_registers $ a : num 4
#__ $ b : num 12
#__ $ .metadata: list()
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
initialize_new_registers(r, c(&quot;a&quot;, &quot;b&quot;, &quot;w&quot;, &quot;a&quot;, &quot;s&quot;, &quot;j&quot;))
#__ List of 6
#__ $ a : num 4
#__ $ b : num 12
#__ $ .metadata: list()
#__ $ w : num 0
#__ $ s : num 0
#__ $ j : num 0
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
Finally, we update our evaluation function to do this step automatically. I’m
also going to add some code to record the value of the maximum register whenever
an instruction is evaluated because, ummm, that’s the whole point of puzzle.
eval_instruction $ d : num 0
#__ $ c : num 10
#__ $ a : num 0
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
Now, for the moment of truth… Let’s process all 1,000 instructions.
r % create_r_instruction()
r List of 27
#__ $ .metadata:List of 1
#__ ..$ max: num 4832
#__ $ kd : num -2334
#__ $ gm : num -4239
#__ $ x : num -345
#__ $ kjn : num -1813
#__ $ ey : num 209
#__ $ n : num -764
#__ $ t : num 2997
#__ $ f : num 4468
#__ $ msg : num -3906
#__ $ ic : num -263
#__ $ zv : num -599
#__ $ gub : num 2025
#__ $ yp : num -2530
#__ $ lyr : num -2065
#__ $ j : num 3619
#__ $ e : num -4230
#__ $ riz : num 863
#__ $ lzd : num 4832
#__ $ ucy : num -3947
#__ $ i : num 3448
#__ $ omz : num -3365
#__ $ djq : num 392
#__ $ bxy : num 1574
#__ $ tj : num 1278
#__ $ y : num 1521
#__ $ m : num 2571
#__ - attr(*, &quot;class&quot;)= chr [1:2] &quot;register_machine&quot; &quot;list&quot;
:star: Ta-da! The maximum register value is 4,832. Problem solved!
And then the rules change
Advent of Code problems come in two parts, and we don’t learn the question
behind Part 2 until we complete Part 1. In this case, after submitting our
solution for Part 1, we receive the following requirement:
To be safe, the CPU also needs to know the highest value held in any
register during this process so that it can decide how much memory to allocate
to these operations.
Accounting for this twist requires a small change to the evaluation code. We add another metadata variable to track the highest value ever stored in a register.
eval_instruction