指称语义学讲义

前言

我们的目的在于介绍domain论和指称语义, 并展示其是如何为推理程序行为提供数学基础的.

推荐书目

深入阅读

第1章 引论

幻灯片1提示了给出编程语言的形式语义的几种方法. 操作性方法于Part IB课程Semantics of Programming Languages中介绍, 而公理性方法在Part II课程Hoare Logic中刻画. 本课程讲义给出了指称性方法的一些技巧的简要导引. 指称语义学的目的之一在于以尽可能抽象且实现无关的方式描述编程语言的构造: 通过这种方法, 我们有可能获得对于某些概念的洞察, 而这些概念构成了编程语言以及其间关系的基础, 甚至有时还能理解在语言设计中实现这些概念的新方式. 当然, 验证指称性描述可以被实现是重要的. 换言之, 即将指称语义和操作语义联系起来: 我们将在之后刻画如何施行此事.

形式语义的风格

操作的.程序片段的意义基于程序执行过程中其可以施行的计算步骤定义.

公理的.程序片段的意义间接地通过程序性质的某种逻辑的公理和规则定义.

指称的.关心给出编程语言的数学模型. 程序片段的意义抽象地定义为某种适当数学结构的元素.

幻灯片1
指称语义的特征性质

  • 每个程序片段P被赋予一个指称⟦P⟧, 这是一个数学对象, 其代表了P对于完整程序的意义的贡献.
  • 一个程序片段的意义只由其子片段决定, 或者说指称语义是可复合的.
幻灯片2

第1.1节 指称语义的基本例子

考虑基本的编程语言IMP−, 其相当于带有控制结构的算术和布尔表达式, 而这里的控制结构是由赋值, 顺序, 条件刻画的, 见幻灯片3.

指称语义的基本例子 (I):

IMP−的句法

算术表达式: A∈Aexp⩴n_|L|A+A|…其中n是整数, 而L∈𝕃, 𝕃是给定的位置的集合.

布尔表达式: B∈Bexp⩴true|false|A=A|¬B|…

命令: C∈Comm⩴skip|L≔A|C;C|if B then C else C

幻灯片3
译者注记. n_是代表整数n的句法.

为了给出一个编程语言的指称语义, 我们需要赋予每种程序片段的句法范畴以一个解释的domain (domain of interpretation), 然后复合性地描述各种形成程序片段 (phrase-forming) 的构造所对应的语义函数. 对于IMP−, 幻灯片4到10给出了其指称语义, 并且这个语义也很容易在SML中实现.

指称语义的基本例子 (II)

语义函数
A:Aexp→(State→ℤ)B:Bexp→(State→𝔹)C:Comm→(State⇀State)其中ℤ={…,−1,0,1,…}𝔹={true,false}State=(𝕃→ℤ)
幻灯片4
译者注记. ⇀的含义是部分函数 (partial function). 另外, true和true是不同的, 前者是句法, 而后者是一个数学对象.
指称语义的基本例子 (III)

语义函数A
A⁡⟦n_⟧=λs∈State.nA⁡⟦L⟧=λs∈State.s⁡(L)A⁡⟦A1+A2⟧=λs∈State.A⁡⟦A1⟧⁡(s)+A⁡⟦A2⟧⁡(s)
幻灯片5
指称语义的基本例子 (IV)

