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

Size: px

Start display at page:

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

기섭 엽
6 years ago
Views:

1 오늘할것 5 6

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

3 Review: OR ~20 ~40 ~60 ~80 ~100

4 M 언어 e ::= const constant id identifier fn id => e function e e application let bind in e end local block if e then e else e branch e op e infix binary operation read input write e output (e) malloc e allocation e := e assignment!e bang, dereference e ; e sequence (e,e) pair e.1 first component e.2 second component bind ::= val id = e rec id = fn id => e op ::= + - = and or const ::= true false string num id string num

5 M

6 Dynamic Semantics [Const] σ, M const const in Val, M [Id] σ(x) = v σ, M x v, M [Fun] σ, M fn x => e λx.e, σ, M [App] σ, M e 1 λx.e, σ, M σ, M e 2 v 2, M σ [x v 2 ], M e v, M σ, M e 1 e 2 v, M [RecApp] σ, M e 1 fλx.e, σ, M σ, M e 2 v 2, M σ [x v 2 ][f fλx.e, σ ], M e v, M σ, M e 1 e 2 v, M [Let] σ, M e 1 v 1, M σ[x v 1 ], M e 2 v, M σ, M let x = e 1 in e 2 end v, M [RecLet] σ, M e 1 λx.e, σ, M σ[f fλx.e, σ ], M e 2 v, M σ, M let rec f = e 1 in e 2 end v, M...

7 Static Semantics [Num] Γ n : i Type τ ::= i integer type b boolean type s string type τ τ pair type τ loc location type τ τ function type [Bool] Γ true : b Γ false : b [String] [Fun] [App] Γ string : s Γ[x τ 1 ] e : τ 2 Γ fn x => e : τ 1 τ 2 Γ e 1 : τ 1 τ 2 Γ e 2 : τ 1 Γ e 1 e 2 : τ 2 [Let] Γ e 1 : τ 1 Γ[x τ 1 ] e 2 : τ 2 Γ let x = e 1 in e 2 end : τ 2...

8 추론알고리즘구현

9 타입시스템 Γ 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 : ι

10 타입체커구현? E : τ E τ

11 구현이간단할까? ( 재귀적으로가능할까?) Γ n : ι Γ (x) =τ Γ x : τ Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 Γ + x : τ 1 E : τ 2 Γ λx.e : τ 1 τ 2

12 타입을명시하면가능 Γ n : ι Γ (x) =τ Γ x : τ Γ E 1 : τ 1 τ 2 Γ E 2 : τ 1 Γ E 1 E 2 : τ 2 Γ + x : τ 1 E : τ 2 Γ λx : τ 1.E : τ 1 τ 2

13 타입유추알고리즘

14 방정식도출 (λx. x ) α 1 = α x α 2 = α β α 3 = ι α = α 3 β = α x α x = α α 4 = β

15 연립방정식세우기 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 α

16 연립방정식세우기예 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 α

17 동일화알고리즘 unify(τ, τ ) : TyVar fin Type unify(ι, ι) = unify(α, τ) or unifty(τ, α) = {α τ} if α does not occur in τ unify(τ 1 τ 2, τ 1 τ 2) = let S = unify(τ 1, τ 1) in S S unify( ) = fail S = unify(sτ 2, Sτ 2)

18 타입

19 치환 ex) S = {α1 int, α2 int} : ( ) ex) {α1 int, α2 bool} (α1 α2) = int int : type type

20 치환의생성 / 합성 (x) (tau) ( ) f

21 cf) 하나만바꾸는치환? {α β,β α} (α) = β {β α}{α β} (α) = α 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

22 타입환경

23 (unification algorithm)

24 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

25 타입방정식확장 TyEqn u τ =τ 타입방정식 u u 연립 u u? Type τ α TyVar 타입변수 ι τ τ [Write] [Op] Γ e : τ τ = i, b, or s Γ write e : τ Γ e 1 : τ Γ e 2 : τ τ = i, b, s, or l Γ e 1 = e 2 : b

26 cf) 간단한경우면충분, (u u) ((u u) u) (u u) (u u) u

27 방정식도출 constraints

28 방정식도출

29 방정식풀기 let val x = 1 in write x end Or (a1, [string,bool,int]) ^ U (a1, a2) ^ U (a2, int) U(a1,string) ^ U (a1, a2) ^ U (a2, int) U(a1,bool) ^ U (a1, a2) ^ U (a2, int) U(a1,int) ^ U (a1, a2) ^ U (a2, int)

30 순서변경 Or (a1, [string,bool,int]) ^ U (a1, a2) ^ U (a2, int) vs. U (a1, a2) ^ U (a2, int) ^ Or (a1, [string,bool,int])

31 방정식풀기

32 SNU , 2011 HW6 Due: 6/3(Fri), 24:00 Exercise 1 (50pts) M 1 M, (simple type system) let- (let-polymorphic type system).,, (polymorphic function, ). Homework 6,, let-. SNU , 2011 TA M let-. (* example 1: polymorphic toys *) Due: 6/3(Fri), 24:00 val add = fn x => x.1 + x.1 let val I = fn x => x val const = fn n => 10 in

33 ,, let- TA M let- (* example 1: polymorphic toys *) let val I = fn x => x val add = fn x => x.1 + x.1 val const = fn n => 10 in I I; add(1, true) + add(2, "snu 310 fall 2009"); const 1 + const true + const "kwangkeun yi" end (* example 2: polymorphism with imperatives *) 1

34 add(1, true) + add(2, "snu 310 fall 2009"); const 1 + const true + const "kwangkeun yi" end (* example 2: polymorphism with imperatives *) 1 let val f = fn x => malloc x. in let val a = f 10 val b = f "pl" val c = f true in a :=!a + 1; b := "hw7"; c :=!c or false end end 1

35 (* example 3: polymorphic swap *) let val swap = fn order_pair => if (order_pair.1) (order_pair.2) then (order_pair.2) else (order_pair.2.2, order_pair.2.1) in swap(fn pair => pair = pair.2, (1,2)); swap(fn pair => pair.1 or pair.2, (true, false)) end

36 (* S K I combinators *) let val I = fn x => x val K = fn x => fn y => x val S = fn x => fn y => fn z => (x z) (y z) in S (K (S I)) (S (K K) I) 1 (fn x => x+1) end

λ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