Question

考虑程序含义的最实际方法是思考它做了些什么：在运行程序的时候，我们期望发生什么呢？在运行时编程语言中不同的结构都是如何表现的？把它们放到一起组成更大的程序时会是什么效果？

这是操作语义学（operational semantic）的基础，这种方法为程序在某种机器上的执行定义一些规则，以此来捕捉编程语言的含义。这个机器常常是一种抽象的机器：为了解释这种语言所写的程序如何执行而设计出来的一个想象的、理想化的计算机。为了更好地捕获编程语言的运行时行为，通常需要针对不同种类的编程语言设计不同的抽象机器。

有了操作语义，我们可以朝着严谨而准确地研究语言中特定结构的目标前进了。用英语写成的语言规范可能暗藏着二义性，并且可能遗漏边缘情况，但一个形式化的操作性规范不会如此，为了令人信服地传达语言的行为，它必须明确而且无二义性。

2.3.1　小步语义

那么，我们如何设计一台抽象机器，并使用它定义一种编程语言的操作语义呢？一种方法就是假想一台机器，用这台机器直接按照这种语言的语法进行操作一小步一小步地对其进行反复规约，从而对一个程序求值。不管最后得到的结果含义是什么，我们每一步都能让程序更接近最终结果。

这种小步规约类似于对代数式求值的方式。例如，为了对(1×2) + (3×4)求值，我们知道应该：

1.执行左侧的乘法（1×2 变成了 2），这样表达式就规约成了 2 + (3×4)；

2.执行右侧的乘法（3×4 变成了 12），这样表达式规约成了 2 + 12；

3.执行加法（2 + 12 变成了 14），最终得到 14。

我们可以认为 14 就是结果，因为通过上面步骤已经不能再进一步规约了；我们认为 14 是一个特殊代数表达式，它是一个值，有自己的含义，不需要进一步的努力了。

把如何进行每一小步的规约写成形式化规则，这个非形式化的过程就可以转换成一个操作语义。这些规则本身需要用某种语言（元语言）写下来，而这种语言通常是数学符号。

本章，我们将探索一个玩具级编程语言的语义，姑且将这种语言叫作 Simple3。

3你可以把它看成简单命令式语言（simple imperative language）的缩写。

Simple 的小步语义（small-step semantic）的数学化描述如下所示：

从数学上讲，这是一个推理规则的集合，它定义了基于 Simple 抽象语法树的一个规约关系。实际点儿讲，这是一堆怪异的符号，关于计算机程序的含义它没有讲任何能让人理解的东西。

我们不会试图直接理解这种形式化的符号，而是研究如何用 Ruby 编写同样的推导规则。对程序员来说使用 Ruby 做元语言更容易理解，而且这样还有一个优点，就是这些规则可以执行，我们能看到它们是如何工作的。

我们并不打算尝试用“靠实现来规范”的方式描述 Simple 的语义。使用 Ruby而不是用数学符号来描述小步语义，主要是为了使描述更容易被人们所理解。最终得到一个这种语言的可执行实现，只是这么做的额外好处。

使用 Ruby 有一大缺点：这是在使用一种更复杂的语言解释一种简单的语言，从哲学上来说这可能很失败。我们应该记住，数学化的规则是语义的权威描述，而使用 Ruby 只是为了更容易地理解这些规则的含义。

1. 表达式

首先来研究一下 Simple 语言中表达式的语义。规则将作用于这些表达式的抽象语法树，所以我们必须把 Simple 表达式表示成 Ruby 对象。要做到这一点，一种方式就是为 Simple语法中每一种不同的元素都定义一个 Ruby 类，包括数字（number）、加法（add）、乘法（multiply）等，然后把每一个表达式表示成由这些类的实例构成的一棵树。

例如，下面是 Number、Add 和 Multiply 三个类的定义：

class Number < Struct.new(:value)
end

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

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

实例化这些类来手工构造抽象语法树：

>> 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>
  >
>

当然，最终我们想通过一个语法解析器自动构建这些树。2.6 节将介绍如何完成这件事情。

三个类（Number、Add 和 Multiply）都继承了 Struct对 #inspect 的通用定义，所以在 IRB中它们实例的字符串表示会含有大量不重要的细节。为了方便在 IRB 中查看抽象语法树的内容，我们将覆盖每个类的 #inspect 方法4，让它返回自定义的字符串表示：

4为了让代码保持简单，我们将抑制住把公共代码提取到超类或者模块中的欲望。

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

这样每个抽象语法树都将在 IRB 中以 Simple 源代码的形式呈现，外边会加上书名号（«»）以便与正常的 Ruby 值区分。

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

