We’ll start by looking at the semantics of Simple expressions. The rules will operate on the abstract syntax of these expressions, so we need to be able to represent Simple expressions as Ruby objects. One way of doing this is to define a Ruby class for each distinct kind of element from Simple’s syntax—numbers, addition, multiplication, and so on—and then represent each expression as a tree of instances of these classes.

For example, here are the definitions of Number, Add, and Multiply classes:

class Number < Struct.new(:value)
end

class Add < Struct.new(:left, :right)
end

class Multiply < Struct.new(:left, :right)
end

We can instantiate these classes to build abstract syntax trees by hand:

>> Add.new(
     Multiply.new(Number.new(1), Number.new(2)),
     Multiply.new(Number.new(3), Number.new(4))
   )
=> #<struct Add
     left=#<struct Multiply
       left=#<struct Number value=1>,
       right=#<struct Number value=2>
     >,
     right=#<struct Multiply
       left=#<struct Number value=3>,
       right=#<struct Number value=4>
     >
   >

The Number, Add, and Multiply classes inherit Struct’s generic definition of #inspect, so the string representations of their instances in the IRB console contain a lot of unimportant detail. To make the content of an abstract syntax tree easier to see in IRB, we’ll override #inspect on each class^[5] so that it returns a custom string representation:

class Number
  def to_s
    value.to_s
  end

  def inspect
    "«#{self}»"
  end
end

class Add
  def to_s
    "#{left} + #{right}"
  end

  def inspect
    "«#{self}»"
  end
end

class Multiply
  def to_s
    "#{left} * #{right}"
  end

  def inspect
    "«#{self}»"
  end
end

Now each abstract syntax tree will be shown in IRB as a short string of Simple source code, surrounded by «guillemets» to distinguish it from a normal Ruby value:

>> Add.new(
     Multiply.new(Number.new(1), Number.new(2)),
     Multiply.new(Number.new(3), Number.new(4))
   )
=> «1 * 2 + 3 * 4»
>> Number.new(5)
=> «5»

>> Multiply.new(
     Number.new(1),
     Multiply.new(
       Add.new(Number.new(2), Number.new(3)),
       Number.new(4)
     )
   )
=> «1 * 2 + 3 * 4»

Now we can begin to implement a small-step operational semantics by defining methods that perform reductions on our abstract syntax trees—that is, code that can take an abstract syntax tree as input and produce a slightly reduced tree as output.

Before we can implement reduction itself, we need to be able to distinguish expressions that can be reduced from those that can’t. Add and Multiply expressions are always reducible—each of them represents an operation, and can be turned into a result by performing the calculation corresponding to that operation—but a Number expression always represents a value, which can’t be reduced to anything else.

In principle, we could tell these two kinds of expression apart with a single #reducible? predicate that returns true or false depending on the class of its argument:

def reducible?(expression)
  case expression
  when Number
    false
  when Add, Multiply
    true
  end
end

However, it’s generally considered bad form to write code like this in an object-oriented language;^[6] when the behavior of some operation depends upon the class of its argument, the typical approach is to implement each per-class behavior as an instance method for that class, and let the language implicitly handle the job of deciding which of those methods to call instead of using an explicit case statement.

So instead, let’s implement separate #reducible? methods for Number, Add, and Multiply:

class Number
  def reducible?
    false
  end
end

class Add
  def reducible?
    true
  end
end

class Multiply
  def reducible?
    true
  end
end

This gives us the behavior we want:

>> Number.new(1).reducible?
=> false
>> Add.new(Number.new(1), Number.new(2)).reducible?
=> true

We can now implement reduction for these expressions; as above, we’ll do this by defining a #reduce method for Add and Multiply. There’s no need to define Number#reduce, since numbers can’t be reduced, so we’ll just need to be careful not to call #reduce on an expression unless we know it’s reducible.