语义函数B
B⁡⟦true⟧=λs∈State.trueB⁡⟦false⟧=λs∈State.falseB⁡⟦A1=A2⟧=λs∈State.eq⁡(A⁡⟦A1⟧⁡(s),A⁡⟦A2⟧⁡(s))其中eq⁡(a,a′)={true, 如果a=a′false, 如果a≠a′B⁡⟦¬B⟧=λs∈State.¬(B⁡⟦B⟧⁡(s))
幻灯片6
指称语义的基本例子 (V)

语义函数C
⟦skip⟧=λs∈State.s

注记: 从现在开始, 语义函数的名字都将省略.

幻灯片7
可复合性一例

给定部分函数⟦C⟧,⟦C′⟧:State⇀State以及函数⟦B⟧:State→{true,false}, 我们可以定义⟦if B then C else C′⟧=λs∈State.if⁡(⟦B⟧⁡(s),⟦C⟧⁡(s),⟦C′⟧⁡(s))其中if⁡(b,x,x′)={x, 如果b=truex′, 如果b=false

幻灯片8
指称语义的基本例子 (VI)

语义函数C
⟦L≔A⟧=λs∈State.λl∈𝕃.if⁡(l=L,⟦A⟧⁡(s),s⁡(l))
幻灯片9
顺序复合的指称语义

两个命令的顺序复合C;C′的指称为⟦C;C′⟧=⟦C′⟧∘⟦C⟧=λs∈State.⟦C′⟧⁡(⟦C⟧⁡(s))这实际上就是命令的指称 (即部分函数⟦C⟧,⟦C′⟧:State⇀State) 的复合而已.


与之相对的是, 顺序复合的操作语义为C,s⇓s′C′,s′⇓s″C;C′,s⇓s″

幻灯片10

第1.2节 例子: 作为不动点的while循环

幻灯片2所提及的可复合性的要求是相当tough的. 我们用以赋予程序片段指称的数学对象必须足够丰富, 因为需要支持建模所讨论编程语言的一切形成程序片段的构造. 某些形成程序片段的构造是容易处理的, 而其他一些可能就不那么容易了. 例如, 牵涉状态改变命令的条件表达式 [译注: 更准确地说, 应该是条件命令] 可以基于应用相应的分支函数于立即子表达式的指称给出其指称语义: 见幻灯片8. 类似地, 命令的顺序复合的指称语义可由从状态到状态的部分函数的复合操作得到, 如幻灯片10.

现在我们来考虑基本编程语言IMP的指称语义, 其扩展了IMP−以while循环:C∈Comm⩴…|while B do C然而, 这种循环构造并不容易以可复合的方式解释!

while循环的转换语义为⟨while B do C,s⟩→⟨if B then C;(while B do C) else skip,s⟩这暗示了其作为从状态到状态的部分函数的指称应该满足⟦while B do C⟧=⟦if B then C;(while B do C) else skip⟧我们应该注意到这不能直接用来定义⟦while B do C⟧, 因为右边恰恰包含有一个我们想要定义其指称的子片段. 使用顺序复合和if的指称语义, 以及skip的指称为恒等函数λs∈State.s的事实, 上面这条等式是在说⟦while B do C⟧应该是幻灯片11中给出的不动点方程的一个解.

⟦while B do C⟧的不动点性质

⟦while B do C⟧=f⟦B⟧,⟦C⟧⁡(⟦while B do C⟧)其中, 对于每个b:State→{true,false}和c:State⇀State, 我们定义fb,c:(State⇀State)→(State⇀State)为fb,c=λw∈(State⇀State).λs∈State.if⁡(b⁡(s),w⁡(c⁡(s)),s)
  • 为什么w=f⟦B⟧,⟦C⟧⁡(w)有解?
  • 若此方程具有多解, 那么选取哪一个作为⟦while B do C⟧呢?
幻灯片11

在赋予带有递归特性的编程语言以指称语义时, 这样的不动点方程经常出现. 自Dana Scott于60年代晚期的先驱性研究始, 一种被称为domain论的数学理论建立起来以提供一种背景环境, 其中我们不仅总是可以找到因指称语义而生的不动点方程的解, 而且还能选出在某种适切意义下最小的解, 而这实际上保证了指称语义和操作语义之间的协调配合. 关键的想法在于考虑用作指称的数学对象之间的一种偏序, 此偏序表达了这样的事实, 一个对象由另一个对象近似, 或者说比另一个对象携带了更多的信息, 或者说比另一个对象更加良定. 然后, 不动点方程的最小解可以被构造为对于解的近似升链的极限. 在下一章里, 这些想法将会变得从数学角度来说更加精确和一般, 但是目前先让我们具体地阐明该如何运用此想法解决幻灯片11中的特定问题.

为了确定起见, 让我们考虑以下特定的while循环while X>0 do (Y≔X⁎Y;X≔X−1)其中X和Y是两个不同的整数存储位置 (变量), 而位置的集合𝕃={X,Y}.

译者注记. 在某种意义上说, 将𝕃的元素既用作句法也用作讨论语义时所牵涉的概念对象是一种(司空见惯的)滥用. 但是, 只要满足目的就好.

在这种情形之下, 我们可以就取状态为赋值[X↦x,Y↦y], 其中x,y∈ℤ, 这记录了位置X和Y的当前内容. 因此, State=(𝕃→ℤ).

译者注记. 实际上, 幻灯片4中就已经定义State为(𝕃→ℤ)了.

我们正在试着将这个while循环的指称定义为一个部分函数w:State⇀State其应该是幻灯片11上的不动点方程w=f⟦X>0⟧,⟦Y≔X⁎Y;X≔X−1⟧⁡(w)的一个解.

对于特定的布尔表达式B=(X>0)和命令C=(Y≔X⁎Y;X≔X−1), 函数f⟦B⟧,⟦C⟧恰好与幻灯片12上定义的函数f相同.

⟦while X>0 do (Y≔X⁎Y;X≔X−1)⟧

令State=def(𝕃→ℤ)D=def(State⇀State)对于⟦while X>0 do (Y≔X⁎Y;X≔X−1)⟧∈D, 我们寻求w=f⁡(w)的一个最小的解, 其中f:D→D被定义为f⁡(w)⁡([X↦x,Y↦y])={[X↦x,Y↦y], 如果x≤0w⁡([X↦x−1,Y↦x⁎y]), 如果x>0
幻灯片12
D上的偏序

  • D上的偏序⊑:
    w⊑w′当且仅当对于每个s∈State, 如果w在s上有定义, 那么w′也在s上有定义, 并且w⁡(s)=w′⁡(s). 另外一种描述是, w的图包含于w′的图.
  • 最小元⊥∈D w.r.t. ⊑:
    ⊥即全然未定义的部分函数, 或者说图为空的部分函数, 其满足对于每个w∈D, ⊥⊑w.
幻灯片13

考虑幻灯片13上给出的D=(State⇀State)的元素之间的偏序⊑. 注意到⊑实际上就是前文所提及的"信息序"的具体化身: 如果w⊑w′, 那么w′在w有定义的地方都保持和w的一致, 但是它可能在其他一些参数上也有定义. 我们还应该注意到的是, D包含一个相对于此偏序的最小元: 对于全然未定义的部分函数, 我们将其记作⊥, 它满足对于任意的w∈D都有⊥⊑w.

自⊥开始, 我们反复应用函数f以构造一个部分函数的序列w0,w1,w2,…:w0=def⊥;wn+1=deff⁡(wn).使用幻灯片12上的f的定义, 我们发现w1⁡[X↦x,Y↦y]=f⁡(⊥)⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0undefined, 如果x≥1w2⁡[X↦x,Y↦y]=f⁡(w1)⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦y], 如果x=1undefined, 如果x≥2w3⁡[X↦x,Y↦y]=f⁡(w2)⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦y], 如果x=1[X↦0,Y↦2⁎y], 如果x=2undefined, 如果x≥3w4⁡[X↦x,Y↦y]=f⁡(w3)⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦y], 如果x=1[X↦0,Y↦2⁎y], 如果x=2[X↦0,Y↦6⁎y], 如果x=3undefined, 如果x≥4并且, 在n≥1的一般情况下, 我们有wn⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦(!x)⁎y], 如果0<x<nundefined, 如果x≥n其中!x是x的阶乘.

