Understanding Computation (32 page)

Thankfully this noncheating version of
MOD
still
works:

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

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

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

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

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

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

And they work like this:

>>
my_list
=
UNSHIFT
[
UNSHIFT
[
UNSHIFT
[
EMPTY
][
THREE
]
][
TWO
]
][
ONE
]
=> #
>>
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
)
=> [#, #, #]
>>
to_array
(
my_list
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [1, 2, 3]

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

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

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

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

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

Does this work?

>>
my_range
=
RANGE
[
ONE
][
FIVE
]
=> #
>>
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
]
=> #
>>
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.