Understanding Computation (30 page)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Here’s
DECREMENT
in
action:

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

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

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

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

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

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

For example, to calculate
17
modulo
5
:

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

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

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

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

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