Read Understanding Computation Online

Authors: Tom Stuart

Tags: #COMPUTERS / Programming / General

Understanding Computation (6 page)

BOOK: Understanding Computation
7.1Mb size Format: txt, pdf, ePub
ads

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:

  • If the condition can be reduced, then reduce it, resulting in a reduced
    conditional statement and an unchanged environment.

  • If the condition is the expression «
    true
    »,
    reduce to the consequence statement and an unchanged environment.

  • If the condition is the expression «
    false
    »,
    reduce to the alternative statement and an unchanged environment.

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:

  • If the first statement is a «
    do-nothing
    »
    statement, reduce to the second statement and the original environment.

  • If the first statement is not «
    do-nothing
    »,
    then reduce it, resulting in a new sequence (the reduced first statement followed by
    the second statement) and a reduced environment.

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
»).

BOOK: Understanding Computation
7.1Mb size Format: txt, pdf, ePub
ads

Other books

Grey Eyes by Frank Christopher Busch
Erotic Research by Mari Carr
With a Vengeance by Annette Dashofy
Little Chicago by Adam Rapp
Ransom by Lee Rowan
Dangerous Surrender by Carrie Kelly
Sylvia Day - [Georgian 04] by Don't Tempt Me
Private Dancer by Nevea Lane