子定型及有关概念课件.PPTVIP

8.2 有子定型的简单类型化?演算 ? |-- ? <:? 从Sub中的断言，用公理和推理规则可以证明子定型断言? <:? 引理 对任何基调?，如果?|--? <:?，那么? 匹配? 对?<: ?的子定型的语义解释 子定型可以解释为转换或者包含 转换解释有助于澄清子定型为什么是前序而不是偏序 前序解释：可能同时有? <:?和? <:?，但??? 可相互转换的值集并不一定有同样表示 8.2 有子定型的简单类型化?演算 2. 项 ?<: ?项的定型规则 包括??项的所有定型规则(cst)、(var)、(? Intro)、(? Elim)、(add var) 新增包容规则 (subsumption) ? M : ?, ?|-- ? <: ? ? M : ? 8.2 有子定型的简单类型化?演算 例 假定基调中有int <: real、2: int、2.0: real和 div: real?real?real 令M是项?x: real.(div x 2.0): real ? real 确定M 2的类型 方式1: 利用real ? real <: int ? real的事实 方式2: 利用int <: real，使得2: real 8.2 有子定型的简单类型化?演算 3. 等式规则 ?<: ?等式证明系统和??的正好包含同样的公理和推理规则 等价关系: (ref)、(sym)和(trans) 加变量到类型指派: (add var) ?抽象和作用: (?)、(?)和(?) 同余关系: (?)和(?) 只有在? M ??和? N ??都是可推导时，才把等式 ? M ? N ??看成是合式的 8.2 有子定型的简单类型化?演算 有了子定型后会引起一些定型上的混淆 外延公理(?) ? ?x:?. (Mx) ? M x在M中不是自由的 会导致相等的项有不同的类型 适当地定义M会出现： ? ?x:?. (Mx) : ? ?? ? M : ???? 但? <: ?? 8.2 有子定型的简单类型化?演算 两个项在一种类型下相等而在另一种类型下不相等 在??中，等式的形式写成? M ? N:?，以直接表示这两个项的公共定型 ?x: real.?x? ? ?x: real. x: real ? real ?x: real.?x? ? ?x: real. x: int ? real 通常，如果A <: B，在类型A上有不同值的表达式在类型B上却相等是可能的 8.2 有子定型的简单类型化?演算 子定型和等式的一般原则由下面推理规则给出 该规则是一个导出规则 (subsumption eq) ? M = N :?, ? ? <: ? ? M = N : ? 8.2 有子定型的简单类型化?演算 例 对任何?<:?项? ?x:?. M: ? ? ?，且? <:?,可以证明等式 ? ?x:?. M = ?x:?. M : ? ? ? 证明的最后两步： ? ?x:?. (?x:?.M) x = ?x:?.M: ? ? ? ----使用 (?) ? ?x:?. (?x:?.M) x = ?x:?.M: ? ?? ----使用 (? ) 此例说明，在?<:?项上，?和?归约没有合流性 可以由加一个归约规则来补救 ? ?x:?.M ? ?x: ?. M:? ? ? 只要 ? |--? <:? (type label) 8.3 记 录 8.3.1 记录子定型的一般性质 类型分别为?1, …, ?n的成员l1, …, ln构成的记录的类型 ? l1:?1, …, ln: ?n? 记录和笛卡儿积相比，有更加丰富的子定型性质，因此记录到积的翻译不能保子定型 8.3 记 录 例 employee =def ?name : string, manager : string, salary : int? manager =def ?name : string, manager : string, salary : int, dept: department? manager <: employee 确定一个记录类型是否为另一个的子类型的主要原则是所有的操作必须保持合理的和良定义的 8.3 记 录 例 employee =def ?name : string, manager : string, salary : int? manager =def ?nam