PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

考屈栾
5 years ago
Views:

1 Typed Lambda Caculus,+, 程序设计语言理论张昱中国科学技术大学计算机科学与技术学院

2 References PFPL Chapters: 4 Statics, 5 Dynamics, 6 Type Safety, 7 Evaluation Dynamics Chapters: 10 Product Types, 11 Sum Types (Void & Unit, Boolean, Enumerate, Options) TAPL The algebra (and calculus!) of algebraic data types 2

3 Outline L int,bool (typed lambda calculus) Algebraic Data Types Product type Sum type 3

4 L int,bool : Statics and Dynamics Syntax Semantics Type Safety

5 L int,bool - Syntax Syntax 5

6 L int,bool - semantics Semantics: judgements, rules Dynamics Values: judgement a val t val (V-z) z val st ( )val (V-s) Introduction form of int type ( 引入 int 类型的值 ) false val (V-F) true val (V-T) Introduction form of bool type ( 引入 bool 类型的值 ) interpreter.ml 6

7 L int,bool - semantics Dynamics Small-step semantics (structural) Judgement: t t Structural Dynamics 按语法结构来归纳计算到 closed value Search transitions 决定指令执行次序 Instruction transitions 基础的求值步 interpreter.ml 7

8 L int,bool - semantics Semantics: judgements, rules Dynamics Example interpreter.ml 8

9 L int,bool - semantics Semantics: judgements, rules Statics: Type system (typing rules) Judgement t : 项是良类型的 (well-typed) Elimination rules of int/bool type: 该类型上的表达式可以进行的操作 Introduction rules of int/bool type: 引入该类型的值 interpreter.ml 9

10 L int,bool - semantics Semantics: judgements, rules Example interpreter.ml 10

11 L int,bool - soundness A language is safe/sound if satisfying two theorems Progress if t : then either t val or t such that t t Preservation if t : and t t then t : Prove the theorems by induction on the typing rules interpreter.ml 11

12 L : Typed Lambda Calculus Syntax Semantics Type Safety

13 : Syntax and Values : typed lambda calculus Syntax Type :: int Values 1 2 Term t :: n t t x ( x : ). t t t n val (V-n) ( x : ). tval (V-fn) 13

14 : Syntax : typed lambda calculus Syntax Type :: int 1 2 Term t :: n t t x ( x : ). t t t

15 : Dynamics Dynamics Values n val (V-n) Type :: int 1 2 Term t :: n t t x ( x : ). t t t (V-fn) ( x : ). tval Dynamics t t (D-app ) t t ( ( x : ). t ) t [ t / x] t t t t t 1 1 t t t t (D-add ) 1 n n n n n n (D-add ) t val t t t t t t (D-app ) (D-add ) 2 15

16 : Statics Statics G: typing context (T-n) n : int G Type :: int 1 2 Term t :: n t t x ( x : ). t t t t : int G t : int 1 2 (T-add) G t t : int G G, x : t : 1 2 ( x : ). t : (T-fn) G t : G t : G t t : (T-app) x G : G (T-var) x : Introduction rule of function type ( 引入该类型的值 ) Elimination rule of function type ( 该类型的表达式上可以进行的操作 ) 16

17 L,+, : Algebraic Data Types Syntax Semantics Type Safety

18 Algebraic Data Types Product types Sum types (variants) Type :: Term t :: ( t, t ) injection 注入 : 注入 d 标记项 t 得到类型值 case 分析 : 如果 t 是由 L 标记项得到的, 则记 L 标记项为 x 1, 按 t 1 计算 ; 若由 R 标记项得到, 则记 R 标记项为 x 2, 按 t 2 计算 td. 1 2 inj t d as Direction d :: L R ordered pair 序偶 projection 投影 case t { x t x t } injection 注入

19 Product Types: Examples ( x : int int). x. L x. R ( x : (int int) int). x. Lx. R (1,(2,(3, 4))) : int (int (int int)) 19

20 Product Types: Examples ( x : int int). x. L x. R 函数 : 对 pair 中的两个元素求和 ( x : (int int) int). x. Lx. R 函数 : 接收由一个函数和一个整数组成的 pair, 以该整数为参数调用这个函数 (1,(2,(3, 4))) : int (int (int int)) 由 pairs 产生 n 元组 20

21 Product Types: Semantics Statics Introduction rule G G t : G t : ( t, t ) : (T-pair) Elimination rules G G t : 1 2 tl. : 1 (T-project-L) G G t : 1 2 tr. : 2 (T-project-R) 21

22 Product Types: Semantics Dynamics t t 1 1 (D-pair ) 1 ( t, t ) ( t, t ) t val t t (D-pair ) 2 ( t, t ) ( t, t ) t val t val (D-pair 3 ) ( t, t )val t t t. d t. d ( t, t )val 1 2 ( t, t ). R t (D-proj ) 1 (D-proj ) 3 ( t, t )val 1 2 ( t, t ). L t (D-proj ) 2 22