So what are the rules for reducing an addition expression? If the left and right arguments are already numbers, then we can just add them together, but what if one or both of the arguments needs reducing? Since we’re thinking about small steps, we need to decide which argument gets reduced first if they are both eligible for reduction.^[7] A common strategy is to reduce the arguments in left-to-right order, in which case the rules will be:

The structure of these rules is characteristic of small-step operational semantics. Each rule provides a pattern for the kind of expression to which it applies—an addition with a reducible left argument, with a reducible right argument, and with two irreducible arguments respectively—and a description of how to build a new, reduced expression when that pattern matches. By choosing these particular rules, we’re specifying that a Simple addition expression uses left-to-right evaluation to reduce its arguments, as well as deciding how those arguments should be combined once they’ve been individually reduced.

We can translate these rules directly into an implementation of Add#reduce, and almost the same code will work for Multiply#reduce (remembering to multiply the arguments instead of adding them):

class Add
  def reduce
    if left.reducible?
      Add.new(left.reduce, right)
    elsif right.reducible?
      Add.new(left, right.reduce)
    else
      Number.new(left.value + right.value)
    end
  end
end

class Multiply
  def reduce
    if left.reducible?
      Multiply.new(left.reduce, right)
    elsif right.reducible?
      Multiply.new(left, right.reduce)
    else
      Number.new(left.value * right.value)
    end
  end
end

Having implemented #reduce for these kinds of expressions, we can call it repeatedly to fully evaluate an expression via a series of small steps:

>> expression =
     Add.new(
       Multiply.new(Number.new(1), Number.new(2)),
       Multiply.new(Number.new(3), Number.new(4))
     )
=> «1 * 2 + 3 * 4»
>> expression.reducible?
=> true
>> expression = expression.reduce
=> «2 + 3 * 4»
>> expression.reducible?
=> true
>> expression = expression.reduce
=> «2 + 12»
>> expression.reducible?
=> true
>> expression = expression.reduce
=> «14»
>> expression.reducible?
=> false

By maintaining a piece of state—the current expression—and repeatedly calling #reducible? and #reduce on it until we end up with a value, we’re manually simulating the operation of an abstract machine for evaluating expressions. To save ourselves some effort, and to make the idea of the abstract machine more concrete, we can easily write some Ruby code that does the work for us. Let’s wrap up that code and state together in a class and call it a virtual machine:

class Machine < Struct.new(:expression)
  def step
    self.expression = expression.reduce
  end

  def run
    while expression.reducible?
      puts expression
      step
    end

    puts expression
  end
end

This allows us to instantiate a virtual machine with an expression, tell it to #run, and watch the steps of reduction unfold:

>> Machine.new(
     Add.new(
       Multiply.new(Number.new(1), Number.new(2)),
       Multiply.new(Number.new(3), Number.new(4))
     )
   ).run
1 * 2 + 3 * 4
2 + 3 * 4
2 + 12
14
=> nil

It isn’t difficult to extend this implementation to support other simple values and operations: subtraction and division; Boolean true and false; Boolean and, or, and not; comparison operations for numbers that return Booleans; and so on. For example, here are implementations of Booleans and the less-than operator:

class Boolean < Struct.new(:value)
  def to_s
    value.to_s
  end

  def inspect
    "«#{self}»"
  end

  def reducible?
    false
  end
end

class LessThan < Struct.new(:left, :right)
  def to_s
    "#{left} < #{right}"
  end

  def inspect
    "«#{self}»"
  end

  def reducible?
    true
  end

  def reduce
    if left.reducible?
      LessThan.new(left.reduce, right)
    elsif right.reducible?
      LessThan.new(left, right.reduce)
    else
      Boolean.new(left.value < right.value)
    end
  end
end

Again, this allows us to reduce a boolean expression in small steps:

>> Machine.new(
     LessThan.new(Number.new(5), Add.new(Number.new(2), Number.new(2)))
   ).run
5 < 2 + 2
5 < 4
false
=> nil

