Since we’re going to be building entire programs out of procs, let’s spend a minute looking at their properties before we dive into using them.

-> x { x + 2 }.call(1)

-> x, y {
  x + y
}.call(3, 4)

-> x {
  -> y {
    x + y
  }
}.call(3).call(4)

>> p = -> n { n * 2 }
=> #<Proc (lambda)>

>> q = -> x { p.call(x) }
=> #<Proc (lambda)>

>> p.call(5)
=> 10
>> q.call(5)
=> 10

>> -> x { x + 5 }[6]
=> 11

Our goal is to write the well-known FizzBuzz program:

This is an intentionally simple problem, designed to test whether an interview candidate has any programming experience at all. Anybody who knows how to program should be able to solve it without much difficulty.

Here’s an implementation of FizzBuzz in full-featured Ruby:

(1..100).each do |n|
  if (n % 15).zero?
    puts 'FizzBuzz'
  elsif (n % 3).zero?
    puts 'Fizz'
  elsif (n % 5).zero?
    puts 'Buzz'
  else
    puts n.to_s
  end
end

This isn’t the cleverest implementation of FizzBuzz—there are plenty of clever ones out there—but it’s a straightforward one that anyone could write without thinking about it.

However, this program contains some puts statements, and we have no way to print text to the console using only procs,^[44] so we’re going to replace it with a roughly equivalent program that returns an array of strings rather than printing them:

(1..100).map do |n|
  if (n % 15).zero?
    'FizzBuzz'
  elsif (n % 3).zero?
    'Fizz'
  elsif (n % 5).zero?
    'Buzz'
  else
    n.to_s
  end
end

This is still a meaningful solution to the FizzBuzz problem, but now it’s one that we have a chance of implementing using only procs.

Despite its simplicity, this is quite an ambitious program if we don’t have any of the features of a programming language: it creates a range, maps over it, evaluates a big conditional, does some arithmetic with the modulo operator, uses the Fixnum#zero? predicate, uses some string literals, and turns numbers into strings with Fixnum#to_s. That’s a fair amount of built-in Ruby functionality, and we’re going to have to strip it all out and reimplement it with procs.

We’re going to start by focusing on the numbers that appear in FizzBuzz. How can we possibly represent numbers without using Fixnums or any of the other datatypes that Ruby provides?

If we’re going to try to implement numbers^[45] from scratch, we’d better have a solid understanding of what we’re implementing. What is a number, anyway? It’s hard to come up with a concrete definition that doesn’t accidentally assume some aspect of what we’re trying to define; for example, “something that tells us how many…” is not very useful, because “how many” is really just another way of saying “number.”

Here’s one way of characterizing numbers: imagine we have a bag of apples and a bag of oranges. We take an apple out of one bag, an orange out of the other, and put them aside; then we keep taking out an apple and an orange together until at least one of the bags is empty.

If both bags become empty at the same time, we’ve learned something interesting: in spite of containing different things, those bags had some shared property that meant they became empty at the same time; at every point during the procedure of repeatedly removing an item from each bag, either both bags were nonempty or both bags were empty. This abstract property shared by the bags is what we can call a number (although we don’t know which number!), and we can compare these bags with any other bag in the world to see if it has the same “number” as them.

So one way to characterize numbers is by repetition (or iteration) of some action, in this case, taking an item from a bag. Each number corresponds to a unique way of repeating an action: the number one corresponds to just performing the action; the number two corresponds to performing it and then performing it again; and so on. The number zero, unsurprisingly, corresponds to not performing the action at all.

Since making and calling procs are the only “actions” our program can perform, we can try implementing a number n with code that repeats the action of calling a proc n times.

For example, if we were allowed to define methods—which we’re not, but play along—then we could define #one as a method that takes a proc and some arbitrary second argument, and then calls the proc with that argument once:

def one(proc, x)
  proc[x]
end

We could also define #two, which calls the proc once and then calls it again with whatever the result of calling it the first time was:^[46]

def two(proc, x)
  proc[proc[x]]
end

And so on:

def three(proc, x)
  proc[proc[proc[x]]]
end

Following this pattern, it’s natural to define #zero as a method that takes a proc and some other argument, ignores the proc entirely (i.e., calls it zero times), and returns the second argument untouched:

def zero(proc, x)
  x
end

All of these implementations can be translated into methodless representations; for example, we can replace the method #one with a proc that takes two arguments^[47] and then calls the first argument with the second one. They look like this:

ZERO  = -> p { -> x {       x    } }
ONE   = -> p { -> x {     p[x]   } }
TWO   = -> p { -> x {   p[p[x]]  } }
THREE = -> p { -> x { p[p[p[x]]] } }

This avoids functionality that we’re not allowed to use, and instead gives names to procs by assigning them to constants.

Now, although we’re eschewing Ruby’s features inside our FizzBuzz solution, it would be useful to translate these foreign representations of numbers into native Ruby values once they’re outside our code—so that they can be usefully inspected on the console or asserted against in tests, or at least so that we can convince ourselves that they really do represent numbers in the first place.

Fortunately we can write a #to_integer method that performs this conversion:

def to_integer(proc)
  proc[-> n { n + 1 }][0]
end

This method takes a proc that represents a number and calls it with another proc (which just increments its argument) and the native Ruby number 0. If we call #to_integer with ZERO then, because of ZERO’s definition, the incrementing proc doesn’t get called at all and we get an untouched Ruby 0 back:

>> to_integer(ZERO)
=> 0

And if we call #to_integer with THREE, the incrementing proc gets called three times and we get a Ruby 3 back:

>> to_integer(THREE)
=> 3

So these proc-based representations really do encode numbers, and we can convert them into a more practical representation whenever we want to.

For FizzBuzz, we need the numbers five, fifteen, and one hundred, which can all be implemented with the same technique:

FIVE    = -> p { -> x { p[p[p[p[p[x]]]]] } }
FIFTEEN = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } }
HUNDRED = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } }

These aren’t very compact definitions, but they work, as we can confirm with #to_integer:

>> to_integer(FIVE)
=> 5
>> to_integer(FIFTEEN)
=> 15
>> to_integer(HUNDRED)
=> 100

So, going back to the FizzBuzz program, all of the Ruby numbers can be replaced with their proc-based implementations:

(ONE..HUNDRED).map do |n|
  if (n % FIFTEEN).zero?
    'FizzBuzz'
  elsif (n % THREE).zero?
    'Fizz'
  elsif (n % FIVE).zero?
    'Buzz'
  else
    n.to_s
  end
end

Unfortunately, this program doesn’t work anymore, because we’re now using operations like .. and % on the proc-based implementations of numbers. Because Ruby doesn’t know how to treat these as numbers it’ll just blow up: TypeError: can't iterate from Proc, NoMethodError: undefined method `%' for #<Proc (lambda)>, and so on. We need to replace all of the operations to work with these representations—and we can only use procs to do it.

Before we can reimplement any of the operations, though, we need implementations of true and false.

How can we represent Booleans using only procs? Well, Booleans exist solely to be used in conditional statements, and in general, a conditional says “if some Boolean then this else that”:

>> success = true
=> true
>> if success then 'happy' else 'sad' end
=> "happy"
>> success = false
=> false
>> if success then 'happy' else 'sad' end
=> "sad"

So the real job of a Boolean is to allow us to choose between two options, and we can take advantage of this by representing a Boolean as a proc that chooses one of two values. Instead of thinking of a Boolean as a lifeless piece of data that can be read by some future code to decide which of two options to choose, we’ll just implement it directly as a piece of code that, when called with two options, either chooses the first option or chooses the second option.

Implemented as methods, then, #true and #false could be:

def true(x, y)
  x
end

def false(x, y)
  y
end

#true is a method that takes two arguments and returns the first one, and #false takes two arguments and returns the second. This is enough to give us crude conditional behavior:

>> success = :true
=> :true
>> send(success, 'happy', 'sad')
=> "happy"
>> success = :false
=> :false
>> send(success, 'happy', 'sad')
=> "sad"

As before, it’s straightforward to translate these methods into procs:

TRUE  = -> x { -> y { x } }
FALSE = -> x { -> y { y } }

And just as we defined #to_integer as a sanity check, to make sure it was possible to convert proc-based numbers into Ruby numbers, so we can define a #to_boolean method that can turn the TRUE and FALSE procs into Ruby’s native true and false objects:

def to_boolean(proc)
  proc[true][false]
end

This works by taking a proc that represents a Boolean and calling it with true as its first argument and false as its second. TRUE just returns its first argument, so to_boolean(TRUE) will return true, and likewise for FALSE:

>> to_boolean(TRUE)
=> true
>> to_boolean(FALSE)
=> false

So representing Booleans with procs is surprisingly easy, but for FizzBuzz, we don’t just need Booleans, we need a proc-only implementation of Ruby’s if-elsif-else. In fact, because of the way these Boolean implementations work, it’s easy to write an #if method too:

def if(proc, x, y)
  proc[x][y]
end

And that’s easy to translate into a proc:

IF =
  -> b {
    -> x {
      -> y {
        b[x][y]
      }
    }
  }

Clearly IF doesn’t need to do any useful work, because the Boolean itself picks the right argument—IF is just sugar—but it looks more natural than calling the Boolean directly:

>> IF[TRUE]['happy']['sad']
=> "happy"
>> IF[FALSE]['happy']['sad']
=> "sad"

Incidentally, this means we can revise the definition of #to_boolean to use IF:

def to_boolean(proc)
  IF[proc][true][false]
end

While we’re refactoring, it’s worth noting that the implementation of IF can be cleaned up significantly, because it contains some procs that are equivalent to simpler ones, as discussed in Equality. For example, look at IF’s innermost proc:

-> y {
  b[x][y]
}

This code means:

Steps 1 and 3 are dead wood: when we call this proc with an argument, it just passes it on to another proc. So the whole thing is equivalent to just step 2, b[x], and we can remove the dead wood in the implementation of IF to make it simpler:

IF =
  -> b {
    -> x {
      b[x]
    }
  }

We can see the same pattern again in what’s now the innermost proc:

-> x {
  b[x]
}

For the same reason, this proc is the same as just b, so we can simplify IF even further:

IF = -> b { b }

We’re not going to be able to simplify it any more than that.

Anyway, now that we have IF, we can go back to the FizzBuzz program and replace the Ruby if-elsif-else with nested calls to IF:

(ONE..HUNDRED).map do |n|
  IF[(n % FIFTEEN).zero?][
    'FizzBuzz'
  ][IF[(n % THREE).zero?][
    'Fizz'
  ][IF[(n % FIVE).zero?][
    'Buzz'
  ][
    n.to_s
  ]]]
end

Our next job is to replace Fixnum#zero? with a proc-based implementation that will work with proc-based numbers. The underlying algorithm of #zero? for Ruby values is something like this:

def zero?(n)
  if n == 0
    true
  else
    false
  end
end

(This is more verbose than is necessary, but it’s explicit about what happens: compare the number with 0; if it’s equal, then return true; otherwise, return false.)

How can we adapt this to handle procs instead of Ruby numbers? Look at our implementation of numbers again:

ZERO  = -> p { -> x {       x    } }
ONE   = -> p { -> x {     p[x]   } }
TWO   = -> p { -> x {   p[p[x]]  } }
THREE = -> p { -> x { p[p[p[x]]] } }
⋮

Notice that ZERO is the only number that doesn’t call p—it just returns x—whereas all of the other numbers call p at least once. We can take advantage of this: if we call an unknown number with TRUE as its second argument, it’ll return TRUE immediately if the number is ZERO. If it’s not ZERO, then it’ll return whatever calling p returns, so if we make p a proc that always returns FALSE, we’ll get the behavior we want:

def zero?(proc)
  proc[-> x { FALSE }][TRUE]
end

Again, it’s easy to rewrite this as a proc:

IS_ZERO = -> n { n[-> x { FALSE }][TRUE] }

We can use #to_boolean on the console to check that it works:

>> to_boolean(IS_ZERO[ZERO])
=> true
>> to_boolean(IS_ZERO[THREE])
=> false

That’s working fine, so in FizzBuzz, we can replace all of the calls to #zero? with IS_ZERO:

