文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

9.2 静态语义

发布于 2023-05-18 19:12:04 字数 13710 浏览 0 评论 0 收藏 0

到目前为止，我们已经看到了如何不实际执行计算就能发现它的近似信息。我们本可以通过实际执行计算来获得更多信息，但近似的信息比没有还是要强，而且对于某些程序（如路线规划），可能这就是我们所需要的全部了。

在乘法和加法的例子里，我们通过把输入的具体数换成抽象值，把一个小程序转成了一个更简单更抽象的版本，但如果想要研究更大更复杂的程序，用这种技术只能到这个程度了。提供给它们自己乘法和加法实现的值很容易创建，但更一般的情况下，Ruby 并不允许值控制它们自身的行为（例如在 if 语句中使用它们的时候），因为它对特定的语法片段如何工作有硬编码的规则4。除此之外，仍然存在的问题是：因为一些程序会永远循环而不会返回结果，所以通常情况下通过运行程序并等待其输出来了解程序并不可行。

4和 SmallTalk 不同。

乘法和加法的例子还有另一个缺点，那就是它们没什么意思，没有人会关注它们的程序返回正数或者负数。在实践中，有意思的是像“我的程序运行时会崩溃吗？”和“我的程序能变得更有效率吗？”这类问题。

我们可以通过思考它们的静态语义来回答关于程序的更有趣的问题。在第 2 章，我们了解了编程语言的动态语义，一种定义代码运行时含义的方法。一种语言的静态语义告诉我们程序性质，无需执行就可以研究。静态语义的经典例子就是类型系统：它是一个能用来分析程序的规则集合，能检查其中是否含有某种 bug。在 2.3.1 节的“正确性”里，我们考虑的是像 «x=true; x=x+1» 这样的 Simple 程序，它在语法上有效但执行时会引起动态语义的问题。一个类型系统可以事先预判这些错误，在一些坏程序被人尝试执行之前就自动拒绝它。

抽象解释给了我们思考程序静态语义的方式。程序注定要执行，因此一个程序含义的标准解释就是由它的动态语义给出的：«x=1+2; y=x*3»这个程序通过进行算术运算并把它们存储在内存的某个地方来操纵数字。但如果有另一个这种语言的更抽象语义，我们可以根据不同的规则“执行”同样的程序，并得到更抽象的结果，这个结果可以提供关于程序在正常解释时所发生事情的一部分信息。

9.2.1　实现

通过为第 2 章的 Simple 语言构建一个类型系统，我们可以把这个思想具体化。表面上，这看起来很像 2.3.2 节中的大步操作语义：将为每个表示 Simple 程序（Number、Add 等）的语法类实现一个方法，而且调用这个方法将会返回一个最终结果。在动态语义中，这个方法叫 #evaluate，而且它的结果要么是完全求过值的 Simple 值，要么是一个把名字和 Simple值关联起来的环境，这取决于是在对表达式求值还是在对语句求值：

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

对于静态语义，我们将实现不同的方法，它做的工作更少而且会返回更抽象的结果。这里的抽象值不是具体的值和环境，而是类型。一个类型代表许多可能的值：一个 Simple 表达式可以求值成一个数或者一个布尔值，因此对于表达式，我们的类型将是“任何数”和“任何布尔值”。这些类型与之前看到的 Sign 值类似，特别是像实际上含义是“任何数”的Sign::UNKNOWN。就像 Sign 那样，可以通过定义一个叫 Type 的类并创建一些实例来引入类型：

class Type < Struct.new(:name)
  NUMBER, BOOLEAN = [:number, :boolean].map { |name| new(name) }

  def inspect
    "#<Type #{name}>"
  end
end

新方法将会返回类型，因此我们叫它 #type。它应该回答一个问题：这个 Simple 语法求值的时候，它将返回哪种类型的值呢？这对 Simple 的 Number 和 Boolean 语法类很容易实现，因为数字和布尔值求值之后为自身，因此我们能准确地知道将得到的值的类型：

class Number
  def type
    Type::NUMBER
  end
end

class Boolean
  def type
    Type::BOOLEAN
  end
end