23 Record Types Syntactic Sugar Syntax Statics Type :: { l :,, l : } 1 1 Term t :: ( l t,, l t ) 1 1 t. l (1 i k) i k k k k Dynamics 23

24 Sum Types: Examples (inj l L as int (int int)) : int (int int) case (inj l L as int (int int)){ x x 1 x x 2} l

25 Sum Types: Examples (inj l L as int (int int)) : int (int int) 将左标记项包装成一个 sum 类型的值 case (inj l L as int (int int)){ x x 1 x x 2} l 1 用 case 算子对 sum 值分情况处理, 当前是左标记形成的 sum 值, 故按 x x 计算, 得到 l

26 Sum Types: Statics Statics Introduction rules G t : 1 (T-inject-L) G inj t L as : G t : 2 (T-inject-R) G inj t R as : Elimination rule G t : G, x : t : G, x : t : (T-case) G case t { x t x t } :

27 Sum Types: Dynamics Dynamics Inject t t (D-inject ) 1 inj t d as inj t d as case t val (D-inject ) 2 inj t d as val t t (D-case ) 1 case t { x t x t } case t { x t x t } t val case inj t L as { x t x t } [ t / x ] t t val case inj t R as { x t x t } [ t / x ] t (D-case ) 2 (D-case ) 3 27

28 Type Algebra void and unit types Type :: void unit Term t :: null void 是无参的和类型 unit 是无参的积类型 null 是 unit 类型的唯一值 void 类型没有值相等的类型 ( 表示类型值的个数 ) unit void 若 = bool, 有 bool x unit 的项 (true, null), (false, null) 将 unit 加入 pair, 对数据结构并未增加额外的信息 The algebra (and calculus!) of algebraic data types 28

29 Some Useful Sum Types Enumerate types 例 : 扑克牌的花色类型引入形式 ( 值 ): 消去形式 card unit+(unit+(unit+unit)) hearts spades diamonds clubs hearts inj null L as card spades inj (inj null L as (unit+(unit+unit))) R as card... case hearts as card { f f f f } f * case spades as card { f f f f } f *

30 Some Useful Sum Types Option types 类型引入形式 ( 值 ): 消去形式 option null inj null L as option unit+ null just( M) just( M) inj M R as option, M : ifnull : option (unit ) ( ) ifnull null { _:unit. e x :. e } e ifnull just( M) { _:unit. e x :. e } [ M / x] e

31 Some Useful Sum Types 理解空指针错误 option 类型的意义之一在 OO 语言中, 所有对象都是引用 ( 指针 ), 对象的引用可能为空, 不能通过空引用来访问对象的域类型如何避免空指针错误? 一些语言提供空指针的检测函数 null : bool if null(e) then error else ok 但是空指针异常仍然普遍, 原因 : 1) 缺少空指针检测 ; 2) 极少在程序的异常处进行空指针检测解决 : 用 option 描述类型为的可选值类型, 其值或者为类型的值, 或者为空. 消去形式 ifnull e { _:unit. error x:. ok } 31

32 Reduction Strategies 操作语义与符号解释器不确定的解释器 : 每一步可选择任意的子表达式进行归约确定的解释器 : 每一步选择一个特定的下一步归约并行的解释器 : 把几个归约同时作用于不相交的子表达式确定的归约 : 归约策略归约策略 : 是项到项的部分函数 F, 它具有性质 : 如果 F(e)=e', 那么 e e'. 求值函数 : e if F( e ) is not defined 1 1 eval ( e ) F 1 e if F( e ) e and eval ( e ) e F

33 Reduction Strategies 三种归约策略例, 若 e 1 e 1 ' 且 e 2 e 2 ', 则 ( x:.e 1 ) e 2 可以归约成 [e 2 / x] e 1 : 最左最外归约, 最左归约, 惰性归约. 对于函数应用, 称为按名调用若 e 1 中有形参 x 的多次出现, 用 e 2 代换 x 会使函数体中有多个 e 2, 从而 e 2 的归约会重复多次. ( x:. e 1 ) e 2 ' : 急切归约. 对于函数应用, 称为按值调用若 e 2 无范式, 则 ( x:. e 1 ) e 2 的急切归约不会终止. 若 e 2 在最终的结果中不使用, 则最左归约方式因无需归约 e 2 而终止. ( x:.e 1 ') e 2 : 在提供 e 2 前试图优化函数 x:.e 1 33

WWW PHP Comments Literals Identifiers Keywords Variables Constants Data Types Operators & Expressions 2

WWW PHP Comments Literals Identifiers Keywords Variables Constants Data Types Operators & Expressions 2 WWW PHP 2003 1 Comments Literals Identifiers Keywords Variables Constants Data Types Operators & Expressions 2 Comments PHP Shell Style: # C++ Style: // C Style: /* */ $value = $p * exp($r * $t); # $value