Understanding Computation (39 page)

To avoid both these problems, we’ll define a
#callable?
predicate for checking whether it’s appropriate to use
#call
with the results of
#combinator
and
#arguments
. A vanilla symbol is never callable, and a
combinator is only callable if the number of arguments is correct:

class
SKISymbol
def
callable?
(
*
arguments
)
false
end
end
def
S
.
callable?
(
*
arguments
)
arguments
.
length
==
3
end
def
K
.
callable?
(
*
arguments
)
arguments
.
length
==
2
end
def
I
.
callable?
(
*
arguments
)
arguments
.
length
==
1
end

>>
def
add
(
x
,
y
)
x
+
y
end
=> nil
>>
add_method
=
method
(
:add
)
=> #
>>
add_method
.
arity
=> 2

class
SKICombinator
def
callable?
(
*
arguments
)
arguments
.
length
==
method
(
:call
)
.
arity
end
end

Now we can recognize expressions where the reduction rules directly
apply:

>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
x
,
y
),
z
)
=> x[y][z]
>>
expression
.
combinator
.
callable?
(
*
expression
.
arguments
)
=> false
>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
S
,
x
),
y
)
=> S[x][y]
>>
expression
.
combinator
.
callable?
(
*
expression
.
arguments
)
=> false
>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
SKICall
.
new
(
S
,
x
),
y
),
z
)
=> S[x][y][z]
>>
expression
.
combinator
.
callable?
(
*
expression
.
arguments
)
=> true

We’re finally ready to implement the familiar
#reducible?
and
#reduce
methods for SKI expressions:

class
SKISymbol
def
reducible?
false
end
end
class
SKICall
def
reducible?
left
.
reducible?
||
right
.
reducible?
||
combinator
.
callable?
(
*
arguments
)
end
def
reduce
if
left
.
reducible?
SKICall
.
new
(
left
.
reduce
,
right
)
elsif
right
.
reducible?
SKICall
.
new
(
left
,
right
.
reduce
)
else
combinator
.
call
(
*
arguments
)
end
end
end

And that’s it! We can now evaluate SKI expressions by repeatedly
reducing them until no more reductions are possible. For example, here’s
the expression
S[K[S[I]]][K]
, which
swaps the order of its two arguments, being called with the symbols
x
and
y
:

>>
swap
=
SKICall
.
new
(
SKICall
.
new
(
S
,
SKICall
.
new
(
K
,
SKICall
.
new
(
S
,
I
))),
K
)
=> S[K[S[I]]][K]
>>
expression
=
SKICall
.
new
(
SKICall
.
new
(
swap
,
x
),
y
)
=> S[K[S[I]]][K][x][y]
>>
while
expression
.
reducible?
puts
expression
expression
=
expression
.
reduce
end
;
puts
expression
S[K[S[I]]][K][x][y]
K[S[I]][x][K[x]][y]
S[I][K[x]][y]
I[y][K[x][y]]
y[K[x][y]]
y[x]
=> nil

The SKI calculus can produce surprisingly complex behavior with its
three simple rules—so complex, in fact, that it turns out to be universal.
We can prove it’s universal by showing how to translate any lambda
calculus expression into an SKI expression that does the same thing,
effectively using the SKI calculus to give a denotational semantics for
the lambda calculus. We already know that the lambda calculus is
universal, so if the SKI calculus can completely simulate it, it follows
that the SKI calculus is universal too.

At the heart of the translation is a method called
#as_a_function_of
:

class
SKISymbol
def
as_a_function_of
(
name
)
if
self
.
name
==
name
I
else
SKICall
.
new
(
K
,
self
)
end
end
end
class
SKICombinator
def
as_a_function_of
(
name
)
SKICall
.
new
(
K
,
self
)
end
end
class
SKICall
def
as_a_function_of
(
name
)
left_function
=
left
.
as_a_function_of
(
name
)
right_function
=
right
.
as_a_function_of
(
name
)
SKICall
.
new
(
SKICall
.
new
(
S
,
left_function
),
right_function
)
end
end

The precise details of how
#as_a_function_of
works aren’t important, but
roughly speaking, it converts an SKI expression into a new one that turns
back into the original when called with an argument. For example, the
expression
S[K][I]
gets converted into
S[S[K[S]][K[K]]][K[I]]
:

>>
original
=
SKICall
.
new
(
SKICall
.
new
(
S
,
K
),
I
)
=> S[K][I]
>>
function
=
original
.
as_a_function_of
(
:x
)
=> S[S[K[S]][K[K]]][K[I]]
>>
function
.
reducible?
=> false

When
S[S[K[S]][K[K]]][K[I]]
is called with an argument,
say, the symbol
y
, it reduces back to
S[K][I]
:

>>
expression
=
SKICall
.
new
(
function
,
y
)
=> S[S[K[S]][K[K]]][K[I]][y]
>>
while
expression
.
reducible?
puts
expression
expression
=
expression
.
reduce
end
;
puts
expression
S[S[K[S]][K[K]]][K[I]][y]
S[K[S]][K[K]][y][K[I][y]]
K[S][y][K[K][y]][K[I][y]]
S[K[K][y]][K[I][y]]
S[K][K[I][y]]
S[K][I]
=> nil
>>
expression
==
original
=> true

The
name
parameter is only used if the original
expression contains a symbol with that name. In that case,
#as_a_function_of
produces something more interesting: an expression that, when
called with an argument, reduces to the original expression with that argument in place of the
symbol:

>>
original
=
SKICall
.
new
(
SKICall
.
new
(
S
,
x
),
I
)
=> S[x][I]
>>
function
=
original
.
as_a_function_of
(
:x
)
=> S[S[K[S]][I]][K[I]]
>>
expression
=
SKICall
.
new
(
function
,
y
)
=> S[S[K[S]][I]][K[I]][y]
>>
while
expression
.
reducible?
puts
expression
expression
=
expression
.
reduce
end
;
puts
expression
S[S[K[S]][I]][K[I]][y]
S[K[S]][I][y][K[I][y]]
K[S][y][I[y]][K[I][y]]
S[I[y]][K[I][y]]
S[y][K[I][y]]
S[y][I]
=> nil
>>
expression
==
original
=> false