Homework 2 SNU 4190.310, Fall 2015 Kwangkeun Yi due: 9/30, 24:00 Exercise 1 (10pts) k- 친수 일반적으로 k 진수 (k > 1) 는다음과같이표현한다. d 0 d n 여기서 d i {0,, k 1}. 그리고 d 0 d n 은크기가 d 0 k 0 + + d n k n 인정수를표현한다. 이것을살짝확장해서 k친수 를다음과같이정의해보자. 표현은 d 0 d n 여기서 d i {1 k,, 0} {0,, k 1}. 그리고 d 0 d n 은크기가 d 0 k 0 + + d n k n 인정수를표현한다. 예를들어, 2친수의경우를생각하자. 베이스가 { 1, 0, 1} 이되겠다. 0이 0을, + 가 1을 -가 1을표현한다고하면, + 는 1을, +0+ 는 5를, +-는 1을, +-0-는 9인정수를표현한다. 1
OCaml로 2친수라는타입을다음과같이정의했다 : type crazy2 = NIL ZERO of crazy2 ONE of crazy2 MONE of crazy2 예를들어, 0+-은 ZERO(ONE(MONE NIL)) 로표현된다. 위와같이표현되는 2친수를받아서그것의값을계산하는함수 crazy2val을정의하세요. crazy2val: crazy2 -> int. Exercise 2 (10pts) 친수의합 두 2친수를받아서 2친수의합에해당하는 2친수를내어놓는함수 crazy2add를정의하세요. crazy2add: crazy2 * crazy2 -> crazy2 위의 crazy2add는다음의성질이만족되야한다 : 임의의 2친수 z 과 z 에대해서 crazy2val (crazy2add(z,z )) = crazy2val(z) + crazy2val(z ). Exercise 3 (10pts) CheckMetroMap 아래 metro 타입을생각하자 : type metro = STATION of name AREA of name * metro CONNECT of metro * metro and name = string 아래 checkmetro 함수를정의하라 : checkmetro: metro -> bool checkmetro는주어진 metro 가제대로생겼는지를확인해준다. metro가제대로생겼다 는것은 (iff) 메트로역이름 (id in STATION(id)) 들이항상자기이름의지역 (m in AREA(id, m)) 에서만나타나는경우를뜻한다. 예를들어, 제대로생긴 metro 들은 : 2
AREA("a", STATION "a") AREA("a", AREA("a", STATION "a")) AREA("a", AREA("b", CONNECT(STATION "a", STATION "b"))) AREA("a", CONNECT(STATION "a", AREA("b", STATION "a"))) 그렇지못한것들의예들은 : AREA("a", STATION "b") AREA("a", CONNECT(STATION "a", AREA("b", STATION "c"))) AREA("a", AREA("b", CONNECT(STATION "a", STATION "c"))) Exercise 4 (15pts) 짚-짚-나무 임의의나무를여러분바지의 지퍼 로구현할수있답니다. 나무구조타입은아래와같이정의됩니다 : type item = string type tree = LEAF of item NODE of tree list 아래의 zipper가나무의줄기를타고자유자재로찢어놓기도하고붙여놓기도합니다. type zipper = TOP HAND of tree list * zipper * tree list 현재나무줄기의어느지점에멈춰있는지퍼손잡이 HAND(l,z,r) 에서, l은왼편형제나무들 (elder siblings) 이고 r은오른편형제나무들 (younger siblings) 이다. 나뭇가지에서의현재위치 location는현재위치를뿌리로하는나무자체와지퍼 (zipper) 로표현되는주변나무들로구성된다. type location = LOC of tree * zipper 예를들어, a b + c d 가다음과같은나무구조로표현될것이다. 모든심볼은항상잎새에매달리게된다. NODE [ NODE [LEAF a; LEAF *; LEAF b]; 3
LEAF +; NODE [LEAF c; LEAF *; LEAF d] ] 두번째곱셈표에의위치는다음과같다 : LOC (LEAF *, HAND([LEAF c], HAND([LEAF +; NODE [LEAF a; LEAF *; LEAF b]], TOP, []), [LEAF d])) 자, 주어진위치에서이제자유자재로나무를탈수있습니다. 왼편으로옮겨가는것은다음과같지요 : let goleft loc = match loc with LOC(t, TOP) -> raise (NOMOVE "left of top") LOC(t, HAND(l::left, up, right)) -> LOC(l, HAND(left, up, t::right)) LOC(t, HAND([],up,right)) -> raise NOMOVE "left of first" 다음의나머지함수들을정의하세요 : goright: location -> location goup: location -> location godown: location -> location Exercise 5 (10pts) Galculator 다음의계산기 galculator: exp -> float 를만듭시다. type exp = X INT of int REAL of float ADD of exp * exp SUB of exp * exp MUL of exp * exp DIV of exp * exp 4
SIGMA of exp * exp * exp INTEGRAL of exp * exp * exp 예를들어우리가쓰는수식이 exp 타입으로는다음과같이표현된다 : 10 x=1 10.0 x=1.0 (x x 1) SIGMA(INT 1, INT 10, SUB(MUL(X, X), INT 1)) (x x 1)dx INTEGRAL(REAL 1.0, REAL 10.0, SUB(MUL(X, X), INT 1)) 적분식을계산할때의알갱이크기 (dx) 는 0.1 로정한다. Exercise 6 (10pts) Queue = 2 Stacks 큐는반드시하나의리스트일필요는없습니다. 두개의스택으로큐를효 율적으로규현할수있습니다. 큐에넣고빼는작업이거의한스텝에이루어 질수있습니다. ( 하나의리스트위를더듬는두개의포인터를다루었던 C 의 구현과장단점을비교해보세요.) 각각의큐연산들의타입들은 : emptyq: queue enq: queue * element -> queue deq: queue -> element * queue 큐를 [a 1 ; ; a m ; b 1 ; ; b n ] 라고합시다 (b n 이머리 ). 이큐를두개의리스트 L 과 R 로표현할수있습니다 : L = [a 1 ; ; a m ], R = [b n ; ; b 1 ]. 한원소 x 를삼키면새로운큐는다음이됩니다 : [x; a 1 ; ; a m ], [b n ; ; b 1 ]. 원소를하나빼고나면새로운큐는다음이됩니다 : [a 1 ; ; a m ], [b n 1 ; ; b 1 ]. 뺄때, 때때로 L 리스트를뒤집어서 R 로같다놔야하겠습니다. 빈큐는 ([], []) 이겠지요. 다음과같은 Queue 타입의모듈을작성합니다 : module type Queue = sig 5
type element type queue exception EMPTY Q val emptyq: queue val enq: queue * element -> queue val deq: queue -> element * queue end 다양한큐모듈이위의 Queue 타입을만족시킬수있습니다. 예를들어 : module IntListQ = struct type element = int list type queue =... exception EMPTY Q let emptyq =... let enq =... let deq =... end 는정수리스트를큐의원소로가지는경우겠지요. 위의모듈에서함수 enq와 deq를정의하기바랍니다. 이모듈에있는함수들을이용해서큐를만드는과정의예는 : let myq = IntListQ.emptyQ let yourq = IntListQ.enQ(myQ, [1]) let (x,restq) = IntListQ.deQ yourq let hisq = IntListQ.enQ(myQ, [2]) Exercise 7 (20pts) 계산실행 아래 ZEXPR 꼴을가지는모듈 Zexpr를정의해봅시다. signature ZEXPR = sig exception Error of string type id = string type expr = NUM of int PLUS of expr * expr MINUS of expr * expr 6
MULT of expr * expr DIVIDE of expr * expr MAX of expr list VAR of id LET of id * expr * expr type environment type value val emptyenv: environment val eval: env * expr -> value end ZEXPR.expr 타입의식을 E라고하면, ZEXPR.eval (ZEXPR.emptyEnv, E) 는식 E를실행시키게되는데, 성공적으로끝나면최종값을프린트하고끝나게됩니다. 이때, VAR "x" 는 x라고명명된값을뜻합니다. 이름을정의하고그유효범위를한정하는식은 LET("x", E 1, E 2 ) 입니다. 이경우 E 1 값을계산해서 x라고이름짓게되고, 그이름의유효범위는 E 2 로한정됩니다. 현재환경에서정의되지않은이름이식에서사용되면그식은의미가없습니다. 예를들어, LET("x", 1, PLUS (LET("x", 2, PLUS(VAR "x", VAR "x")), VAR "x") ) 의계산결과는 5입니다. LET("x", 1, PLUS (LET("y", 2, PLUS(VAR "x", VAR "y")), VAR "x") ) 의계산결과는 4입니다. LET("x", 1, PLUS (LET("y", 2, PLUS(VAR "y", VAR "x")), VAR "y") ) 는의미가없습니다. 바깥 PLUS식의환경에서 y가정의되어있지않기때문입니다. 7
MAX 식은정수식리스트에서가장큰정수를찾아내는정수식입니다. 즉, MAX [NUM 1, NUM 3, NUM 2] 의계산결과는 3 입니다. MAX 가빈리스트를받 은경우결과는 0 입니다. 8