Understanding Computation (6 page)

This process is even more laborious than manually reducing
expressions, so let’s reimplement our virtual machine to handle
statements, showing the current statement and environment at each
reduction step:

Object
.
send
(
:remove_const
,
:Machine
)
class
Machine
<
Struct
.
new
(
:statement
,
:environment
)
def
step
self
.
statement
,
self
.
environment
=
statement
.
reduce
(
environment
)
end
def
run
while
statement
.
reducible?
puts
"
#{
statement
}
,
#{
environment
}
"
step
end
puts
"
#{
statement
}
,
#{
environment
}
"
end
end

Now the machine can do the work for us again:

>>
Machine
.
new
(
Assign
.
new
(
:x
,
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
))),
{
x
:
Number
.
new
(
2
)
}
)
.
run
x = x + 1, {:x=>«2»}
x = 2 + 1, {:x=>«2»}
x = 3, {:x=>«2»}
do-nothing, {:x=>«3»}
=> nil

We can see that the machine is still performing expression
reduction steps («
x + 1
» to
«
2 + 1
» to «
3
»), but they now happen inside a statement
instead of at the top level of the syntax tree.

Now that we know how statement reduction works, we can extend it
to support other kinds of statements. Let’s begin with
conditional statements like «
if (x) { y = 1 } else { y = 2 }
», which
contain an expression called
the
condition
(«
x
»), and two statements that we’ll call the
consequence
(«
y =
1
») and the
alternative
(«
y = 2
»).
^[
8
]
The reduction rules for conditionals are
straightforward:

In this case, none of the rules changes the environment—the
reduction of the condition expression in the first rule will only
produce a new expression, not a new environment.

Here are the rules translated into an
If
class:

class
If
<
Struct
.
new
(
:condition
,
:consequence
,
:alternative
)
def
to_s
"if (
#{
condition
}
) {
#{
consequence
}
} else {
#{
alternative
}
}"
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
true
end
def
reduce
(
environment
)
if
condition
.
reducible?
[
If
.
new
(
condition
.
reduce
(
environment
),
consequence
,
alternative
),
environment
]
else
case
condition
when
Boolean
.
new
(
true
)
[
consequence
,
environment
]
when
Boolean
.
new
(
false
)
[
alternative
,
environment
]
end
end
end
end

And here’s how the reduction steps look:

>>
Machine
.
new
(
If
.
new
(
Variable
.
new
(
:x
),
Assign
.
new
(
:y
,
Number
.
new
(
1
)),
Assign
.
new
(
:y
,
Number
.
new
(
2
))
),
{
x
:
Boolean
.
new
(
true
)
}
)
.
run
if (x) { y = 1 } else { y = 2 }, {:x=>«true»}
if (true) { y = 1 } else { y = 2 }, {:x=>«true»}
y = 1, {:x=>«true»}
do-nothing, {:x=>«true», :y=>«1»}
=> nil

That all works as expected, but it would be nice if we could support conditional
statements with no «
else
» clause, like «
if (x) { y = 1 }
». Fortunately, we can already do that by
writing statements like «
if (x) { y = 1 } else { do-nothing
}
», which behave as though the «
else
»
clause wasn’t there:

>>
Machine
.
new
(
If
.
new
(
Variable
.
new
(
:x
),
Assign
.
new
(
:y
,
Number
.
new
(
1
)),
DoNothing
.
new
),
{
x
:
Boolean
.
new
(
false
)
}
)
.
run
if (x) { y = 1 } else { do-nothing }, {:x=>«false»}
if (false) { y = 1 } else { do-nothing }, {:x=>«false»}
do-nothing, {:x=>«false»}
=> nil

Now that we’ve implemented assignment and conditional statements
as well as expressions, we have the building blocks for programs that
can do real work by performing calculations and making decisions. The
main restriction is that we can’t yet connect these blocks together:
we have no way to assign values to more than one variable, or to
perform more than one conditional operation, which drastically limits
the usefulness of our language.

We can fix this by defining another kind of
statement, the
sequence
, which connects two statements
like «
x = 1 + 1
» and «
y = x +
3
» to make one larger statement like «
x = 1 + 1; y =
x + 3
». Once we have sequence statements, we can use them repeatedly to build
even larger statements; for example, the sequence «
x = 1 + 1; y =
x + 3
» and the assignment «
z = y + 5
» can
be combined to make the sequence «
x = 1 + 1; y = x + 3; z = y +
5
».
^[
9
]

The reduction rules for sequences are slightly subtle:

Seeing the code may make these rules clearer:

class
Sequence
<
Struct
.
new
(
:first
,
:second
)
def
to_s
"
#{
first
}
;
#{
second
}
"
end
def
inspect
"«
#{
self
}
»"
end
def
reducible?
true
end
def
reduce
(
environment
)
case
first
when
DoNothing
.
new
[
second
,
environment
]
else
reduced_first
,
reduced_environment
=
first
.
reduce
(
environment
)
[
Sequence
.
new
(
reduced_first
,
second
),
reduced_environment
]
end
end
end

The overall effect of these rules is that, when we repeatedly
reduce a sequence, it keeps reducing its first statement until it
turns into «
do-nothing
», then
reduces to its second statement. We can see this happening when we run
a sequence in the virtual machine:

>>
Machine
.
new
(
Sequence
.
new
(
Assign
.
new
(
:x
,
Add
.
new
(
Number
.
new
(
1
),
Number
.
new
(
1
))),
Assign
.
new
(
:y
,
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
3
)))
),
{}
)
.
run
x = 1 + 1; y = x + 3, {}
x = 2; y = x + 3, {}
do-nothing; y = x + 3, {:x=>«2»}
y = x + 3, {:x=>«2»}
y = 2 + 3, {:x=>«2»}
y = 5, {:x=>«2»}
do-nothing, {:x=>«2», :y=>«5»}
=> nil

The only really major thing still missing from
Simple
is some kind of unrestricted
looping construct, so to finish off, let’s introduce a «
while
» statement so that programs can perform repeated
calculations an arbitrary number of times.
^[
10
]
A statement like «
while (x < 5) { x = x * 3
}
» contains an expression called the
condition
(«
x < 5
») and a statement called the
body
(«
x = x * 3
»).