我们对#to_s的基本实现并没有把运算优先级考虑进来，所以有时候如果按照传统的优先级规则（例如 * 通常比 + 优先级更高）它们的输出是不正确的。以下面的抽象语法树为例：

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

这棵树表示«1 * (2 + 3) * 4»与«1 * 2 + 3 * 4» 不是一个表达式（具有不同的含义），但字符串表示并没有反映出这一点。

这个问题很严重，但与我们关于语义的讨论完全无关。为简单起见，暂时先忽略此事，避开可能拥有不正确字符串描述的表达式。我们将在 3.3.1 节为另一种语言给出更合适的实现。

现在为抽象语法树定义规约方法，这将是我们实现一个小步操作语义的起点。也就是说，代码可以以一个抽象语法树作为输入，然后生成一个规约树作为输出。

在实现规约本身之前，我们先要区分什么样的表达式能规约，什么样的表达式不能规约。Add 和 Multiply 表达式总是能规约的（它们的每一个表达式都表示一个操作，并能够通过那种操作对应的计算变成一个结果），但是 Number 表达式总是代表一个值，它就不能规约成任何其他东西了。

原则上，我们可以使用简单的#reducible?断言把这两种表达式区分开，它能判断参数是否可规约，并返回true或者false：

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

在 Ruby 的 case 语句里，控制表达式与case 值是否匹配，是通过将控制表达式的值作为参数调用每个 case 值的 #=== 方法来判断的。方法 #=== 的实现会检查它的参数是否是那个类或者那个子类的实例，这样我们可以使用“case 对象 when 类名”这样的语法为一个类匹配一个对象。

但是，在一种面向对象语言里这么写代码通常被认为是不好的做法 5；如果一些运算的行为依赖于它参数的类型，典型的做法是将这种每个类都有的行为实现为它们的实例方法，从而让语言隐式地决定调用哪个方法，而不是使用显式的 case 语句。

5尽管我们用 Haskell 或者 ML 这样的函数式语言写 #reducible? 时就是这么写的。

因此，我们将分别为Number、Add和 Multiply 实现 #reducible? 方法：

class Number
  def reducible?
    false
  end
end

class Add
  def reducible?
    true
  end
end

class Multiply
  def reducible?
  true
   end
end

这回的表现正是我们想要的：

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

现在可以为这些表达式实现规约了：像上面一样，我们为 Add 和 Multiply 定义一个#reduce方法。既然数字不能再规约，那就没有必要定义 Number#reduce 了，因此除非确切知道一个表达式能够规约，否则不要对其调用#reduce 方法。

那么规约加法表达式的规则是什么呢？如果左右参数都是数字，那我们就能把它们加到一起，但如果其中一个或者所有参数需要规约怎么办？既然我们在考虑一小步一小步地进行规约，那就有必要在它们都符合规约条件的时候决定哪个参数先进行规约6。一个常用的策略是按照从左到右的顺序对参数进行规约，规则是这样的：

6选择什么顺序并没有区别，但是在这个时候我们必须做出决策。

· 如果加法左边的参数能够规约，就规约左边的参数；

· 如果加法左边的参数不能规约，但是右边的参数可以规约，就规约右边的参数；

· 如果两边都不能规约，它们应该都是数字了，就把它们加到一起。

上面这些规则的结构是小步规约操作语义的特征。每一个规则都提供了它能得以应用的表达式模式（左边参数可规约的加法，右边参数可规约的加法，两边参数分别都不能规约的加法），还有对当模式匹配上之后如何构建一个规约后的新表达式的描述。选择了这些特定的规则之后，我们不仅确定了那些参数分别规约好之后应该如何合并到一起，还特别指出了一个 Simple 表达式要使用从左到右求值的方法对参数进行规约。

我们可以把这些规则直接翻译成一个Add#reduce 的实现，同样的代码对 Multiply#reduce也适用（别忘了要把参数乘起来而不是加起来）：

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

方法 #reduce 总是构建出新的表达式，而不是对已有的表达式进行修改。为这几种表达式实现了 #reduce 方法之后，我们可以反复对其进行调用，从而通过很多的一小步来完整地求出表达式的值：

>> 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

注意，#reduce 总是把一个表达式转换成另一个表达式，这正是小步规约操作语义应该遵守的规则。特别要注意的是，Add.new(Number.new(2),Number.new(12)).reduce 返回的 Number.new(14) 表示 Simple 表达式，而不仅仅是 14 这个 Ruby 中的数字。

