Understanding Computation (4 page)

Having implemented
#reduce
for these kinds of expressions, we can call it repeatedly to fully
evaluate an expression via a series of small steps:

>>
expression
=
Add
.
new
(
Multiply
.
new
(
Number
.
new
(
1
),
Number
.
new
(
2
)),
Multiply
.
new
(
Number
.
new
(
3
),
Number
.
new
(
4
))
)
=> «1 * 2 + 3 * 4»
>>
expression
.
reducible?
=> true
>>
expression
=
expression
.
reduce
=> «2 + 3 * 4»
>>
expression
.
reducible?
=> true
>>
expression
=
expression
.
reduce
=> «2 + 12»
>>
expression
.
reducible?
=> true
>>
expression
=
expression
.
reduce
=> «14»
>>
expression
.
reducible?
=> false

By maintaining a
piece of state—the current expression—and repeatedly
calling
#reducible?
and
#reduce
on it until we end up with a value,
we’re manually simulating the operation of an abstract machine for
evaluating expressions. To save ourselves some effort, and to make the
idea of the abstract machine more concrete, we can easily write some
Ruby code that does the work for us. Let’s wrap up that code and state
together in a class and call it a
virtual
machine
:

class
Machine
<
Struct
.
new
(
:expression
)
def
step
self
.
expression
=
expression
.
reduce
end
def
run
while
expression
.
reducible?
puts
expression
step
end
puts
expression
end
end

This allows us to instantiate a virtual machine
with an expression, tell it to
#run
, and watch the steps of reduction
unfold:

>>
Machine
.
new
(
Add
.
new
(
Multiply
.
new
(
Number
.
new
(
1
),
Number
.
new
(
2
)),
Multiply
.
new
(
Number
.
new
(
3
),
Number
.
new
(
4
))
)
)
.
run
1 * 2 + 3 * 4
2 + 3 * 4
2 + 12
14
=> nil

It isn’t difficult to extend this implementation to support other simple values and
operations: subtraction and division; Boolean
true
and
false
; Boolean
and
,
or
, and
not
; comparison operations for numbers that return Booleans; and so on. For
example, here are implementations of Booleans and the less-than operator:

class
Boolean
<
Struct
.
new
(
:value
)
def
to_s
value
.
to_s
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
false
end
end
class
LessThan
<
Struct
.
new
(
:left
,
:right
)
def
to_s
"
#{
left
}
<
#{
right
}
"
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
true
end
def
reduce
if
left
.
reducible?
LessThan
.
new
(
left
.
reduce
,
right
)
elsif
right
.
reducible?
LessThan
.
new
(
left
,
right
.
reduce
)
else
Boolean
.
new
(
left
.
value
<
right
.
value
)
end
end
end

Again, this allows us to reduce a boolean expression in small
steps:

>>
Machine
.
new
(
LessThan
.
new
(
Number
.
new
(
5
),
Add
.
new
(
Number
.
new
(
2
),
Number
.
new
(
2
)))
)
.
run
5 < 2 + 2
5 < 4
false
=> nil

So far, so straightforward: we have begun to specify the
operational semantics of a language by implementing a virtual machine
that can evaluate it. At the moment the state of this virtual machine
is just the current expression, and the behavior of the machine is
described by a collection of rules that govern how that state changes
when the machine runs. We’ve implemented the machine as a program that
keeps track of the current expression and keeps reducing it, updating
the expression as it goes, until no more reductions can be
performed.

But this language of simple algebraic expressions isn’t very
interesting, and doesn’t have many of the features that we expect from
even the simplest programming language, so let’s build it out to be
more sophisticated and look more like a language in which we could
write useful programs.

First off, there’s something obviously missing from
Simple
: variables. In any useful language, we’d expect to be able to talk
about values using meaningful names rather than the literal values themselves. These names
provide a layer of indirection so that the same code can be used to process many different
values, including values that come from outside the program and therefore aren’t even
known when the code is written.

We can introduce a new class of expression,
Variable
, to represent variables in
Simple
:

class
Variable
<
Struct
.
new
(
:name
)
def
to_s
name
.
to_s
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
true
end
end

To be able to reduce a variable, we need the abstract machine to store a mapping from
variable names onto their values, an
environment
, as well as the
current expression. In Ruby, we can implement this mapping as a hash, using symbols as
keys and expression objects as values; for example, the hash
{ x:
Number.new(2), y: Boolean.new(false) }
is an environment that associates the
variables
x
and
y
with a
Simple
number and Boolean, respectively.

Given an environment, we can easily implement
Variable#reduce
: it just looks up the
variable’s name in the environment and returns its value.

class
Variable
def
reduce
(
environment
)
environment
[
name
]
end
end

Notice that we’re now
passing an
environment
argument into
#reduce
, so we’ll need to revise the other
expression classes’ implementations of
#reduce
to both accept and provide this
argument:

class
Add
def
reduce
(
environment
)
if
left
.
reducible?
Add
.
new
(
left
.
reduce
(
environment
)
,
right
)
elsif
right
.
reducible?
Add
.
new
(
left
,
right
.
reduce
(
environment
)
)
else
Number
.
new
(
left
.
value
+
right
.
value
)
end
end
end
class
Multiply
def
reduce
(
environment
)
if
left
.
reducible?
Multiply
.
new
(
left
.
reduce
(
environment
)
,
right
)
elsif
right
.
reducible?
Multiply
.
new
(
left
,
right
.
reduce
(
environment
)
)
else
Number
.
new
(
left
.
value
*
right
.
value
)
end
end
end
class
LessThan
def
reduce
(
environment
)
if
left
.
reducible?
LessThan
.
new
(
left
.
reduce
(
environment
)
,
right
)
elsif
right
.
reducible?
LessThan
.
new
(
left
,
right
.
reduce
(
environment
)
)
else
Boolean
.
new
(
left
.
value
<
right
.
value
)
end
end
end