Programming with Nothing

Contents

Ruining Ruby

I love Ruby! I’ve used it every day for years and I’m not sick of it yet. It’s an easy language to love: it’s expressive, flexible and syntactically beautiful; it has a unique combination of useful features like mixins, metaclasses and blocks; it comes with a useful core library and comprehensive standard library; and it has an excellent ecosystem, with plenty of great third-party libraries available.

In fact, you know what? I love Ruby so much that I want to ruin it. Let’s see how much it can do if we remove all of its features. Naturally that means no gems, no standard library, no modules, methods, classes or objects. But this is love, so let’s go all the way: no control flow, no assignment, no arrays, strings, numbers or booleans.

(To clarify: this is just a game. It is not software engineering advice.)

Unfortunately we can’t remove absolutely everything and still have a language, so here are the Ruby features we’re going to keep:

As a grudging concession to clarity, we should also allow ourselves to use constants to abbreviate our code: if we create a complex proc, we may assign it to a constant to give it a short name that we can reuse later. But referring to the name is no different from retyping the original proc again — the name just makes the code more readable — so it’s not really using a language feature. We could always undo the abbreviations by replacing each constant with the proc it refers to.

Thinking procs

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

Aiming high

Our goal will be to write the well-known FizzBuzz program:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

This is an ostensibly simple problem, designed to test whether an interview candidate is lying about being a programmer. Any competent programmer should be able to solve it within a minute.

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

(I am available for freelance programming work.)

This isn’t the cleverest implementation of FizzBuzz — there are plenty of clever ones out there — but it’s the one I would 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, so I’m going to replace it with a roughly equivalent program which 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

Hopefully you’ll agree that 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 you 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.

Numbers

I’m 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 from scratch, we’d better have a solid understanding of what we’re implementing. But 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 you how many…” is not very useful, because “how many” is really just another way of saying “number”.

To be more specific, what we want to implement here is the natural numbers — whole, non-negative numbers — also known as the counting numbers: zero, one, two, three, and so on.

Here’s one way of characterising them: imagine you have a bag of apples and a bag of oranges; you take an apple out of one bag, an orange out of the other, and put them aside; then you 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, you’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 non-empty 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 you can compare these bags with any other bag in the world to see if it has the same “number” as these ones.

So one way to characterise numbers is by repetition (a.k.a. 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 (this is “iterating the function”):

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 which takes two arguments 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 the “defining methods” 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 program, it would be useful to be able to translate these foreign representations of numbers into native Ruby values once they’re outside our program — 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 (one 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 using 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 of those numbers, 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

(As promised, I’m writing ONE instead of -> p { -> x { p[x] } }, and so on, to make the code clearer.)

Unfortunately this program doesn’t work any more, because we’re now using operations like .. and % on the proc-based implementations of numbers, and 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.

Booleans

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”, so the real job of a boolean is to allow you to choose between two options.

We can take advantage of this by representing a boolean with a proc that chooses one of two values. This cuts out the middleman: 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 can 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. As before, it’s straightforward to translate them 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 this TRUE and FALSE into Ruby-native true and false:

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

This works by taking a proc that represents a boolean and calling it with Ruby true as the first argument and Ruby false as the second argument. Because TRUE just returns its first argument, to_boolean(TRUE) will therefore 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][:foo][:bar]
=> :foo

>> IF[FALSE][:foo][:bar]
=> :bar

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 (or “extensionally equal”) to simpler ones, as discussed earlier. For example, look at IF’s innermost proc:

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

Breaking the code down, it says:

  1. “take an argument y”; then
  2. “call b with x to get a proc”; and finally
  3. “call that proc with y”.

Steps 1 and 3 are dead wood: when you call this proc with an argument, it just calls another proc with that argument. 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]
    }
  }

You 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

Predicates

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 which 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 which always returns FALSE, we’ll get the behaviour 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

Numeric operations

Now that we have numbers, booleans, conditionals and predicates, we’re ready to reimplement Fixnum#%. (Don’t despair: this is the last thing I’m going to show you in detail. Once we’ve done it I’ll skim the rest and get to the punchline as soon as possible.)

Before we can do anything as ambitious as taking the modulo of two numbers, we need fundamental operations like incrementing and decrementing. To keep things moving I’ll just recite their standard implementations:

INCREMENT = -> n { -> p { -> x { p[n[p][x]] } } }
DECREMENT = -> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }]
                                  [-> y { x }][-> y { y }] } } }

