第二章：程序的含义 - 设计和实现一种简单的编程语言

[murphywuwu]

• [x] 2.1 ”含义“的含义
• [x] 2.2 语法
• [x] 2.3 操作语义
  • [x] 2.3.1 小步语义
  • [x] 2.3.2 大步语义
• [x] 2.4 指称语义
  • [x] 2.4.1 表达式
  • [x] 2.4.2 语句
  • [x] 2.4.3 应用
• [x] 2.5 形式化语义实践
  • [x] 2.5.1 形式化
  • [x] 2.5.2 找到含义
  • [x] 2.5.3 备选方案
• [x] 2.6 实现语法解析器

[murphywuwu]

这颗树表示<<1 * (2 + 3) * 4>>与·<<1 2 + 3 4>>`不是一个表达式(具有不同的含义)，但字符串表示并没有反映出这一点

[murphywuwu]

为抽象语法树定义规约方法，这将是我们实现一个小步操作语义的起点。也就是说，代表可以以一个抽象语法树作为输入，然后生成一个规约树作为输出。在实现规约本身之前，我们先要区分什么样的表达式能规约，什么样的表达式不能规约。Add和Multiple表达式总是能规约的，但是Number表达式总是代表一个值,它就不能规约成任何东西了。

[murphywuwu]

• 如果加法左边的参数能够规约，就规约左边的参数
• 如果加法左边的参数不能规约，但是右边的参数可以规约，就规约右边的参数
• 如果两边都不能规约，它们应该都是数字了，就把它们加到一起

[murphywuwu]

我们在维护一个状态---也就是当前表达式---并且对其反复调#reducible?和#reduce，直到得到一个值为止，通过这种方式，可以手工模拟一个抽象机器对表达式求值的操作

[murphywuwu]

目前为止，Simple还有一个明显缺失的东西：变量。在任何有用的语言中，我们都期望在讨论值时能够使用有意义的名字而不是它们本身的字面值。这些名字提供了一个间接层，这样同一个代码可以用来处理很多不同的值。

为了能规约一个变量，抽象机器不仅仅需要存储当前表达式，还要存储从变量名称到它们值的映射--环境(enviroment)

在ruby中，我们可以把这个映射实现成一个散列表(hash)，其中用符号作为键，用表达式对象作为值：例如 {x: Number.new(2), y: Boolean.new(false)}f

[murphywuwu]

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

[murphywuwu]

语句。它是一个表达式，用来求值生成另一个表达式；换句话说，一个语句能够通过求值改变抽象器的状态。机器唯一的状态(除了当前程序)就是环境，因此我们将允许Simple语句生成一个新的环境以替换当前环境。 我们的实现将使用Hash#merge创建一个新的散列表来更新环境，不会改变旧值。

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

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

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

[murphywuwu]

既然知道语句规约是如何工作的了，那么我们就可以对其进行扩展，以支持其他类型的语句。比如条件语句

• 如果条件能规约，那就对其规约，得到的结果是一个规约了的条件语句和一个没有改变的环境
• 如果条件是表达式true了，就规约成结果语句和一个没有变换的环境
• 如果条件是表达式false，就规约成替代语句和一个没有变化的环境

[murphywuwu]

序(Sequence)，它把两个语句(如 x = x + 1, y = x + 3)连接到一起，组成一个更大的语句。一旦有了序列语句，我们就可以反复使用它们构建更大的语句。

[murphywuwu]

小步语义大部分都有迭代的味道，它要求抽象机器反复执行规约步骤(Machine#run中的while循环)。

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

大步语义的规则描述了如何只对程序的抽象语法树访问一次就计算出整个程序的结果，因此不需要处理状态和重复。我们将只对表达式和语句类定义一个#evaluate方法，然后直接调用它

[murphywuwu]

Sequence：用第一次求值的结果作为第二次求值的参数

While:

• 对条件求值，得到true或者false；
• 如果条件求值结果是true，就对语句主体求值得到一个新的环境，然后在那个新的环境下重复循环，最后返回作为结果的环境
• 如果条件求值结果是false，就返回未修改的环境

[murphywuwu]

小步语义设定了一台能执行小操作的简单抽象机器，因此它包含了关于如何产生有用中间结果的详尽细节；大步语义把汇编整个计算的重担交给了机器或者执行它的人，在仅通过一步操作就把整个程序转换成一个最终结果的过程中，要求它跟踪许多中间子目标。

[murphywuwu]

指称语义

到目前为止，我们已经从操作性方面观察了程序设计语言的含义，它通过展示执行之后发生的事情解释了程序的含义。而指称语义转而关心从程序本来的语言到其他表示的转换。指称语义确实是一种比操作语义更抽象的方法，因为它只是用一种语言替换另一种语言，而不是把一种语言转换成真实的行为。例如，如果我们需要向一个人解释英语动词walk的含义，但和他没有共同的口头语言，可以通过来回走的动作来沟通。另一方面如果我们需要向一个说法语的人解释walk，可以跟他讲marcher--不可否认这是一种更高层次的沟通方式，不需要麻烦地运动了。

把Simple转换成Ruby从而得到Simple语言的指称语义，事实上，这意味着把一个抽象语法树转换成一个Ruby代码的字符串。它的主要目的是展示如何把Simple翻译成Ruby，它将后者作为工具来解释不同的语言结构是什么意思。

[murphywuwu]

小结

操作语义通过为一种语言设计一个解释器来解释这种语言的含义。与此对比，语言到语言的指称语义更像是一个编译器；在这种情况下，我们的#to_ruby实现高效地把Simple编译成Ruby。

指称语义的一个优点比操作语义抽象层次更高，它忽略了程序如何执行的细节，而只关心把它转换成一个不同的表示