Metaprogramming and Currying

Along with what feels like half of the internet, I’m participating in Advent of Code this December. The problems/puzzles in this exercise are the kind of small programming exercise that I enjoy. Incidentally, many of these problems, especially the early ones, look very similar to interview questions I’ve been given over the years.

This year there have been many problems that require writing an interpreter for a simple language. My favorite of these has been day 16 which had you execute some “dance moves” that modify an array. One of the dance moves is “spin” which involves rotating the array by a constant. Another is “exchange X Y” where the elements in the array at X and Y change places. The moves themselves aren’t complicated. The parsing of the input file isn’t complicated either. The problem gets hard though when you are asked to execute the entire sequence of dance moves 999,999,999 times.

In my first solution, I was using regexes to parse the instructions every time I made a move. This was incredibly slow. My next thought was that I should parse the file once and just store the code that needed to be executed in each step. This put me in the position that I needed to write code that could take the constants I was parsing out of the file and create a function that could perform the correct actions on the array later.

For example, take the instruction x5/3. This is an exchange instruction that says the elements at position 5 and position 3 change places. To implement my “parse once, run the code multiple times” approach I needed to write a function that took in 5 and 3 and returned a function that would take the array and swap elements 5 and 3. In Ruby we metaprogram with lambdas and procs. After some trials and errors, I ended up with this function that wrote code to handle the exchange case.

def make_exchange x, y
  lambda { |ary| ary[x], ary[y] = ary[y], ary[x] }
end

This code returns a function that takes an array and does the exchange. When I parse the x5/3, I pass 5 and 3 to this function and get a lambda back. When it is time to modify the array I pass the array to the lambda like this l.call ary. This works, and it is surprisingly fast, but I found the multiple levels of metaprogramming a bit confusing. What I wanted was to define a method exchange that took two locations and the array as parameters. To do this though I needed a way to supply the x and y while parsing the file and the array while running the array transformations.

Supplying parameters to a function in stages reminded me of currying in languages like Scheme and Lisp. Out of curiosity I searched “Ruby currying” and found out that Proc#curry is in the standard lib. To use Proc#curry, you create a Proc object and then supply whatever parameters you have in square brackets. When the Proc has enough arguments, it runs and returns the result. Here’s an example of Proc#curry for addition.

p = proc { |x, y| x + y }
=> #<Proc:0x007f9fcf990108>
q = p.curry[3]
=> #<Proc:0x007f9fd01b9ed8>
q.curry[5]
=> 8

On the first line, I create a new proc named p that adds its two arguments. This returns a proc object. Then I call curry with the argument 3, supplied in square brackets. This returns a new proc object that I store in the variable q. Finally, I call q.curry with the argument 5 and that returns the sum 8.

So how can this be used for my advent of code problem? Instead of defining a function that writes a lambda I can specify the lambda once and use curry to supply the arguments as I have access to them. Using this method, my code looks like this:

exchange = lambda { |x, y, ary|
                    ary[x], ary[y] = ary[y], ary[x]
                  }

# When parsing I run this code
instruction = exchange.curry[$1.to_i, $2.to_i]

# When executing the instructions, run this
instruction.curry[ary]

This solution works, but I won’t say it is a good idea. It is slower than the solution I described above. I can’t think of a case where I’d use currying instead of metaprogramming in production. But it was a fun diversion, and it provided an opportunity to explore using Ruby more functionally.