λx.x (λz.λx.x z) (λx.x)(λz.(λx.x)z) (λz.(λx.x) z) Call-by Name. Normal Order. (λz.z)

Size: px

Start display at page:

Download "λx.x (λz.λx.x z) (λx.x)(λz.(λx.x)z) (λz.(λx.x) z) Call-by Name. Normal Order. (λz.z)"

기현 묘
5 years ago
Views:

1 λx.x (λz.λx.x z) (λx.x)(λz.(λx.x)z) (λz.(λx.x) z) Call-by Name. Normal Order. (λz.z)

2 Simple Type System - -

3 1+malloc(), {x:=1,y:=2}+2,... (stuck) { } { } ADD σ,m e 1 n 1,M σ,m e 1 σ,m e 2 n 2,M + e 2 n 1 + n 2, M = = E1 + E2 E1 E2 E.1 E1 := E2 if E1 E2 E3

4 P1 P2 accept P1 reject P2

5 .. P1 P5 P2 P4 P6 P3 accept P1 P2 reject P4 P3 P5 P6

6 .. P1 P5 P2 P4 P6 P3 accept P1 P2 reject P4 P3 P5 P6

7 = (formal logic)

8 ) f T F f f f f f f f

9 ) [T ] = true [F ] = false [ f ] = not[f ] [f 1 f 2 ] = [f 1 ] andalso [f 2 ] [f 1 f 2 ] = [f 1 ] orelse [f 2 ] [f 1 f 2 ] = [f 1 ] implies [f 2 ]

10 ) T f 1 f 2 f 1 f 2

11 ) Γ f Γ f Γ T Γ f f Γ Γ F Γ f Γ f Γ f f f f Γ f 1 Γ f 2 Γ f 1 f 2 Γ f 1 f 2 Γ f 1 Γ f 1 Γ f 1 f 2 Γ {f 1 } f 3 Γ {f 2 } f 3 Γ f 1 f 2 Γ f 3 Γ {f 1 } f 2 Γ f 1 f 2 Γ f 1 Γ f 1 f 2 Γ f 2 Γ {f} F Γ f Γ f Γ f Γ F

12 ) = Γ f 1 Γ f 2 Γ f 1 f 2 {p p, p} p {p p, p} p p {p p, p} p {p p, p} p {p p, p} F {p p} p

13 ) f f f f f f f

14 : & E n x λx.e EE E + E v n λx.e [] { } E 1 E1 E 1 E 2 E1 E 2 E 2 E2 ve 2 ve2 (λx.e) v {x v}e E 1 E1 E 1 +E 2 E1+E 2 E 2 E2 v+e 2 v+e2 z 1 +z 2 z 1 + z 2

15 Γ E : τ τ ι τ τ ( ) Γ Id fin Type [Γ E : τ ] = true iff σ = Γ.E 이영원히돌든가, 값을계산 E v 하면 v : τ. (=, tau )

16 Γ E : τ Γ n : ι Γ(x) =τ Γ x : τ Γ + x : τ 1 E : τ 2 Γ λx.e : τ 1 τ 2.. λx.x + 1 : ι ι (λy.y) 2 : ι (λx.x + 1) ((λy.y) 2) : ι.!. λy.y : ι ι λz.z : ι λx.x + 1 : ι ι (λy.y) (λz.z) : ι (λx.x + 1) ((λy.y) (λz.z)) : ι Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 {x : ι} x : ι λx.x : ι ι {x : ι ι} x : ι ι λx.x : (ι ι) (ι ι) Γ E 1 : ι Γ E 2 : ι Γ E 1 +E 2 : ι.. {f : τ τ } f : τ τ {f : τ τ } f : τ τ = τ τ {f : τ τ } f f : τ λf.f f : (τ τ ) τ

17 e : τ 이고 e 가값이아니면반드시 e e. e : τ 이고 e e 이면 e : τ. Γ v : τ 이고 Γ + x : τ E : τ 이면 Γ {v/x}e : τ.

18 Lemma 1 (Progress). Suppose E is a closed, well-typed term (that is, E : τ for some τ). Then either E is a value or else there is some E with E E. Proof. By structural induction on E. E = n: Immediate, since E is a value. E = λx.e 1 : Immediate, since E is a value. E = x: Cannot occur (because E is closed). E = E 1 E 2 : By the following typing rule, E 1 : τ τ E 2 : τ E 1 E 2 : τ E 1 and E 2 are well-typed. Thus, induction hypothesis (I.H.) says that either E 1 is a value or else it can make a step of evaluation, and likewise E 2. There are three cases to consider. If E 1 is not a value: By I.H. (E 1 E 1) and the evaluation rules, E 1 E 2 E 1 E 2. If E 1 is a value and E 2 can take a step: By I.H. (E 2 E 2) and the evaluation rules, E 1 E 2 E 1 E 2. If both E 1 and E 2 are values, because of E 1 : τ τ, E 1 must be E 1 = λx.e. E 1 E 2 = λx.e v {x v}e E = E 1 +E 2 (exercise)

19 Lemma 2 (Preservation). If E : τ and E E, then E : τ. Proof. By structural induction on E. E = n or λx.e 1 : Vacuously satisfied. E = x: Cannot occur (because E is closed). E 1 : τ τ E 2 : τ E = E 1 E 2 :Bytypingrule, E 1 E 2 : τ, E 1 and E 2 are welltyped. Thus, induction hypothesis (I.H.) says that If E 1 E1 then E1 : τ τ If E 2 E2 then E2 : τ There are three cases in order for E 1 E 2 to make a step (E 1 E 2 E ): E 1 E1 and hence E 1 E 2 E1 E 2 : By I.H. and typing rules, E1 E 2 : τ E 2 E2 and hence E 1 E 2 E 1 E2: By I.H. and typing rules, E 1 E2 : τ Both E 1 and E 2 are values: E 1 must be λx.e, and hence E 1 E 2 = λx.e v. That is, E 1 E 2 = λx.e v {x v}e.byλx.e : τ τ Γ + x : τ 1 E : τ 2 and the typing rule Γ λx.e : τ 1 τ 2, x : τ E : τ holds. From x : τ E : τ and v : τ, {x v}e : τ (Preservation under Substitution Lemma). E = E 1 +E 2 (exercise)