(ONE..HUNDRED).map do |n|
  IF[IS_ZERO[n % FIFTEEN]][
    'FizzBuzz'
  ][IF[IS_ZERO[n % THREE]][
    'Fizz'
  ][IF[IS_ZERO[n % FIVE]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

We have usable data in the form of numbers and Booleans, but we don’t have any data structures for storing more than one value in an organized way. We’ll soon need some kind of data structure in order to implement more complex functionality, so let’s pause briefly to introduce one.

The simplest data structure is a pair, which is like a two-element array. Pairs are quite easy to implement:

PAIR  = -> x { -> y { -> f { f[x][y] } } }
LEFT  = -> p { p[-> x { -> y { x } } ] }
RIGHT = -> p { p[-> x { -> y { y } } ] }

The purpose of a pair is to store two values and provide them again later on request. To construct a pair, we call PAIR with two values, an x and a y, and it returns its inner proc:

-> f { f[x][y] }

This is a proc that, when called with another proc f, will call it back with the earlier values of x and y as arguments. LEFT and RIGHT are the operations that pick out the left and the right element of a pair by calling it with a proc that returns its first or second argument respectively. It all works simply enough:

>> my_pair = PAIR[THREE][FIVE]
=> #<Proc (lambda)>
>> to_integer(LEFT[my_pair])
=> 3
>> to_integer(RIGHT[my_pair])
=> 5

This very simple data structure is enough to get us started; we’ll use pairs later, in Lists, as a building block for more complex structures.

Now that we have numbers, Booleans, conditionals, predicates, and pairs, we’re almost ready to reimplement the modulo operator.

Before we can do anything as ambitious as taking the modulo of two numbers, we need to be able to perform simpler operations like incrementing and decrementing a single number. Incrementing is fairly straightforward:

INCREMENT = -> n { -> p { -> x { p[n[p][x]] } } }

Look at how INCREMENT works: we call it with a proc-based number n, and it’ll return a new proc that takes some other proc p and some arbitrary second argument x, just like numbers do.

What does this new proc do when we call it? First it calls n with p and x—since n is a number, this means “call p, n times, on x,” just as the original number would have done—and then calls p one more time on the result. Overall, then, this is a proc whose first argument gets called n + 1 times on its second argument, which is exactly how to represent the number n + 1.

But what about decrementing? This looks like a much harder problem: once a proc has already been called n times, it’s easy enough to add an extra call so that it’s been called n + 1 times, but there’s no obvious way to “undo” one of them to make n - 1 calls.

One solution is to design a proc that, when called n times on some initial argument, returns the number n - 1. Fortunately, pairs give us a way of doing exactly that. Think about what this Ruby method does:

def slide(pair)
  [pair.last, pair.last + 1]
end

When we call slide with a two-element array of numbers, it returns a new two-element array containing the second number and the number that’s one greater than it; if the input array contains consecutive numbers, the effect is that of “sliding” a narrow window up the number line:

>> slide([3, 4])
=> [4, 5]
>> slide([8, 9])
=> [9, 10]

This is useful to us, because by starting that window at -1, we can arrange a situation where the first number in the array is one less than the number of times we’ve called slide on it, even though we’re only ever incrementing numbers:

>> slide([-1, 0])
=> [0, 1]
>> slide(slide([-1, 0]))
=> [1, 2]
>> slide(slide(slide([-1, 0])))
=> [2, 3]
>> slide(slide(slide(slide([-1, 0]))))
=> [3, 4]

We can’t do exactly this with proc-based numbers, because we don’t have a way of representing -1, but what’s interesting about slide is that it only looks at the second number in the array anyway, so we can put any dummy value—say, 0—in place of -1 and still get exactly the same result:

>> slide([0, 0])
=> [0, 1]
>> slide(slide([0, 0]))
=> [1, 2]
>> slide(slide(slide([0, 0])))
=> [2, 3]
>> slide(slide(slide(slide([0, 0]))))
=> [3, 4]

This is the key to making DECREMENT work: we can turn slide into a proc, use the proc representation of the number n to call slide n times on a pair of ZEROs, and then use LEFT to pull out the left number from the resulting pair.

SLIDE     = -> p { PAIR[RIGHT[p]][INCREMENT[RIGHT[p]]] }
DECREMENT = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] }

Here’s DECREMENT in action:

>> to_integer(DECREMENT[FIVE])
=> 4
>> to_integer(DECREMENT[FIFTEEN])
=> 14
>> to_integer(DECREMENT[HUNDRED])
=> 99
>> to_integer(DECREMENT[ZERO])
=> 0

Now that we have INCREMENT and DECREMENT, it’s possible to implement more useful numeric operations like addition, subtraction, multiplication, and exponentiation:

ADD      = -> m { -> n { n[INCREMENT][m] } }
SUBTRACT = -> m { -> n { n[DECREMENT][m] } }
MULTIPLY = -> m { -> n { n[ADD[m]][ZERO] } }
POWER    = -> m { -> n { n[MULTIPLY[m]][ONE] } }

These implementations are largely self-explanatory. If we want to add m and n, that’s just “starting with m, INCREMENT it n times,” and likewise for subtraction; once we have ADD, we can multiply m and n by saying “starting with ZERO, ADD m to it n times,” and similarly for exponentiation with MULTIPLY and ONE.

That should be enough arithmetic to get us started, but before we can implement % with procs, we need to know an algorithm for performing the modulo operation. Here’s one that works on Ruby’s numbers:

def mod(m, n)
  if n <= m
    mod(m - n, n)
  else
    m
  end
end

For example, to calculate 17 modulo 5:

But we can’t implement #mod with procs yet, because it uses another operator, <=, for which we don’t yet have an implementation, so we need to digress briefly to implement <= with procs.

We can begin with what looks like a pointlessly circular implementation of #less_or_equal? for Ruby numbers:

def less_or_equal?(m, n)
  m - n <= 0
end

This isn’t very useful, because it begs the question by relying on <=, but it does at least recast the problem in terms of two other problems we’ve already looked at: subtraction and comparison with zero. Subtraction we’ve already dealt with, and we’ve done comparison for equality with zero, but how do we implement less-than-or-equal-to zero?

As it happens we don’t need to worry about it, because zero is already the smallest number we know how to implement—recall that our proc-based numbers are the nonnegative integers—so “less than zero” is a meaningless concept in our number system. If we use SUBTRACT to subtract a larger number from a smaller one, it’ll just return ZERO, because there’s no way for it to return a negative number, and ZERO is the closest it can get:^[48]

>> to_integer(SUBTRACT[FIVE][THREE])
=> 2
>> to_integer(SUBTRACT[THREE][FIVE])
=> 0

We’ve already written IS_ZERO, and since SUBTRACT[m][n] will return ZERO if m is less than or equal to n (i.e., if n is at least as large as m), we have enough to implement #less_or_equal? with procs:

def less_or_equal?(m, n)
  IS_ZERO[SUBTRACT[m][n]]
end

And let’s turn that method into a proc:

IS_LESS_OR_EQUAL =
  -> m { -> n {
    IS_ZERO[SUBTRACT[m][n]]
  } }

Does it work?

>> to_boolean(IS_LESS_OR_EQUAL[ONE][TWO])
=> true
>> to_boolean(IS_LESS_OR_EQUAL[TWO][TWO])
=> true
>> to_boolean(IS_LESS_OR_EQUAL[THREE][TWO])
=> false

Looks good.

This gives us the missing piece for our implementation of #mod, so we can rewrite it with procs:

def mod(m, n)
  IF[IS_LESS_OR_EQUAL[n][m]][
    mod(SUBTRACT[m][n], n)
  ][
    m
  ]
end

And replace the method definition with a proc:

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      MOD[SUBTRACT[m][n]][n]
    ][
      m
    ]
  } }

