Homework 3 SNU , 2011 가을이광근 Program Due: 10/10, 24:00 Essay Due: 10/12, 15:30 이번숙제의목적은 : 수업시간에살펴본, 상식적인명령형언어의정확한정의를이해하고그실행기를구현해보기. 상식적인수준에서디자인

Size: px

Start display at page:

Download "Homework 3 SNU , 2011 가을이광근 Program Due: 10/10, 24:00 Essay Due: 10/12, 15:30 이번숙제의목적은 : 수업시간에살펴본, 상식적인명령형언어의정확한정의를이해하고그실행기를구현해보기. 상식적인수준에서디자인"

용선 원
4 years ago
Views:

1 Homework 3 SNU , 2011 가을이광근 Program Due: 10/10, 24:00 Essay Due: 10/12, 15:30 이번숙제의목적은 : 수업시간에살펴본, 상식적인명령형언어의정확한정의를이해하고그실행기를구현해보기. 상식적인수준에서디자인된명령형언어의대표격인 C언어의역사와, 컴퓨터실행 ( 기계적인계산 ) 과상위논리의관계, 제대로정의된언어의쓰임새등에대한이야기를읽고느낀바를글로쓰기. 앞으로프로그래밍언어구현에서넘어야할산이, 상식만가지고는넘기어렵다는것을겪어보기. Exercise 1 (30pts) 논술에세이 강의홈페이지의읽을거리 [Part I] 에매달린글들을읽고 ( 비디오포함 ) 리포트로작성해서제출합니다. 논술의구성은 : 읽은내용정리 30%, 읽고느낀점 70% 로. 각단락은두괄식으로. 두괄식이란, 단락의결론을단락의첫문장으로가져오는것을말합니다. 단락내용을정리한문장 (topic sentence) 이단락의첫문장. 작성한에세이단락들의첫문장들만을읽어도논술의흐름이부드럽게되는지확인. A4용지총 10 페이지를넘기지말것. 1

2 반드시컴퓨터로출력해서제출. 10/12( 월 ) 수업시간에제출. No delay acceptable. Exercise 2 (40pts) K- 실행기 수업시간에정의한명령형언어 K- 1 를생각하자. 이번숙제는 K- 프로그램을의미정의대로실행시키는함수 (interpreter) 를작성하는것이다. 아래의 KMINUS 꼴을가지는모듈 K를정의하라. module type KMINUS = sig exception Error of string type id = string type exp = NUM of int TRUE FALSE UNIT VAR of id ADD of exp * exp SUB of exp * exp MUL of exp * exp DIV of exp * exp EQUAL of exp * exp LESS of exp * exp NOT of exp SEQ of exp * exp (* sequence *) IF of exp * exp * exp (* if-then-else *) WHILE of exp * exp (* while loop *) LETV of id * exp * exp (* variable binding *) LETF of id * id list * exp * exp (* procedure binding *) CALLV of id * exp list (* call by value *) CALLR of id * id list (* call by reference *) RECORD of (id * exp) list (* record construction *) FIELD of exp * id (* access record field *) ASSIGN of id * exp (* assign to variable *) ASSIGNF of exp * id * exp (* assign to record field *) READ of id 1 숙제를위한문법과의미의정확한정의는 TA페이지참고. 2

3 WRITE of exp type program = exp type memory type env type value val emptymemory: memory val emptyenv: env val run: memory * env * program -> value end K- 프로그램이어떻게 exp들로표현될지는쉽게추측할수있을것입니다. exp으로표현된 K- 프로그램이 S라고하면, K.run (K.emptyMemory, K.emptyEnv, S) 는프로그램 S를실행시키게되는데, 성공적으로끝나면최후의값을내어주게됩니다. 이때프로그램은실행중에 I/O를하면서프로그램이하는일을바깥세상에드러내게됩니다. 실행중에타입이맞지않는프로그램이면 Error라는예외상황을발생시키고프로그램실행이중단되야합니다. Error 란 (if and only if) 정의된의미규칙으로는그프로그램의의미가정의될수없는경우입니다. 입출력은정수만가능합니다. 출력은정수를화면에뿌리고 newline 을프린트합니다. Exercise 3 (10pts) K- 프로그래밍 : 거스름방법의수 다음을 K- 로작성하고, 위에서구현한실행기 K.run로실행시켜제대로실행되는지를확인한다. 우리나라에는 1원, 10원, 100원, 500원, 1000원, 5000원, 10000원, 50000원권이있습니다. 주어진액수의거스름돈을만들어주는방법의수를계산하는함수 numch를 K-로정의하라. 예를들어 numch(100) 은 12가지이다 : 1원만 100개로거스르는경우부터, 10원 1개와 1원 90개로거스르기,, 100원 1개로거스르기. 힌트 : 1원이하로만거스르는경우수는 1. 10원이하로만거스르는경우수는 1원이하로만거스르는경우수 + 10원을하나이상사용해서 10원이하로만거르스는경우수. 100원이하로만거스르는경우수는 10원이하로만거스르는경우수 + 100원을하나이상사용해서 100원이하로만거스르는경우수, 등등이다. 즉, 대략다음과같이정의될것이다. K--로완성해서, 여러분이작성한 K.run으로테스트해보기바랍니다. 3

