Homework 4 SNU 4190.310, 2013 가을이광근 Program Due: 10/26( 토 ) 24:00 Essay Due: 10/28( 월 ), 14:00 이번숙제의목적은 : 상식적인수준에서디자인된명령형언어의대표격인 C언어의역사와, 컴퓨터실행 ( 기계적인계산 ) 과상위논리의관계, 프론티어들의프로그래밍언어사용경향에대한자료등을읽고느낀바를글로쓰기. 언어사이의자동번역기를제작해보기. 메모리재활용의기본개념을구현해보기. 앞으로프로그래밍언어구현에서넘어야할산이, 상식만으로는넘기어렵다는것을겪어보기. Exercise 1 (30pts) 논술에세이 강의홈페이지의읽을거리 [Part I] 에매달린글들을읽고리포트로작성해서제출합니다. 논술의구성은 : 읽은내용정리 30%, 읽고느낀점 70% 로. 각단락은두괄식으로. 두괄식이란, 단락의결론을단락의첫문장으로가져오는것을말합니다. 단락내용을정리한문장 (topic sentence) 이단락의첫문장. 작성한에세이단락들의첫문장들만을읽어도논술의흐름이부드럽게되는지확인. 1
A4 용지총 4 페이지를넘기지말것. 반드시컴퓨터로출력해서제출. 10/28( 월 ) 수업시간에제출. No delay acceptable. Exercise 2 (40pts) SM5 K--( 교재 4.3) 프로그램들을가상기계 (abstract machine) 인 SM5에서실행될수있도록번역하는번역기를제작한다. SM5는가상의기계이다. SM 은 Stack Machine 을뜻하고, 5 는그기계의부품이 5개이기때문이다 : (S, M, E, C, K) S 는스택, M 은메모리, E 는환경, C 는명령어, K 는남은할일 ( continuation 이라고부름 ) 을뜻하고다음집합들의원소이다 : S Stack = Svalue list M Memory = Loc Value E Environment = (Var (Loc + Proc)) list C Command = Cmd list K Continuation = (Command Environment) list v Value = Integer + Bool + { } + Record + Loc x Var a, o, l Loc = Base Offset Offset = Integer z Integer b Bool r Record = (Var Loc) list w Svalue = Value + Proc + (Var Loc) (* stackable values *) p Proc = Var Command Environment Cmd = {push v, push x, push(x,c ), pop, store, load, jtr(c,c ), malloc, box z, unbox x, bind x, unbind, get, put, call, add, sub, mul, div, eq, less, not} 2
기계의작동은다음과같이기계의상태가변화하는과정으로정의할수있다 : (S, M, E, C, K) (S, M, E, C, K ) 언제어떻게위의기계작동의한스텝 ( ) 이일어나는지는다음과같다 : (S, M, E, push v :: C, K) (v :: S, M, E, C, K) (S, M, E, push x :: C, K) (w :: S, M, E, C, K) if (x, w) is the first such entry in E (S, M, E, push (x, C ) :: C, K) ((x, C, E) :: S, M, E, C, K) (w :: S, M, E, pop :: C, K) (S, M, E, C, K) (l :: v :: S, M, E, store :: C, K) (S, M{l v}, E, C, K) (l :: S, M, E, load :: C, K) (M(l) :: S, M, E, C, K) 3
(true :: S, M, E, jtr(c 1, C 2 ) :: C, K) (S, M, E, C 1 :: C, K) (false :: S, M, E, jtr(c 1, C 2 ) :: C, K) (S, M, E, C 2 :: C, K) (S, M, E, malloc :: C, K) ( a, 0 :: S, M, E, C, K) new a (w 1 :: :: w z :: S, M, E, box z :: C, K) ([w 1,, w z ] :: S, M, E, C, K) ([w 1,, w z ] :: S, M, E, unbox x :: C, K) (v :: S, M, E, C, K) w k = (x, v), 1 k z (w :: S, M, E, bind x :: C, K) (S, M, (x, w) :: E, C, K) (S, M, (x, w) :: E, unbind :: C, K) ((x, w) :: S, M, E, C, K) (l :: v :: (x, C, E ) :: S, M, E, call :: C, K) (S, M{l v}, (x, l) :: E, C, (C, E) :: K) (S, M, E, empty, (C, E ) :: K) (S, M, E, C, K) (S, M, E, get :: C, K) (z :: S, M, E, C, K) read z from outside (z :: S, M, E, put :: C, K) (S, M, E, C, K) print z and newline 4
(v 2 :: v 1 :: S, M, E, add :: C, K) (plus(v 1, v 2 ) :: S, M, E, C, K) (v 2 :: v 1 :: S, M, E, sub :: C, K) (minus(v 1, v 2 ) :: S, M, E, C, K) (z 2 :: z 1 :: S, M, E, mul :: C, K) ((z 1 z 2 ) :: S, M, E, C, K) similar for div (v 2 :: v 1 :: S, M, E, eq :: C, K) (equal(v 1, v 2 ) :: S, M, E, C, K) (v 2 :: v 1 :: S, M, E, less :: C, K) (less(v 1, v 2 ) :: S, M, E, C, K) (b :: S, M, E, not :: C, K) ( b :: S, M, E, C, K) less(z 1, z 2 ) = z 1 < z 2 plus(z 1, z 2 ) = z 1 + z 2 plus( a, z 1, z 2 ) = a, z 1 + z 2 if z 1 + z 2 0 plus(z 1, a, z 2 ) = a, z 1 + z 2 if z 1 + z 2 0 minus(z 1, z 2 ) = z 1 z 2 minus( a, z 1, z 2 ) = a, z 1 z 2 if z 1 z 2 0 equal(z 1, z 2 ) = z 1 = z 2 equal(b 1, b 2 ) = b 1 = b 2 equal(, ) = true equal(r 1, r 2 ) = ( x, l r 1 : x, l r 2 ) ( x, l r 2 : x, l r 1 ) equal( a 1, z 1, a 2, z 2 ) = a 1 = a 2 z 1 = z 2 equal(, ) = false SM5 의프로그램 C 를실행한다는것은, C 만가지고있는빈기계상태를위 에서정의한방식으로변환해간다는뜻이다 : (empty, empty, empty, C, empty) 5
예를들어, push 1 :: push 2 :: add :: put :: empty 는 K-- 프로그램 write 1+2과같은일을하게된다. 여러분이할것은, 잘돌아가는 K-- 프로그램을입력으로받아서같은일을하는 SM5 프로그램으로변환하는함수 trans: K.program -> Sm5.command 를작성하는것이다. trans가제대로정의되었는지는, K-- 프로그램 E에대해서, K.run(E) 와 Sm5.run(trans(E)) 을실행해서확인할수있을것이다. 모듈 Sm5, 모듈 K, 그리고 K--의파서는제공된다 (TA 페이지참고 ). Exercise 3 (40pts) SM5 Limited = SM5 + 메모리재활용 SM5 메모리에서는무한히많은새로운주소가샘솟을수없다. 이제, SM5의메모리는 8K(2 13 ) 개의주소만있다고하자. 위의문제에서주어진모듈 Sm5를뜯어고쳐서, malloc할것이더이상없을때메모리를재활용하는함수 gc를장착하라. 즉, (S, M, E, malloc :: C, K) (l :: S, M, E, C, K) new l 이아래와같이변경될것이다 : (S, M, E, malloc :: C, K) (l :: S, M, E, C, K) new l, if domm < 2 13 (S, M, E, malloc :: C, K) (l :: S, gc( ), E, C, K) recycled l, if domm = 2 13 재활용함수 gc는실제구현보다훨씬간단하다. 현재메모리에서미래에사용할수있는부분만을모으면될것이다. 그러한부분들은현재기계상태의두개의부품 ( 와 ) 에서부터도달가능한모든메모리주소들이될것이다. Exercise 4 (30pts) 탐사준비 탐사해야할지역의지도를보고탐사를성공리에마치기위해필요한최소의준비물을알아내는프로그램을작성해보자. 탐사는지도에나타난길을따라이동하면서길에놓인보물상자를열고보물을모아가는것이고, 모든보물이모아지면그탐사는성공한것이다. 준비물은모든보물상자를열수있는열쇠들이다. 보물상자와열쇠 : 6
보물상자에는고유의알파벳이름이표시되어있다. 이름없이 라고찍혀있는보물상자도있다. 같은이름의보물상자는같은열쇠로열린다. 하나의열쇠는외갈래혹은두갈래로갈라진가지구조 (tree) 이다. 열쇠는반복해서사용할수있다. 보물상자와열쇠를 OCaml 타입으로정의하면, type treasure = StarBox NameBox of string type key = Bar Node of key * key 탐사지도 : 시작지점은하나이다. 길들은모두외길이거나두갈래로나뉘어진다. 보물상자들은모두막다른골목의끝에있다. 갔던길을되돌아오지않고왔던곳으로다시오는방법은없다 (tree). 길목에세워진안내판에는앞으로만날보물상자의알파벳이름이쓰여져있다. 모든안내판의이름은모두다르다. 탐사지도를 OCaml 타입으로정의하면, type map = End of treasure Branch of map * map Guide of string * map 보물상자마다필요한열쇠의모양은보물상자의위치가전체탐사지도에서어디냐에따라결정되는데, 지도에서각지역이암시하는열쇠의모양은다음의조건으로결정된다 : 7
현재위치 ( 지도 ) e 위치의뜻열쇠모양의조건 보물상자 - (Bar) x x 라는이름의보 물상자 현재위치에서 x 를열어줄열쇠모양 x e 1 안내판 x 이앞에있는지도 e 1 e 1 안에서만날보물상자 x 의열쇠가 α 이고 e 1 의시작점이암시하는열쇠모양을 e 1 e 2 e 1 과 e 2 로갈라 지는갈림길 β 라고하면, 현재위치가암시하는열쇠모 양은 (α, β)( 왼쪽가지 α, 오른쪽가지 β). e 1 의시작점이암시하는열쇠모양은 (α, β) 이여야하고 e 2 의시작점이암시하 는열쇠모양은 α 이어야한다. 이때, 현재 위치가암시하는열쇠모양은 β. 예를들어, 각지도를성공적으로탐험할최소의 ( 열쇠들크기의합을기준으 로 ) 열쇠꾸러미는다음과같다 : 1. 지도 x 에는 { }. 2. 지도 x x 에는 { }. 3. 지도 ( x x) 에는 { }. 4. 지도 ( x (x x)) 를성공적으로탐험하는것은불가능. 5. 지도 ( x x) (( y y) ) 에는 { }. 6. 지도 ( x x) ( y y) 에는 {, (, )}. 7. 지도 x 에는 {, (, )}. 다음의타입에맞도록, 위와같은일을하는 getready 함수 를정의하기바랍니다. getready: map key list 8