Simple 语言（我们正在为其定义语义）和 Ruby 元语言（我们正在使用它定义语义）在明显不同的时候区分起来很容易——就像元语言是数学符号而不是一种程序设计语言时一样容易区分——但是这里因为两种语言看起来很像，所以需要更加小心。

我们在维护着一个状态——也就是当前表达式——并且对其反复调用 #reducible? 和#reduce，直到得到了一个值为止，通过这种方式，可以手工模拟一个抽象机器对表达式求值的操作。为了节省点力气，也为了让这个抽象机器的思想更为具体，我们可以轻松地写些 Ruby 代码。把这些代码和状态封装到一个类里，并称为虚拟机：

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

这允许我们用一个表达式实例化一个虚拟机，让它运行（#run），并观察逐渐规约的各个步骤：

>> 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

要扩展这个实现以支持其他简单的值和运算并不难：减法和除法，布尔值 true 和 false，布尔运算 and、or 和 not，对数字进行比较并返回布尔值的运算，等等。例如，下面是一个布尔值以及小于运算的实现：

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

这仍然允许我们一小步一小步地规约布尔表达式：

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

目前为止都是直截了当的东西：我们通过实现能对一种语言求值的虚拟机来定义它的操作语义。虚拟机当前的状态就是当前的表达式，而机器的行为是由一个规则集合来描述的，这个规则集合负责管理机器运行时的状态切换。我们已经把机器实现成了程序，这个程序跟踪当前表达式，持续对其进行规约，并随之更新表达式，直到没有更进一步的规约可以继续执行为止。

但是这种由简单代数表达式组成的语言不是十分有趣，这种语言没有几个我们期望拥有的哪怕是最简单编程语言中的特性。接下来我们把它构建得更复杂一些，让它看起来更像是一种能写出有用程序的语言。

首先，Simple 有一个明显缺失的东西：变量。在任何有用的语言中，我们都期望在讨论值时能够使用有意义的名字而不是它们本身的字面值。这些名字提供了一个间接层，这样同一个代码可以用来处理很多不同的值——包括来自于程序外部因而在写代码时甚至都不知道的值。

我们可以引入一个新的表达式类 Variable 来表示 Simple 中的变量：

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

  def inspect
    "«#{self}»"
  end

  def reducible?
    true
  end
end

为了能规约一个变量，抽象机器不仅仅需要存储当前表达式，还要存储从变量名称到它们值的映射——环境（environment）。在 Ruby 中，我们可以把这个映射实现成一个散列表（hash），其中用符号作为键，用表达式对象作为值；例如，散列表 {x:Number.new(2),y:Boolean.new(false) } 是一个环境，它分别把变量 x和y 与 Simple 的数字和布尔值进行了关联。

对这种语言来说，环境的目的只是把变量名映射到Number.new(2) 这样不可规约的值上，而不是映射到 Add.new(Number.new(1), Number.new(2)) 这样可以规约的表达式。稍后我们编写能改变环境的规则时要注意这个约束。

有了环境，我们很容易实现 Variable#reduce：它只是在环境里查找变量的名字并返回其值。

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

注意，我们正在把一个环境作为参数传进 #reduce，所以需要修改其他类的 #reduce 的实现，以便能接受和提供这个参数：

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

现在 #reduce 的所有实现在更新之后都已经能支持环境了，因此还需要重新定义虚拟机，以便维持一个环境并把它提供给 #reduce：

Object.send(:remove_const, :Machine) # 忘记原来的 Machine 类

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

机器对 #run 的定义仍然没变，但它有了一个新的环境属性，这个属性提供给 #step 方法新的实现使用。

现在只要我们也提供一个包含变量值的环境，就可以对包含变量的表达式进行规约了：

>> 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

环境的引入完成了表达式的操作语义。我们已经设计了抽象机器，它由一个初始表达式和环境开始，然后在每次规约的一小步中使用当前的表达式和环境生成一个新的表达式，这个过程中环境始终没有改变。

2. 语句

现在我们可以看一下另一种程序结构的实现：语句。它是一个表达式，用来求值生成另一个表达式；换句话说，一个语句能够通过求值改变抽象机器的状态。机器唯一的状态（除了当前程序）就是环境，因此我们将允许 Simple 的语句生成一个新的环境以替换当前环境。

最简单的语句就是什么都不做的语句：它不能规约，因为对环境没有任何影响。这实现起来很简单：

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

➊ 其他所有语法类都从 Struct 类继承，但是 DoNothing 没有继承任何类。这是因为DoNothing 什么属性都没有，而且遗憾的是，Struct.new 还不让我们传一个空的属性名称列表。