So far, so straightforward: we have begun to specify the operational semantics of a language by implementing a virtual machine that can evaluate it. At the moment the state of this virtual machine is just the current expression, and the behavior of the machine is described by a collection of rules that govern how that state changes when the machine runs. We’ve implemented the machine as a program that keeps track of the current expression and keeps reducing it, updating the expression as it goes, until no more reductions can be performed.

But this language of simple algebraic expressions isn’t very interesting, and doesn’t have many of the features that we expect from even the simplest programming language, so let’s build it out to be more sophisticated and look more like a language in which we could write useful programs.

First off, there’s something obviously missing from Simple: variables. In any useful language, we’d expect to be able to talk about values using meaningful names rather than the literal values themselves. These names provide a layer of indirection so that the same code can be used to process many different values, including values that come from outside the program and therefore aren’t even known when the code is written.

We can introduce a new class of expression, Variable, to represent variables in Simple:

class Variable < Struct.new(:name)
  def to_s
    name.to_s
  end

  def inspect
    "«#{self}»"
  end

  def reducible?
    true
  end
end

To be able to reduce a variable, we need the abstract machine to store a mapping from variable names onto their values, an environment, as well as the current expression. In Ruby, we can implement this mapping as a hash, using symbols as keys and expression objects as values; for example, the hash { x: Number.new(2), y: Boolean.new(false) } is an environment that associates the variables x and y with a Simple number and Boolean, respectively.

Given an environment, we can easily implement Variable#reduce: it just looks up the variable’s name in the environment and returns its value.

class Variable
  def reduce(environment)
    environment[name]
  end
end

Notice that we’re now passing an environment argument into #reduce, so we’ll need to revise the other expression classes’ implementations of #reduce to both accept and provide this argument:

class Add
  def reduce(environment)
    if left.reducible?
      Add.new(left.reduce(environment), right)
    elsif right.reducible?
      Add.new(left, right.reduce(environment))
    else
      Number.new(left.value + right.value)
    end
  end
end

class Multiply
  def reduce(environment)
    if left.reducible?
      Multiply.new(left.reduce(environment), right)
    elsif right.reducible?
      Multiply.new(left, right.reduce(environment))
    else
      Number.new(left.value * right.value)
    end
  end
end

class LessThan
  def reduce(environment)
    if left.reducible?
      LessThan.new(left.reduce(environment), right)
    elsif right.reducible?
      LessThan.new(left, right.reduce(environment))
    else
      Boolean.new(left.value < right.value)
    end
  end
end

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

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

Writing the correct reduction rules for a «while» statement is slightly tricky. We could try treating it like an «if» statement: reduce the condition if possible; otherwise, reduce to either the body or «do-nothing», depending on whether the condition is «true» or «false», respectively. But once the abstract machine has completely reduced the body, what next? The condition has been reduced to a value and thrown away, and the body has been reduced to «do-nothing», so how do we perform another iteration of the loop? Each reduction step can only communicate with future steps by producing a new statement and environment, and this approach doesn’t give us anywhere to “remember” the original condition and body for use on the next iteration.

The small-step solution^[11] is to use the sequence statement to unroll one level of the «while», reducing it to an «if» that performs a single iteration of the loop and then repeats the original «while». This means we only need one reduction rule:

And this rule is easy to implement in Ruby:

class While < Struct.new(:condition, :body)
  def to_s
    "while (#{condition}) { #{body} }"
  end

  def inspect
    "«#{self}»"
  end

  def reducible?
    true
  end

  def reduce(environment)
    [If.new(condition, Sequence.new(body, self), DoNothing.new), environment]
  end
end

This gives the virtual machine the opportunity to evaluate the condition and body as many times as necessary:

>> Machine.new(
     While.new(
       LessThan.new(Variable.new(:x), Number.new(5)),
       Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3)))
     ),
     { x: Number.new(1) }
   ).run