Great! Does it work?

>> to_integer(MOD[THREE][TWO])
SystemStackError: stack level too deep

No.

Ruby dives off into an infinite recursive loop when we call MOD, because our translation of Ruby’s native functionality into procs has missed something important about the semantics of conditionals. In languages like Ruby, the if-else statement is nonstrict (or lazy): we give it a condition and two blocks, and it evaluates the condition to decide which of the two blocks to evaluate and return—it never evaluates both.

The problem with our IF implementation is that we can’t take advantage of the lazy behavior that’s built into Ruby if-else; we just say “call a proc, IF, with two other procs,” so Ruby charges ahead and evaluates both arguments before IF gets a chance to decide which one to return.

Look again at MOD:

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      MOD[SUBTRACT[m][n]][n]
    ][
      m
    ]
  } }

When we call MOD with values for m and n, and Ruby starts evaluating the body of the inner proc, it reaches the recursive call to MOD[SUBTRACT[m][n]][n] and immediately starts evaluating it as an argument to pass to IF, regardless of whether IS_LESS_OR_EQUAL[n][m] evaluated to TRUE or FALSE. This second call to MOD results in another unconditional recursive call, and so on, hence the infinite recursion.

To fix this, we need a way of telling Ruby to defer evaluation of IF’s second argument until we’re sure we need it. Evaluation of any expression in Ruby can be deferred by wrapping it in a proc, but wrapping an arbitrary Ruby value in a proc will generally change its meaning (e.g., the result of 1 + 2 does not equal -> { 1 + 2 }), so we might need to be more clever.

Fortunately we don’t, because this is a special case: we know that the result of calling MOD will be a single-argument proc, because all of our values are single-argument procs, and we already know (from Equality) that wrapping any proc p with another proc that takes the same arguments as p and immediately calls p with them will produce a value that is indistinguishable from just p, so we can use that trick here to defer the recursive call without affecting the meaning of the value being passed into IF:

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        MOD[SUBTRACT[m][n]][n][x]
      }
    ][
      m
    ]
  } }

This wraps the recursive MOD call in -> x { …[x] } to defer it; Ruby now won’t try to evaluate the body of that proc when it calls IF, but if the proc gets chosen by IF and returned as the result, it can be called by its recipient to finally trigger the (now definitely required) recursive call to MOD.

Does MOD work now?

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
     POWER[THREE][THREE]
   ][
     ADD[THREE][TWO]
   ])
=> 2

Yes! Hooray!

But don’t celebrate yet, because there’s another, more insidious problem: we are defining the constant MOD in terms of the constant MOD, so this definition is not just an innocent abbreviation. This time we’re not merely assigning a complex proc to a constant in order to reuse it later; in fact, we’re relying on Ruby’s assignment semantics in order to assume that, even though MOD has obviously not yet been defined while we’re still defining it, we can nonetheless refer to it in MOD’s implementation and expect it to have become defined by the time we evaluate it later.

That’s cheating, because in principle, we should be able to undo all of the abbreviations—“where we said MOD, what we actually meant was this long proc”—but that’s impossible as long as MOD is defined in terms of itself.

We can solve this problem with the Y combinator, a famous piece of helper code designed for exactly this purpose: defining a recursive function without cheating. Here’s what it looks like:

Y = -> f { -> x { f[x[x]] }[-> x { f[x[x]] }] }

The Y combinator is hard to explain accurately without lots of detail, but here’s a (technically inaccurate) sketch: when we call the Y combinator with a proc, it will call that proc with the proc itself as the first argument. So, if we write a proc that expects an argument and then call the Y combinator with that proc, then the proc will get itself as that argument and therefore can use that argument whenever it wants to call itself.

Sadly, for the same reason that MOD was looping forever, the Y combinator will loop forever in Ruby too, so we need a modified version. It’s the expression x[x] that causes the problem, and we can again fix the problem by wrapping the occurrences of that expression in inert -> y { …[y] } procs to defer their evaluation:

Z = -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }

This is the Z combinator, which is just the Y combinator adapted for strict languages like Ruby.

We can now finally make a satisfactory implementation of MOD by giving it an extra argument, f, wrapping a call to the Z combinator around it, and calling f where we used to call MOD:

MOD =
  Z[-> f { -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        f[SUBTRACT[m][n]][n][x]
      }
    ][
      m
    ]
  } } }]

Thankfully this noncheating version of MOD still works:

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
     POWER[THREE][THREE]
   ][
     ADD[THREE][TWO]
   ])
=> 2

Now we can replace all of the occurrences of % in the FizzBuzz program with calls to MOD:

(ONE..HUNDRED).map do |n|
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

We only have a few Ruby features left to reimplement for FizzBuzz: the range, the #map, the string literals, and the Fixnum#to_s. We’ve seen lots of detail for the other values and operations we’ve implemented, so we’ll go through the remaining ones quickly and in as little detail as possible. (Don’t worry about understanding everything; we’ll just be getting a flavor.)