4 numch(n) = if n<10 then numch1(n) else if n<100 then numch10(n)... numch1(n) = 1 numch10(n) = if n<10 then numch1(n) else if... else numch1(n) + numch10(n-10)... Exercise 4 (10pts) K- 프로그래밍 : compound data 다음을 K- 로작성하고, 위에서구현한실행기 K.run로실행시켜제대로실 행되는지를확인한다. 두갈래나무구조 (binary tree) 를만들고쓸수있는아래의함수들을정의하 라 : leaf: int tree (* a leaf tree *) makeltree: int tree tree (* a tree with only a left subtree *) makertree: int tree tree (* a tree with only a right subtree *) maketree: int tree tree tree (* a tree with both subtrees *) isempty: tree bool (* see if empty tree *) rtree: tree tree (* right subtree *) ltree: tree tree (* left subtree *) nodeval: tree int (* node value *) dft: tree unit (* print node values in depth-first order *) bft: tree unit (* print node values in breath-first order *) 위의함수들만을이용해서나무구조를만들고 dft 와 bft 를돌려서제대 로된순서로출력되는지를확인하라. 참고로, 만든실행기에메모리소모량을측정하는장치를달고, 프로그램을 돌렸을때얼만큼의메모리를소모하는지를재보자. 메모리소모가될수있 으면작도록프로시져를구현하도록해보자. Exercise 5 (20pts) 탐사준비 탐사해야할지역의지도를보고탐사를성공리에마치기위해필요한최소 의준비물을알아내는프로그램을작성해보자. 4

5 탐사는지도에나타난길을따라이동하면서길에놓인보물상자를열고보물을모아가는것이고, 모든보물이모아지면그탐사는성공한것이다. 준비물은모든보물상자를열수있는열쇠들이다. 보물상자와열쇠 : 보물상자에는고유의알파벳이름이표시되어있다. 이름없이 라고찍혀있는보물상자도있다. 같은이름의보물상자는같은열쇠로열린다. 하나의열쇠는외갈래혹은두갈래로갈라진가지구조 (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 보물상자마다필요한열쇠의모양은보물상자의위치가전체탐사지도에서어디냐에따라결정되는데, 지도에서각지역이암시하는열쇠의모양은다음의조건으로결정된다 : 5

6 현재위치 ( 지도 ) 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 6

A4 용지총 4 페이지를넘기지말것. 반드시컴퓨터로출력해서제출. 10/28( 월 ) 수업시간에제출. No delay acceptable. Exercise 2 (40pts) SM5 K--( 교재 4.3) 프로그램들을가상기계 (abstract machine) 인 SM5에서실

A4 용지총 4 페이지를넘기지말것. 반드시컴퓨터로출력해서제출. 10/28( 월 ) 수업시간에제출. No delay acceptable. Exercise 2 (40pts) SM5 K--( 교재 4.3) 프로그램들을가상기계 (abstract machine) 인 SM5에서실 Homework 4 SNU 4190.310, 2013 가을이광근 Program Due: 10/26( 토 ) 24:00 Essay Due: 10/28( 월 ), 14:00 이번숙제의목적은 : 상식적인수준에서디자인된명령형언어의대표격인 C언어의역사와, 컴퓨터실행 ( 기계적인계산 ) 과상위논리의관계, 프론티어들의프로그래밍언어사용경향에대한자료등을읽고느낀바를글로쓰기.