while (x < 5) { x = x * 3 }, {:x=>«1»}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«1»}
if (1 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«1»}
if (true) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«1»}
x = x * 3; while (x < 5) { x = x * 3 }, {:x=>«1»}
x = 1 * 3; while (x < 5) { x = x * 3 }, {:x=>«1»}
x = 3; while (x < 5) { x = x * 3 }, {:x=>«1»}
do-nothing; while (x < 5) { x = x * 3 }, {:x=>«3»}
while (x < 5) { x = x * 3 }, {:x=>«3»}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«3»}
if (3 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«3»}
if (true) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«3»}
x = x * 3; while (x < 5) { x = x * 3 }, {:x=>«3»}
x = 3 * 3; while (x < 5) { x = x * 3 }, {:x=>«3»}
x = 9; while (x < 5) { x = x * 3 }, {:x=>«3»}
do-nothing; while (x < 5) { x = x * 3 }, {:x=>«9»}
while (x < 5) { x = x * 3 }, {:x=>«9»}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«9»}
if (9 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«9»}
if (false) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=>«9»}
do-nothing, {:x=>«9»}
=> nil

Perhaps this reduction rule seems like a bit of a dodge—it’s almost as though we’re perpetually postponing reduction of the «while» until later, without ever actually getting there—but on the other hand, it does a good job of explaining what we really mean by a «while» statement: check the condition, evaluate the body, then start again. It’s curious that reducing «while» turns it into a syntactically larger program involving conditional and sequence statements instead of directly reducing its condition or body, and one reason why it’s useful to have a technical framework for specifying the formal semantics of a language is to help us see how different parts of the language relate to each other like this.

We’ve completely ignored what will happen when a syntactically valid but otherwise incorrect program is executed according to the semantics we’ve given. The statement «x = true; x = x + 1» is a valid piece of Simple syntax—we can certainly construct an abstract syntax tree to represent it—but it’ll blow up when we try to repeatedly reduce it, because the abstract machine will end up trying to add «1» to «true»:

>> Machine.new(
     Sequence.new(
       Assign.new(:x, Boolean.new(true)),
       Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
     ),
     {}
   ).run