To be able to implement ranges and #map, we need an implementation of lists, and the easiest way to build lists is to use pairs. The implementation works like a linked list, where each pair stores a value and a pointer to the next pair in the list; in this case, we use nested pairs instead of pointers. The standard list operations look like this:

EMPTY     = PAIR[TRUE][TRUE]
UNSHIFT   = -> l { -> x {
              PAIR[FALSE][PAIR[x][l]]
            } }
IS_EMPTY  = LEFT
FIRST     = -> l { LEFT[RIGHT[l]] }
REST      = -> l { RIGHT[RIGHT[l]] }

And they work like this:

>> my_list =
     UNSHIFT[
       UNSHIFT[
         UNSHIFT[EMPTY][THREE]
       ][TWO]
     ][ONE]
=> #<Proc (lambda)>
>> to_integer(FIRST[my_list])
=> 1
>> to_integer(FIRST[REST[my_list]])
=> 2
>> to_integer(FIRST[REST[REST[my_list]]])
=> 3
>> to_boolean(IS_EMPTY[my_list])
=> false
>> to_boolean(IS_EMPTY[EMPTY])
=> true

Using FIRST and REST to pull out individual elements of lists is quite clumsy, so as with numbers and Booleans we can write a #to_array method to help us on the console:

def to_array(proc)
  array = []

  until to_boolean(IS_EMPTY[proc])
    array.push(FIRST[proc])
    proc = REST[proc]
  end

  array
end

This makes it easier to inspect lists:

>> to_array(my_list)
=> [#<Proc (lambda)>, #<Proc (lambda)>, #<Proc (lambda)>]
>> to_array(my_list).map { |p| to_integer(p) }
=> [1, 2, 3]

How can we implement ranges? In fact, instead of finding a way to explicitly represent ranges as procs, let’s just write a proc that can build a list of all the elements in a range. For native Ruby numbers and “lists” (i.e., arrays), we can write it like this:

def range(m, n)
  if m <= n
    range(m + 1, n).unshift(m)
  else
    []
  end
end

This algorithm is slightly contrived in anticipation of the available list operations, but it makes sense: the list of all the numbers from m to n is the same as the list of all the numbers from m + 1 to n with m unshifted onto the front; if m is greater than n, then the list of numbers is empty.

Happily, we already have everything we need to translate this method directly into procs:

RANGE =
  Z[-> f {
    -> m { -> n {
      IF[IS_LESS_OR_EQUAL[m][n]][
        -> x {
          UNSHIFT[f[INCREMENT[m]][n]][m][x]
        }
      ][
        EMPTY
      ]
    } }
  }]

Does this work?

>> my_range = RANGE[ONE][FIVE]
=> #<Proc (lambda)>
>> to_array(my_range).map { |p| to_integer(p) }
=> [1, 2, 3, 4, 5]

Yes, so let’s use it in FizzBuzz:

RANGE[ONE][HUNDRED].map do |n|
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

To implement #map, we can use a helper called FOLD, which is a bit like Ruby’s Enumerable#inject:

FOLD =
  Z[-> f {
    -> l { -> x { -> g {
      IF[IS_EMPTY[l]][
        x
      ][
        -> y {
          g[f[REST[l]][x][g]][FIRST[l]][y]
        }
      ]
    } } }
  }]

FOLD makes it easier to write procs that process every item in a list:

>> to_integer(FOLD[RANGE[ONE][FIVE]][ZERO][ADD])
=> 15
>> to_integer(FOLD[RANGE[ONE][FIVE]][ONE][MULTIPLY])
=> 120

Once we have FOLD, we can write MAP concisely:

MAP =
  -> k { -> f {
    FOLD[k][EMPTY][
      -> l { -> x { UNSHIFT[l][f[x]] } }
    ]
  } }

Does MAP work?

>> my_list = MAP[RANGE[ONE][FIVE]][INCREMENT]
=> #<Proc (lambda)>
>> to_array(my_list).map { |p| to_integer(p) }
=> [2, 3, 4, 5, 6]

Yes. So we can replace #map in FizzBuzz:

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
}]

Nearly finished! All that remains is to deal with the strings.

Strings are easy to handle: we can just represent them as lists of numbers, as long as we agree on an encoding that determines which number represents which character.

We can choose any encoding we want, so instead of using a general-purpose one like ASCII, let’s design a new one that’s more convenient for FizzBuzz. We only need to encode digits and the strings 'FizzBuzz', 'Fizz', and 'Buzz', so we can use the numbers 0 to 9 to represent the characters '0' to '9', and the numbers from 10 to 14 to encode the characters 'B', 'F', 'i', 'u', and 'z'.

This already gives us a way to represent the string literals we need (being careful not to clobber the Z combinator):

TEN = MULTIPLY[TWO][FIVE]
B   = TEN
F   = INCREMENT[B]
I   = INCREMENT[F]
U   = INCREMENT[I]
ZED = INCREMENT[U]

FIZZ     = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][ZED]][ZED]][I]][F]
BUZZ     = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][ZED]][ZED]][U]][B]
FIZZBUZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[BUZZ][ZED]][ZED]][I]][F]

To check that these work, we can write some external methods to convert them into Ruby strings:

def to_char(c)
  '0123456789BFiuz'.slice(to_integer(c))
end

def to_string(s)
  to_array(s).map { |c| to_char(c) }.join
end

Alright, do the strings work?

>> to_char(ZED)
=> "z"
>> to_string(FIZZBUZZ)
=> "FizzBuzz"

Great. So we can use them in FizzBuzz:

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    FIZZBUZZ
  ][IF[IS_ZERO[MOD[n][THREE]]][
    FIZZ
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    BUZZ
  ][
    n.to_s
  ]]]
}]

The very last thing to implement is Fixnum#to_s. For that, we need to be able to split a number into its component digits, and here’s one way to do that in Ruby:

def to_digits(n)
  previous_digits =
    if n < 10
      []
    else
      to_digits(n / 10)
    end

  previous_digits.push(n % 10)
end

We haven’t implemented <, but we can dodge that problem by using n <= 9 instead of n < 10. Unfortunately, we can’t dodge implementing Fixnum#/ and Array#push, so here they are:

DIV =
  Z[-> f { -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        INCREMENT[f[SUBTRACT[m][n]][n]][x]
      }
    ][
      ZERO
    ]
  } } }]

PUSH =
  -> l {
    -> x {
      FOLD[l][UNSHIFT[EMPTY][x]][UNSHIFT]
    }
  }

Now we can translate #to_digits into a proc:

TO_DIGITS =
  Z[-> f { -> n { PUSH[
    IF[IS_LESS_OR_EQUAL[n][DECREMENT[TEN]]][
      EMPTY
    ][
      -> x {
        f[DIV[n][TEN]][x]
      }
    ]
  ][MOD[n][TEN]] } }]

Does it work?

>> to_array(TO_DIGITS[FIVE]).map { |p| to_integer(p) }
=> [5]
>> to_array(TO_DIGITS[POWER[FIVE][THREE]]).map { |p| to_integer(p) }
=> [1, 2, 5]

Yes. And because we had the foresight to design a string encoding where 1 represents '1' and so on, the arrays produced by TO_DIGITS are already valid strings:

>> to_string(TO_DIGITS[FIVE])
=> "5"
>> to_string(TO_DIGITS[POWER[FIVE][THREE]])
=> "125"

So we can replace #to_s with TO_DIGITS in FizzBuzz:

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    FIZZBUZZ
  ][IF[IS_ZERO[MOD[n][THREE]]][
    FIZZ
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    BUZZ
  ][
    TO_DIGITS[n]
  ]]]
}]

We’ve finally finished! (This would’ve been the longest, most awkward job interview ever.) We now have an implementation of FizzBuzz written entirely with procs. Let’s run it to make sure it works properly:

>> solution =
     MAP[RANGE[ONE][HUNDRED]][-> n {
       IF[IS_ZERO[MOD[n][FIFTEEN]]][
         FIZZBUZZ
       ][IF[IS_ZERO[MOD[n][THREE]]][
         FIZZ
       ][IF[IS_ZERO[MOD[n][FIVE]]][
         BUZZ
       ][
         TO_DIGITS[n]
       ]]]
     }]
=> #<Proc (lambda)>
>> to_array(solution).each do |p|
     puts to_string(p)
   end; nil
1
2
Fizz
4
Buzz
Fizz
7
⋮
94
Buzz
Fizz
97
98
Fizz
Buzz
=> nil

Having gone to so much trouble to make sure that every constant is just an abbreviation of some longer expression, we owe it to ourselves to replace each constant with its definition so we can see the complete program:

-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } }] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y { y } }] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } }] }[-> p { p[-> x { -> y { y } }] }[l]] }[l]][y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[l][f[x]] } }] } }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[m][n]][-> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[f[-> n { -> p { -> x { p[n[p][x]] } } }[m]][n]][m][x] }][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]] } } }][-> p { -> x { p[x] } }][-> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } }]][-> n { -> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } }]]][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]][-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]][-> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> p { -> x { p[p[p[x]]] } }]]][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]][-> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]][-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> n { -> l { -> x { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } }] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y { y } }] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y { y } }] }[l]] }[l]][y] }] } } } }][l][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][x]][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }] } }[-> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> x { f[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { -> n { -> p { -> x { p[n[p][x]] } } }[f[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n]][x] }][-> p { -> x { x } }] } } }][n][-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][x] }]][-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]] } }][n]]]] }]

Beautiful.

Constructing programs entirely out of procs takes a lot of effort, but we’ve seen that it’s possible to get real work done as long as we don’t mind applying a bit of ingenuity. Let’s take a quick look at a couple of other techniques for writing code in this minimal environment.

ZEROS = Z[-> f { UNSHIFT[f][ZERO] }]

>> to_integer(FIRST[ZEROS])
=> 0
>> to_integer(FIRST[REST[ZEROS]])
=> 0
>> to_integer(FIRST[REST[REST[REST[REST[REST[ZEROS]]]]]])
=> 0

def to_array(l, count = nil)
  array = []

  until to_boolean(IS_EMPTY[l]) || count == 0
    array.push(FIRST[l])
    l = REST[l]
    count = count - 1 unless count.nil?
  end

  array
end

>> to_array(ZEROS, 5).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0]
>> to_array(ZEROS, 10).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>> to_array(ZEROS, 20).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

>> UPWARDS_OF = Z[-> f { -> n { UNSHIFT[-> x { f[INCREMENT[n]][x] }][n] } }]
=> #<Proc (lambda)>
>> to_array(UPWARDS_OF[ZERO], 5).map { |p| to_integer(p) }
=> [0, 1, 2, 3, 4]
>> to_array(UPWARDS_OF[FIFTEEN], 20).map { |p| to_integer(p) }
=> [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]

>> MULTIPLES_OF =
     -> m {
       Z[-> f {
         -> n { UNSHIFT[-> x { f[ADD[m][n]][x] }][n] }
       }][m]
     }
=> #<Proc (lambda)>
>> to_array(MULTIPLES_OF[TWO], 10).map { |p| to_integer(p) }
=> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>> to_array(MULTIPLES_OF[FIVE], 20).map { |p| to_integer(p) }
=> [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

>> to_array(MULTIPLES_OF[THREE], 10).map { |p| to_integer(p) }
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
>> to_array(MAP[MULTIPLES_OF[THREE]][INCREMENT], 10).map { |p| to_integer(p) }
=> [4, 7, 10, 13, 16, 19, 22, 25, 28, 31]
>> to_array(MAP[MULTIPLES_OF[THREE]][MULTIPLY[TWO]], 10).map { |p| to_integer(p) }
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]

>> MULTIPLY_STREAMS =
     Z[-> f {
       -> k { -> l {
         UNSHIFT[-> x { f[REST[k]][REST[l]][x] }][MULTIPLY[FIRST[k]][FIRST[l]]]
       } }
     }]
=> #<Proc (lambda)>
>> to_array(MULTIPLY_STREAMS[UPWARDS_OF[ONE]][MULTIPLES_OF[THREE]], 10).
     map { |p| to_integer(p) }
=> [3, 12, 27, 48, 75, 108, 147, 192, 243, 300]

def multiples_of(n)
  Enumerator.new do |yielder|
    value = n
    loop do
      yielder.yield(value)
      value = value + n
    end
  end
end

