Understanding Computation (8 page)

We can use this
idea to write implementations of a
#to_ruby
method for the
Number
and
Boolean
classes:

class
Number
def
to_ruby
"-> e {
#{
value
.
inspect
}
}"
end
end
class
Boolean
def
to_ruby
"-> e {
#{
value
.
inspect
}
}"
end
end

Here is how they behave on the console:

>>
Number
.
new
(
5
)
.
to_ruby
=> "-> e { 5 }"
>>
Boolean
.
new
(
false
)
.
to_ruby
=> "-> e { false }"

Each of these methods produces a string that happens to contain
Ruby code, and because Ruby is a language whose meaning we already
understand, we can see that both of these strings are programs that
build procs. Each proc takes an environment argument called
e
, completely ignores it, and returns a Ruby
value.

Because these denotations are strings of Ruby source code, we can
check their behavior in IRB by using
Kernel#eval
to turn
them into real, callable
Proc
objects:
^[
18
]

>>
proc
=
eval
(
Number
.
new
(
5
)
.
to_ruby
)
=> #
>>
proc
.
call
({})
=> 5
>>
proc
=
eval
(
Boolean
.
new
(
false
)
.
to_ruby
)
=> #
>>
proc
.
call
({})
=> false

To denote expressions that do use the environment, we need to decide how environments
are going to be represented in Ruby. We’ve already seen environments in our operational
semantics, and since they were implemented in Ruby, we can just reuse our earlier idea of
representing an environment as a hash. The details will need to change, though, so beware
the subtle difference: in our operational semantics, the environment lived inside the
virtual machine and associated variable names with
Simple
abstract syntax trees like
Number.new(5)
, but in our
denotational semantics, the environment exists in the language we’re translating our
programs into, so it needs to make sense in that world instead of the “outside world” of a
virtual machine.

In particular, this means that our denotational environments should associate variable
names with native Ruby values like
5
rather than with
objects representing
Simple
syntax. We can think of an
operational environment like
{ x: Number.new(5) }
as
having a denotation of
'{ x: 5 }'
in the language we’re
translating into, and we just need to keep our heads straight because both the
implementation metalanguage and the denotation language happen to be Ruby.

Now we know that the environment will be a hash, we can implement
Variable#to_ruby
:

class
Variable
def
to_ruby
"-> e { e[
#{
name
.
inspect
}
] }"
end
end

This translates a variable expression into the source code of a
Ruby proc that looks up the appropriate value in the environment
hash:

>>
expression
=
Variable
.
new
(
:x
)
=> «x»
>>
expression
.
to_ruby
=> "-> e { e[:x] }"
>>
proc
=
eval
(
expression
.
to_ruby
)
=> #
>>
proc
.
call
({
x
:
7
})
=> 7

An important aspect of denotational semantics is that it’s
compositional
: the denotation of a program is
constructed from the denotations of its parts. We can see this
compositionality in practice when we move onto denoting larger
expressions like
Add
,
Multiply
, and
LessThan
:

class
Add
def
to_ruby
"-> e { (
#{
left
.
to_ruby
}
).call(e) + (
#{
right
.
to_ruby
}
).call(e) }"
end
end
class
Multiply
def
to_ruby
"-> e { (
#{
left
.
to_ruby
}
).call(e) * (
#{
right
.
to_ruby
}
).call(e) }"
end
end
class
LessThan
def
to_ruby
"-> e { (
#{
left
.
to_ruby
}
).call(e) < (
#{
right
.
to_ruby
}
).call(e) }"
end
end

Here we’re using string concatenation
to compose the denotation of an expression out of the
denotations of its subexpressions. We know that each subexpression will
be denoted by a proc’s Ruby source, so we can use them as part of a
larger piece of Ruby source that calls those procs with the supplied
environment and does some computation with their return values. Here’s
what the resulting denotations look like:

>>
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
))
.
to_ruby
=> "-> e { (-> e { e[:x] }).call(e) + (-> e { 1 }).call(e) }"
>>
LessThan
.
new
(
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)),
Number
.
new
(
3
))
.
to_ruby
=> "-> e { (-> e { (-> e { e[:x] }).call(e) + (-> e { 1 }).call(e) }).call(e) <
(-> e { 3 }).call(e) }"

These denotations are now complicated enough that it’s difficult
to see whether they do the right thing. Let’s try them out to
make sure:

>>
environment
=
{
x
:
3
}
=> {:x=>3}
>>
proc
=
eval
(
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
))
.
to_ruby
)
=> #
>>
proc
.
call
(
environment
)
=> 4
>>
proc
=
eval
(
LessThan
.
new
(
Add
.
new
(
Variable
.
new
(
:x
),
Number
.
new
(
1
)),
Number
.
new
(
3
))
.
to_ruby
)
=> #
>>
proc
.
call
(
environment
)
=> false