因此, 我们得到了一个部分函数的递增序列w0⊑w1⊑w2⊑…⊑wn⊑…所有这些部分函数之并是元素w∞∈D, 其为w∞⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦(!x)⁎y], 如果x>0注意到w∞是f的一个不动点, 因为对于每个[X↦x,Y↦y], 我们有f⁡(w∞)⁡[X↦x,Y↦y]={[X↦x,Y↦y], 如果x≤0w∞⁡[X↦x−1,Y↦x⁎y], 如果x>0(根据f的定义)={[X↦x,Y↦y], 如果x≤0[X↦0,Y↦1⁎y], 如果x=1[X↦0,Y↦!(x−1)⁎x⁎y], 如果x>1(根据w∞的定义)=w∞⁡[X↦x,Y↦y]实际上, 我们可以表明w∞是f的最小不动点, 意即对于任意的w∈D, 有w=f⁡(w)⇒w∞⊑w.我们取这个最小不动点w∞作为while X>0 do (Y≔X⁎Y;X≔X−1)的指称, 其构造方式是下一章要证明的Tarski不动点定理的一个实例. 我们也应该注意到, w∞的确就是命令while X>0 do (Y≔X⁎Y;X≔X−1)的结构操作语义所给出的从状态到状态的函数, 见Part IB课程Semantics of Programming Languages.

第1.3节 练习

练习1. 在SML中实现IMP−的指称语义.
练习2. 考虑幻灯片11上定义的函数fb,c:(State⇀State)→(State⇀State)
  1. 根据n上的归纳证明fb,cn⁡(⊥)=λs∈State.{ck⁡(s), 如果存在0≤k<n满足对于每个0≤i<k有b⁡(ci⁡(s))=true而b⁡(ck⁡(s))=falseundefined, 如果对于每个0≤i<n有b⁡(ci⁡(s))=true
  2. 令wb,c:State⇀State是由wb,c=defλs∈State.{ck⁡(s), 如果存在k≥0满足对于每个0≤i<k有b⁡(ci⁡(s))=true而b⁡(ck⁡(s))=falseundefined, 如果对于每个i≥0有b⁡(ci⁡(s))=true定义的部分函数, 证明wb,c满足不动点方程wb,c=fb,c⁡(wb,c).
  3. 对于b=⟦true⟧=λs∈State.true和c=⟦skip⟧=λs∈State.s, 描述函数fb,c. 什么样的从状态到状态的部分函数是fb,c的不动点呢? 相对于⊑的最小不动点是什么呢? 这个最小不动点和while true do skip的操作语义所确定的从状态到状态的部分函数是一致的吗?
练习3. 说明幻灯片13上的关系⊑的确是一个偏序, 而且⊥是最小元.
练习4. 证明w∞的确是f的最小不动点. 更一般地, 根据幻灯片13和练习2的定义, 证明对于任意的w∈(State⇀State), 有w=fb,c⁡(w)⇒wb,c⊑w.

第2章 最小不动点

本章介绍了被称为domain论的数学理论, 其为构造各种编程语言特性的指称语义中所用到的最小不动点提供了一个一般性的框架. 该理论是由Dana Scott提出的.

第2.1节 偏序集和单调函数

论点

  • 所有计算的domain都是带有最小元的偏序集.
  • 所有可计算函数都是单调的.
幻灯片14

第2.1.1小节 偏序集

domain论使用满足特定完备性质的偏序集. 我们在幻灯片15中回顾了偏序的定义. D被称为偏序集(D,⊑)的基础集(underlying set). 大部分时候, 我们只以基础集的名字引用偏序集, 而以相同的符号⊑代表不同偏序集的偏序.

偏序集

集合D上的二元关系⊑是一个偏序, 当且仅当它是
  • 自反的: ∀d∈D.d⊑d;
  • 传递的: ∀d,d′,d″∈D.d⊑d′⊑d″⇒d⊑d″;
  • 反对称的: ∀d,d′∈D.d⊑d′⊑d⇒d=d′.
序对(D,⊑)被称为一个偏序集.
幻灯片15
译者注记. d⊑d′⊑d″是d⊑d′&d′⊑d″的缩写.
偏序集公理: 规则形式

x⊑x
x⊑yy⊑zx⊑z
x⊑yy⊑xx=y
幻灯片16
部分函数的domain, X⇀Y

  • 基础集: 由所有定义域dom⁡(f)⊆X且取值于Y的部分函数f构成.
  • 偏序: f⊑g当且仅当dom⁡(f)⊆dom⁡(g)且∀x∈dom⁡(f).f⁡(x)=g⁡(x), 或者说graph⁡(f)⊆graph⁡(g).
幻灯片17
译者注记. 实在是一点可有可无且无聊的注记. 若A⊆X而B⊆Y, 那么应该将f:A⇀B也视为X⇀Y的元素吗 (假设排除A=X且B=Y的平凡情形)? 这是微妙的, 往往取决于具体的上下文.
例子1. 从集合X到集合Y的所有部分函数构成的集合(X⇀Y)可以看成是一个偏序集, 如幻灯片17那样. 前一章里, 我们取这个domain在X=Y=State (某个状态集合) 情形下的实例作为命令的指称集.

第2.1.2小节 单调函数

幻灯片18中给出了偏序集之间的单调映射的概念.

单调性

两个偏序集之间的函数f:D→E是单调的, 如果∀d,d′∈D.d⊑d′⇒f⁡(d)⊑f⁡(d′).
x⊑yf⁡(x)⊑f⁡(y)(f单调)
幻灯片18
例子2. 给定偏序集D和E, 显然常函数λd∈D.e:D→E是单调的.
例子3. 当D是部分函数的domain (State⇀State) (见幻灯片17) 时, 幻灯片11上定义的与while循环的指称语义有关的函数fb,c:D→D是一个单调函数. 我们将其验证留作练习.

第2.2节 最小元和前不动点 (pre-fixed point)

定义1. 设D是一个偏序集, S是D的一个子集, d∈S被称为S的最小元, 如果其满足∀x∈S.d⊑x.

注意到因为⊑是反对称的, 所以S至多拥有一个最小元. 我们也应该注意到, 有的偏序集是没有最小元的. 例如, 带有通常偏序的ℤ.

函数f:D→D的一个不动点, 根据定义, 是满足f⁡(d)=d的一个元素d∈D. 如果D是一个偏序集, 我们可以考虑一个更弱的概念, 即前不动点, 见幻灯片19.

前不动点

令D是一个偏序集而f:D→D是一个函数.
一个元素d∈D是f的一个前不动点, 如果其满足f⁡(d)⊑d.
f的最小前不动点, 如果存在的话, 记作fix⁡(f).因此, 最小前不动点由以下两条性质(唯一地)刻画:
  • (lpf1): f⁡(fix⁡(f))⊑fix⁡(f);
  • (lpf2): ∀d∈D.f⁡(d)⊑d⇒fix⁡(f)⊑d.
幻灯片19
证明原理

  1. f⁡(fix⁡(f))⊑fix⁡(f)
  2. 令D是一个偏序集, f:D→D是一个带有最小前不动点fix⁡(f)∈D的函数.
    对于任意的x∈D, 为了证明fix⁡(f)⊑x, 只需要证明f⁡(x)⊑x.f⁡(x)⊑xfix⁡(f)⊑x
幻灯片20
命题2. 设D是一个偏序集而f:D→D是一个带有最小前不动点fix⁡(f)的函数. 只要f是单调的, 那么fix⁡(f)实际上就是f的一个不动点, 因此也是f的最小不动点.
证明. 因为fix⁡(f)是f的前不动点, 所以f⁡(fix⁡(f))⊑fix⁡(f). 如果f是单调的, 那么f⁡(f⁡(fix⁡(f)))⊑f⁡(fix⁡(f)).换言之, f⁡(fix⁡(f))也是f的一个前不动点. 但是, 鉴于fix⁡(f)是最小的前不动点, 我们可以推出fix⁡(f)⊑f⁡(fix⁡(f)).根据偏序的反对称性, 我们可以断言fix⁡(f)=f⁡(fix⁡(f))即fix⁡(f)是f的一个不动点. 而且, 考虑到偏序的自反性, 不动点也是前不动点. 对于任意的d∈D满足d=f⁡(d), 我们有fix⁡(f)⊑d. 换言之, fix⁡(f)是f的最小不动点.
◻

第2.3节 完全偏序 (cpo) 和连续函数

论点*

  • 所有计算的domain都是带有最小元的完全偏序.
  • 所有可计算函数都是连续的.
幻灯片21

第2.3.1小节 domain

定义1.
  1. 若存在, 我们将偏序集D的最小元记为⊥D. 若D在上下文中是已知的, 写成⊥就可以了. 因此, ⊥由性质∀d∈D.⊥⊑d唯一确定. 偏序集的最小元有时也被称为其底(bottom)元素.
  2. 偏序集D中的一个可数的升链是由D的元素构成的一个序列满足d0⊑d1⊑d2⊑…这样的链的一个上界是任意满足∀n∈ℕ.dn⊑d的d∈D. 若链的最小上界(lub)存在, 我们将其记为⨆n≥0dn.因此, 根据定义:
    • ∀m∈ℕ.dm⊑⨆n≥0dn.
    • 对于任意的d∈D, 如果∀m∈ℕ.dm⊑d, 那么⨆n≥0dn⊑d.
译者注记. 所谓的链, 指的是偏序集的全序子集. 不过, 本讲义实际上只考虑以(通常的)序列面目出现的可数的升链.
评注2. 以下是读者应该注意的点.
  1. 我们不需要考虑偏序集中不可数的链, 或者降链: 因此, "链"将总是指可数的升链.
  2. 就和偏序集的任意子集的最小元一样, 链的最小上界若存在则唯一. 当然, 链可以没有最小上界, 例如ℕ中的0≤1≤2≤…, 不过它连上界也没有.
  3. 最小上界有时也被称为上确界. ⨆n≥0dn的一些其他常见替代记号为⨆n=0∞dn和⨆{dn|n≥0}.
  4. 链的元素不必是互异的. 实际上, 我们称一个链d0⊑d1⊑d2⊑…终至恒常, 如果存在N∈ℕ使得∀n≥N.dn=dN. 注意到此时⨆n≥0dn=dN.
  5. 如果我们丢弃链的开头任意有限数目的元素, 也并不会影响其上界集和最小上界:∀N∈ℕ.⨆n≥0dn=⨆n≥0dN+n.
cpo和domain

一个链完备偏序集(chain-complete poset), 或者说缩写为cpo, 是一个偏序集(D,⊑)满足其中的每个链d0⊑d1⊑d2⊑…都具有最小上界⨆n≥0dn:
  • (lub1): ∀m≥0.dm⊑⨆n≥0dn;
  • (lub2): ∀d∈D.(∀m≥0.dm⊑d)⇒⨆n≥0dn⊑d.
一个domain是一个带有最小元⊥的cpo:∀d∈D.⊥⊑d.
幻灯片22
译者注记. 幻灯片22的两个冒号后面的内容, 只是为了解释什么是最小上界和最小元. 另外, 链完备偏序集也被称为完全偏序, complete partial order.
最小元和最小上界的定义: 规则形式

⊥⊑x
xi⊑⨆n≥0xn(i≥0而⟨xn⟩是一个链)
∀m≥0.xm⊑x⨆n≥0xn⊑x(⟨xn⟩是一个链)
幻灯片23

本讲义里我们关心的是具有特定完备性质的偏序集, 见幻灯片22. 读者应该注意的是, 在有关的指称语义的文献中, 术语"domain"的含义是相当宽泛的: 存在各种各样的domain, 它们可能具有各种各样的序论性质, 而不仅仅是满足链完备性质和拥有最小元.

例子3. 从集合X到集合Y的所有部分函数的集合(X⇀Y)上可以赋予一个偏序成为domain, 见幻灯片24. 在第1.2节, 我们使用了X=Y=State的特殊情形作为命令的指称集. 我们应该注意到, 声称是链f0⊑f1⊑f2⊑…的最小上界的f的确是一个良定的部分函数, 因为在有定义的地方, 每个fn的值都是一致的. 至于验证f的确是偏序集(X⇀Y,⊑)中的f0⊑f1⊑f2⊑…的最小上界, 我们将其留给读者作为练习.
部分函数的domain, X⇀Y

基础集: 由所有满足以下条件的部分函数f构成, 其定义域dom⁡(f)⊆X而取值于Y.
偏序: f⊑g当且仅当dom⁡(f)⊆dom⁡(g)且∀x∈dom⁡(f).f⁡(x)=g⁡(x), 或者说graph⁡(f)⊆graph⁡(g).
链的最小上界: 链f0⊑f1⊑f2⊑…的最小上界是部分函数f, 其dom⁡(f)=⋃n≥0dom⁡(fn)而f⁡(x)={fn⁡(x), 如果存在某个n∈ℕ使得x∈dom⁡(fn)undefined, 否则的话最小元素: ⊥是全然未定义的部分函数.
幻灯片24
例子4. 对于任意的偏序集(D,⊑)而言, 如果D是有限的, 那么该偏序集是一个cpo. 这是因为, 在这样的偏序集中, 任何链都将终至恒常, 因而拥有最小上界. 当然, 有限的偏序集也不一定拥有最小元, 即不是一个domain. 例如, 考虑以下Hasse图所描述的偏序集.一个偏序集的Hasse图是一个有向图, 其顶点是偏序集的基础集的元素, 而从顶点x到顶点y有一条边当且仅当x≠y且∀z.(x⊑z&z⊑y)⇒(z=x∨z=y).
"扁平自然数集"ℕ⊥:012⋯nn+1⋯⊥"垂直自然数集"Ω:ωn+1n210⋮⋮
图1

图1展示两个非常简单但却无限的domain, 而以下是两个并非cpo的偏序集的例子.

例子5. 装备有通常偏序≤的自然数集ℕ={0,1,2,…}不是一个cpo, 因为链0≤1≤2≤…在ℕ中没有上界.
例子6. 考虑上图的第二个例子的一种修改版本, 其中我们为ℕ添加了两个不同的上界ω1≠ω2. 换言之, 我们考虑的是D=defℕ∪{ω1,ω2}, 而其上的偏序⊑为d⊑d′⇔def{d≤d′, 如果d,d′∈ℕd∈ℕ∨d=d′, 如果d′∈{ω1,ω2}然后, D中的链0⊑1⊑2⊑…拥有两个上界, 即ω1和ω2, 但是没有最小的上界, 因为ω1和ω2不可比较. 因此, (D,⊑)不是一个cpo.
链的最小上界的一些性质

设D是一个cpo.
  1. 对于任意的d∈D, ⨆n≥0d=d.
  2. 对于D中的每个链d0⊑d1⊑…⊑dn⊑…, 我们有⨆n≥0dn=⨆n≥0dN+n对于任意的N∈ℕ成立.
幻灯片25
链的最小上界的一些性质 (续)

  1. 对于D中的两条链d0⊑d1⊑…⊑dn⊑…和e0⊑e1⊑…⊑en⊑…, 如果对于每个n∈ℕ有dn⊑en, 那么⨆n≥0dn⊑⨆n≥0en.
∀n∈0.xn⊑yn⨆n≥0xn⊑⨆n≥0yn(⟨xn⟩和⟨yn⟩俱是链)
幻灯片26
双链的对角化

引理. 令D是一个cpo, 设双下标索引的元素dm,n∈D (其中m,n≥0) 构成的族满足m≤m′&n≤n′⇒dm,n⊑dm′,n′那么我们有⨆n≥0d0,n⊑⨆n≥0d1,n⊑⨆n≥0d2,n⊑…以及⨆m≥0dm,0⊑⨆m≥0dm,1⊑⨆m≥0dm,2⊑…而且⨆m≥0(⨆n≥0dm,n)=⨆k≥0dk,k=⨆n≥0(⨆m≥0dm,n).
幻灯片27
证明. 我们利用了定义链的最小上界的性质, 即幻灯片22上的(lub1)和(lub2). 首先, 注意到如果m≤m′, 那么dm,n⊑dm′,n⊑⨆n′≥0dm′,n′对于每个n≥0成立. 因此, ⨆n≥0dm,n⊑⨆n′≥0dm′,n′. 于是, 我们的确可以得到一条由最小上界构成的链⨆n≥0d0,n⊑⨆n≥0d1,n⊑⨆n≥0d2,n⊑…并且我们可以构造其最小上界⨆m≥0⨆n≥0dm,n. 运用两次(lub1), 我们有dk,k⊑⨆n≥0dk,n⊑⨆m≥0⨆n≥0dm,n对于每个k≥0成立, 那么根据(lub2)可以得到⨆k≥0dk,k⊑⨆m≥0⨆n≥0dm,n反过来, 对于每个m,n≥0, 我们注意到dm,n⊑dmax⁡(m,n),max⁡(m,n)⊑⨆k≥0dk,k因而再应用两次(lub2)就可以推出⨆m≥0⨆n≥0dm,n⊑⨆k≥0dk,k根据⊑的反对称性, 我们就得出了想要的等式. 剩余的结果也可按照相同的论证手法得到, 只需要交换m和n的角色.
◻

第2.3.2小节 连续函数

连续性和严格性

  • 如果D和E是cpo, 函数f是连续的当且仅当
    1. f是单调的;
    2. f保持链的最小上界, 即对于D中的每条链d0⊑d1⊑…, 我们有f⁡(⨆n≥0dn)=⨆n≥0f⁡(dn).
  • 如果D和E都拥有最小元, 那么称函数f是严格的, 如果f⁡(⊥)=⊥.
幻灯片28
评注7. 我们注意到如果f:D→E是单调的, 并且d0⊑d1⊑d2⊑…是D中的一个链, 那么应用f就可以得到E中的一个链f⁡(d0)⊑f⁡(d1)⊑f⁡(d2)⊑…. 而且, 如果d是第一条链的一个上界, 那么f⁡(d)是第二条链的一个上界. 换言之, 如果f:D→E是cpo之间的单调函数, 我们总有⨆n≥0f⁡(dn)⊑f⁡(⨆n≥0dn)因此, 根据⊑的固有性质, 给定cpo之间的单调函数f:D→E, f是连续的等价于对于D中的每条链d0⊑d1⊑d2⊑…, E中f⁡(⨆n≥0dn)⊑⨆n≥0f⁡(dn)成立.
例子8. 给定cpo D和E, 对于每个e∈E而言, 常函数λd∈D.e:D→E是连续的.
例子9. 当D是部分函数的domain (State⇀State)时 (见幻灯片24), 定义于幻灯片11的与while循环的指称语义有关的函数fb,c:D→D是一个连续函数. 我们将其验证留作练习.
例子10. 令Ω是垂直自然数的domain, 那么由f⁡(x)={0, 如果x∈ℕω, 如果x=ω定义的函数f:Ω→Ω既是单调的也是严格的, 但是并非连续, 因为f⁡(⨆n≥0n)=f⁡(ω)=ω然而⨆n≥0f⁡(n)=⨆n≥00=0

第2.4节 Tarski不动点定理

Tarski不动点定理

令f:D→D是domain D上的一个连续函数, 那么
  • f具有最小前不动点, 由fix⁡(f)=⨆n≥0fn⁡(⊥)给出.
  • 于是, fix⁡(f)也是f的不动点, 因而是f的最小不动点.
幻灯片29

幻灯片29给出了关于domain上的连续函数的关键结果, 其允许我们赋予牵涉递归特性的程序以指称语义. 幻灯片上所用的记号fn⁡(⊥)是递归定义的:f0⁡(⊥)=def⊥;fn+1⁡(⊥)=deff⁡(fn⁡(⊥)).注意到既然∀d∈D.⊥⊑d, 我们有f0⁡(⊥)=⊥⊑f1⁡(⊥); 而根据单调性, 又可以推出fn⁡(⊥)⊑fn+1⁡(⊥)⇒fn+1⁡(⊥)=f⁡(fn⁡(⊥))⊑f⁡(fn+1⁡(⊥))=fn+2⁡(⊥).因此, 通过对于n∈ℕ进行归纳, 我们可以得到∀n∈ℕ.fn⁡(⊥)⊑fn+1⁡(⊥).换言之, 元素fn⁡(⊥)构成了D中的一条链. 所以说, 既然D是cpo, 那么幻灯片29上用到的⨆n≥0fn⁡(⊥)的确是有意义的.

证明. 首先我们注意到f⁡(fix⁡(f))=f⁡(⨆n≥0fn⁡(⊥))=⨆n≥0f⁡(fn⁡(⊥))根据f的连续性=⨆n≥0fn+1⁡(⊥)根据函数的幂次的定义=⨆n≥0fn⁡(⊥)根据第2.3节的评注2=fix⁡(f)因此, fix⁡(f)的确是f的一个不动点, 当然也就满足幻灯片19上的条件(lpf1). 为了验证(lpf2), 即前不动点的最小性, 我们设d∈D满足f⁡(d)⊑d, 那么既然⊥在D是最小的, 可以得到f0⁡(⊥)=⊥⊑d并且fn⁡(⊥)⊑d⇒fn+1⁡(⊥)=f⁡(fn⁡(⊥))⊑f⁡(d)⊑d根据归纳, 我们可以推出∀n∈ℕ.fn⁡(⊥)⊑d. 换言之, d是链的一个上界, 所以它大于等于最小上界, 即fix⁡(f)=⨆n≥0fn⁡(⊥)⊑d这就是我们想要的(lpf2)了.
◻
例子1. 定义于幻灯片11上的函数f⟦B⟧,⟦C⟧是domain (State⇀State)上的一个连续函数, 因而我们可以应用Tarski不动点定理, 将⟦while B do C⟧定义为fix⁡(f⟦B⟧,⟦C⟧). 实际上, 第1.2节中我们构造部分函数w∞的方法不过就是不动点定理的一个实例而已.
⟦while B do C⟧

⟦while B do C⟧=fix⁡(f⟦B⟧,⟦C⟧)=⨆n≥0f⟦B⟧,⟦C⟧n⁡(⊥)=λs∈State.{⟦C⟧k⁡(s), 如果存在k≥0满足对于每个0≤i<k有⟦B⟧⁡(⟦C⟧i⁡(s))=true而⟦B⟧⁡(⟦C⟧k⁡(s))=falseundefined, 如果对于每个i≥0有⟦B⟧⁡(⟦C⟧i⁡(s))=true
幻灯片30

第2.5节 练习

练习1. 验证幻灯片24上的断言.
练习2. 证明幻灯片25和27中的声明.
练习3. 验证例子9中fb,c是连续函数的断言. 何时fb,c是严格的?
译者注记. 以上练习皆相当平凡.

第3章 domain上的构造

本节我们将给出诸多构造domain和连续函数的方式, 实际上专注于PCF编程语言的指称语义所需的构造, PCF是本讲义的后半部分的研究对象. 注意到为了描述一个cpo, 我们必须先定义一个装备有某二元关系的集合, 然后证明

  1. 这个关系是一个偏序;
  2. 对于这个偏序集中所有的链, 其最小上界存在.
另外, 为了使得cpo成为一个domain, 我们还需要说明
  1. 存在最小的元素.
注意到既然链的最小上界以及最小元若存在则唯一, 那么cpo和domain完全由其基础集和偏序决定. [译注: 意味不明.] 之后我们将给出各种各样构造cpo和domain的方法, 而将验证i, ii, iii成立的任务留作练习.

第3.1节 扁平domain

为了模拟PCF的基本类型 (ground type) nat和bool, 我们将使用幻灯片31给出的扁平domain的概念.

离散cpo和扁平domain

对于任意的集合X, 相等关系x⊑x′⇔defx=x′使得(X,⊑)成为一个cpo, 其被称为以X为基础集的离散cpo.
令X⊥=defX∪{⊥}, 其中⊥是某个不在X中的元素, 那么d⊑d′⇔def(d=d′)∨(d=⊥)使得(X⊥,⊑)成为一个以⊥为最小元的domain, 其被称为由X确定的扁平domain.
幻灯片31

自然数的扁平domain ℕ⊥, 上一章的图1中我们就已描绘过其图像. 至于布尔值的扁平domain 𝔹⊥, 其Hasse图为truefalse⊥以下牵涉扁平domain的连续函数实例对于PCF的指称语义而言也是必要的, 我们将其验证留给读者作为练习.

命题1. 令f:X⇀Y是两个集合之间的部分函数, 那么f⊥⁡(d)=def{f⁡(d), 如果d∈X且f定义于d⊥, 如果d∈X而f在d上没有定义⊥, 如果d=⊥定义了相应扁平domain之间的连续函数f⊥:X⊥→Y⊥.

第3.2节 domain的积

cpo和domain的二元积

两个cpo (D1,⊑1)和(D2,⊑2)之积的基础集为D1×D2={(d1,d2)|d1∈D1&d2∈D2}而其上的偏序⊑定义如下(d1,d2)⊑(d1′,d2′)⇔defd1⊑1d1′&d2⊑2d2′链的最小上界可以按照分量进行计算:⨆n≥0(d1,n,d2,n)=(⨆i≥0d1,i,⨆j≥0d2,j)若(D1,⊑1)和(D2,⊑2)都是domain, 那么(D1×D2,⊑)也是一个domain, 并且⊥D1×D2=(⊥D1,⊥D2)
幻灯片32
命题1. 投影和配对. 令D1和D2是cpo, 那么投影π1:D1×D2→D1,(d1,d2)↦d1和π2:D1×D2→D2,(d1,d2)↦d2是连续函数. 如果f1:D→D1和f2:D→D2是连续函数, 其中D是一个cpo, 那么⟨f1,f2⟩:D→D1×D2,d↦(f1⁡(d),f2⁡(d))是连续的.
证明. 这些函数的连续性可由幻灯片32上对于D1×D2中的链的最小上界的刻画直接推出.
◻
命题2. 对于每个domain D, 函数if:𝔹⊥×(D×D)→D,(x,(d,d′))↦{d, 如果x=trued′, 如果x=false⊥D, 如果x=⊥是连续的.

我们将会需要以下更一般的积构造.

定义3. 依赖积. 给定集合I, 设对于每个i∈I我们有一个cpo (Di,⊑i), 那么这个cpo族之积为就和二元积的情况一样, (∏i∈IDi,⊑)中的链的最小上界也可以逐分量计算: 如果p0⊑p1⊑p2⊑…是积cpo中的一个链, 那么其最小上界是将每个i∈I映射至Di中的链p0⁡(i)⊑p1⁡(i)⊑p2⁡(i)⊑…的最小上界的函数, 即(⨆n≥0pn)⁡(i)=⨆n≥0pn⁡(i),i∈I.而且, 对于每个i∈I, 第i投影函数πi:∏j∈IDj→Di,p↦p⁡(i)是连续的. 如果每个Di都是domain, 那么它们的积也是domain, 并且其最小元是将每个i∈I映射至Di的最小元的函数.
两个参数的连续函数

命题. 令D,E,F是cpo, 那么函数f:D×E→F是单调的当且仅当其对于每个参数分别都是单调的:∀d,d′∈D,e∈E.d⊑d′⇒f⁡(d,e)⊑f⁡(d′,e)∀d∈D,e,e′∈E.e⊑e′⇒f⁡(d,e)⊑f⁡(d,e′)而且, 其是连续的当且仅当其对于每个参数分别都是连续的 [译注: 在单调的基础之上, 也就是对于每个参数分别都是保持链的最小上界的]:f⁡(⨆n≥0dn,e)=⨆n≥0f⁡(dn,e)f⁡(d,⨆n≥0en)=⨆n≥0f⁡(d,en)
幻灯片33
两个参数的连续函数: 推导规则

  • 在f单调的情况下, 我们有x⊑x′y⊑y′f⁡(x,y)⊑f⁡(x′,y′)
  • 在f连续的情况下, 我们有f⁡(⨆m≥0xm,⨆n≥0yn)=⨆k≥0f⁡(xk,yk)
幻灯片34
证明. "仅当"的方向是直接的, 其证明依赖于简单的观察, 即d⊑d′⇒(d,e)⊑(d′,e)和(⨆n≥0dn,e)=⨆n≥0(dn,e), 以及它们之于右参数的对偶版本. 对于"当"的方向, 首先设f对于每个参数分别都是单调的, 那么如果D×E中有(d,e)⊑(d′,e′), 根据二元积的定义, 我们可以推出D中有d⊑d′而E中有e⊑e′, 因此f⁡(d,e)⊑f⁡(d′,e)根据对于第一个参数的单调性⊑f⁡(d′,e′)根据对于第二个参数的单调性于是, f⁡(d,e)⊑f⁡(d′,e′), 即f是单调函数.
现在设f对于每个参数分别都是连续的, 那么如果(d0,e0)⊑(d1,e1)⊑(d2,e2)⊑…是二元积中的一个链, 我们有f⁡(⨆n≥0(dn,en))=f⁡(⨆i≥0di,⨆j≥0ej)见幻灯片32=⨆i≥0f⁡(di,⨆j≥0ej)根据对于第一个参数的连续性=⨆i≥0⨆j≥0f⁡(di,ej)根据对于第二个参数的连续性=⨆n≥0f⁡(dn,en)根据幻灯片27上的引理而这就说明了f的连续性.
◻

第3.3节 函数domain

两个cpo/domain之间的所有连续函数的集合可以赋予一个偏序而成为一个cpo/domain, 见幻灯片35. 有时我们也用术语"指数cpo/domain (exponential cpo/domain)"而不是"函数cpo/domain".

函数cpo和domain

给定cpo (D,⊑D)和(E,⊑E), 函数cpo (D→E,⊑)的基础集为 [译注: 以下符号有点过载](D→E)=def{f:D→E|f连续}而偏序为f⊑f′⇔def∀d∈D.f⁡(d)⊑Ef′⁡(d)推导规则:f⊑(D→E)gx⊑Dyf⁡(x)⊑Eg⁡(y)
幻灯片35
函数cpo和domain (续)

链的最小上界可以逐参数计算:⨆n≥0fn=λd∈D.⨆n≥0fn⁡(d)推导规则:(⨆n≥0fn)⁡(⨆n≥0xn)=⨆k≥0fk⁡(xk)如果D和E还是domain, 那么D→E也成为一个domain, 并且最小元为⊥D→E:D→E,d↦⊥E.
幻灯片36
证明.
◻

第4章 Scott归纳

第5章 PCF

第6章 PCF的指称语义

第7章 将指称语义和操作语义联系起来

第8章 完全抽象