➋ 想要比较任意两个语句是否相等。其他类都从 Struct 继承了 #== 的实现，但 DoNothing只能定义它自己的了。

一个什么都不做的语句可能看起来没什么意义，但是能有一个特殊的语句表示程序已经执行成功会非常方便。其他语句完成了它们的工作之后，我们会将它们最终规约成 «do-nothing»。

要看个实用语句的例子，最简单的就是像 «x = x + 1» 这样的赋值语句，但在实现赋值语句之前，我们还需要决定它的规约规则。

一个赋值语句由一个变量名（x）、一个等号和一个表达式（«x + 1»）组成。如果赋值语句中的表达式是可规约的，我们就可以按照表达式规约规则对其进行规约并最终得到一个包含规约后表达式的新的赋值语句。例如，在一个变量 x 值为 «2» 的环境里对 «x = x + 1» 进行规约，我们会得到语句 «x = 2 + 1»，然后再把它规约就得到 «x = 3»。

可是然后呢？如果表达式已经是 «3» 这样的值了，那么我们就应该执行赋值，也就意味着对环境进行更新，即把这个值与适当的变量名关联起来。因此规约一个语句不单需要生成一个规约了的新语句，还要产生一个新的环境，这个环境有时候会与执行规约时的环境不同。

我们的实现将使用 Hash#merge 创建一个新的散列来更新环境，不会改变旧值：

> 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»}

可以选择破坏性地改变当前环境，而不是创建一个新的，但是避免破坏性的修改可以促使我们把 #reduce 的结果完全明确出来。如果 #reduce 想要改变当前的环境，它就得给调用者返回一个改变后的环境进行通知；反之，如果它不返回一个环境，那么就可以肯定没有造成任何变化。

这个约束帮助我们强化了表达式和语句的区别。对于表达式，把一个环境传递给 #reduce，然后得到一个规约了的表达式；因为没有返回一个新的环境，所以很明显规约一个表达式不会改变环境。对于语句，我们将用当前的环境调用 #reduce，然后得到一个新的环境，这表明规约一个语句会对环境有影响。（换句话说，Simple 小步语义的结构告诉我们：Simple 的表达式是纯净无害的，而它的语句不是这样。）

因此从一个空的环境规约 «x = 3»应该会产生一个新的环境{ x: Number.new(3) }，但是我们还期望这个语句以某种方式得到规约；不然的话，抽象机器将会不断地把 «3»赋值给x。这时候 «do-nothing» 就派上用场了：一个完整的赋值语句规约成«do-nothing»，就表明语句的规约已经结束，并且可以认为新环境中的东西就是执行结果。

总结起来，赋值的规约规则是：

· 如果赋值表达式能规约，那么就对其规约，得到的结果就是一个规约了的赋值语句和一个没有改变的环境；

· 如果赋值表达式不能规约，那么就更新环境把这个表达式与赋值的变量关联起来，得到的结果是一个 «do-nothing» 语句和一个新的环境。

这样，我们就有了实现一个赋值类Assign 的足够信息。唯一的困难就是 Assign#reduce 需要既返回一个语句又返回一个环境——而 Ruby 的方法只能返回一个对象——但我们可以把它们放到由两个元素组成的数组中返回，这就模拟了这种情况。

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

正如我们承诺的那样，Assign 的规约规则保证了如果一个表达式不可规约（如一个值），它就只会增加到环境上。

可以像表达式一样对一个赋值语句反复规约，直到其不能再规约为止。通过这个方法就可以对一个赋值表达式求值。

>> 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

这个过程甚至比手工规约表达式更难，因此为了处理语句，需要重新实现虚拟机，让它能在每一步规约时显示当前的语句和环境：

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

现在这台机器又可以为我们工作啦：

>> 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

可以看到，这台机器仍然在执行表达式的规约步骤（«x + 1»规约成 «2 + 1»，再规约成«3»），但是这个规约过程现在不是发生在语法树的顶层，而是在一个语句里。

既然知道语句规约是如何工作的了，那么我们就可以对其进行扩展，以支持其他类型的语句。让我们从«if (x) { y = 1 } else { y = 2 }» 这样的语句开始，这个语句包含了一个叫作条件（«x»）的表达式，还有两个语句，一个称为结果（«y = 1»），另一个是替代语句（«y = 2»7。对条件进行规约的规则很简单：

7此条件语句与 Ruby 的 if 不同，Ruby 中的 if 是返回一个值的表达式，但是在 Simple 中，这是一个语句，它从其他两个语句中选择一个求值，并且它唯一的结果就是对当前环境的影响。

