类型化演算的模型.ppt

第4章 类型化演算的模型,PCF语言由三部分组成 带函数类型和积类型的纯类型化演算 自然数类型和布尔类型 不动点算子 第2章对代数数据类型进行了透彻的研究 第3章研究简单类型化演算 本章先研究递归函数和不动点算子 然后研究类型化演算的模型，因为第3章的模型不能解释不动点算子,4.1 引 言,本章的主要内容 递归函数和不动点算子，以及PCF语言的编程实例 基于完全偏序集合的，带不动点算子的类型化演算的论域理论模型 不动点归纳法，这是一种对递归定义进行推理的证明方法,4.2 递归函数和不动点算子,4.2.1 递归函数和不动点算子 在类型化演算中，可以加递归定义letrec f : = M in N f可以出现在M中 M的类型必须是，否则等式f = M没有意义 例：定义阶乘函数和计算5的阶乘letrec f : nat  nat =  y : nat.(if Eq? y 0 then 1 else y  f (y – 1)) in f 5 把该等式看成关于f的方程：f : nat  nat =y : nat. if Eq? y 0 then 1 else y  f (y – 1),4.2 递归函数和不动点算子,从数学的观点看 含PCF表达式M的方程f : = M是否都有解？ 若有若干个解的话，选择哪个解？ 在讨论PCF的指称语义时解决这些问题 从计算的观点看 递归函数声明有清楚的计算解释 因此，暂且假定每个这样的等式都有解，并在PCF中增加上述表示它的语法,4.2 递归函数和不动点算子,函数的不动点 若F : 是类型 到它自身的函数，则F的不动点是使得F (x) = x的值x :例如，自然数上平方函数的不动点有0和1恒等函数有无数个不动点后继函数没有不动点,4.2 递归函数和不动点算子,重要联系 递归定义f : = M可以用函数f :.M来表示，因为函数f :.M的不动点正好是方程f = M的解(f :.M)N = N，即[N/f]M = N， N是f = M的解 方程f = M的求解转化为找函数f :.M的不动点 例： 阶乘函数是F  f : nat  nat.y : nat.if Eq? y 0 then 1else y  f (y – 1) 的不动点,4.2 递归函数和不动点算子,PCF的最后一个基本构造fix : (  )  , 对每个类型fix为任何 到 的函数产生一个不动点letrec声明形式看成是let和不动点算子组合的一 种语法美化letrec f :  M in N let f : = (fix f :.M) in N也可用语法美化letrec f (x :) : = M in N  letrec f :  x :.M in N,4.2 递归函数和不动点算子,fix等式公理fix = f :  .f (fix f ) (fix)fix MM (fix M) （使用( ) 可得）fix归约规则fix  f : . f (fix f ) (fix),4.2 递归函数和不动点算子,继续阶乘函数的例子 使用fixnatnat，阶乘函数写成fact  fixnatnat F，其中F是表达式F  f :natnat.y:nat.if Eq? y 0 then 1else yf (y-1) fact n  fix F n //计算fact n的前几步 F(fix F) n (f : natnat.y:nat.if Eq? y 0 then 1else yf(y-1)) (fix F) n if Eq? n 0 then 1 else n(fix F) (n-1),4.2 递归函数和不动点算子,乘运算的递归定义 基于加运算，并假定有前驱函数pred，它把n > 0映射到n 1，并把0映射到0 letrec mult : nat  nat  nat =p : nat  nat.if Eq? (Proj1 p) 0 then 0else (Proj2 p) + mult pred (Proj1 p), Proj2 pin mult 8, 10 使用更多语法美化：letrec mult x : nat, y : nat : nat = if Eq? x 0 then 0else y + mult pred x, y in mult 8, 10,4.2 递归函数和不动点算子,4.2.2 有不动点算子的急切归约 考虑fix对各种归约策略的影响最左归约、惰性归约、并行归约只要在原来的公理中增加fix归约公理即可急切归约若沿用原来的fix规则，则对变元先求值的要求会导致归约不终止引入“延迟”（ delay）来暂停对递归定义函数的归约，直到有变元提供给它为止,4.2 递归函数和不动点算子,值（在急切归约中需要引入值的概念）若V是常量、变量、抽象或值的序对，则V是值delayMx:.Mx, x在M :  中非自由的 公理(x :.M)V eager VxM V是值Proji(V1, V2) eager Vi V1和V2是值fixV eager V(delay  fixV) V是值… … 子项规则和上一章一样,4.2 递归函数和不动点算子,例：仅含一个平凡不动点(fix (x : nat  nat.y : nat.y)) ((z : nat.z +1)2) eager(x:nat  nat.y:nat.y)(delayfix(x:nat  nat. y : nat.y)) ((z : nat.z +1)2) eager(y:nat.y)((z : nat.z +1)2) eager (y:nat.y)(2+1) eager (y:nat.y)3 eager 3 例：急切归约可能发散（无不动点） let f (x : nat) : nat = 5 inletrec g (x : nat) : nat = g (x +1) in f (g 3),4.3 论域理论模型和不动点,4.3.1 递归定义和不动点算子 用fix归约的特点来启发论域的主要性质 以阶乘函数为例：fact  fixnatnat F，其中F是表达式F  f :natnat.y:nat.if Eq? y 0 then 1else yf (y-1) 考虑fix F的有限步展开，用另一种方式来理解fact,4.3 论域理论模型和不动点,fix F的有限步展开 官场小说 fix[n]F描述F体的计算最多使用n次的递归计算fix[0]F = diverge （表示处处无定义的函数）fix[n+1]F = F(fix[n]F)(fix[2]F) 0 = 1，(fix[2]F)1 = 1，(fix[2]F) n对n  2没有定义把函数看成二元组的集合后，fix[n1]F = (fix[n]F)  {n, n}，真包含所有的fix[i]F (in)即  {0, 0!}  {0, 0!, 1, 1!}  {0, 0!, 1, 1!, 2, 2!}  …,4.3 论域理论模型和不动点,n( fix[n]F)和F的不动点让fact = n( fix[n]F)是有直观计算意义的尚不足以相信，对任意的F， n( fix[n]F)就是F的不动点强加一些相对自然的条件到F才能保证这一点当用集合包含对部分函数排序时， n( fix[n]F)将是F的最小不动点,4.3 论域理论模型和不动点,论域用集合之间的包含 关系来定义部分函数 之间的偏序在类型化演算的 论域理论模型中， 类型指称值的偏 序集合，叫做论域,4.3 论域理论模型和不动点,计算不终止的项和递归相联系的一个特别问题是如何给计算不终止的项以合理解释?letrec f : nat  nat = x: nat. f (x1) in f 3延伸“自然数”论域，包含一个额外的值nat，表示类型nat上的不终止的计算部分数值函数可看成值域为 {nat}的全函数，在该论域上nat所有的自然数论域上的偏序可以用来刻画称之为“信息量”或“定义度”的特征,4.3 论域理论模型和不动点,4.3.2 完全偏序集合、提升和笛卡儿积 定义偏序集合D, 有自反、反对称和传递关系 的集合D离散序指x  y iff x  y。

