[신동진]

hw6-2의 cps 변환 함수가 올바른 cps 형태로 변환되었는지 확인할 수 있는 방법이 있나요?

예를 들어 e1+e2를 λk.k(e1+e2)로 변환해버린다면 타입은 맞고 실행결과도 맞게 나오지만 이는 올바른 cps 변환이 아니라고 생각합니다. e1과 e2가 그대로 남아있으니까요.

그리고 모든 exp 타입이 다 cps 처리되어 식을 구성한다고 해도 올바른 형태가 아닐 수 있을 것 같습니다. (e1+e2 = λk.k( ((cps e1) λx.x) + ((cps e2) λx.x) )같은 경우)

본인이 정확한 변환을 했는지 확인할 수 있는 방법이 있을지 질문드립니다.

[최재승]

안녕하세요,

저도 이 문제 때문에 고민을 많이 하고 교수님 의견을 물어보았습니다. 최종적으로 다음과 같이 결정되었으며, 추가 스펙 공지글에도 업데이트 되었습니다.

(1) 우선, 실행 결과는 당연히 변환 전과 후가 같아야 합니다.
(2) 어떤 mexp에 나타난 sub-expression들은 모두 cps 변환되어야 합니다. 예를 들어 cps(e1+e2)의 경우, e1, e2는 각각 cps로 변환된 (cps e1), (cps e2) 형태로 나타나야 합니다.
(3-1) e가 상수(Num, Var, Fn, Rec) 일때만 cps(e) = \k.k(...) 형태를 허용합니다. 상수의 경우 계산할 게 없으므로 바로 k에 전달하는 것입니다.
(3-2) e가 상수가 아니면 항상 cps(e) = \k....(\v....k... ) 형태로 변형되어야 합니다. 복합식의 경우, 일부를 먼저 변환하고 남은 할 일을 k를 가지고 구성해서 전달하는 것입니다.

예시를 들어드린 Add의 경우를 보면, 복합식 e1 + e2 에서 일부인 e1을 변환한 다음, 앞으로 할 일을 인자로 전해주고 있습니다. 이 '앞으로 할 일'을 정의하는 데 k가 사용되고요.