· 如果条件能规约，那就对其进行规约，得到的结果是一个规约了的条件语句和一个没有改变的环境；

· 如果条件是表达式«true» 了，就规约成结果语句和一个没有变化的环境；

· 如果条件是表达式 «false»，就规约成替代语句和一个没有变化的环境。

在这种情况下，所有规则都不会改变环境——第一条规则中对条件表达式的规约只会生成一个新的表达式，而不会产生新的环境。

下面是翻译成 If 类的规则：

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

下面是规约操作：

>> 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

这些都与预期一致，但如果能支持不带«else» 从句的条件语句就好了，比如 «if (x) {y =1}»。幸运的是，把语句写成 «if (x) { y = 1 } else { do-nothing }» 就可以做到，这和没有 «else» 从句的效果是一样的：

>> 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

既然不仅实现了表达式，还实现了赋值语句和条件语句，我们就有了组成程序所需要的基础材料，这样的程序可以执行计算和进行决策，做实际的工作。主要的限制是我们还不能把这些基础材料“连接”到一起：没有办法给多个变量赋值或者执行多个条件运算，这大幅度地限制了语言的可用性。

为摆脱这个限制我们可以再定义一种语句——序（sequence），它把两个语句（如 «x = 1+ 1» 和 «y = x + 3»）连接到一起，组成一个更大的语句（如 «x = 1 + 1; y = x + 3»）。一旦有了序列语句，我们就可以反复使用它们构建更大的语句；例如，序列 «x = 1 + 1; y = x + 3» 和赋值语句 «z = y + 5» 能连到一起组成序列 «x = 1 + 1; y = x + 3; z = y + 5»8。

8为了达到我们的目的，这个语句构造成 «(x = 1 + 1; y = x + 3); z = y + 5» 还是«x = 1 + 1;(y = x + 3; z = y + 5)» 都没有关系。在执行规约时，这个选择会影响规约的顺序，但是两种方式最终的结果是一样的。

对序列进行规约的规则有点微妙：

· 如果第一条语句是«do-nothing»，就规约成第二条语句和原始的环境；

· 如果第一条语句不是«do-nothing»，就对其进行规约，得到的结果是一个新的序列（规约之后的第一条语句，后边跟着第二条语句）和一个规约了的环境。

看了代码你会更清楚这些规则：

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

这些规则的总体效果就是：不断规约一个序列时，一直都在规约它的第一个语句，直到成为 «do-nothing»，然后再去规约第二个语句。在虚拟机里运行一个序列，我们可以看到这种效果：

>> 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