20 Lemma 3 (Preservation under Substitution). If Γ v : τ and Γ + x : τ E : τ, then Γ {x v}e : τ. Proof. By induction on a derivation of Γ + x : τ E : τ. E = λy.e : Assume y {x} FV(v). Then, {x v}λy.e λy.{x v}e. T.S. Γ λy.{x v}e : τ = τ 1 τ 2 From Γ + x : τ λy.e : τ 1 τ 2 and typing rules, Γ + x : τ + y : τ 1 E : τ 2 By weakening Γ v : τ (and from the fact that y is new, i.e., y FV(v)), Γ + y : τ 1 v : τ I.H. Γ +y : τ 1 v : τ Γ +y : τ 1 +x : τ E : τ 2 Γ +y : τ 1 {x v}e : τ 2 From the I.H. and typing rules, Γ λy.{x v}e : τ 1 τ 2 Other cases: (exercise)

21 Γ n : ι Γ(x) =τ Γ x : τ Γ + x : τ 1 E : τ 2 Γ λx.e : τ 1 τ 2 Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 Γ E 1 : ι Γ E 2 : ι Γ E 1 +E 2 : ι

22 ? E : τ E τ

23 ? (?) Γ n : ι Γ (x) =τ Γ x : τ Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 Γ + x : τ 1 E : τ 2 Γ λx.e : τ 1 τ 2

24 Γ n : ι Γ (x) =τ Γ x : τ Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 Γ + x : τ 1 E : τ 2 Γ λx : τ 1.E : τ 1 τ 2

26 (λx. x ) α 1 = α x α 2 = α β α 3 = ι α = α 3 β = α x α x = α α 4 = β

27 α 1 = α x α 2 = α β α 3 = ι α = α 3 β = α x α x = α α 4 = β α 1 = α x α 2 = α β α 3 = ι α = ι β = α x α x = α α 4 = β α 1 = α x α 2 = ι β α 3 = ι α = ι β = α x α x = ι α 4 = β α 1 = ι α 2 = ι β α 3 = ι α = ι β = ι α x = ι α 4 = β α 1 = ι α 2 = ι ι α 3 = ι α = ι β = ι α x = ι α 4 = ι

28 TyEqn u τ =τ 타입방정식 u u 연립 Type τ α TyVar 타입변수 ι τ τ V (Γ, n, τ) = τ =ι V (Γ, x, τ) = τ =τ if x : τ Γ V (Γ, E 1 + E 2, τ) = τ =ι V (Γ, E 1, ι) V (Γ, E 2, ι) V (Γ, λx.e, τ) = τ = α 1 α 2 V (Γ + x : α 1, e, α 2 ) new α 1,α 2 V (Γ, E 1 E 2, τ) = V (Γ, E 1, α τ) V (Γ, E 2, α) new α

29 V (, (λx.x) 1, τ) = V (, λx.x, α τ) V (, 1, α) new α = α τ =. α 1 α 2 V (x : α 1,x,α 2 ) α =. ι = α τ.. = α 1 α 2 α 1 = α 2 α =. ι new α 1, α 2 V (Γ, n, τ) = τ =ι V (Γ, x, τ) = τ =τ if x : τ Γ V (Γ, E 1 + E 2, τ) = τ =ι V (Γ, E 1, ι) V (Γ, E 2, ι) V (Γ, λx.e, τ) = τ = α 1 α 2 V (Γ + x : α 1, e, α 2 ) new α 1,α 2 V (Γ, E 1 E 2, τ) = V (Γ, E 1, α τ) V (Γ, E 2, α) new α

30 } V (Γ,E,τ) Γ E : τ Proof. By structural induction on E.

31 ( ) (unifier) S TyVar fin Type {{α ι} } = α =. ι {α ι, α 1 ι, α 2 ι, τ ι} = α τ =.. α 1 α 2 α 1 = α 2 α =. ι unify(τ, τ ) : TyVar fin Type unify(ι, ι) = unify(α, τ) or unifty(τ, α) = {α τ} if α does not occur in τ unify(τ 1 τ 2, τ 1 τ 2) = let S = unify(τ 1, τ 1) S = unify(sτ 2, Sτ 2) in S S unify( ) = fail

32 unify(α, int int) ={α int int} unify(α, int α) = fail unify(α β, int int) ={α int, β int} unify(α β, int α) = S = unify(α, int) ={α int} S = unify({α int}β, {α int}α) =unify(β, int) ={β int} S S = {β int}{α int} S S { }{ S = {a b},s = {b c} S (Sa)=S b = c S (S a)=sa= b

33 unify-all(τ =τ, S) = (unify(τ, τ ))S unify-all(u u, S) = let T = unify-all(u, S) in unify-all(t u, T ) U : TyEqn (TyVar fin Type) U(V (, E, α)) (new α)

34 S S S S S = TSfor some T ι. = ι = ι {}: most general {} unifier {α ι} : a (less general) unifier

35 : (* polymorphic functions *) let I = \x.x const = \n.10 in I I; const 1 + const true end

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

오늘할것 5 6 HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M. Review: 5-2 7 7 17 5 4 3 4 OR 0 2 1 2 ~20 ~40 ~60 ~80 ~100 M 언어 e ::= const constant