>> multiples_of_three = multiples_of(3)
=> #<Enumerator: #<Enumerator::Generator>:each>
>> multiples_of_three.next
=> 3
>> multiples_of_three.next
=> 6
>> multiples_of_three.next
=> 9

>> multiples_of(3).first
=> 3
>> multiples_of(3).take(10)
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
>> multiples_of(3).detect { |x| x > 100 }
=> 102

>> multiples_of(3).lazy.map { |x| x * 2 }.take(10).force
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
>> multiples_of(3).lazy.map { |x| x * 2 }.select { |x| x > 100 }.take(10).force
=> [102, 108, 114, 120, 126, 132, 138, 144, 150, 156]
>> multiples_of(3).lazy.zip(multiples_of(4)).map { |a, b| a * b }.take(10).force
=> [12, 48, 108, 192, 300, 432, 588, 768, 972, 1200]

def decrease(m, n)
  if n <= m
    m - n
  else
    m
  end
end

>> decrease(17, 5)
=> 12
>> decrease(decrease(17, 5), 5)
=> 7
>> decrease(decrease(decrease(17, 5), 5), 5)
=> 2
>> decrease(decrease(decrease(decrease(17, 5), 5), 5), 5)
=> 2
>> decrease(decrease(decrease(decrease(decrease(17, 5), 5), 5), 5), 5)
=> 2

MOD =
  -> m { -> n {
    m[-> x {
      IF[IS_LESS_OR_EQUAL[n][x]][
        SUBTRACT[x][n]
      ][
        x
      ]
    }][m]
  } }

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
     POWER[THREE][THREE]
   ][
     ADD[THREE][TWO]
   ])
=> 2

>> to_integer(MOD[THREE][ZERO])
=> 3

def countdown(pair)
  [pair.first.unshift(pair.last), pair.last - 1]
end

>> countdown([[], 10])
=> [[10], 9]
>> countdown(countdown([[], 10]))
=> [[9, 10], 8]
>> countdown(countdown(countdown([[], 10])))
=> [[8, 9, 10], 7]
>> countdown(countdown(countdown(countdown([[], 10]))))
=> [[7, 8, 9, 10], 6]

COUNTDOWN = -> p { PAIR[UNSHIFT[LEFT[p]][RIGHT[p]]][DECREMENT[RIGHT[p]]] }

RANGE = -> m { -> n { LEFT[INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]]] } }

>> to_array(RANGE[FIVE][TEN]).map { |p| to_integer(p) }
=> [5, 6, 7, 8, 9, 10]

The untyped lambda calculus is a programming language with only three kinds of expression: variables, function definitions, and calls. Rather than introduce a new concrete syntax for lambda calculus expressions, we’ll stick with the Ruby conventions—variables look like x, functions look like -> x { x }, and calls look like x[y]—and try not to get the two languages confused.

We can implement LCVariable, LCFunction, and LCCall syntax classes in the usual way:

class LCVariable < Struct.new(:name)
  def to_s
    name.to_s
  end

  def inspect
    to_s
  end
end

class LCFunction < Struct.new(:parameter, :body)
  def to_s
    "-> #{parameter} { #{body} }"
  end

  def inspect
    to_s
  end
end

class LCCall < Struct.new(:left, :right)
  def to_s
    "#{left}[#{right}]"
  end

  def inspect
    to_s
  end
end

These classes let us build abstract syntax trees of lambda calculus expressions, just like we did with Simple in Chapter 2 and regular expressions in Chapter 3:

>> one =
     LCFunction.new(:p,
       LCFunction.new(:x,
         LCCall.new(LCVariable.new(:p), LCVariable.new(:x))
       )
     )
=> -> p { -> x { p[x] } }
>> increment =
     LCFunction.new(:n,
       LCFunction.new(:p,
         LCFunction.new(:x,
           LCCall.new(
             LCVariable.new(:p),
             LCCall.new(
               LCCall.new(LCVariable.new(:n), LCVariable.new(:p)),
               LCVariable.new(:x)
             )
           )
         )
       )
     )
=> -> n { -> p { -> x { p[n[p][x]] } } }
>> add =
     LCFunction.new(:m,
       LCFunction.new(:n,
         LCCall.new(LCCall.new(LCVariable.new(:n), increment), LCVariable.new(:m))
       )
     )
=> -> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }

Because the language has such minimal syntax, those three classes are enough to represent any lambda calculus program.

Now we’re going to give a small-step operational semantics for the lambda calculus by implementing a #reduce method on each syntax class. Small-step is an attractive choice, because it allows us to see the individual steps of evaluation, which is something we can’t easily do for Ruby expressions.

class LCVariable
  def replace(name, replacement)
    if self.name == name
      replacement
    else
      self
    end
  end
end

class LCFunction
  def replace(name, replacement)
    if parameter == name
      self
    else
      LCFunction.new(parameter, body.replace(name, replacement))
    end
  end
end

class LCCall
  def replace(name, replacement)
    LCCall.new(left.replace(name, replacement), right.replace(name, replacement))
  end
end

>> expression = LCVariable.new(:x)
=> x
>> expression.replace(:x, LCFunction.new(:y, LCVariable.new(:y)))
=> -> y { y }
>> expression.replace(:z, LCFunction.new(:y, LCVariable.new(:y)))
=> x
>> expression =
     LCCall.new(
       LCCall.new(
         LCCall.new(
           LCVariable.new(:a),
           LCVariable.new(:b)
         ),
         LCVariable.new(:c)
       ),
       LCVariable.new(:b)
     )
=> a[b][c][b]
>> expression.replace(:a, LCVariable.new(:x))
=> x[b][c][b]
>> expression.replace(:b, LCFunction.new(:x, LCVariable.new(:x)))
=> a[-> x { x }][c][-> x { x }]

>> expression =
     LCFunction.new(:y,
       LCCall.new(LCVariable.new(:x), LCVariable.new(:y))
     )
=> -> y { x[y] }
>> expression.replace(:x, LCVariable.new(:z))
=> -> y { z[y] }
>> expression.replace(:y, LCVariable.new(:z))
=> -> y { x[y] }

>> expression =
     LCCall.new(
       LCCall.new(LCVariable.new(:x), LCVariable.new(:y)),
       LCFunction.new(:y, LCCall.new(LCVariable.new(:y), LCVariable.new(:x)))
     )