DECREMENT is too complicated to explain succinctly, but look briefly at how INCREMENT works: 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 you 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.

Anyway, once we have INCREMENT and DECREMENT, it’s possible to implement 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 aren’t too hard to understand. For example, if you want to add m and n, that’s just “n times, INCREMENT m”, and likewise for subtraction; once you have ADD, you can multiply m and n by saying “n times, ADD m to ZERO”, 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 computing the modulo of two numbers. 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 natural numbers — 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:

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

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

(You might protest that 3 - 5 = 0 isn’t called “subtraction” where you come from, and you’d be right: the technical name for this operation is “monus”, because the natural numbers under addition form a commutative monoid instead of a proper abelian group.)

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 non-strict (a.k.a. “lazy”): you 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 behaviour 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. 41 + 1 does not equal -> { 41 + 1 }) 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 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 I said MOD, what I 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 you call the Y combinator with a proc, it will call that proc with the proc itself as the first argument. So, if you 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 impotent -> 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. (The verbatim Y combinator only works in non-strict languages like Haskell.)

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 non-cheating 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

Lists, briefly

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 I’ll go through the remaining ones quickly and in as little detail as possible. (Don’t worry about understanding everything; I’ll just be giving a flavour.)

To be able to implement ranges and #map we need an implementation of lists. The easiest way to build lists is to use pairs, which are like two-element arrays. 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 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 which, when called with another proc, will call it back with the earlier values of x and y as arguments. LEFT and RIGHT are the operations which 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

Once we have pairs, we can use them to implement lists. This 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
      ]
    } }
  }]

(Note the use of the Z combinator for recursion, and a deferring -> x { …[x] } proc around the TRUE branch of the conditional.)

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, briefly

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, so 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]
  ]]]
}]

Victory

We’ve finally finished! (This would’ve been the longest, most awkward job interview ever.) Here is FizzBuzz, written entirely with procs:

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]
  ]]]
}]

But wait! We’ve gone to a lot of trouble to make sure that every constant is just an abbreviation of some longer expression, so we owe it to ourselves to replace each constant with its definition in order to reveal the full glorious 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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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 { x } }] }[-> 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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }[-> 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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { -> n { -> p { -> x { p[n[p][x]] } } }[f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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 { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][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.

Why?

Being limited to Proc.new and Proc#call sounds impossibly restrictive, but I’ve tried to present enough evidence to convince you that we can still build any data structure and implement any algorithm.

In this alien world there is no data, only code. Data is an inert artefact for controlling the behaviour of the code that reads it, but you can always cut out the middleman by replacing a piece of data with the living code that does what the data-reading code would have done when it read that data.

We don’t know how to design a programming language, or even make a computer, that has more computational power than this combination of Proc.new and Proc#call. I think this is an awe-inspiring fundamental fact — like knowing that every atom in your body that isn’t hydrogen, helium or lithium was either synthesised in the heart of a star or in the subsequent supernova that distributed its matter throughout the universe. It tells us what we, as programmers, are made of.

So why doesn’t everyone just use Proc.new and Proc#call if they’re so powerful? Why do we have more elaborate programming languages at all, and what differentiates them from each other if they’re all equivalently capable of computation?

The answers are obvious: programming languages have different degrees of expressiveness and aesthetic appeal; some of them are safe, some of them are flexible, and that’s a trade-off; some of them have better performance than others; different languages have different qualities of ecosystem.

In fact, every aspect of a programming language’s design is a trade-off — what is expressive for your work may not be expressive for someone else’s — but there is a particular sweet spot among those trade-offs for people who care about simplicity, flexibility and syntactic beauty; Ruby is in our sweet spot.

There are many languages like Ruby, but this one is ours.

Epilogue

The simple programming language demonstrated in this article is the untyped lambda calculus, and the implementations of datatypes are Church encodings. The lambda calculus is powerful because it’s Turing complete.

If you’d like to play with these implementations, please download the supplementary code, where you can find specs for everything I’ve shown you.

If you’re feeling brave you can start from scratch and try to make all these specs pass with your own proc-based implementations; if you’re not feeling brave, there’s another branch which walks you through writing those implementations (e.g. implementing ADD, MULTIPLY and POWER) as well as doing a bit of refactoring (e.g. extracting a proc called INJECT).

Enjoy!