Programming with Nothing
Contents
 Ruining Ruby
 Thinking procs
 Aiming high
 Numbers
 Booleans
 Predicates
 Numeric operations
 Lists, briefly
 Strings, briefly
 Victory
 Why?
 Epilogue
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 thirdparty 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:
 creating procs; and
 calling procs.
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.

Procs are plumbing for moving values around your program. Consider what happens when you call a proc:
lambda { x x + 1 }.call(41)
The value that’s provided as an argument to the call, in this case
41
, flows into the parameter of the block, in this casex
, and then flows out of the parameter to all the places where that parameter is used, so Ruby ends up evaluating41 + 1
. It’s the rest of the language that does the actual work; procs just connect parts of the program together and make values flow to where they’re needed. 
Procs don’t need to take multiple arguments. If you’ve got a proc that takes multiple arguments…
lambda { x, y x + y }.call(3, 4)
…you can always rewrite it as nested singleargument procs:
lambda { x lambda { y x + y } }.call(3).call(4)
Here the outer proc takes one argument,
x
, and returns the inner proc, which also takes one argument,y
. We can call the outer proc with a value forx
and then call the inner proc with a value fory
, and we get the same result as in the multiargument case. (This is called “currying”, incidentally, and in Ruby 1.9 you can useProc#curry
to do this transformation.)Since we’re trying to remove as many features of Ruby as possible, let’s restrict ourselves to creating and calling singleargument procs; it won’t make things much worse.

The only way to find out about the code inside a proc is to call it. This means that two procs can be considered equal if they behave identically when called, even if their internal code is different. (This idea is called extensionality.)
For example, if you have a proc which takes an argument and then simply calls another proc
p
with that argument…lambda { x p.call(x) }
…then the whole construction is indistinguishable from just
p
, because it does exactly the same thing. This is a refactoring opportunity: if you see this pattern in your program you may choose to eliminate it, and under certain circumstances (which we’ll see later) you might intentionally introduce it. 
There are four ways to explicitly create a proc:
Proc.new { x x + 1 } proc { x x + 1 } lambda { x x + 1 } > x { x + 1 }
You can use
Proc.new
,Kernel.proc
orKernel.lambda
, and in Ruby 1.9 you can use the “stabby lambda” syntax.(These are all roughly equivalent. Procs created with
Proc.new
andKernel.proc
do differ slightly from those created withKernel.lambda
and>
in how they handle multiple arguments and explicitreturn
s, but we’re not using either of those language features.)Similarly, there are four ways to call a proc:
p.call(41) p[41] p === 41 p.(41)
You can use
Proc#call
orProc#[]
, and in Ruby 1.9 you can useProc#===
(in case you want to put your proc in acase
statement) andProc#()
.For this article I’m just going to choose a syntax and stick with it. Instead of saying…
lambda { x x + 1 }.call(41)
…I’m going to say…
> x { x + 1 }[41]
…which makes it easier to see the body and argument of the proc. This isn’t necessarily the best syntax for procs, it’s just the most convenient for what we’re going to do.
Aiming high
Our goal will be to write the wellknown 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 fullfeatured 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 builtin 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 Fixnum
s 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, nonnegative 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 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 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 procbased 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 procbased 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 procbased 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 procbased numbers into Ruby numbers, so we can define a #to_boolean
method that can turn this TRUE
and FALSE
into Rubynative 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 proconly 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:
 “take an argument
y
”; then  “call
b
withx
to get a proc”; and finally  “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 procbased implementation that will work with procbased 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 procbased 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
:
 if
5
is less than or equal to17
, which it is, then subtract5
from17
and call#mod
again with the result, i.e. try12
modulo5
; 5
is less than or equal to12
, so try7
modulo5
;5
is less than or equal to7
, so try2
modulo5
;5
is not less than or equal to2
, so return the result2
.
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 lessthanorequalto 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 procbased 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 nonstrict (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 singleargument proc, because all of our values are singleargument 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 nonstrict 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 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
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 twoelement 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 generalpurpose 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]]]] }]
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 datareading 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 aweinspiring 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 tradeoff; 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 tradeoff — what is expressive for your work may not be expressive for someone else’s — but there is a particular sweet spot among those tradeoffs 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 procbased 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!