集合有离散的偏序 上界若D, ，则子集SD的上界是元素xD，使得对任何yS都有y  x,4.3 论域理论模型和不动点,定义最小上界S的一 个上界，它小于等于()S的任何其它上界有向集合在D, 中，对子集SD，若每个有限集合S0S都有上界在S中，则称子集S有向有向集合都非空若SD是线性序，则S一定有向线性序对所有的x, yS，都有x  y或y  x,4.3 论域理论模型和不动点,例偏序集合{a0, b0, a1, b1, a2, b2, …}，其中对任意i j 都有ai  aj, bj并且bi  aj, bj两个线性序a0a1a2…，和b0b1b2…{ai, bi}有上界ai+1和bi+1等，但没有最小上界,4.3 论域理论模型和不动点,定义完全偏序集合D,  （简称CPO）若每个有向集合SD都有最小上界（∨S） 例使用离散序，任何集合都可看成CPO任何有限偏序集合都是CPO考虑普通算术序，自然数集合不是CPO有理数的非平凡闭区间不是CPO，所有小于 的有理数的最小上界是无理数若S，TD都有向，且S的每个元素都T的某个元素，那么∨S  ∨T,4.3 论域理论模型和不动点,定义有最小元的CPO D  D, 存在元素a，使得对D的任何元素b都有a  b最小元（也叫底元）用D表示提升集合AA  {}提升CPO D，类似地可得到有底元的CPO D,4.3 论域理论模型和不动点,引理4.3若D是一个CPO，那么D是有底元的CPO 引理4.4若D和E都是CPO并都有底元，则它们的积DE也是有底元的CPO。

而且，若SDE是有向的，则∨S = ∨S1, ∨S2，其中Si= ProjiS如果D和E分别有最小元D和E，那么D,E是DE 的最小元,4.3 论域理论模型和不动点,4.3.3 连续函数CPO上的连续函数包括了在程序设计中使用的所有普通函数给出的是一类有不动点的函数本节证明从一个CPO到另一个CPO的所有连续函数的集合形成一个CPO在构造把每个类型看成一个CPO的模型时，这是最本质的一步，因为构造这样的模型时，函数类型必须解释成CPO,4.3 论域理论模型和不动点,记号如果f : D  E是函数，如果S  D，用记号f(S)表示E的子集：f (S) = { f (d ) | dS} 定义单调函数若D=D, D和E=E, E都是CPO，且f : D E 是它们基础集合上的函数，若dd蕴涵 f(d) f (d), 则f 单调若f 单调且S有向，则f (S)有向,4.3 论域理论模型和不动点,定义连续函数 360小说单调，且若对每个有向的S D，都有f (∨S)  ∨f (S) 例在实轴闭区间[x, y]上，若把[x, y]看成CPO时，则通常计算意义下的连续函数仍然连续任何CPO上的常函数是平凡地连续的若D是离散序，则D上每个函数都连续从提升集合A到任何CPO的单调函数连续,4.3 论域理论模型和不动点,定义提升函数如果D和E都是CPO，且f :D  E连续，定义 f : (D  {})  (E  {})如下：f(d) = if d  D then f(d) else 严格函数若f 是有底元CPO之间的函数，且f ()   引理4.5令D和E 都是CPO, 若f:DE连续, 则f:DE严格并连续,。