Simple 里重要但仍缺失的只有某种无限制的循环结构了，所以为了完成任务，我们引入一个«while» 语句，以便程序可以执行任意次数的重复计算9。像«while(x < 5) { x = x* 3» 这样的语句，包含了一个叫作条件（«x < 5»）的表达式和一个叫作语句主体（body）的语句（«x = x * 3»）。

9使用序列语句，我们已经能够硬编码固定数量的重复操作了，但还是无法控制运行时的重复行为。

为一个 «while» 语句写出正确的规约规则需要一点技巧。我们尝试着像«if» 语句那样对其处理：如果能规约就对条件进行规约；不能的话，就根据条件是«true» 还是«false» 相应地规约语句主体或者执行 «do-nothing»，那下一步会怎么样呢？条件已经被规约成一个值或者丢弃了，并且语句主体已经被规约成 «do-nothing»，那么我们如何执行下一周期的循环呢？每一步规约要想与将来的规约步骤交流，只能通过产生一个新的语句和环境来实现，而使用这种方法，我们就没有地方记录最初的条件和语句主体供下一个循环使用。

小步的解决方式10是使用序列语句把«while» 的一个级别展开，把它规约成一个只执行一次循环的 «if» 语句，然后再重复原始的 «while»。这意味着我们只需要一个规约规则：

10我们总试图把 «while» 的迭代行为直接构建成规约规则，而不是找到一种途径让抽象机器去处理它，但这不是小步语义的工作方式。参考 2.3.2 节，其中介绍的大步语义是一种让规则完成工作的语义。

· 把 «while ( 条件 ) { 语句主体 }» 规约成 «if ( 条件 ) { 语句主体 ; while ( 条件 ){ 语句主体 } } else { do-nothing }» 和一个没有改变的环境。

在 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

这给了虚拟机根据需要对条件和语句主体进行求值的机会：

>> 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

或许这个规约规则看起来有点像是在逃避——好像我们总是在往后推迟对 «while» 的规约，一直没有实际进展——但它确实很好地解释了一个«while» 语句真正的意思：检查条件，对语句主体求值，然后重新开始。奇怪的是，对 «while» 进行规约，会把它转换成一个语法上更庞大的程序，其中包括条件语句和序列语句，而不是直接对它的条件和语句主体进行规约，但有一个能定义一种语言形式语义的技术方案是非常好的，因为我们会更易理解这种语言中的不同部分彼此之间是如何关联的。

3. 正确性

如果程序只是语法有效但实际上是错误的，这时按照我们给出的语义执行会发生什么呢？我们之前完全忽视了这一点。语句«x = true; x = x + 1» 是一段语法有效的 Simple 代码，我们确实可以构建一个抽象语法树来表示它，但试图反复对其规约的时候，它将会崩溃，因为在尝试往 «true» 上加 «1»的时候抽象机器会终止。

>> 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

处理这个问题的一个方法就是在表达式能被规约的时候增加更多的约束，加入对求值失败可能性的考虑，这时求值过程有可能会中止，而不是总要试图规约成一个值（然后就可能在处理过程中崩溃）。我们本来可以把 Add#reducible? 实现成这样：«+»的两个参数要么都是可规约的，要么都是数字类型（Number）实例，这时它才返回 true，这种情况下，表达式 «true + 1»将会中止处理而永远不会变成一个值。

最终，我们需要一个比语法更强大的工具，它要能“看到未来”并让我们避免执行任何可能崩溃或者中止处理的程序。这一章是关于动态语义（dynamic semantic）的——程序执行时具体在做什么——但那并不是一个程序所拥有的唯一一种含义；在第 9 章，我们将研究静态语义（static semantic），看看如何根据语言的动态语义来判断一个语法上有效的程序是否具有有用的含义。

4. 应用

我们定义的程序设计语言非常基本，但在写下所有规约规则的时候，仍然不得不做了一些设计上的决策并明确地表述它们。例如，与 Ruby 不同的是，Simple 这种语言会区分表达式和语句，前者返回一个值，后者不会返回值；与 Ruby 相同的是，Simple 的环境只与已经完全规约成值的变量关联，而不与仍然有待执行的更大表达式关联 11。我们可以通过给出不同的小步语义来改变上面任何的策略，这将描述一种新的语言，这种语言拥有同样的语法，但有着不同的运行时行为。如果向语言中增加更多精心设置的特性——数据结构、过程调用、异常和一个对象系统——我们需要做出更多的设计决策并在定义语义时无歧义 地表达它们。

11Ruby 的 proc 在某种意义上允许把复合表达式复制给变量，但是一个 proc 仍然是一个值：它本身不能再执行任何求值操作了，但是能和其他值一起作为一个更大表达式的一部分进行规约。

小步语义的细节化、面向执行的风格能让它无歧义地定义真实世界的编程语言。例如，Scheme 编程语言最新的 R6RS 标准使用了小步语义（http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-15.html） 描述其执行， 并 提供了 PLT Redex 语 言（http://redex.racket-lang.org/）（设计用来定义和调试操作语义的一门特定领域的语言）对那些语义的参考实现（http://www.r6rs.org/refimpl）。OCaml 编程语言，在一个更简单的 Core ML 语言基础之上构建了一系列的分层，也有对于基础语言运行时行为的小步语义定义（http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-ml.html#htoc5）。

参考 6.2.2 节，那里还有一个小步操作语义的例子，它用了一个甚至更简单的叫作 lambda演算的编程语言定义了表达式的含义。

2.3.2　大步语义

我们已经看到了小步操作语义是什么样子的：设计一台抽象机器维护一些执行状态，然后定义一些规约规则，这些规则详细说明了如何才能对每种程序结构循序渐进地求值。特别地，小步语义大部分都带有迭代的味道，它要求抽象机器反复执行规约步骤（Machine#run中的 while 循环），这些步骤以及与它们同样类型的信息可以作为自身的输入和输出，这让它们适合这种反复进行的应用程序。12

12对一个表达式和一个环境进行规约将得到一个新的表达式，而且下一次还可以重用旧的环境；对一个语句和一个环境进行规约将得到一个新的语句和一个新的环境。

这种小步的方法有一个优势，就是能把执行程序的复杂过程分成更小的片段解释和分析，但它确实有点不够直接：我们没有解释整个程序结构是如何工作的，而只是展示了它是如何慢慢规约的。为什么不能更直接地解释一个语句，完整地说明它的执行过程呢？好吧，我们可以，而这正是大步语义（big-step semantic）的依据。

大步语义的思想是，定义如何从一个表达式或者语句直接得到它的结果。这必然需要把程序的执行当成一个递归的而不是迭代的过程：大步语义说的是，为了对一个更大的表达式求值，我们要对所有比它小的子表达式求值，然后把结果结合起来得到最终答案。

在很多方面，这都比小步的方法更自然，但确实失去了一些对细节的关注。例如，小步语义明确定义了操作应该发生的顺序，因为在每一步都明确了下一步规约应该是什么。但是大步语义经常会写成更为松散的形式，只会说哪些子计算会执行，而不会指明它们按什么顺序执行。13 小步语义还提供一种轻松的方式用以监视计算的中间阶段，而大步语义只是返回一个结果，不会产生任何关于如何计算的证据。

13我们用这种方法实现的大步语义不会有二义性，因为 Ruby 本身已经进行了排序决策，但是在数学化地定义大步语义时，就不可避免地要讲清楚准确的求值策略了。

为了理解做出的这种权衡，让我们回顾一些常见的语言结构，并看如何在 Ruby 中实现它们的大步语义。我们的小步语义要求有一个 Machine 类跟踪状态并反复执行规约，但是这里不需要这个类了；大步规约的规则描述了如何只对程序的抽象语法树访问一次就计算出整个程序的结果，因此不需要处理状态和重复。我们将只对表达式和语句类定义一个#evaluate 方法，然后直接调用它。

1. 表达式

处理小步语义时，我们不得不区分像 «1 + 2» 这样可规约的表达式和像 «3» 这样不可规约的表达式，这样规约规则才能识别一个子表达式什么时候可以用来组成更大的程序。但是在大步语义中，每个表达式都能求值。唯一的区别，如果我们想要有个区别的话，就是对一些表达式求值会直接得到它们自身，而对另一些表达式求值会执行一些计算并得到一个不同的表达式。

大步语义的目标是像小步语义那样对一些运行时行为进行建模，这意味着我们期望对于每一种程序结构，大步语义规则都要与小步语义规则程序最终生成的东西保持一致。（把操作语义写成数学形式之后，这是能被准确证明的。）小步语义规则规定，像数值（Number）和布尔值（Boolean）这样的值不能再规约了，因此它们的大步规约非常简单：求值的结果直接就是它们本身。

class Number
  def evaluate(environment)
    self
   end
end

class Boolean
   def evaluate(environment)
    self
   end
end

变量（Variable）表达式是唯一的，这样它们的小步语义允许它们在成为一个值之前只规约一次，所以它们的大步语义规则与小步规则一样：在环境中查找变量名然后返回它的值。

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

二元表达式 Add、Multiply 和 LessThan 更有意思，它们要求先对左右子表达式递归求值，然后再用恰当的 Ruby 运算合并两边的结果值：

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

为了检查这些大步的表达式语义是否正确，下面将在 Ruby 的控制台验证一下：

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

2. 语句

在我们要定义语句的行为时，这种类型的语义就能发挥作用了。在小步语义下表达式会规约成其他表达式，但语句会规约成 «do-nothing» 并且得到一个经过修改的环境。我们可以把大步语义的语句求值看成一个过程，这个过程总是把一个语句和一个初始环境转成一个最终的环境，这避免了小步语义不得不对 #reduce 产生的中间语句进行处理的复杂性。例如，对一个赋值语句按照大步的方法求值应该完整地对其表达式求值，并返回一个包含结果值的更新了的环境：

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

类似地，DoNothing#evaluate 无疑将把未更改的环境返回，而 If#evaluate 的工作相当地直接：对条件求值，然后把环境返回，这个环境来自于对序列或者替代语句求值得到的结果。

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

有两种有趣的情况就是序列语句和 «while» 循环表达式。对于序列，我们只需要对两个语句求值，但是初始环境需要“穿过”这两个求值过程，这样第一个语句求值的结果就能成为第二个语句求值的环境。这可以写成 Ruby 代码：用第一次求值的结果作为第二次求值的参数：

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

为了让先前的语句为后边的做准备，“穿过”环境是至关重要的：

>> 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»}

