Understanding Computation (35 page)

During the
FizzBuzz exercise, we used recursive functions like
MOD
and
RANGE
to demonstrate the use of
the Z combinator. This is convenient, because it lets us translate from an unconstrained
recursive Ruby implementation to a proc-only one without changing the structure of the
code, but technically, we can implement these functions without the Z combinator by taking
advantage of the behavior of Church numerals.

For example, our implementation of
MOD[m][n]
works by repeatedly subtracting
n
from
m
as long as
n
<= m
, always checking the condition to decide whether to
make the next recursive call. But we can get the same result by
blindly performing the action “subtract
n
from
m
if
n <= m
” a fixed number of
times instead of using recursion to dynamically control the
repetition. We don’t know exactly how many times we need to repeat it,
but we do know that
m
times is
definitely enough (for the worst case where
n
is
1
),
and it doesn’t hurt to do it more times than necessary:

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

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

We can therefore rewrite
MOD
to make use of a proc that takes a number and either subtracts
n
from it (if it’s greater than
n
) or returns it untouched. This
proc gets called
m
times on
m
itself to give the final
answer:

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

This version of
MOD
works
just as well as the recursive one:

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

Although this implementation is arguably simpler than the original, it is both harder
to read and less efficient in general, because it always performs a worst-case number of
repeated calls instead of stopping as soon as possible. It’s also not extensionally equal
to the original, because the old version of
MOD
would
loop forever if we asked it to divide by
ZERO
(the
condition
n <= m
would never become false), whereas
this implementation just returns its first argument:

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

RANGE
is slightly more challenging, but we can use
a trick similar to the one that makes
DECREMENT
work:
design a function that, when called
n
times on some
initial argument, returns a list of
n
numbers from the
desired range. As with
DECREMENT
, the secret is to use
a pair to store both the resulting list and the information needed by the next
iteration:

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

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

This is easy to rewrite with procs:

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

Now we just need to implement
RANGE
so that it calls
COUNTDOWN
the right number of times (the
range from
m
to
n
always has
m - n
+ 1
elements) and unpacks the result list from the final
pair:

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

Again, this combinator-free version works just
fine:

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

In this context, the word
calculus
means a system of rules
for manipulating strings of symbols.
^[
49
]
The native syntax of the lambda calculus uses the Greek letter lambda (λ) in
place of Ruby’s
->
symbol; for instance,
ONE
is written as
λp.λx.p
x
.

Before we can
implement
#reduce
, we need another
operation called
#replace
, which finds occurrences of a
particular variable inside an expression and replaces them with some other
expression:

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

This works in the obvious way on variables and calls:

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

For functions, the situation is more complicated.
#replace
only acts on the body of a function, and it only replaces
free variables
—that is, variables that haven’t been
bound
to the function by being named as its parameter:

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

This lets us replace occurrences of a variable throughout an
expression without accidentally changing unrelated variables that
happen to have the same name:

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

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