Free Understanding Computation by Tom Stuart
Authors: Tom Stuart
4
>>
proc
=
eval
(
LessThan
.
new
(
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)),
Number
.
new
(
3
))
.
to_ruby
)
=> #
>>
proc
.
call
(
environment
)
=> false
Statements
We canspecify the denotational semantics of statements in a
similar way, although remember from the operational semantics that
evaluating a statement produces a new environment rather than a value.
This means that
Assign#to_ruby
needs
to produce code for a proc whose result is an updated environment
hash:
class
Assign
def
to_ruby
"-> e { e.merge({
#{
name
.
inspect
}
=> (
#{
expression
.
to_ruby
}
).call(e) }) }"
end
end
Again, we can check this on the console:
>>
statement
=
Assign
.
new
(
:y
,
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)))
=> «y = x + 1»
>>
statement
.
to_ruby
=> "-> e { e.merge({ :y => (-> e { (-> e { e[:x] }).call(e) + (-> e { 1 }).call(e) })
.call(e) }) }"
>>
proc
=
eval
(
statement
.
to_ruby
)
=> #
>>
proc
.
call
({
x
:
3
})
=> {:x=>3, :y=>4}
As always, the semantics of
DoNothing
is very simple:
class
DoNothing
def
to_ruby
'-> e { e }'
end
end
For conditional statements, we can translate Simple ’s
«
if (
…
) {
…
} else {
…
}
» into a Ruby
if
…
then
…
else
…
end
, making sure that the environment gets to all
the places where it’s needed:
class
If
def
to_ruby
"-> e { if (
#{
condition
.
to_ruby
}
).call(e)"
+
" then (
#{
consequence
.
to_ruby
}
).call(e)"
+
" else (
#{
alternative
.
to_ruby
}
).call(e)"
+
" end }"
end
end
As in big-step operational semantics, we need to be careful about
specifying the sequence statement: the result of evaluating the first
statement is used as the environment for evaluating the second.
class
Sequence
def
to_ruby
"-> e { (
#{
second
.
to_ruby
}
).call((
#{
first
.
to_ruby
}
).call(e)) }"
end
end
And lastly, as with conditionals, we cantranslate «
while
»
statements into procs that use Ruby
while
to repeatedly execute the body before
returning the final environment:
class
While
def
to_ruby
"-> e {"
+
" while (
#{
condition
.
to_ruby
}
).call(e); e = (
#{
body
.
to_ruby
}
).call(e); end;"
+
" e"
+
" }"
end
end
Even a simple «
while
» can have
quite a verbose denotation, so it’s worth getting the Ruby interpreter
to check that its meaning iscorrect:
>>
statement
=
While
.
new
(
LessThan
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
5
)),
Assign
.
new
(
:x
,
Multiply
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
3
)))
)
=> «while (x < 5) { x = x * 3 }»
>>
statement
.
to_ruby
=> "-> e { while (-> e { (-> e { e[:x] }).call(e) < (-> e { 5 }).call(e) }).call(e);
e = (-> e { e.merge({ :x => (-> e { (-> e { e[:x] }).call(e) * (-> e { 3 }).call(e)
}).call(e) }) }).call(e); end; e }"
>>
proc
=
eval
(
statement
.
to_ruby
)
=> #
>>
proc
.
call
({
x
:
1
})
=> {:x=>9}
Comparing Semantic Styles
«
while
» is a goodexample of the difference between small-step, big-step,
and denotational semantics.
The small-step operationalsemantics of «
while
»
is written as a reduction rule for an abstract machine. The overall
looping behavior isn’t part of the rule’s action—reduction just turns
a «
while
» statement into an
«
if
» statement—but it emerges as a
consequence of the future reductions performed by the machine. To
understand what «
while
» does, we
need to look at all of the small-step rules and work out how they
interact over the course of a Simple program’s execution.
«
while
»’s big-step operationalsemantics is written as an evaluation rule that shows how to compute the final
environment directly. The rule contains a recursive call to itself, so there’s an explicit
indication that «
while
» will cause a loop during
evaluation, but it’s not quite the kind of loop that a Simple programmer would recognize. Big-step rules are written in a recursive
style, describing the complete evaluation of an expression or statement in terms of the
>>
proc
=
eval
(
LessThan
.
new
(
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)),
Number
.
new
(
3
))
.
to_ruby
)
=> #
>>
proc
.
call
(
environment
)
=> false
Statements
We canspecify the denotational semantics of statements in a
similar way, although remember from the operational semantics that
evaluating a statement produces a new environment rather than a value.
This means that
Assign#to_ruby
needs
to produce code for a proc whose result is an updated environment
hash:
class
Assign
def
to_ruby
"-> e { e.merge({
#{
name
.
inspect
}
=> (
#{
expression
.
to_ruby
}
).call(e) }) }"
end
end
Again, we can check this on the console:
>>
statement
=
Assign
.
new
(
:y
,
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)))
=> «y = x + 1»
>>
statement
.
to_ruby
=> "-> e { e.merge({ :y => (-> e { (-> e { e[:x] }).call(e) + (-> e { 1 }).call(e) })
.call(e) }) }"
>>
proc
=
eval
(
statement
.
to_ruby
)
=> #
>>
proc
.
call
({
x
:
3
})
=> {:x=>3, :y=>4}
As always, the semantics of
DoNothing
is very simple:
class
DoNothing
def
to_ruby
'-> e { e }'
end
end
For conditional statements, we can translate Simple ’s
«
if (
…
) {
…
} else {
…
}
» into a Ruby
if
…
then
…
else
…
end
, making sure that the environment gets to all
the places where it’s needed:
class
If
def
to_ruby
"-> e { if (
#{
condition
.
to_ruby
}
).call(e)"
+
" then (
#{
consequence
.
to_ruby
}
).call(e)"
+
" else (
#{
alternative
.
to_ruby
}
).call(e)"
+
" end }"
end
end
As in big-step operational semantics, we need to be careful about
specifying the sequence statement: the result of evaluating the first
statement is used as the environment for evaluating the second.
class
Sequence
def
to_ruby
"-> e { (
#{
second
.
to_ruby
}
).call((
#{
first
.
to_ruby
}
).call(e)) }"
end
end
And lastly, as with conditionals, we cantranslate «
while
»
statements into procs that use Ruby
while
to repeatedly execute the body before
returning the final environment:
class
While
def
to_ruby
"-> e {"
+
" while (
#{
condition
.
to_ruby
}
).call(e); e = (
#{
body
.
to_ruby
}
).call(e); end;"
+
" e"
+
" }"
end
end
Even a simple «
while
» can have
quite a verbose denotation, so it’s worth getting the Ruby interpreter
to check that its meaning iscorrect:
>>
statement
=
While
.
new
(
LessThan
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
5
)),
Assign
.
new
(
:x
,
Multiply
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
3
)))
)
=> «while (x < 5) { x = x * 3 }»
>>
statement
.
to_ruby
=> "-> e { while (-> e { (-> e { e[:x] }).call(e) < (-> e { 5 }).call(e) }).call(e);
e = (-> e { e.merge({ :x => (-> e { (-> e { e[:x] }).call(e) * (-> e { 3 }).call(e)
}).call(e) }) }).call(e); end; e }"
>>
proc
=
eval
(
statement
.
to_ruby
)
=> #
>>
proc
.
call
({
x
:
1
})
=> {:x=>9}
Comparing Semantic Styles
«
while
» is a goodexample of the difference between small-step, big-step,
and denotational semantics.
The small-step operationalsemantics of «
while
»
is written as a reduction rule for an abstract machine. The overall
looping behavior isn’t part of the rule’s action—reduction just turns
a «
while
» statement into an
«
if
» statement—but it emerges as a
consequence of the future reductions performed by the machine. To
understand what «
while
» does, we
need to look at all of the small-step rules and work out how they
interact over the course of a Simple program’s execution.
«
while
»’s big-step operationalsemantics is written as an evaluation rule that shows how to compute the final
environment directly. The rule contains a recursive call to itself, so there’s an explicit
indication that «
while
» will cause a loop during
evaluation, but it’s not quite the kind of loop that a Simple programmer would recognize. Big-step rules are written in a recursive
style, describing the complete evaluation of an expression or statement in terms of the
Similar Books
Torchworld: Outsiders Collection
Dannielle Levan
Losing Faith
Scotty Cade
The Midnight Hour
Neil Davies
The Willard
LeAnne Burnett Morse
Green Ace
Stuart Palmer
Seven Kisses: A Beauty and the Beast Dark Romance
Giselle Renarde
Noble Destiny
Katie MacAlister
Daniel
Henning Mankell
Bringing Down the Krays
Bobby Teale