shkim
가입: 2019년 7월 30일
올린 글: 86
|
 올려짐: 2021년4월1일 20:14 주제: [숙제 4] 공지사항 및 보충 스펙(4월 19일 수정) |
 |
|
안녕하세요,
숙제 4가 올라왔음을 알려드립니다.
내용 : http://ropas.snu.ac.kr/~kwang/4190.310/21/hw4.pdf
제출 : http://ropas.snu.ac.kr/~ta/4190.310/21/submit/index.pl
기한 : 4/18 밤 12시
* K- 언어 문법 및 의미구조
http://ropas.snu.ac.kr/~ta/4190.310/21/show/k-.pdf
* 뼈대코드
- http://ropas.snu.ac.kr/~ta/4190.310/21/show/K_skel.zip (링크 클릭으로 다운이 진행되지 않을시 브라우저 새 탭에 주소를 입력해 주시기 바랍니다)
- 뼈대코드에는 K- 언어로 짜여진 프로그램을 읽어들이는 파서, K- 언어의 정의 및 실행기의 뼈대가 들어있습니다. k.ml 파일에서 TODO 로 표시해 둔 부분을 완성하여 실행기를 완성하시기 바랍니다.
- 뼈대코드에는 여러분이 숙제를 쉽게 하실 수 있도록 보조 모듈과 보조 함수들에 제공됩니다.
- 뼈대코드 디렉토리에서 make 명령을 실행하시면 숙제 전체가 컴파일되고, 'run' 이라는 실행파일이 생성됩니다. run 파일을 다음과 같이 실행하시면 examples 디렉토리에 제공해 드린 예제를 실행기로 돌려볼 수 있습니다. 채점에 사용될 테스트케이스도 이 예제들의 범위를 크게 벗어나지 않을 것입니다. (다소 응용한 케이스는 있을 수 있습니다.)
| 코드: | make
./run examples/test1.k-
|
* 과제 관련 주의 사항
과제를 하고 제출하기에 앞서 꼭 제출시 주의사항 공지를 확인해 주세요.
* 숙제 스펙 보충사항
(질문은 이 글에 답글로 달지 마시고, 별도의 글로 질문해 주시기 바랍니다)
Exercise 1 "K- 실행기"
- 제출시에는 뼈대코드 중 k.ml 파일을 제출합니다. 꼭 주의해 주세요, 엉뚱한 ml 파일을 잘못 제출하시면 조교팀이 해결해 드릴 방법이 없습니다.
- read의 실행의미 구현에는 read_int 를, write의 구현에는 "print_endline (string_of_int n)"을 사용하는 것으로 합니다.
즉, hw3.pdf 에 설명된 대로 정수를 출력한 다음에 개행 문자(newline)를 출력해야 합니다.
마침 숙제의 감을 잡으실 수 있도록 뼈대 코드에 read와 write의 실행 의미를 정의해 두었으므로, 이 정의를 그대로 두시면 되겠습니다.
- K.run 의 결과는 출력 대상이 아닙니다. 입출력은 read/write 로만 이루어집니다.
- 실행 의미 규칙이 정의되지 않은 경우 Error 예외를 발생시킵니다. 몇몇 구체적인 상황과, 각각의 경우 Error 예외의 문자열은 다음과 같이 정하겠습니다.
(1) 타입 에러 - 정수 값이 와야 하는 곳에 하는데 참/거짓(bool) 값이 나오거나, Addr이 나와야 하는데 Procedure가 나온 경우
| 코드: | | raise (Error "TypeError ...") |
TypeError 뒤에 추가적인 정보를 더 붙이셔도 됩니다. 예를 들어 아래와 같이 쓸 수 있습니다. 채점시에는 스트링의 앞글자들만 매칭할 것이므로 모두 정답으로 인정됩니다.
| 코드: | Error "TypeError : not int"
Error "TypeError : boolean is expected" |
(2) Bind되지 않은 변수나 함수가 사용되는 경우
| 코드: | | raise (Error "Unbound") |
(3) callv, callr에서 함수에 넘겨준 인자 개수와 함수 정의에서 받는 인자 개수가 다른 경우 :
| 코드: | | raise (Error "InvalidArg") |
그 외에 실행의미가 정의되지 않은 경우에 대해서는, Error 예외의 문자열은 자유롭게 사용하시면 됩니다.
-어느 예외가 먼저 발생해야 하는지 모호한 경우는 테스트하지 않겠습니다. 예를 들어
| 코드: | let proc f (x) = x in
f (1, 2 + true) |
는 Error "TypeError : ... "를 발생시켜야 하는 케이스에 해당하기도 하고, Error "InvalidArg"를 발생시켜야 하는 케이스에 해당하기도 합니다.
숙제 문서의 실행 의미 정의만으로는 어떤 예외가 우선시되는지 판단하기 애매하므로, 이런 경우는 테스트하지 않을 것입니다.
- CALLR의 semantics에서, σ(y)는 항상 메모리 주소(K- 문서의 "Addr", 뼈대 코드의 "Loc.t")인 경우만 가정하겠습니다.
σ(y)에 함수가 bind된 경우는 테스트하지 않겠으며, 이 경우는 예외를 내셔도 좋고 그대로 실행되어도 무방합니다.
- RECORD의 FIELD에 ASSIGN하는 경우, 만약 정의되어있지 않은 필드에 값을 할당하려는 경우는 오류처리하도록 구현해주세요. 언어 정의문서의 레코드 필드에 값을 할당하는 부분 정의에 앞선 경우와 같은 경우에 어떻게 처리할지(새로운 필드를 만들어서 그곳에 값을 할당할지 오류처리를 할지) 정확히 명시가 되어있지 않기에 그렇습니다.
이러한 이상한 경우를 테스트하지는 않을 예정이므로 이미 이 부분을 레코드를 수정해서 새로운 필드를 추가하도록 구현해두신 경우는 그대로 두셔도 상관은 없지만, 아직 구현하지 않고 계신 분들은 위의 스펙에 따라 구현해주시면 좋을것같습니다.
(4월 19일 수정)
k- 언어 정의 문서의 실행의미(Semantics)대로 실행되는 프로그램만이 제대로된 프로그램이고, 그렇지 않은 프로그램은 잘못된 프로그램으로 Error를 발생시켜야 합니다. RECORD의 FILED에 ASSIGN하는 경우를 보자면, 레코드 r에 x라는 필드가 없다면 r(x)가 정의되지 않겠지요. 이 경우 실행의미대로 프로그램이 돌아갈 수 없으므로 Error를 내야 합니다. RECORD LOOKUP 등의 다른 경우도 마찬가지로, 실행의미만을 가지고 프로그램 실행을 정의할 수 없다면 잘못된 프로그램이므로 Error를 내야 합니다.
마치 언어정의 외의 다른 정보가 필요한 것 처럼 혼동을 드려 죄송합니다. 언어정의만으로 k- 실행기를 구현하면 모호한 부분이 없을 것입니다. 다만 공지가 늦어진 만큼 이 부분 때문에 숙제4 채점에 불이익을 받는 일은 없도록 하겠습니다.
---
Exercise 2 "K-프로그래밍: 거스름 방법의 수"
- K- 언어로 프로그램을 작성하신 후, 확장자를 .txt로 하여 제출해 주세요. 중앙전산원에서 .k- 확장자 파일 제출을 차단하기 때문입니다.
- 제공해 드린 뼈대 코드로 실행했을 때 파싱 에러가 발생하지 않도록 해 주세요
- numch 함수 작성 후 in 안에서 정수를 하나 입력으로 받고(input), numch(input) 을 출력하는 코드까지 작성해 주세요.
즉 다음과 같은 형태가 되면 됩니다.
| 코드: | ...
let proc numch (x) =
...
in
let input := 0 in
read input;
write (numch(input)) |
- numch 함수의 인자로는 양의 정수만 들어온다고 가정하셔도 됩니다.
양의 정수 아닌 값이 인자로 들어올 경우 자유롭게 처리하시기 바랍니다.
- 우리나라에는 50원 동전이 있지만, 본 숙제에서는 hw4.pdf 의 스펙을 따라 50원 동전은 없는 것으로 간주합니다.
--
Exercise 3 "K- 프로그래밍: 구조물 데이터"
- K- 언어로 프로그램을 작성하신 후, 확장자를 .txt로 하여 제출해 주세요. 중앙전산원에서 .k- 확장자 파일 제출을 차단하기 때문입니다.
- 제공해 드린 뼈대 코드로 실행했을 때 파싱 에러가 발생하지 않도록 해 주세요
- 구현해야 하는 모든 함수 작성 후 마지막에 ... in 2019 로 끝내주세요. 마지막에 숫자 2019로 끝내는 것은 파싱 에러를 피하기 위해서입니다.
즉 다음과 같은 형태가 되면 됩니다.
| 코드: | let proc leaf(i) =
...
in
...
...
let proc bft (t) =
...
in
2019 |
- dft 함수는 preorder로 방문하도록 작성해 주세요(https://en.wikipedia.org/wiki/Tree_traversal#Pre-order).
bft 함수를 작성할 때는 왼편 자식 트리를 먼저 방문하도록 작성하시기 바랍니다.
예를 들어, 아래 트리의 dft 방문 순서, bft 방문 순서는 모두 1->2->3 이 됩니다.
- makeLtree/makeRtree에 의해 만들어져서 한쪽에만 subtree를 가지고 있는 tree의 경우, 반대편에 empty tree가 매달려 있는 것으로 하겠습니다.
Leaf 양쪽에도 빈 트리가 달려있다고 볼 수도 있겠지만, 이 과제에서는 그렇지 않은 것으로 정의합니다.
즉, 다음과 같이 계산되어야 합니다
isEmpty(rTree(makeLtree (1, leaf (2)))) = true
isEmpty(ltree(makeRtree (1, leaf (2)))) = true
- Empty tree는 dft/bft 함수로 방문할 때 아무것도 출력하지 않아야 합니다.
- rTree/lTree의 인자로 empty tree나 leaf가 들어오는 경우, 그리고 nodeVal의 인자로 empty tree가 들어오는 경우는 테스트하지 않겠으니 자유롭게 구현하시면 됩니다.
-숙제에서 제시된 함수들은 모두 call by value로 호출될 때 올바르게 동작하도록 작성해주세요.
(예를들어 채점시에는 if isEmpty (lTree (tr)) then write (1) else write (0) 이러한 코드의 실행결과가 올바른지 채점할 예정입니다.)
-----
Exercise 4 "즐거운 고민"
-별도의 뼈대코드는 없으며, 문제에 제시된 타입들을 파일에 포함한 상태에서 shoppingList 함수를 구현한 .ml 파일을 제출해주시면 됩니다.
-shoppingList의 계산결과를 list로 작성할때, 조카의 이름 ABC 순서대로 리스트의 원소를 정렬해주세요. 숙제 파일에 제시된 답안 예시처럼 구현해주시면 됩니다.
- 각 조카가 받게 될 선물 리스트들도 오름차순으로 정렬해주세요. 마찬가지로 숙제 파일에 제시된 답안 예시처럼 구현해주시면 됩니다.
-----
Exercise 5 "탐사 준비"
- 별도의 뼈대코드는 없으며, 문제에 제시된 타입들을 파일에 포함한 상태에서 getReady 함수를 구현한 .ml 파일을 제출해주시면 됩니다.
- 탐험이 불가능할 때는 아래의 IMPOSSIBLE 예외를 발생시킵니다.
- Guide ("x", e1) 에 대해 다음과 같이 설명되어 있습니다.
| 인용: | | e1 안에서 만날 보물상자 x의 열쇠가 α이고 ... |
이때 e1 안에는 반드시 x 가 존재한다고 가정하겠습니다.
- getReady 가 내놓는 키 리스트에서 원소들의 순서는 상관 없습니다. 다만 리스트에 겹치는 원소는 없어야 합니다.
아래는 전년도의 문제의 이해를 돕기 위한 보충 설명입니다.
| 인용: | '보물지도에서 암시하는 열쇠모양'이라는 것은, 실제로 보물상자를 열 때 필요한 열쇠모양이 아니라고 보셔도 됩니다. 단, 이 보물지도에서 암시하는 열쇠모양을 제대로 알아낼 수 있다면 그 정보를 통해 실제 보물상자들을 여는 열쇠모양을 모두 알아낼 수 있다고 생각하시면 됩니다.
숙제문서의 두번째 예제를 보면서 생각해보겠습니다. 각 보물지도가 암시하는 열쇠의 모양에 대한 표를 참고하시면, (안내판x|x) 꼴의 보물지도가 암시하는 모양은 (-,-) 라고 볼 수 있습니다. 실제로는 ((-,-), (-,-)) 등 여러가지 경우가 있을수 있겠지만, 열쇠꾸러미 크기를 최소로 한다고 하였으니 (-,-)라고 보시면 됩니다.
이제 이 보물지도가 암시하는 열쇠모양을 제대로 알아냈으니, 실제로 보물상자를 열기위해 필요한 열쇠 모양을 생각해봅시다. 지도의 시작지점이 암시하는 열쇠모양이 (-,-)라는 걸 알아냈고, 안내판에 x가 쓰여있었으니, x라는 보물상자는 -로 열수있다고 생각할 수 있을 것이고, 실제로 만나게 되는 보물상자도 x뿐이니 숙제문서의 두번째 예제는 - 하나로도 탐사를 마칠 수 있는 것입니다.
세번째 예제도 간단하게 설명드리자면, ((안내판x | x) | star) 꼴의 보물지도에서 뒤쪽의 star부분이 암시하는 열쇠모양은 -입니다. 여기서 전체가 암시하는 열쇠모양을 판별해야 하는데, (안내판 x | x)가 암시하는 열쇠모양은 (-,-) 혹은 ((-,-) , (-,-))와 같이 여러가지 모양이 있을 수 있습니다. 하지만 보물지도 암시 규칙표의 마지막 부분을 보시면, 앞선 (안내판 x | x) 부분이 암시하는 열쇠모양이 (-,-)가 되어야만 전체 보물지도가 암시하는 열쇠모양이 -로 제대로 나오게 됩니다. (star의 -와 모양을 맞춰야 하기때문이죠.)
위와 같이 보물지도의 열쇠모양 암시에 성공했으므로, 그 정보들을 가지고 보물상자를 열기위한 열쇠모양을 찾아보면, 전체 보물지도에서 보물상자는 x와 star입니다. star는 -로 열수있는 것이 자명하며, x또한 위의 열쇠모양 암시를 보면 -로 열 수 있다는 것을 알수있습니다.
이런식으로 열쇠모양에 대한 암시와 실제 필요한 열쇠꾸러미를 구분하시면 됩니다. |
|
|
FAQ
검색
멤버리스트
사용자 그룹
사용자 등록하기
개인 정보
비공개 메시지를 확인하려면 로그인하십시오
로그인