对于 «while» 语句，我们需要彻底想清楚对一个循环完整求值的各个阶段：

· 对条件求值，得到«true» 或者 «false»；

· 如果条件求值结果是«true»，就对语句主体求值得到一个新的环境，然后在那个新的环境下重复循环（也就是说对整个 «while» 语句再次求值），最后返回作为结果的环境；

· 如果条件求值结果是 «false»，就返回未修改的环境。

这是对一个«while»语句行为的递归解释。就像序列语句，循环体生成的更新了的环境被下一个迭代使用这一点非常重要；不然的话，条件一直都是 «true»，那么循环就永远也没有机会停下来了。14

14当然，没有什么能够阻止 Simple 程序员写出条件永远也不会为《false》的《while》语句，但如果那就是他们想要的，那也是可行的。

知道了大步«while» 语义的行为表现之后，就可以实现 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

➊ 循环在这里发生：body.evaluate(environment)对循环求值得到一个新的环境，然后我们把那个环境传回当前方法中开始下一次迭代。这意味着可能会堆积很多对While#evaluate 的嵌套调用，直到条件最后成为«false» 然后返回最后的环境。

就像任何递归代码一样，如果调用嵌套得太深可能会导致 Ruby 调用栈溢出。一些 Ruby 的实现会实验性地支持对尾调用的优化，这个技术能通过尽可能重用同样的栈帧来减少溢出风险。在 Ruby 的官方实现（MRI）里，我们可以这样打开尾调用优化：

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

