Understanding Computation (31 page)

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

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 (or
lazy
): we 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 behavior
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., the result of
1 + 2
does not equal
-> { 1 + 2
}
), 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 (from
Equality
) 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 we said
MOD
, what we 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 we call the Y
combinator with a proc, it will call that proc
with the proc
itself as the first argument
. So, if we 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 inert
-> 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.

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