对于像 Add、Multiply 和LessThan 这样的操作，就要复杂一点了。例如，我们知道对 Add求值会返回一个数，而我们还知道只有 Add 的两个参数都求值为一个数时它才能求值成功，不然 Simple 解释器将会报错：

>> Add.new(Number.new(1), Number.new(2)).evaluate({})
=> «3»
>> Add.new(Number.new(1), Boolean.new(true)).evaluate({})
TypeError: true can't be coerced into Fixnum

怎么弄清楚一个参数是否将求值成一个数呢？那是它的类型告诉我们的。因此对于Add，规则类似这样：如果两个参数的类型是Type::NUMBER，那最终的结果类型是 Type::NUMBER;不然的话，结果没有类型，因为任何试图进行非数字加法的表达式求值都会在返回任何结果之前失败。为了简单，我们将让#type 方法返回 nil 以表明这个失败；在其他环境下，如果能让最终的实现更简单，我们可能会选择抛出异常或者返回某个特别的错误值（例如Type::ERROR）。

Add 的代码看起来像这样：

class Add
  def type
    if left.type == Type::NUMBER && right.type == Type::NUMBER
      Type::NUMBER
    end
  end
end

对 Multiply#type 的实现是一样的，LessThan#type 也非常类似，只是它会返回 Type::BOOLEAN而不是Type::NUMBER：

class LessThan
  def type
    if left.type == Type::NUMBER && right.type == Type::NUMBER
      Type::BOOLEAN
    end
  end
end

在控制台上，我们可以看到这足以区分能成功求值和不能成功求值的表达式，而 Simple 的语法两者都支持：

>> Add.new(Number.new(1), Number.new(2)).type
=> #<Type number>
>> Add.new(Number.new(1), Boolean.new(true)).type
=> nil
>> LessThan.new(Number.new(1), Number.new(2)).type
=> #<Type boolean>
>> LessThan.new(Number.new(1), Boolean.new(true)).type
=> nil

我们假设抽象语法树至少句法上是有效的。由于树叶子上的实际值被静态语义忽略了，所以 #type可能会错误预测一个坏形式表达式的求值行为：

