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

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

Simple Type System - -

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

P1 P2 accept P1 reject P2

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

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

= (formal logic)

) f T F f f f f f f f

) [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 ]

) T f 1 f 2 f 1 f 2

) Γ 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

) = Γ 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

) f f f f f f f

: & 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

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

Γ 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 : (τ τ ) τ

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

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)

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)

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)

Γ 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 : ι

? E : τ E τ

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

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

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

α 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 = ι

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 α

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 α

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

( ) (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

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

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 α)

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

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