[신채환]

과제 7의 1, 2번 문제와 관련하여 질문이 있어 글을 쓰게 되었습니다.

처음 1번을 풀 때는 Fn과 Fnr 모두 상수로 취급한다는 점에서 그냥 \k.k(...)의 형태로 작성하였습니다.
근데 2번에서는 출력 식에 raise와 handle이 없어야 하므로 Fn, Fnr 내 식에도 xcps'를 적용해야 하겠다는 생각이 들었습니다.
그렇게 생각하니 1번에서도 Fn, Fnr 내 식에 cps'를 적용해야 하는 것이 아닌지 궁금해졌습니다.

1, 2번 모두 Fn, Fnr 내의 식도 CPS 변환을 해야 하나요?

[이재호]

안녕하세요,

네, 이해하신 것처럼 함수의 몸통을 CPS 변환하지 않으면 온전히 CPS 변환한 것이 아닙니다.
1번도 2번을 푸실 때와 같이 몸통도 같이 CPS 변환하여야 올바른 풀이입니다.

감사합니다.

조교 드림


TA 이재호
e-mail: jhlee@ropas.snu.ac.kr

[신채환]

감사합니다!

[신채환]

안녕하세요, 혹시나 하는 마음에 추가적으로 질문 드립니다.
함수 내 식도 CPS 변환을 해야 한다는 것이, 함수의 자료형까지 바꿔야 한다는 뜻인지 궁금합니다. 예를 들어 int형의 식을 CPS 변환하면 (int -> result) -> result형이 되는데, int형 식을 출력하는 함수 내 식을 CPS 변환한 후 그대로 사용하면 출력의 자료형이 (int -> result) -> result형이 될 것 같습니다. 이걸 추가적으로 변형해 그대로 int형을 출력하도록 코드를 작성해도 CPS 변환한 것으로 인정해 주시는지, 아니면 이걸 그대로 두고 함수를 적용하는 부분에서 이를 바탕으로 코드를 수정해야 하는 것인지 궁금합니다.

[이재호]

함수 적용을 CPS 변환하는 자체가 CPS 변환된 식들의 적용을 잘 처리하기 위해서 진행하는 것입니다.

조금 더 이해를 돕기 위해 부연 설명을 드리겠습니다.
CPS 변환의 목적 중 하나는 값 중심 프로그래밍 언어를 폰 노이만 구조를 가진 컴퓨터의 기계어로 변환하는 것입니다. 값 중심 언어 버전의 SSA 변환이라고 보셔도 됩니다.
예를 들어, (ML 문법으로)
let f x =
if x = 0 then 1 else
x * (f (x - 1))
의 몸통에서 f에게 (x - 1)을 넘긴 후, 계산된 결과를 들고 다시 f x의 몸통으로 돌아와 x를 곱한 후 마무리됩니다.
이렇게 "돌아오는" 구조를 없애는 것이 CPS 변환입니다.

단순히 컴파일러 최적화를 위한 것이 아니라, 실제로 프로그래밍할 때도 CPS 변환을 통해 프로그램의 성능을 높일 수 있습니다.
우리가 흔히 "꼬리 재귀 (tail-recursion)"라고 부르는 방식을 통해 프로그램을 작성하면, 깊은 재귀를 사용하여도 스택 넘침을 막을 수가 있습니다.
왜냐하면 계산된 결과를 들고 함수를 적용한 몸통으로 다시 돌아오지 않아도 되기 때문입니다.
CPS 변환은 프로그램의 모든 부분을 꼬리 재귀 방식으로 바꾸는 과정입니다.
마저할일을 함수 적용 부분에 넘겨준다면, 다시 그 적용한 부분으로 돌아오지 않아도 되기 때문입니다.

비유하자면, "앞으로 필요한 모든 물자를 다 챙겨보내서, 다시 베이스캠프로 보급으러 돌아오지 않아도 되게 하는 방식"인 것입니다.

---
따라서 "추가적으로 변형해 그대로 int형을 출력하도록 코드를 작성해도 CPS 변환한 것으로 인정"하는 것이 정확히 어떤 방식인지에 따라 다르겠지만, 만약 "그 지점에서 함수 적용을 해서 돌아오게 만드는" 방식이라면 제대로된 CPS 변환이 아닌 것입니다.
CPS 변환된 프로그램은 모든 지점이 꼬리 재귀 방식이어야 합니다.

[신채환]

답변 정말 감사합니다!