Definition.
类型与类型判断
Definition. 类型与类型判断
设 是 词项的集合 中的词项. 类型的语法为 ,分别表示布尔类型与自然数类型. 词项与类型是不同的语法类别,类型系统定义的是它们之间的关系.
类型关系由下面七条类型规则归纳定义:它是对这些规则封闭的最小关系. 类型判断 读作“可以由类型规则推出词项 具有类型 ”; 判断成立,当且仅当存在以它为结论的有限推导.
推导符号 属于元语言,用来标记可推导性,与词项构造子或求值符号无关. 含变量的语言通常写作 , 读作“在语境 中,词项 具有类型 ”. 也称类型环境,记录作用域内变量的类型假设; 把这些假设与待证陈述分开. 词项的集合 的算术语言没有变量,所以采用空语境,并省略 . 为简洁起见,讨论这套规则时, 是 的简写.
横线上的判断是前提,横线下的是结论; 没有前提的规则称为公理,仍是推导规则的特例. 、 等符号按 元变量 代换: 只能取类型, 只能取词项; T-If 两个分支里的 必须代换成同一个类型.
T-True:前提 无;结论 ⊢ true : Bool T-False:前提 无;结论 ⊢ false : Bool T-Zero:前提 无;结论 ⊢ 0 : Nat
T-If:前提 ⊢ t_(1) : Bool;⊢ t_(2) : T;⊢ t_(3) : T;结论 ⊢ if t_(1) then t_(2) else t_(3) : T
T-Succ:前提 ⊢ t_(1) : Nat;结论 ⊢ succ t_(1) : Nat T-Pred:前提 ⊢ t_(1) : Nat;结论 ⊢ pred t_(1) : Nat T-IsZero:前提 ⊢ t_(1) : Nat;结论 ⊢ iszero t_(1) : Bool