Understanding Computation (5 page)

Once all the implementations of
#reduce
have been updated to support
environments, we also need to redefine our virtual machine to maintain
an environment and provide it to
#reduce
:

Object
.
send
(
:remove_const
,
:Machine
)
# forget about the old Machine class
class
Machine
<
Struct
.
new
(
:expression
,
:environment
)
def
step
self
.
expression
=
expression
.
reduce
(
environment
)
end
def
run
while
expression
.
reducible?
puts
expression
step
end
puts
expression
end
end

The machine’s definition of
#run
remains unchanged, but it has a new
environment
attribute that is used
by its new implementation of
#step
.

We can now perform reductions on expressions that contain
variables, as long as we also supply an environment that contains the
variables’ values:

>>
Machine
.
new
(
Add
.
new
(
Variable
.
new
(
:x
),
Variable
.
new
(
:y
)),
{
x
:
Number
.
new
(
3
),
y
:
Number
.
new
(
4
)
}
)
.
run
x + y
3 + y
3 + 4
7
=> nil

The introduction of an environment completes our operational
semantics of expressions. We’ve designed an abstract machine that
begins with an initial expression and environment, and then uses the
current expression and environment to produce a new expression in each
small reduction step, leaving the environment
unchanged.

We can now look at
implementing a different kind of program construct:
statements
. The purpose of an expression is to
be evaluated to produce another expression; a statement, on the other
hand, is evaluated to make some change to the state of the abstract
machine. Our machine’s only piece of state (aside from the current
program) is the environment, so we’ll allow
Simple
statements to produce a new
environment that can replace the current one.

The simplest possible
statement is one that does nothing: it can’t be reduced,
so it can’t have any effect on the environment. That’s easy to
implement:

class
DoNothing
def
to_s
'do-nothing'
end
def
inspect
"«
#{
self
}
»"
end
def
==
(
other_statement
)
other_statement
.
instance_of?
(
DoNothing
)
end
def
reducible?
false
end
end

A statement that does nothing might seem pointless, but it’s
convenient to have a special statement that represents a program whose
execution has completed successfully. We’ll arrange for other
statements to eventually reduce to «
do-nothing
» once they’ve finished doing
their work.

The simplest example of a statement that actually does something useful is an
assignment
like «
x = x + 1
»,
but before we can implement assignment, we need to decide what its reduction rules should
be.

An
assignment statement consists of a variable name
(
x
), an equals symbol, and an
expression («
x + 1
»). If the
expression within the assignment is reducible, we can just reduce it
according to the expression reduction rules and end up with a new
assignment statement containing the reduced expression. For example,
reducing «
x = x + 1
» in an
environment where the variable
x
has the value «
2
» should leave us
with the statement «
x = 2 + 1
», and
reducing it again should produce «
x =
3
».

But then what? If the expression is already a value like «
3
», then we should just perform the assignment, which means updating the
environment to associate that value with the appropriate variable name. So reducing a
statement needs to produce not just a new, reduced statement but also a new environment,
which will sometimes be different from the environment in
which the reduction was performed.

>>
old_environment
=
{
y
:
Number
.
new
(
5
)
}
=> {:y=>«5»}
>>
new_environment
=
old_environment
.
merge
({
x
:
Number
.
new
(
3
)
})
=> {:y=>«5», :x=>«3»}
>>
old_environment
=> {:y=>«5»}

So reducing «
x = 3
» in an
empty environment should produce the new environment
{ x: Number.new(3) }
, but we also expect the
statement to be reduced somehow; otherwise, our abstract machine will
keep assigning «
3
» to
x
forever. That’s what «
do-nothing
» is for: a completed assignment
reduces to «
do-nothing
», indicating
that reduction of the statement has finished and that whatever’s in
the new environment may be considered its result.

To summarize, the reduction rules for assignment are:

This gives us enough information to implement an
Assign
class. The only difficulty is that
Assign#reduce
needs to return both
a statement and an environment—Ruby
methods can only return a single object—but we can
pretend to return two objects by putting them into a two-element array
and returning that.

class
Assign
<
Struct
.
new
(
:name
,
:expression
)
def
to_s
"
#{
name
}
=
#{
expression
}
"
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
true
end
def
reduce
(
environment
)
if
expression
.
reducible?
[
Assign
.
new
(
name
,
expression
.
reduce
(
environment
)),
environment
]
else
[
DoNothing
.
new
,
environment
.
merge
({
name
=>
expression
})
]
end
end
end

As with expressions, we can manually evaluate an assignment
statement by repeatedly reducing it until it can’t be reduced any
more:

>>
statement
=
Assign
.
new
(
:x
,
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)))
=> «x = x + 1»
>>
environment
=
{
x
:
Number
.
new
(
2
)
}
=> {:x=>«2»}
>>
statement
.
reducible?
=> true
>>
statement
,
environment
=
statement
.
reduce
(
environment
)
=> [«x = 2 + 1», {:x=>«2»}]
>>
statement
,
environment
=
statement
.
reduce
(
environment
)
=> [«x = 3», {:x=>«2»}]
>>
statement
,
environment
=
statement
.
reduce
(
environment
)
=> [«do-nothing», {:x=>«3»}]
>>
statement
.
reducible?
=> false