=> x[y][-> y { y[x] }]
>> expression.replace(:x, LCVariable.new(:z))
=> z[y][-> y { y[z] }] 
>> expression.replace(:y, LCVariable.new(:z))
=> x[z][-> y { y[x] }] 

>> expression =
     LCFunction.new(:x,
       LCCall.new(LCVariable.new(:x), LCVariable.new(:y))
     )
=> -> x { x[y] }
>> replacement = LCCall.new(LCVariable.new(:z), LCVariable.new(:x))
=> z[x]
>> expression.replace(:y, replacement)
=> -> x { x[z[x]] }

class LCFunction
  def call(argument)
    body.replace(parameter, argument)
  end
end

>> function =
     LCFunction.new(:x,
       LCFunction.new(:y,
         LCCall.new(LCVariable.new(:x), LCVariable.new(:y))
       )
     )
=> -> x { -> y { x[y] } }
>> argument = LCFunction.new(:z, LCVariable.new(:z))
=> -> z { z }
>> function.call(argument)
=> -> y { -> z { z }[y] }

class LCVariable
  def callable?
    false
  end
end

class LCFunction
  def callable?
    true
  end
end

class LCCall
  def callable?
    false
  end
end

class LCVariable
  def reducible?
    false
  end
end

class LCFunction
  def reducible?
    false
  end
end

class LCCall
  def reducible?
    left.reducible? || right.reducible? || left.callable?
  end

  def reduce
    if left.reducible?
      LCCall.new(left.reduce, right)
    elsif right.reducible?
      LCCall.new(left, right.reduce)
    else
      left.call(right)
    end
  end
end

>> expression = LCCall.new(LCCall.new(add, one), one)
=> -> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[-> p { -> x { p[x] } }][-> p { -> x { p[x] } }]
>> while expression.reducible?
     puts expression
     expression = expression.reduce
   end; puts expression
-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[-> p { -> x { p[x] } }][-> p { -> x { p[x] } }]
-> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][-> p { -> x { p[x] } }] }[-> p { -> x { p[x] } }]
-> p { -> x { p[x] } }[-> n { -> p { -> x { p[n[p][x]] } } }][-> p { -> x { p[x] } }]
-> x { -> n { -> p { -> x { p[n[p][x]] } } }[x] }[-> p { -> x { p[x] } }]
-> n { -> p { -> x { p[n[p][x]] } } }[-> p { -> x { p[x] } }]
-> p { -> x { p[-> p { -> x { p[x] } }[p][x]] } }
=> nil

>> inc, zero = LCVariable.new(:inc), LCVariable.new(:zero)
=> [inc, zero]
>> expression = LCCall.new(LCCall.new(expression, inc), zero)
=> -> p { -> x { p[-> p { -> x { p[x] } }[p][x]] } }[inc][zero]
>> while expression.reducible?
     puts expression
     expression = expression.reduce
   end; puts expression
-> p { -> x { p[-> p { -> x { p[x] } }[p][x]] } }[inc][zero]
-> x { inc[-> p { -> x { p[x] } }[inc][x]] }[zero]
inc[-> p { -> x { p[x] } }[inc][zero]]
inc[-> x { inc[x] }[zero]]
inc[inc[zero]]
=> nil

Now that we’ve got a working semantics, let’s finish things off by building a parser for lambda calculus expressions. As usual, we can use Treetop to write a grammar:

grammar LambdaCalculus
  rule expression
    calls / variable / function
  end

  rule calls
    first:(variable / function) rest:('[' expression ']')+ {
      def to_ast
        arguments.map(&:to_ast).inject(first.to_ast) { |l, r| LCCall.new(l, r) }
      end

      def arguments
        rest.elements.map(&:expression)
      end
    }
  end

  rule variable
    [a-z]+ {
      def to_ast
        LCVariable.new(text_value.to_sym)
      end
    }
  end

  rule function
    '-> ' parameter:[a-z]+ ' { ' body:expression ' }' {
      def to_ast
        LCFunction.new(parameter.text_value.to_sym, body.to_ast)
      end
    }
  end
end

The parser and operational semantics together give us a complete implementation of the lambda calculus, allowing us to read expressions and evaluate them:

>> require 'treetop'
=> true
>> Treetop.load('lambda_calculus')
=> LambdaCalculusParser
>> parse_tree = LambdaCalculusParser.new.parse('-> x { x[x] }[-> y { y }]')
=> SyntaxNode+Calls2+Calls1 offset=0, "…}[-> y { y }]" (to_ast,arguments,first,rest):
     SyntaxNode+Function1+Function0 offset=0, "… x { x[x] }" (to_ast,parameter,body):
       SyntaxNode offset=0, "-> "
       SyntaxNode offset=3, "x":
         SyntaxNode offset=3, "x"
       SyntaxNode offset=4, " { "
       SyntaxNode+Calls2+Calls1 offset=7, "x[x]" (to_ast,arguments,first,rest):
         SyntaxNode+Variable0 offset=7, "x" (to_ast):
           SyntaxNode offset=7, "x"
         SyntaxNode offset=8, "[x]":
           SyntaxNode+Calls0 offset=8, "[x]" (expression):
             SyntaxNode offset=8, "["
             SyntaxNode+Variable0 offset=9, "x" (to_ast):
               SyntaxNode offset=9, "x"
             SyntaxNode offset=10, "]"
       SyntaxNode offset=11, " }"
     SyntaxNode offset=13, "[-> y { y }]":
       SyntaxNode+Calls0 offset=13, "[-> y { y }]" (expression):
         SyntaxNode offset=13, "["
         SyntaxNode+Function1+Function0 offset=14, "… { y }" (to_ast,parameter,body):
           SyntaxNode offset=14, "-> "
           SyntaxNode offset=17, "y":
             SyntaxNode offset=17, "y"
           SyntaxNode offset=18, " { "
           SyntaxNode+Variable0 offset=21, "y" (to_ast):
             SyntaxNode offset=21, "y"
           SyntaxNode offset=22, " }"
         SyntaxNode offset=24, "]"
>> expression = parse_tree.to_ast
=> -> x { x[x] }[-> y { y }]
>> expression.reduce
=> -> y { y }[-> y { y }]