> bad_expression = Add.new(Number.new(true) Number.new(1)) ➊
=> «true + 1»
> bad_expression.type
=> #<Type number> ➋
> bad_expression.evaluate({})
NoMethodError: undefined method `+' for true:TrueClass ➌

➊ 这个抽象语法树的高层结构看起来正确（一个 Add 含有两个 Number），但第一个 Number 对象是畸形的，因为它的值属性是 true 而不是 Fixnum。
➋ 静态语义假设把两个 Number 加在一起总是产生另一个 Number，因此#type说求值将会成功……
➌ ……但如果实际对这个表达式求值，在 Ruby 尝试往 true 上加 1 的时候我们会得到一个异常。

Simple 解析器应该永远也不会产生坏形式的表达式，因此这在实际中不太可能是问题。

这是之前加法、乘法和 Sign 小技巧的更通用的版本。即使没有进行任何实际的加法或者数字比较，静态语义给了我们“执行”程序的另一种方式，这种方式仍将返回有用的结果。

我们没有把表达式«1+2» 解释成关于值的程序，而是扔掉一些细节，把它解释成关于类型的一个程序，而静态语义提供了 «1»、«2» 和 «+» 的另一种解释，这让我们运行这个关于类型的程序来看看结果是什么。这个结果没那么具体，比起我们根据动态语义正常运行程序所得到的更抽象，但尽管如此它仍然是个有用的结果，因为我们有办法把它转换成具体世界中有意义的一些东西：Type::NUMBER 意味着“在这个表达式上调用#evaluate 将会返回一个Number”，而 nil 的意思是“调用 #evaluate 可能会引起错误”。

我们现在几乎有了 Simple 表达式的完整静态语义，但还没看变量呢。Variable#type 应该返回什么呢？这取决于变量含有什么值：在像 «x=5; y=x+1» 的程序里，变量y 拥有类型Type::NUMBER，但在 «x=5; y=x<1» 里，它的类型是 Type::BOOLEAN。怎么处理这种情况呢？

我们在 2.3.1 节中看到，Variable 的动态语义使用一个环境散列把变量名映射到它们的值上，而静态语义需要某种类似的东西：从变量名到类型的映射。我们可以称其为“类型环境”，但还是使用类型上下文这个名称以便避免与这两种环境混淆。如果把一个类型上下文传给 Variable#type，它需要做的就是在上下文中查找这个变量：

class Variable
  def type(context)
    context[name]
  end
end

这个类型上下文来自哪里呢？目前，我们将假设它能通过某种方式得到，不管什么时候需要，都能通过某种外部机制提供。例如，或许每个 Simple 程序都有一个头文件来声明所有用到的变量；这个文件在程序运行的时候没有作用，而只是用来在开发过程中与静态语义进行自动检查。

现在 #type 期望一个上下文参数，我们需要回过头去修改出 #type 的另一个实现以接受一个类型上下文：

class Number
  def type(context)
    Type::NUMBER
  end
end

class Boolean
  def type(context)
    Type::BOOLEAN
  end
end

class Add
  def type(context)
    if left.type(context) == Type::NUMBER && right.type(context) == Type::NUMBER
      Type::NUMBER
    end
  end
end

class LessThan
  def type(context)
    if left.type(context) == Type::NUMBER && right.type(context) == Type::NUMBER
      Type::BOOLEAN
    end
  end
end

这提供了包含变量的表达式类型，只要给它们提供一个正确类型的上下文即可：

>> expression = Add.new(Variable.new(:x), Variable.new(:y))
=>«x + y»
>> expression.type({})
=> nil
>> expression.type({ x: Type::NUMBER, y: Type::NUMBER })
=> #<Type number>
>> expression.type({ x: Type::NUMBER, y: Type::BOOLEAN })
=> nil

这给了我们各种表达式语法的 #type 实现，那么语句呢？对一个 Simple 语句求值会返回一个环境，而不是一个值，那么在静态语义中如何表达呢？

处理语句的最简单方式就是把它们看成是一种无效的表达式：假设它们不返回值（这是真的）并且忽略它们对环境的影响。我们可以想出一个含义是“不返回值”的新类型，并把这个类型与任何子部件有正确类型的语句联系起来。给这种新类型起名字叫 Type::VOID：

class Type
  VOID = new(:void)
end

DoNothing 和 Sequence 的 #type 实现很简单。DoNothing 的求值总是会成功，只要连接的语句没有错误，对 Sequence 的求值就会成功：

class DoNothing
  def type(context)
    Type::VOID
  end
end

class Sequence
  def type(context)
    if first.type(context) == Type::VOID && second.type(context) == Type::VOID
      Type::VOID
    end
  end
end

If 和 While 则都含有能作为条件的表达式，而且为了让程序能工作正常，这个条件必须求值成一个布尔值：

class If
  def type(context)
    if condition.type(context) == Type::BOOLEAN &&
      consequence.type(context) == Type::VOID &&
      alternative.type(context) == Type::VOID
      Type::VOID
    end
  end
end

class While
  def type(context)
    if condition.type(context) == Type::BOOLEAN && body.type(context) == Type::VOID
      Type::VOID
    end
  end
end

这让我们能区分求值过程中会出错和不会出错的语句：

>> If.new(
    LessThan.new(Number.new(1), Number.new(2)), DoNothing.new, DoNothing.new
  ).type({})
=> #<Type void>
>> If.new(
    Add.new(Number.new(1), Number.new(2)), DoNothing.new, DoNothing.new
  ).type({})
=> nil
>> While.new(Variable.new(:x), DoNothing.new).type({ x: Type::BOOLEAN })
=> #<Type void>
>> While.new(Variable.new(:x), DoNothing.new).type({ x: Type::NUMBER })
=> nil

Type::VOID 和 nil 在这里有不同的含义。#type 返回 Type::VOID 的时候，意思是“这个代码很好只是没设返回值”；nil 意思是“这个代码含有错误。”

唯一还没实现的方法就是 Assign#type。我们知道它应该返回Type::VOID，但在什么环境下呢？如何决定一个赋值行为是否良好呢？想要根据静态语义检查赋值语句右侧的表达式是否合理，但关心它是什么类型吗？

这些问题让我们要对什么应该是有效的 Simple 程序做出一些设计决策。例如，«x=1; y=2;x=x<y»可以吗？根据动态语义它当然没问题——在它执行的时候不会发生什么坏事——但我们可能（或者可能不！）对变量在执行中从持有一种类型的值转为持有另一种类型的值感到不舒服。这种灵活性可能对一些程序员有价值，但对其他人则可能是意外错误的来源。

从设计静态语义的人的角度来说，处理一种变量类型可以改变的语言也更困难。到目前为止我们假设类型的上下文来自外部并在整个程序中不做改变。但可以选择一个更复杂的系统，这个系统的上下文在程序的开头是空的，而上下文随着变量的声明和赋值逐渐构建起来。这种方式与随着程序的执行动态语义逐渐构建起值的环境一样。但这样很复杂：如果语句能改变类型上下文，那将需要 #type 方法既返回一个类型又返回一个上下文，这种方式与动态语义的#reduce 方法返回一个规约的程序和一个环境一样，是为了一个之前的语句能把一个更新后的上下文传给后面。我们还需要处理类似«if(b){x=1}else{y=2}» 的情况，这里不同的执行路径会产生不同的类型上下文，还有像«if(b){x=1}else{x=true}» 这种情况，这里不同的上下文之间会彼此冲突。5

5一个简单的解决办法是：让类型系统只在它的执行路径产生同样上下文的时候才接受语句。

根本上说，一个类型系统的限制性和我们能在其中写的程序的表达力之间存在矛盾。一个限制性类型系统可能是好的，因为它保证排除了大量可能的错误，但当它阻止我们写想要写的程序时它又是坏的。一个好的类型系统会在限制性和表达力之间找到可接受的妥协方式，在保持让程序员容易理解的同时排除足够的问题是值得的。

通过坚持简单的思想就可以解决这个矛盾：类型上下文由程序自身之外的什么东西提供，而不能被自身的语句修改。这样确实会排除某些类型的程序，而且明确回避了类型上下文从何而来以及如何得来的问题，但它保持了静态语义的简单性并且给出了一个容易遵守的规则。

那么对于赋值语句，我们说表达式的类型应该与被赋值的变量类型一致：

class Assign
  def type(context)
    if context[name] == expression.type(context)
      Type::VOID
    end
  end
end

对可以决定每个变量的类型并让它保持不变的所有程序，这个规则足够好，也是一个可以忍受的约束。例如，可以检查在第 2 章中实现了静态语义的 While 循环：

>> statement =
    While.new(
      LessThan.new(Variable.new(:x), Number.new(5)),
      Assign.new(:x, Add.new(Variable.new(:x), Number.new(3)))
  )
=> «while (x < 5) { x = x + 3 }»
>> statement.type({})
=> nil
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.type({ x: Type::BOOLEAN })
=> nil

9.2.2　好处和限制

已经构建的类型系统可以避免基本的错误。通过根据这些静态语句运行一个程序的玩具版本，可以弄清楚在原始的程序中每一个点上可以出现什么类型的值，并检查这些类型与我们运行它的动态语义将要尝试做的是否正确匹配。这个玩具版本解释的简单性意味着我们只能得到程序求值时可能发生的事情的有限信息，但它还意味着我们很容易进行检查。例如，可以检查一个永远运行的程序：

>> statement =
    Sequence.new(
      Assign.new(:x, Number.new(0)),
      While.new(
        Boolean.new(true),
        Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
      )
  )
=> «x = 0; while (true) { x = x + 1 }»
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.evaluate({})
SystemStackError: stack level too deep

这个程序确实很傻，但它没包含任何类型错误：循环条件是一个布尔值，并且变量 x 也一直用来存储一个数。当然，类型系统不够聪明，没能告诉我们一个程序是否在做我们想要它干的事情，甚至是否在做有用的事情，而只告诉我们它的各个组成部分是否以正确的方式匹配了。但因为它需要是安全的（就像 Sign 抽象一样），所以有时候对一个程序是否含有任何错误会给出过于悲观的答案。如果用额外的一个语句扩展上面的程序，我们就能看出这一点来：

>> statement = Sequence.new(statement, Assign.new(:x, Boolean.new(true)))
=> «x = 0; while (true) { x = x + 1 }; x = true»
>> statement.type({ x: Type::NUMBER })
=> nil

方法#type 返回 nil 表明有错误，因为存在一个把布尔值赋给 x 的语句，可是这个语句永远不会执行，所以在运行时不会实际引发一个问题。我们的类型系统没有那么聪明，认识不到这一点，但它给出了一个安全的答案：“这个程序可能会出错。”这过于小心但并没有错误。有时候在程序中试图把一个布尔值赋给一个数字变量确实有可能出错，但因为某种原因，它实际上不会出错。

并不仅仅是无限循环会引起问题。像下面这个程序的动态语义就没有问题：

>> statement =
    Sequence.new(
      If.new(
        Variable.new(:b),
        Assign.new(:x, Number.new(6)),
        Assign.new(:x, Boolean.new(true))
    ),
    Sequence.new(
      If.new(
        Variable.new(:b),
        Assign.new(:y, Variable.new(:x)),
        Assign.new(:y, Number.new(1))
      ),
      Assign.new(:z, Add.new(Variable.new(:y), Number.new(1)))
    )
  )
=> «if (b) { x = 6 } else { x = true }; if (b) { y = x } else { y = 1 }; z = y + 1»
>> statement.evaluate({ b: Boolean.new(true) })
=> {:b=>«true», :x=>«6», :y=>«6», :z=>«7»}
>> statement.evaluate({ b: Boolean.new(false) })
=> {:b=>«false», :x=>«true», :y=>«1», :z=>«2»}

变量x 根据 b 是 true 或者 false 决定来存储一个数字还是一个布尔值，这在求值过程中从来都不是问题。因为程序会一致地使用一个或者另一个；没有可能的执行路径会让 x 既被处理成一个数又被处理成一个布尔值。但静态语义使用的抽象值没有足够的细节，不能展示出这样是可以的 6，因此安全的近似总是会说“这个程序可能会出错”：

6在这种情况下，细节是 x 的类型依赖于b 的值。我们的类型不含有关于变量具体值的任何信息，从而它们无法表达类型和值的依赖。

>> statement.type({})
=> nil
>> context = { b: Type::BOOLEAN, y: Type::NUMBER, z: Type::NUMBER }
=> {:b=>#<Type boolean>, :y=>#<Type number>, :z=>#<Type number>}
>> statement.type(context)
=> nil
>> statement.type(context.merge({ x: Type::NUMBER }))
=> nil
>> statement.type(context.merge({ x: Type::BOOLEAN }))
=> nil

这是一个静态类型系统（static type system），为了在运行前就对程序进行检查而设计；在一个静态类型语言中，每一个变量都有相关的类型。Ruby 的动态类型系统（dynamic type system）工作方式不同：变量没有类型，而值的类型只是在程序执行过程中它们实际使用时才会检查。这让 Ruby 可以处理赋值给同一变量的不同类型的值，代价就是在程序执行前不能检查出类型的 bug 来。

这个系统专注于编程中某种特定方式的错误：每一段语法的动态语义对其将要处理的值的类型是有某种期望的，而类型系统检查那些期望，以便保证在期望为布尔值的时候不要出现数字，反过来期望为数字的时候不要出现布尔值。但一个程序还存在其他的犯错方式，而这个静态语义并不对其进行检查。例如，这个类型系统不会注意到一个变量在使用之前是否已经被实际赋值了，因此任何包含未初始化变量的程序都能通过这个类型检查器，但在求值过程中则会失败。

>> statement = Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
=> «x = x + 1»
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.evaluate({})
NoMethodError: undefined method `value' for nil:NilClass

我们从类型系统得到的任何信息都有些可疑，并且在决定对其投入多大的信任时得注意它的限制。程序静态语义的一次成功执行并不意味着“这个程序将肯定起作用”，只是表明“这个程序在一种特定的方式下肯定不会报错”。能有一个自动化的系统告诉我们程序没有潜在的 bug 或者错误当然很好，但就像在第 8 章看到的那样，世界就是没那么方便。

分享到QQ

分享到微博