x = true; x = x + 1, {}
do-nothing; x = x + 1, {:x=>«true»}
x = x + 1, {:x=>«true»}
x = true + 1, {:x=>«true»}
NoMethodError: undefined method `+' for true:TrueClass

One way to handle this is to be more restrictive about when expressions can be reduced, which introduces the possibility that evaluation will get stuck rather than always trying to reduce to a value (and potentially blowing up in the process). We could have implemented Add#reducible? to only return true when both arguments to «+» are either reducible or an instance of Number, in which case the expression «true + 1» would get stuck and never turn into a value.

Ultimately, we need a more powerful tool than syntax, something that can “see the future” and prevent us from trying to execute any program that has the potential to blow up or get stuck. This chapter is about dynamic semantics—what a program does when it’s executed—but that’s not the only kind of meaning that a program can have; in Chapter 9, we’ll investigate static semantics to see how we can decide whether a syntactically valid program has a useful meaning according to the language’s dynamic semantics.

The programming language we’ve specified is very basic, but in writing down all the reduction rules, we’ve still had to make some design decisions and express them unambiguously. For example, unlike Ruby, Simple is a language that makes a distinction between expressions, which return a value, and statements, which don’t; like Ruby, Simple evaluates expressions in a left-to-right order; and like Ruby, Simple’s environments associate variables only with fully reduced values, not with larger expressions that still have some unfinished computation to perform.^[12] We could change any of these decisions by giving a different small-step semantics which would describe a new language with the same syntax but different runtime behavior. If we added more elaborate features to the language—data structures, procedure calls, exceptions, an object system—we’d need to make many more design decisions and express them unambiguously in the semantic definition.

The detailed, execution-oriented style of small-step semantics lends itself well to the task of unambiguously specifying real-world programming languages. For example, the latest R6RS standard for the Scheme programming language uses small-step semantics to describe its execution, and provides a reference implementation of those semantics written in PLT Redex, “a domain-specific language designed for specifying and debugging operational semantics.” The OCaml programming language, which is built as a series of layers on top of a simpler language called Core ML, also has a small-step semantic definition of the base language’s runtime behavior.

See Semantics for another example of using small-step operational semantics to specify the meaning of expressions in an even simpler programming language called the lambda calculus.

With small-step semantics we had to distinguish reducible expressions like «1 + 2» from irreducible expressions like «3» so that the reduction rules could tell when a subexpression was ready to be used as part of some larger computation, but in big-step semantics every expression can be evaluated. The only distinction, if we wanted to make one, is that some expressions immediately evaluate to themselves, while others perform some computation and evaluate to a different expression.

The goal of big-step semantics is to model the same runtime behavior as the small-step semantics, which means we expect the big-step rules for each kind of program construct to agree with what repeated application of the small-step rules would eventually produce. (This is exactly the sort of thing that can be formally proved when an operational semantics is written mathematically.) The small-step rules for values like Number and Boolean say that we can’t reduce them at all, so their big-step rules are very simple: values immediately evaluate to themselves.

class Number
  def evaluate(environment)
    self
  end
end

class Boolean
  def evaluate(environment)
    self
  end
end

Variable expressions are unique in that their small-step semantics allow them to be reduced exactly once before they turn into a value, so their big-step rule is the same as their small-step one: look up the variable name in the environment and return its value.

class Variable
  def evaluate(environment)
    environment[name]
  end
end

The binary expressions Add, Multiply, and LessThan are slightly more interesting, requiring recursive evaluation of their left and right subexpressions before combining both values with the appropriate Ruby operator:

class Add
  def evaluate(environment)
    Number.new(left.evaluate(environment).value + right.evaluate(environment).value)
  end
end

class Multiply
  def evaluate(environment)
    Number.new(left.evaluate(environment).value * right.evaluate(environment).value)
  end
end

class LessThan
  def evaluate(environment)
    Boolean.new(left.evaluate(environment).value < right.evaluate(environment).value)
  end
end

To check that these big-step expression semantics are correct, here they are in action on the Ruby console:

>> Number.new(23).evaluate({})
=> «23»
>> Variable.new(:x).evaluate({ x: Number.new(23) })
=> «23»
>> LessThan.new(
     Add.new(Variable.new(:x), Number.new(2)),
     Variable.new(:y)
   ).evaluate({ x: Number.new(2), y: Number.new(5) })
=> «true»

This style of semantics shines when we come to specify the behavior of statements. Expressions reduce to other expressions under small-step semantics, but statements reduce to «do-nothing» and leave a modified environment behind. We can think of big-step statement evaluation as a process that always turns a statement and an initial environment into a final environment, avoiding the small-step complication of also having to deal with the intermediate statement generated by #reduce. Big-step evaluation of an assignment statement, for example, should fully evaluate its expression and return an updated environment containing the resulting value:

class Assign
  def evaluate(environment)
    environment.merge({ name => expression.evaluate(environment) })
  end
end

Similarly, DoNothing#evaluate will clearly return the unmodified environment, and If#evaluate has a pretty straightforward job on its hands: evaluate the condition, then return the environment that results from evaluating either the consequence or the alternative.

class DoNothing
  def evaluate(environment)
    environment
  end
end

class If
  def evaluate(environment)
    case condition.evaluate(environment)
    when Boolean.new(true)
      consequence.evaluate(environment)
    when Boolean.new(false)
      alternative.evaluate(environment)
    end
  end
end

The two interesting cases are sequence statements and «while» loops. For sequences, we just need to evaluate both statements, but the initial environment needs to be “threaded through” these two evaluations, so that the result of evaluating the first statement becomes the environment in which the second statement is evaluated. This can be written in Ruby by using the first evaluation’s result as the argument to the second:

class Sequence
  def evaluate(environment)
    second.evaluate(first.evaluate(environment))
  end
end

This threading of the environment is vital to allow earlier statements to prepare variables for later ones:

>> statement =
     Sequence.new(
       Assign.new(:x, Add.new(Number.new(1), Number.new(1))),
       Assign.new(:y, Add.new(Variable.new(:x), Number.new(3)))
     )
=> «x = 1 + 1; y = x + 3»
>> statement.evaluate({})
=> {:x=>«2», :y=>«5»}

For «while» statements, we need to think through the stages of completely evaluating a loop:

This is a recursive explanation of how a «while» statement should behave. As with sequence statements, it’s important that the updated environment generated by the loop body is used for the next iteration; otherwise, the condition will never stop being «true», and the loop will never get a chance to terminate.^[15]

Once we know how big-step «while» semantics should behave, we can implement While#evaluate:

class While
  def evaluate(environment)
    case condition.evaluate(environment)
    when Boolean.new(true)
      evaluate(body.evaluate(environment)) 
    when Boolean.new(false)
      environment
    end
  end
end

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

To confirm that this works properly, we can try evaluating the same «while» statement we used to check the small-step semantics:

>> 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.evaluate({ x: Number.new(1) })
=> {:x=>«9»}

This is the same result that the small-step semantics gave, so it looks like While#evaluate does the right thing.

Our earlier implementation of small-step semantics makes only moderate use of the Ruby call stack: when we call #reduce on a large program, that might cause a handful of nested #reduce calls as the message travels down the abstract syntax tree until it reaches the piece of code that is ready to reduce.^[16] But the virtual machine does the work of tracking the overall progress of the computation by maintaining the current program and environment as it repeatedly performs small reductions; in particular, the depth of the call stack is limited by the depth of the program’s syntax tree, since the nested calls are only being used to traverse the tree looking for what to reduce next, not to perform the reduction itself.

By contrast, this big-step implementation makes much greater use of the stack, relying entirely on it to remember where we are in the overall computation, to perform smaller computations as part of performing larger ones, and to keep track of how much evaluation is left to do. What looks like a single call to #evaluate actually turns into a series of recursive calls, each one evaluating a subprogram deeper within the syntax tree.

This difference highlights the purpose of each approach. Small-step semantics assumes a simple abstract machine that can perform small operations, and therefore includes explicit detail about how to produce useful intermediate results; big-step semantics places the burden of assembling the whole computation on the machine or person executing it, requiring her to keep track of many intermediate subgoals as she turns the entire program into a final result in a single operation. Depending on what we wish to do with a language’s operational semantics—perhaps build an efficient implementation, prove some properties of programs, or devise some optimizing transformations—one approach or the other might be more appropriate.

The most influential use of big-step semantics for specifying real programming languages is Chapter 6 of the original definition of the Standard ML programming language, which explains all of the runtime behavior of ML in big-step style. Following this example, OCaml’s core language has a big-step semantics to complement its more detailed small-step definition.

Big-step operational semantics is also used by the W3C: the XQuery 1.0 and XPath 2.0 specification uses mathematical inference rules to describe how its languages should be evaluated, and the XQuery and XPath Full Text 3.0 spec includes a big-step semantics written in XQuery.

It probably hasn’t escaped your attention that, by writing down Simple’s small- and big-step semantics in Ruby instead of mathematics, we have implemented two different Ruby interpreters for it. And this is what operational semantics really is: explaining the meaning of a language by describing an interpreter. Normally, that description would be written in simple mathematical notation, which makes everything very clear and unambiguous as long as we can understand it, but comes at the price of being quite abstract and distanced from the reality of computers. Using Ruby has the disadvantage of introducing the extra complexity of a real-world programming language (classes, objects, method calls…) into what’s supposed to be a simplifying explanation, but if we already understand Ruby, then it’s probably easier to see what’s going on, and being able to execute the description as an interpreter is a nice bonus.