为了确认生效，可以尝试对同样的 «while» 语句求值，这是之前用来检查小步语义的：

> 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»}

这与小步语义给出的结果一致，所以看起来 While#evaluate 做的事情没错。

3. 应用

我们稍早时候对小步语义的实现只是适度使用了 Ruby 调用栈：在对一个大型程序调用#reduce 时，消息会遍历抽象树直到其到达一段准备好规约的代码，这会引起一系列对#reduce 的嵌套调用。15 但是伴随着反复执行小步规约，虚拟机通过维护当前程序和环境完成了对整个计算过程的跟踪；值得一提的是，嵌套调用只是用来遍历语法树查找下一步的规约对象，而不是执行规约本身，因此调用栈的深度受到程序语法树深度的限制。

15有一种操作语义的替换形式，叫作规约语义，它通过引入所谓的规约上下文，把“下一步规约什么”和“如何对其进行规约”分离开来。这些上下文只是一些简明描述了规约在程序中何处发生的模式。这意味着我们只需要写真正执行计算的规约规则，从而把一些样板文件（boilerplate）从更大型的语言中去掉。

相比之下，大步方式的实现会执行较小规模的计算，并将其作为更大规模计算的一部分。为了跟踪还有多少求值工作要做，它使用了更多的栈，并完全依赖栈来记住当前处理在整个计算中的位置。看上去像是对 #evaluate 的一次调用，实际上转换成了一系列递归调用，每一次调用都对一个子程序求值，这都让其在语法树中更进一步。

这个差别突出了每一种方法的目的。小步语义设定了一台能执行小操作的简单抽象机器，因此它包含了关于如何产生有用中间结果的详尽细节；大步语义把汇编整个计算的重担交给了机器或者执行它的人，在仅通过一步操作就把整个程序转换成一个最终结果的过程中，要求它跟踪许多中间子目标。根据我们想用一个语言的操作语义干什么——或是构建一个高效的实现，证明程序的某些属性，或是设计某个最佳变换——可能采用其中一种方法或者另一种方法会更合适。

大步语义在定义真正程序设计语言上最有影响的应用是第 6 章提到的标准 ML 编程语言（http://www.lfcs.inf.ed.ac.uk/reports/87/ECS-LFCS-87-36/）的原始定义，它用大步方式定义了 ML 的所有运行时行为。在这个例子之后，OCam 的核心语言用大步语义（[http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-ml.html#htoc7](http://caml. inria.fr/pub/docs/u3-ocaml/ocaml-ml.html#htoc7)）补足了它更细节的小步定义。 W3C 也用到了大步操作语义：XQuery 1.0 和 XPath 2.0 规范（http://www.w3.org/TR/xquerysemantics/）使用数学化的推理规则描述它的语言应该如何求值，并且 XQuery 和 XPath 规 范全文的 3.0 版本（http://www.w3.org/TR/xpath-full-text-30/）包括了一个使用 XQuery 写成的大步语义。

你可能注意到了，通过使用 Ruby 语言而不是数学语言写下 Simple 的小步和大步语义，我们已经为它实现了两个不同的 Ruby 解释器。操作语义实质上是这样的：通过描述一个解析器来说明一种语言的含义。正常情况下，这个描述应该用简单的数学符号来写，只要我们能理解，这将使一切都清晰而且无歧义，但是这样过于抽象而且离现实中的计算机有一定距离。把一种真实世界编程语言的额外复杂性（类、对象、方法调用……）引入到本该简约的说明当中，这是 Ruby 语言的缺点，但是如果我们已经理解 Ruby，那么就更容易理解整个过程，并且能够执行的描述可以当作一个解释器，这是个很好的红利。