EECS101 전자계산입문아홉번째숙제 - Mi-Ocaml 만들기 - (200 점 + α) 이재봉 (novaever@postech) 제출마감 : 5 월 29 일 11:59pm 여러분은이제까지컴퓨터를이용한간단한정수의사칙연산에서부터변수나함수그리고자기호출함수를이용한다양한계산방법까지배웠습니다. 이렇게컴퓨터를이용해계산을하기위해여러분은이제까지 Ocaml이라는프로그래밍언어를이용했습니다. 이번숙제에서는여러분이직접 Ocaml의일부기능을수행하는프로그램을만들어보겠습니다. 부정행위에관한규정은 POSTECH 전자컴퓨터공학부학부위원회의 POSTECH 전자컴퓨터공학부부정행위정의 를따릅니다. (http://http://www.postech.ac.kr/~gla/cs101/disciplary/dex.html) 제 1 절 Mi-Ocaml 두정수의사칙연산을수행하는함수를만들었다고하자. 이함수를이용하면다음과같은계산을할수있다. 3 + 2 5 이번에는다음과같이조금더복잡한연산식이있다고하자. 2 * 3 + 100 / (7-2) 연산자 * 와 / 는 + 나 -보다우선순위가높으므로이를고려하여연산식에괄호를모두집어넣으면 ((2 * 3) + (100 / (7-2))) 이렇게바뀌게된다. 이제이연산식을단계적으로계산하면아래와같다. ((2 * 3) + (100 / (7-2))) (6 + (100 / (7-2))) (6 + (100 / 5)) (6 + 20) 26 1
즉, 두정수의사칙연산을계산하는함수를자기호출하면사칙연산이여러번들어간연산식도계산할수있다. 이번에는변수에대해생각해보자. 다음과같은연산식을계산한다고하자. let a = 2 a + 1 먼저 let과 사이의정의를보고변수 a에정수 2가저장되어있다는것을기억해둔다. 그다음에 뒤에오는연산식 a + 1을계산한다. 변수 a에 2가저장되어있다는것을알고있으므로 a + 1을 2 + 1로바꾸어계산하면 3을구할수있다. 이과정을단계적으로나타내면다음과같다. 아래그림에서왼쪽에있는상자는변수를저장하고있는공간을나타낸다. let a = 2 a + 1 a = 2 a + 1 a = 2 2 + 1 a = 2 3 같은이름의변수를여러번정의할수있으므로연산식을계산하다가변수를만나면가장최근에저장한변수부터사용해야한다. 예를들어다음과같은연산식을계산할경우 let a = 1 let b = a + 1 let a = 2 a * b 두번째줄의 let b = a + 1 을계산할때는변수 a의값이정수 1이지만마지막줄의 a * b를계산할때는변수 a의값이정수 2가된다. 따라서이연산식의계산결과는 4가된다. 마지막으로다음과같이함수를정의하고사용하는경우를살펴보자. let f a b = a + b (f 1 2) * 2 let과 사이의정의를보고함수 f는형식인자로 a와 b를가지고몸통연산식으로 a + b를가진다는것을저장해둔다. 그다음에 뒤에오는연산식 (f 1 2) * 2를계산한다. 연산식을계산하는도중에함수적용 f 1 2를만나면이전에저장해둔함수 f를찾는다. 함수 f는형식인자로 a와 b를가지므로정수 1과 2를각각의형식인자에저장하고몸통연산식인 a + b를계산한다. 변수를계산할때와마찬가지로 a에는 1, b에는 2가저장되어있음을이용하여몸통연산식을계산하면함수적용결과 f 1 2는 3이된다. 이제 3 * 2를계산하면 6을얻을수있다. 이과정을단계적으로나타내면다음과같다. let f a b = a + b (f 1 2) * 2 f a b = a + b (f 1 2) * 2 2
b = 2 a = 1 f a b = a + b (a + b) * 2 b = 2 a = 1 f a b = a + b (a + 2) * 2 b = 2 a = 1 f a b = a + b (1 + 2) * 2 f a b = a + b 3 * 2 f a b = a + b 6 이번숙제에서여러분이직접만들게될 Mi-Ocaml은정수연산식의계산을수행할수있는프로그래밍언어이며 Ocaml의문법을동일하게사용한다. 기본적인정수의사칙연산과나머지연산그리고조건연산식을계산할수있으며변수와함수를정의하여사용할수있다. 이숙제를모두완성하면그림 1과같이과제 3이나과제 4에서작성했던 gcd나 log2 또는 b2dec과같은프로그램을여러분이직접만든 Mi-Ocaml에서계산할수있게된다. 그림 1: 완성한 Mi-Ocaml 의실행예 3
제 2 절 골격파일과검사파일 웹브라우저에서 http://www.postech.ac.kr/~gla/cs101/hw/hw9.ml http://www.postech.ac.kr/~gla/cs101/hw/hw9-check.ml http://www.postech.ac.kr/~gla/cs101/hw/ma.ml http://www.postech.ac.kr/~gla/cs101/hw/parser.ml 또는 FTP client에서 <Hemos home folder> /cs101 hand/hw9/hw9.ml <Hemos home folder> /cs101 hand/hw9/hw9-check.ml <Hemos home folder> /cs101 hand/hw9/ma.ml <Hemos home folder> /cs101 hand/hw9/parser.ml 을내려받는다. 이번숙제에서는총 4개의파일을받아야한다. 제 3 절 숙제작성법 hw9.ml 은다음과같은구조를가지고있다. exception NotImplemented;; < 중략 > (* 연산식계산 * exp -> t *) let rec calc_exp e = raise NotImplemented;; 함수 calc exp는연산식을받아계산결과를넘겨주는함수이다. 이함수를작성하기위해등호와 ;; 사이에있는 raise NotImplemented를삭제하고문제가요구하는올바른연산식을채워넣는다. 연산식 raise NotImplemented는함수의몸통연산식이작성되지않았다는예외상황을표시하며, 의미자체는본숙제의해결에중요하지않다. 만약올바르게함수를정의할수없다고판단하는경우함수의몸통연산식인 raise NotImplemented를삭제하지않고그대로두어야한다. 제 4 절 기본적으로제공되는것들 이번숙제에서는연산식을표현하기위한타입이제공된다. hw9.ml 에서타입선언부분만추려내면다음 과같다. 4
(* 연산식정의 *) type exp = Num of t (* 정수 *) Var of strg (* 변수 *) Neg of exp (* 음수 *) Sum of exp * exp (* 더하기 *) Diff of exp * exp (* 빼기 *) Mult of exp * exp (* 곱하기 *) Div of exp * exp (* 나누기 *) Mod of exp * exp (* 나머지 *) If of exp * exp * exp * exp (* 조건연산식 *) Let of strg * exp * exp (* 변수정의 *) Fun of strg * strg list * exp * exp * bool (* 함수정의 *) App of strg * exp list (* 함수적용 *) ;; exp는연산식을표현하기위한생성자들의합집합이다. 이합집합의각생성자에대해서살펴보자. 각항목아래에있는예는사용자가입력한 Mi-Ocaml 코드를여러분이작성할함수 calc exp에서사용할 exp 타입으로변환한것이다. Num n : 정수 n ( 예 ) 100 Num 100 Var v : 변수 v ( 예 ) sum Var "sum" Neg e : ( 연산식 e) ( 예 ) -10 Neg (Num 10) Sum (e1, e2) : ( 연산식 e1) + ( 연산식 e2) ( 예 ) a + 2 Sum (Var "a", Num 2) Diff (e1, e2) : ( 연산식 e1) ( 연산식 e2) ( 예 ) a - 2 Diff (Var "a", Num 2) Mult (e1, e2) : ( 연산식 e1) ( 연산식 e2) ( 예 ) a * 2 Mult (Var "a", Num 2) Div (e1, e2) : ( 연산식 e1) ( 연산식 e2) ( 예 ) a / 2 Div (Var "a", Num 2) Mod (e1, e2) : ( 연산식 e1) mod ( 연산식 e2) ( 예 ) a mod 2 Mod (Var "a", Num 2) If (c1, c2, e1, e2) : if c1 = c2 then e1 else e2 연산식 c1을계산한값과연산식 c2를계산한값을서로비교하여같으면연산식 e1을계산하고다르면연산식 e2를계산한다. ( 예 ) if a = 3 then 0 else 1 If (Var "a", Num 3, Num 0, Num 1) 5
Let (v, d, e) : let v = d e v라는이름을가진변수에연산식 d를계산한결과를저장한후연산식 e를계산한다. ( 예 ) let a = 1 a + 1 Let ("a", Num 1, Sum (Var "a", Num 1)) Fun (f, [x 1, x 2,..., x n ], d, e, r) r이 true일경우 : let rec f x 1 x 2... x n = d e r이 false일경우 : let f x 1 x 2... x n = d e 형식인자 x 1, x 2,..., x n 과몸통연산식 d를가지는함수 f를저장한후연산식 e를계산한다. 형식인자는반드시하나이상있다고가정한다. r이 true인경우에함수 f는자기호출함수이지만 r이 false인경우에함수 f는자기호출함수가아니다. ( 예 ) let f x y = x + y f 1 2 Fun ("f", ["x"; "y"], Sum (Var "x", Var "y"), App ("f", [Num 1; Num 2]), false) App (f, [e l, e 2,..., e n ]) : f e l e 2... e n 함수 f의인자로 e l, e 2,..., e n 을넘겨주고함수 f를계산한다. 인자는반드시하나이상있다고가정한다. ( 예 ) f 1 2 App ("f", [Num 1; Num 2]) 사용자가입력한 Mi-Ocaml 연산식을 exp 타입으로변환하는기능은이미 ma.ml과 parser.ml에작성되어있으므로이에대해서는신경쓰지않아도된다. 여러분은단지 exp 타입으로변환된 Mi- Ocaml 연산식을계산하여정수값을반환하는함수 calc exp만올바로작성하면된다. 사용자가입력한 Mi-Ocaml 연산식이 exp 타입으로변환된결과를보고싶으면아래와같이한다. Ocaml을실행한다. hw9.ml을연다. ([ 메뉴 ] [File] [Open] hw9.ml을선택 ) parser.ml을연다. ([ 메뉴 ] [File] [Open] parser.ml을선택 ) convert "< 변환할연산식 >";; 을이용하여연산식변환결과를볼수있다. 다음은 convert 함수를사용한예이다. # convert "-10";; - : exp = Neg (Num 10) # convert "let a = 3 a * 2";; - : exp = Let ("a", Num 3, Mult (Var "a", Num 2)) # convert "let f x = x + 1 f 2";; - : exp = Fun ("f", ["x"], Sum (Var "x", Num 1), App ("f", [Num 2]), false) 제 5 절 컴파일및테스트 숙제를작성한후실행결과를확인하는방법에는두가지가있다. 6
컴파일 후 실행 숙제파일 hw9.ml을 비롯해 내려받도록 지시한 파일들을 모두 동일한 폴더에 위치시킨다. 명령 프롬프트([시작] [프로그램] [보조 프로그램] [명령 프롬프트])를 실행한 후, cd명령어를 이 용해 숙제파일 hw9.ml이 위치한 폴더로 이동한다. 아래와 같이 ocamlc 명령어를 이용해 숙제파일을 컴파일한다. ocamlc -o hw9.exe hw9.ml ma.ml 오류 없이 컴파일이 성공하였다면 hw9.exe 파일이 생성된다. hw9.exe를 실행하면 연산식을 입력할 수 있는 상태가 된다. 원하는 연산식을 입력하여 결과를 확인 한다. Ocaml과 동일하게 연산식은 여러줄에 걸쳐 입력할 수 있으며 ;;로 연산식의 끝을 나타낸다. 프로그램을 종료하고 싶으면 Ctrl + c를 누른다. 다음은 컴파일하여 실행 결과를 확인하는 예이다. D:\Programmg\Assignments\Graduate\EECS101\hw9>ocamlc -o hw9.exe hw9.ml ma.ml <Warng 메시지 생략> D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # -10;; -10 # let a = 3 a * 2;; 6 # let f x = x + 1 f 2;; 3 # D:\Programmg\Assignments\Graduate\EECS101\hw9> Ocaml 인터프리터에서 직접 실행 Ocaml을 실행한다. hw9.ml을 연다. ([메뉴] [File] [Open] hw9.ml을 선택) parser.ml을 연다. ([메뉴] [File] [Open] parser.ml을 선택) calc exp (convert "<변환할 연산식>");;을 이용하여 결과를 확인한다. 다음은 Ocaml 인터프리터에서 직접 실행 결과를 확인하는 예이다. 7
# calc_exp (convert "-10");; - : t = -10 # calc_exp (convert "let a = 3 a * 2");; - : t = 6 # calc_exp (convert "let f x = x + 1 f 2");; - : t = 3 Ocaml 인터프리터에서자신이작성한프로그램의결과를테스트할경우, 처음에는반드시 hw9.ml을먼저열고 parser.ml을열어야하며 hw9.ml을수정한후에는반드시다시 hw9.ml과 parser.ml을여는과정을거친후에결과를확인해야한다. 이과정이컴파일러를사용하는방법보다번거롭기때문에되도록이면컴파일러를사용하여컴파일후결과를확인하는방법을사용하기를권장한다. 오류처리 3 * + 2;; 나 a + 1;;( 변수 a를정의하지않고사용 ) 과같이사용자가 Mi-Ocaml에입력한연산식에오류가있는경우다음과같이오류메시지가출력되거나아무런결과가출력되지않고무시된다. D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # 3 * + 2;; Syntax Error # a + 1;; # D:\Programmg\Assignments\Graduate\EECS101\hw9> Ocaml 인터프리터에서직접실행한경우에는다음과같이 Exception:... 메시지가출력된다. # calc_exp (convert "3 * + 2");; Exception: SyntaxError. # calc_exp (convert "a + 1");; Exception: Match_failure ("D:/Programmg/Assignments/Graduate/EECS101/HW9/hw9_sol/hw9.ml", 35, 2). 숙제검사를할때는오류가없는연산식만을사용하므로숙제를작성할때에는입력되는연산식에오류가없다고가정하고프로그램을작성하면된다. 제 6 절 타입확인및제출 문제에대한답을다작성한이후, 작성한숙제파일 hw9.ml 의 calc exp 함수가문제에서제시한타입을 만족하는지확인하기위해다음과같이검사파일을이용한다. 골격파일을편집하여숙제를작성하게되므 로이후골격파일과숙제파일은동일한파일인 hw9.ml 을가리킨다. 8
숙제파일 hw9.ml과 검사파일 hw9-check.ml을 동일한 폴더에 위치시킨다. 명령 프롬프트([시작] [프로그램] [보조 프로그램] [명령 프롬프트])를 실행한 후, cd명령어를 이 용해 숙제파일과 검사파일이 위치한 폴더로 이동한다. 아래와 같이 ocamlc 명령어를 이용해 숙제파일과 검사파일을 함께 컴파일한다. ocamlc -o hw9-check.exe hw9.ml hw9-check.ml 컴파일한 결과 명령 프롬프트에 아무런 메시지가 나타나지 않으면 작성한 함수들이 모두 올바른 타입을 가지고 있음을 의미한다. 단, Warng 메시지는 출력되어도 상관없다. 숙제 작성을 마친 후 FTP client를 이용하여 숙제파일인 hw9.ml을 자신의 숙제 제출 폴더인 <Hemos home folder> /cs101 hand/hw9/<hemos id> 에 저장한다. 주의사항 (꼭 읽어보고 시작하세요!) 필요한 경우 함수의 몸통부분에 지역 변수를 이용하여 값 또는 함수를 자유로이 정의할 수 있다. 골격파일의 어디든지 필요한 타입이나 함수를 자유롭게 정의하여 사용한다. 단, hw9-check.ml을 이용한 타입 검사를 통과해야 한다. 숙제 작성시 타입은 hw9-check.ml을 통과하면 된다. 문제에서 제시하는 함수와 실제 작성을 한 뒤에 나오는 타입이 다르더라도 hw9-check.ml을 통과한다면 문제가 없다. 단, 이번 숙제는 올바르게 프로 그램을 작성해도 Warng 메시지가 여러번 출력될 수 있으므로 Warng 메시지는 무시한다. 파일 이름은 반드시 hw9.ml이어야 한다. hw9.ml이 아닌 다른 이름의 파일을 제출하면 0점 처리 된다. 컴파일되지 않는 숙제는 0점 처리 된다. Ocaml의 라이브러리는 모두 사용해도 된다. 아래와 같은 질문은 삼가해주기 바랍니다. (코드의 내용을 보여주면서) "제 코드가 요구사항대로 동작하지 않는데 어느 부분이 잘못된 건가요?" 자신이 작성한 코드를 보여주면서 틀린부분을 찾아달라는 질문에 대하여 대답해 줄 수 없습니다. "제 코드의 함수 f는 타입이 t->t->t 인데요, 핸드아웃에는 t->(t->t) 라고 되어 있어요, 괜찮은가요?" hw9-check.ml을 이용한 타입 검사를 통과하면 됩니다. "핸드아웃의 실행 예는 다 만족하는데요 그러면 제 코드가 올바르게 작성된 것인가요?" 어떤 입력 값을 넣었을때 자기가 짠 코드가 올바른지 판단하는 몫은 학생여러분 자신들에게 있습 니다. 단 강의게시판에 자신이 테스트한 케이스를 올려두고 다른 학생들의 것과 비교해보는 것은 상 관없습니다. "제가 짠 코드를 복사해서 Ocaml 해석기에 붙여넣어서 테스트하면 잘 되는데 컴파일 하면 에러가 나요 ㅠㅠ." 편집기에서 복사해서 Ocaml 해석기에 붙여넣지 말고, 컴파일러를 이용합니다. 9
제 7 절 문제 8번숙제까지는문제 1개당함수 1개씩을작성하였지만이번숙제에서는처음부터마지막까지 calc exp 함수하나만을작성하며그기능을단계적으로확장해나간다. 함수 calc exp의타입은항상 exp -> t이다. calc exp 함수가이번숙제에서요구한모든계산기능을올바로수행하면만점을받을수있으며, 그렇지못할경우자신이구현한기능에해당하는점수만받게된다. 실행예는컴파일후실행한경우를기준으로작성하였다. Ocaml 인터프리터에서직접실행하는방법은 5절을참고하도록한다. Question 1. [30점] 정수계산을구현하라. ( 설명 ) 정수의사칙연산 (+,,, ) 과부호바꿈그리고나머지연산을수행할수있도록 calc exp를작성한다. ( 컴파일후실행예 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # 3;; 3 # 3 + 2;; 5 # 17 mod 3;; 2 # 3 * -4;; -12 # 17 * 7 mod 4 + 3;; 6 # 17 / (1 + 3 * (1-4));; -2 Question 2. [20점] 조건연산식을구현하라. ( 설명 ) Ocaml의 if와같은조건연산식을계산할수있도록 calc exp를작성한다. 기본적으로 Ocaml의조건연산식과동일한기능을수행하지만등호 (=) 를이용한조건만계산하며 >, < 와같은부등호나기타다른논리연산자는사용하지않는다. 조건연산식 if c1 = c2 then e1 else e2는 If (c1, c2, e1, e2) 로변환되고함수 calc exp는 c1과 c2의계산결과를비교하여서로같으면 e1을, 서로다르면 e2를계산한다. ( 컴파일후실행예 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # if 1 = 1 then 10 else 20;; 10 # if 2 = 1 then 10 else 20;; 20 # if 3 mod 2 = 0 then 5 * (3-1) else 1 + 1;; 2 # if 3 * 4 = 2 + 10 then 5 * (3-1) else 1 + 1;; 10 10
# if 3 = 2 then 10 else if 2 * 2 = 3 + 1 then 17 mod 5 else 18 mod 5;; 2 Question 3. [50점] 변수를구현하라. ( 설명 ) Ocaml에서처럼 let... 을이용하여지역변수를선언하고사용할수있도록 calc exp를작성한다. 이문제에는부분점수가있으며그기준은다음과같다. 변수에정수값을대입하는경우에대해서계산이가능 [10점] 변수에연산식의결과를대입하는경우에대해서계산이가능 [20점] 변수가여러번중첩선언되어있는경우에대해서계산이가능 [20점] 변수가여러번중첩되어선언되었을경우주의할점은다음과같다. let a = 2 let b = let a = 3 a + 1 a + b;; 위와같은연산식을계산할때, 첫번째줄에서변수 a에정수 2를저장했지만세번째줄의 let a = 3 a + 1에서연산식 a + 1을계산하기위해변수 a에정수 3을저장했으므로 a + 1의결과는 4가되고이값이변수 b에저장된다. 그러나 let a = 3은 a + 1에서만의미가있으므로마지막줄의 a + b를계산할때는변수 a의값이 2가되어최종계산결과는 6이된다. ( 힌트 ) 선언된변수이름과변수의값을저장하는방법을고안하고필요한보조함수를작성하여이용한다. 변수이름과변수의값을저장하기위해서는어떤방법을사용해도상관없으나리스트를이용하는것이좋다. ( 컴파일후실행예 : 변수에정수값을대입하는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let a = 3 a + 2;; 5 # let a = 3 let b = 4 a * b - 7;; 5 ( 컴파일후실행예 : 변수에연산식의결과를대입하는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let a = 2 let b = a * 3 a + b;; 8 11
# let a = 2 let b = if a = 2 then 10 else 20 a + b;; 12 ( 컴파일후실행예 : 변수를여러번중첩선언한경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let a = 2 let b = let a = 3 a + 1 a + b;; 6 # let a = 2 let b = let c = 3 c * a let c = a + 1 a * b - c;; 9 Question 4. [100점] 닫힌함수를구현하라. 닫힌함수를정의하고사용할수있도록 calc exp를작성한다. 여기서닫힌함수란함수의몸통연산식에형식인자로명시된변수만사용하는함수를말한다. 예를들어 let f x = x + 2 f 1에서함수 f의몸통연산식인 x + 2에는형식인자인 x 외에다른변수를사용하지않았으므로 f는닫힌함수이다. 반면에 let a = 2 let f x = x + a f 1에서는함수 f의몸통연산식인 x + a에형식인자인 x외에앞에서정의한변수 a도사용하였으므로닫힌함수가아니다. 이문제에는부분점수가있으며그기준은다음과같다. 한개의형식인자를가지는함수에대해서계산이가능 [10점] 여러개의형식인자를가지는함수에대해서계산이가능 [20점] 중첩선언된함수에대해서계산이가능 [20점] 자기호출함수에대해서계산이가능 [50점] 함수가중첩선언되었을경우에주의할점은다음과같다. let f x = x + 1 let g x = let f x = x + 2 f (x * 2) f 1 + g 5;; 위와같은연산식에서첫번째줄에서함수 f는형식인자 x를가지고몸통연산식 x + 1을가지는함수로정의했지만세번째줄에서 f (x * 2) 를계산할때함수 f를형식인자 x를가지고몸통연산식 x + 2을가지는함수로다시정의했으므로여기서는 f의몸통연산식이 x + 1이아닌 x + 2가된다. 하지만마지막 12
줄의 f 1를계산할때는세번째줄에서정의한 f가더이상유효하지않으므로처음에정의한 f가사용된다. 따라서 f 1은 2가되고 g 5는 12가되어최종계산결과는 14가된다. 또한 let rec을이용해서함수를선언하였을경우함수의몸통연산식에서자기자신을사용할수있게만들어서자기호출이가능하도록한다. 함수의인자로함수를넘겨주는경우는고려하지않는다. ( 힌트 ) 선언된함수의정보 ( 함수이름, 형식인자, 몸통연산식 ) 를저장하는방법을고안하고필요한보조함수를작성하여이용한다. 함수를저장하기위해서는어떤방법을사용해도상관없으나리스트를이용하는것이좋다. ( 컴파일후실행예 : 한개의형식인자를가지는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let f x = x + 1 f 2;; 3 # let sum n = if n = 0 then 0 else n * (n + 1) / 2 sum 10;; 55 ( 컴파일후실행예 : 여러개의형식인자를가지는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let f x y = if x = y then 1 else 2 f 3 4;; 2 # let g x = x + 1 let f x y = x * y g 2 + f 3 4;; 15 ( 컴파일후실행예 : 함수를여러번중첩선언한경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let f x = x + 1 let g x = let f x = x + 2 f (x * 2) f 1 + g 5;; 14 13
# let f x y z = x + y + z let g x = let f x = x + 2 f (x * 2) f 1 2 3 + g 2;; 12 ( 컴파일후실행예 : 자기호출함수 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let rec sum x = if x = 0 then 0 else sum (x - 1) + x sum 10;; 55 # let rec fib n = if n = 1 then 1 else if n = 2 then 1 else fib (n - 1) + fib (n - 2) fib 5;; 5 # let b2dec n = let rec b2dec n m s = if n = 0 then s else b2dec (n / 10) (2 * m) (m * (n mod 10) + s) b2dec n 1 0 b2dec 1100100;; 100 제 8 절 도전문제 [ 알림 ] 도전문제에대한질문은일체받지않습니다. Question 1. [+α] 열린함수와일종함수를구현하여라. 닫힌함수를확장하여열린함수를계산할수있도록 calc exp를작성한다. 닫힌함수와달리열린함수는이전에선언한변수나함수도몸통연산식안에서사용할수있다. 예를들어다음과같은연산식이있다고할때 14
let a = 2 let f x y = x * y let g x = f a x g 5;; 세번째줄의 let g x = f a x 에서함수 g는형식인자로 x만을가지지만몸통연산식인 f a x안에는이전에정의된함수 f와변수 a도사용하였다. 따라서함수 g는열린함수이다. 열린함수를계산할때중간에함수의정의가바뀔수있다는것을주의해야한다. 예를들면 let f x = x + 1 let g x = f (x * 2) let f x = x + 2 f 2 + g 4;; 위와같은연산식에서두번째줄인 let g x = f (x * 2) 에서함수 g의몸통연산식에함수 f를사용하였고마지막줄인 f 2 + g 4에서도함수 f를사용하였다. 두함수가같은이름을가지고있지만 g의몸통연산식에서쓰인함수 f는세번째줄에서함수 f를다시정의하기전에사용되었으므로첫번째줄에정의된 f x = x + 1로계산하고마지막줄에사용한함수 f는다시정의한 f x = x + 2로계산한다. 열린함수역시닫힌함수와마찬가지로자기호출함수로사용할수있어야한다. let rec을이용하여자기호출함수로작성한함수와그낭 let만을이용하여작성한함수사이에는큰차이점이있다. 다음의예를보자. let f x = x + 1 let rec f x = if x = 0 then 0 else f (x - 1) + x f 10;; 첫번째줄의함수 f는정수를 1 증가시키는함수이다. 그다음에같은이름의함수 f를정의하는데, 이함수는몸통연산식에서자신과같은이름의함수 f를사용하였다. 이함수는 rec을사용하여자기호출함수로정의하였으므로, 네번째줄에있는함수 f는자기자신을의미한다. 따라서두번째줄에서다시정의한함수 f는자기호출을하며 0부터 x까지정수의합을구하는기능을올바로수행한다. 하지만다음과같이 rec 키워드를빼면 let f x = x + 1 let f x = if x = 0 then 0 else f (x - 1) + x f 10;; 두번째줄에서다시선언한함수 f는더이상자기호출함수가아니므로네번째줄의함수 f는처음에정의한정수를 1 증가시키는함수를의미하게된다. 따라서자기호출이되지않고바로 (10-1) + 1 + 10을계산하므로결과는 20이된다. 또한함수의인자로함수를받을수도있고함수의계산결과가함수가될수도있게하여일종함수를구현한다. 일종함수에관해서는이미수업시간에배웠으므로자세히설명하지않는다. 15
( 알림 ) 열린함수와자기호출그리고일종함수까지완벽하게구현할경우에는최종학점을한단계올려준다. 예를들어, 최종학점이 B+ 인경우 A-를받게된다. 만약도전문제의일부기능만구현했다면구현한기능에따라최대 50점까지부분점수를받을수있다. 도전문제의부분점수기준은다음과같다. 이전에정의한변수를함수안에서사용할수있음 [10점] 이전에정의한함수를함수안에서사용할수있음 [10점] 열린함수의자기호출이가능 [30점] ( 컴파일후실행예 : 이전에정의한변수를사용하는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let a = 2 let f x = x * a f 3;; 6 # let x = 2 let y = 3 let f x = x * y + x f 4 + x + y;; 21 # let f x = x + 1 let a = 3 let b = let f x = x * a let a = 5 f a f a + b;; 19 ( 컴파일후실행예 : 이전에정의한함수를사용하는경우 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let a = 2 let f x y = x * y let g x = f a x g 5;; 10 # let f x = x + 1 let g x = f (x * 2) let f x = x + 2 f 2 + g 4;; 13 16
# let f x = x + 1 let f x = if x = 0 then 0 else f (x - 1) + x f 10;; 20 ( 컴파일후실행예 : 자기호출함수 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let f x = x + 1 let rec f x = if x = 0 then 0 else f (x - 1) + x f 10;; 55 # let rec tegral a b c d e = let f x = a * x * x + b * x + c if d = e then 0 else f d + tegral a b c (d + 1) e tegral 1 1 1 1 100;; 333399 # let a = 0 let s x y = x + y let rec sum x = if x = a then a else s x (sum (x - 1)) let s x y = x * y sum 10 + s 3 4;; 67 ( 컴파일후실행예 : 일종함수 ) D:\Programmg\Assignments\Graduate\EECS101\hw9>hw9.exe # let g x y = x + y let f = g 2 f 3;; 5 17
# let g x y = x * y let h x y = x mod y let app f x y = f x y app g 2 3 + app h 10 3;; 7 # let g x y = x + y let f = g 2 let g x = x * 2 f 3 * g 2;; 20 # let f x = 3 * x * x + x - 9 let rec tegral f a b = if a = b then 0 else f a + tegral f (a + 1) b tegral f 0 10;; 810 제 9 절 숙제에대한의견 숙제에대한학생들의모든의견을환영합니다. 숙제에대한의견이있으면 http://pl.postech.ac.kr/~gla/feedback/ 페이지를방문하여의견을익명으로남겨주시길바랍니다. 여러분들의의견은향후숙제설계와강의준비에중요한자료로이용됩니다. 의견을남기는사람에대한어떤정보도저장되지않습니다. 18