Understanding Computation (38 page)

When
#divide
is called with sensible arguments, it
always returns a result, just like a primitive recursive function:

>>
divide
(
six
,
two
)
=> 3
>>
def
ten
increment
(
multiply
(
three
,
three
))
end
=> nil
>>
ten
=> 10
>>
divide
(
ten
,
three
)
=> 3

But
#divide
doesn’t have to return an answer, because
#minimize
can loop forever.
#divide
by zero is undefined:

>>
divide
(
six
,
zero
)
SystemStackError: stack level too deep

With
#minimize
, it’s possible to fully simulate a
Turing machine by repeatedly calling the primitive recursive function that performs a single
simulation step. The simulation will continue until the machine halts—and if that never
happens, it’ll run forever.

The
SKI combinator calculus
is a
system of rules for manipulating the syntax of expressions,
just like the lambda calculus. Although the lambda calculus is already
very simple, it still has three kinds of expression—variables, functions,
and calls—and we saw in
Semantics
that
variables make the reduction rules a bit complicated. The SKI calculus is
even simpler, with only two kinds of expression—calls and alphabetic
symbols
—and much easier rules. All of its power
comes from the three special symbols
S
,
K
, and
I
(called
combinators
),
each
of which has its own reduction rule:

For example, here’s one way of
reducing the expression
I[S][K][S][I[K]]
:

I[S][K][S][I[K]] → S[K][S][I[K]]
(reduce
I[S]
to
S
)
→ S[K][S][K]
(reduce
I[K]
to
K
)
→ K[K][S[K]]
(reduce
S[K][S][K]
to
K[K][S[K]]
)
→ K
(reduce
K[K][S[K]]
to
K
)

Notice that there’s no lambda-calculus-style variable replacement
going on here, just symbols being reordered, duplicated, and discarded
according to the reduction rules.

It’s easy to implement the abstract syntax of SKI
expressions:

class
SKISymbol
<
Struct
.
new
(
:name
)
def
to_s
name
.
to_s
end
def
inspect
to_s
end
end
class
SKICall
<
Struct
.
new
(
:left
,
:right
)
def
to_s
"
#{
left
}
[
#{
right
}
]"
end
def
inspect
to_s
end
end
class
SKICombinator
<
SKISymbol
end
S
,
K
,
I
=
[
:S
,
:K
,
:I
].
map
{
|
name
|
SKICombinator
.
new
(
name
)
}

These classes and objects can be used to build abstract syntax trees
of SKI expressions:

>>
x
=
SKISymbol
.
new
(
:x
)
=> x
>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
S
,
K
),
SKICall
.
new
(
I
,
x
))
=> S[K][I[x]]

We can give the SKI calculus a small-step operational semantics by implementing its
reduction rules and applying those rules inside expressions. First, we’ll define a method
called
#call
on the
SKICombinator
instances;
S
,
K
, and
I
each get their own
definition of
#call
that implements their reduction
rule:

# reduce S[
a
][
b
][
c
] to
a
[
c
][
b
[
c
]]
def
S
.
call
(
a
,
b
,
c
)
SKICall
.
new
(
SKICall
.
new
(
a
,
c
),
SKICall
.
new
(
b
,
c
))
end
# reduce K[
a
][
b
] to
a
def
K
.
call
(
a
,
b
)
a
end
# reduce I[
a
] to
a
def
I
.
call
(
a
)
a
end

Okay, so this gives us a way to apply the rules of the calculus if
we already know what arguments a combinator is being called with…

>>
y
,
z
=
SKISymbol
.
new
(
:y
),
SKISymbol
.
new
(
:z
)
=> [y, z]
>>
S
.
call
(
x
,
y
,
z
)
=> x[z][y[z]]

…but to use
#call
with a real SKI expression, we need
to extract a combinator and arguments from it. This is a bit fiddly since an expression is
represented as a binary tree of
SKICall
objects:

>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
SKICall
.
new
(
S
,
x
),
y
),
z
)
=> S[x][y][z]
>>
combinator
=
expression
.
left
.
left
.
left
=> S
>>
first_argument
=
expression
.
left
.
left
.
right
=> x
>>
second_argument
=
expression
.
left
.
right
=> y
>>
third_argument
=
expression
.
right
=> z
>>
combinator
.
call
(
first_argument
,
second_argument
,
third_argument
)
=> x[z][y[z]]

To make this structure easier to handle, we can define the methods
#combinator
and
#arguments
on abstract syntax trees:

class
SKISymbol
def
combinator
self
end
def
arguments
[]
end
end
class
SKICall
def
combinator
left
.
combinator
end
def
arguments
left
.
arguments
+
[
right
]
end
end

This gives us an easy way to discover which combinator to call and
what arguments to pass to it:

>>
expression
=> S[x][y][z]
>>
combinator
=
expression
.
combinator
=> S
>>
arguments
=
expression
.
arguments
=> [x, y, z]
>>
combinator
.
call
(
*
arguments
)
=> x[z][y[z]]

That works fine for
S[x][y][z]
, but there are a couple
of problems in the general case. First, the
#combinator
method just returns the leftmost
symbol
from an expression, but that
symbol isn’t necessarily a combinator:

>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
x
,
y
),
z
)
=> x[y][z]
>>
combinator
=
expression
.
combinator
=> x
>>
arguments
=
expression
.
arguments
=> [y, z]
>>
combinator
.
call
(
*
arguments
)
NoMethodError: undefined method `call' for x:SKISymbol

And second, even if the leftmost symbol
is
a combinator, it isn’t
necessarily being called with the right number of arguments:

>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
S
,
x
),
y
)
=> S[x][y]
>>
combinator
=
expression
.
combinator
=> S
>>
arguments
=
expression
.
arguments
=> [x, y]
>>
combinator
.
call
(
*
arguments
)
ArgumentError: wrong number of arguments (2 for 3)