1. Continuation Passing Style (CPS) 를 알아보자

함수형 쪽으로 좀 깊게 파고 들어가다보면 접하게 되는 개념 중에 Continuation Passing Style, 줄여서 CPS라고 하는 것이 있음.

대부분은 들어본 적도 없을거다. 왜냐하면 이건 함슬람 중에도 극한의 복음주의자들만 하는 변태짓이기 때문이다.

아니나 다를까 하스켈도 CPS 기반의 Continuation 모나드라는 걸 기본 모나드 중 하나로 지원하는데

다른 모나드는 그래도 모나드를 이해하고 보면 어디다 쓰는 건지 대충 감이 오지만 이 녀석은 애초에 CPS를 모르면 봐도 뭔 개소린지 알 수가 없다.

이번 글에서는 바로 그 CPS라고 하는 괴물을 소개해 보기로 한다.

(1) 뭐하는 개념인가?

Continuation Passing Style (CPS) 은 코딩 스타일이다. 그런데 그 스타일이 조금 희한하다.

우선 모든 함수에다가 continuation이라는 함수 타입의 추가 인수를 넣는다.

수정된 함수는 수정하기 전의 함수와 같은 계산을 하지만

결과값을 그냥 반환하는 게 아니라 그거로 continuation을 호출한 다음 continuation이 반환한 값을 받아 다시 반환하는 함수가 된다.

말로 설명하니까 조금 어렵다. 가령 pow라는 (int, int) → int 타입의 함수가 있다면 그걸 다음과 같은 함수로 바꾸라는 것임.

여기서 continuation은 계산이 끝난 후 수행될 후속 작업이라고 할 수 있는데,

보통 계산 후에 CPS로 작성한 프로그램 또는 모듈이 종료될 때까지 할 일 전체가 여기에 다 보내진다.

즉 pow_CPS는 pow처럼 결과값을 받아서 또 뭘 할 수 있는 함수가 아니라,

아예 후속 작업까지 다 인자로 보내서 프로그램의 최종적인 결과값까지 얻고 그냥 프로그램을 끝내버리고 싶을 때 쓰는 그런 함수인 것이다.

당연히 R은 CPS 로 코딩할 프로그램의 최종 결과 타입이 된다.

CPS는 모든 함수들을 이렇게 개조한 후 그것들만 가지고 프로그래밍을 하는 행위예술이라고 보면 된다.

가령 2의 10제곱이 3의 6제곱보다 작으면 true, 그렇지 않으면 false를 반환하는 프로그램을 생각해 보자. CPS를 안 쓴다면 이렇게 코딩하면 된다.

하지만 우리는 이걸 CPS로 코딩하기를 원한다. 그러니까 우선 위 코드를 이렇게 단계적으로 계산을 수행하는 코드로 바꾸자.

첫 번째 pow함수를 호출한 뒤 결과값 v1을 가지고 해야 할 후속 작업이 무엇인지가 명확해졌다. 3번째 줄부터 main함수 끝까지 전부다.

그걸 람다로 만들어 pow_CPS의 마지막 인자로 보내면 됨.

이 변환을 계속하면 최종적으로는 다음과 같은 결과를 얻을 수 있다.

물론 CPS함수들도 합성 가능하다. CPS 함수들을 조합해서 더 큰 CPS함수를 만드는 것도 가능함.

아래와 같이 a의 b제곱과 c의 d제곱 중 무엇이 큰지를 확인하는 CPS 함수를 먼저 만든 다음 그걸 가지고 main을 정의할수도 있다.

이 경우 main은 이렇게 될거다.

언뜻 봐서는 이런 식으로 코드를 짜면 당연히 성능이 느려질 것 같다.

그런데 실제로는 별로 느려지지 않는다고 한다. 왜냐하면 CPS로 코딩하면 모든 함수 호출이 다 꼬리재귀가 되기 때문이다.

이 꼬리재귀 때문에 오히려 성능이 올라가는 경우도 있다고 하니 참으로 오묘한 부분이다.

(2) 이거 왜함?

여기까지의 설명만 들으면 람다 중첩된 모양이 그야말로 더럽기 그지없어서

아무리 함슬람이 힙스터들이라고는 하지만 왜 이런 걸 만들어가지고 고생을 사서 하는가 하는 의문이 절로 들것임.

이 의문을 해소하려면 우선 이 CPS라는 게 근본적으로 무엇을 하기 위해 만들어진 것인지를 알아야 한다.

CPS는 기본적으로 goto같은 제어 이동 명령이 있는 저수준 언어로 씌여진 코드를

어떻게 하면 가장 기본적인 기능들만 지원하는 함수형 언어로 쉽게 번역할 수 있을까 하는 문제를 풀다가 나왔다.

대충 자바 비스무리한 언어로 씌여진 다음과 같은 코드가 있다고 생각해 보자.

함수의 마지막 줄에서 값 반환할 때 return v; 대신 v라고만 쓸 수 있는 언어가 꽤 있는데 (러스트, 스칼라 등) 이 언어도 그런 부류다.

즉 program은 getchar()의 반환값을 ch에 저장한 뒤 toInt(ch)를 계산해 그 결과를 반환하는 함수가 된다.

이걸 다른 언어로 번역하려고 한다고 하자.

그 언어도 거의 똑같은데 다만 함수 안에서 세미콜론(;) 쓰면 죽어버리는 병을 앓고 있어서 함수 안에 변수를 정의할 수가 없다.

그냥 ch를 getchar()로 치환하면 되는 거 아니냐고 생각하는 사람도 있을 것 같다.

문제는 이 방법은 일반적으로 적용하기 힘들다는 것이다.

여기서야 ch가 한 번만 사용되었으니 망정이지 여러 번 사용되었다면 getchar도 여러 번 부르게 되어 코드의 동작 자체가 달라지고 만다.

지금 우리 목적은 어떤 특정 코드 하나를 번역하는 게 아니다. 모든 코드를 번역할 수 있는 알고리즘을 찾는 것이다.

정답은 다음과 같이 람다를 이용하는 것이다.

보다시피 변수 정의문은 그 변수를 이용하는 뒷부분 전체를 람다로 묶어서 그 람다 호출하는 문장으로 직접적으로 치환 가능하다.

그리고 또 한 가지 방법이 있는데 바로 CPS를 이용하는 것이다.

만약 이렇게 오직 부수 작용만을 위해 평가되는 표현식이 중간에 끼어 있다면 어떻게 하면 될까?

간단하다. 그냥 표현식을 사용되지 않는 변수를 정의하는 변수 정의문이라고 치고 번역하면 된다.

CPS로는 이렇게 된다.

어차피 그냥 람다로도 다 할 수 있는데 왜 굳이 CPS를 쓰냐고 묻고 싶을 것이다.

사실 지금까지는 그냥 연습이었고 진짜로 번역하고 싶은 코드들은 따로 있다. 바로 중간에 return같은 점프 명령이 있는 이런 코드들이다.

4번째 줄은 실행되지 않으니 그냥 잘라내버리면 되지 않느냐 할지도 모르겠다.

그러나 그건 번역할 코드가 간단할 때나 가능한 얘기고 여기에 if나 while섞이기 시작하면 제어가 어디로 튈지 몰라서 안된다.

되도록이면 원본의 내용을 그대로 유지한 채로 코드를 번역하고 싶은데 이 때 CPS가 활약을 한다.

여기서 return_CPS는 이렇게 정의되는 함수다.

continuation_에 후속 작업으로 뭐가 들어오든 개같이 무시하고 그냥 프로그램의 최종 결과를 쏴버린다.

당연히 CPS에서는 이 함수가 return같은 역할을 하게 된다.

한 마디로 CPS는 함수와 return같은 제어 이동 명령의 차이를 없앤다. 둘다 똑같이 _CPS달린 함수로 만들 수 있다는 것임.

결과적으로 온갖 goto가득한 스파게티 코드들을 위에서부터 읽어나가면서 함수형 언어로 직역할 수 있게 됨.

실로 비범한 능력이며 바로 이것 때문에 CPS를 쓴다고 봐도 무방하다.

주로 함수형 언어로 컴파일러 같은 거 만들 때 CPS를 중간 단계로 사용하거나 한다고 함.

그외에도 분산 프로그래밍이라거나 여러가지에 이 CPS가 응용이 된다고 하는데 나도 뭔 소린지 잘 모르겠으니 넘어가도록 하겠다.

(3) 치환기 callCC

앞에서 얘기했듯이 CPS를 쓰는 건 결국 제어 이동 명령을 함수랑 똑같이 취급할 수 있기 때문임. 좀 더 구체적으로 그걸 하는 방법을 알아보고 싶다.

그러니 다음 함수의 CPS 버전을 만들어 보자.

방금 전 예제와 똑같은 거 아니냐고 할 수 있는데 다르다.

이번에는 CPS 프로그램을 만드는 것이 아니고 CPS 프로그램 내부에서 사용할 func1_CPS를 만드는 것이기 때문이다.

언뜻 생각해 보면 그냥 이렇게 하면 될 것 같기도 하다.

그러나 이건 안 된다. 이렇게 할 경우 return_CPS가 호출되는 순간 func1_CPS만 끝나는 게 아니라 프로그램 전체가 끝나 버리기 때문이다.

해결책은 func1_CPS 안에서만 return_CPS의 정의를 바꾸는 것임.

이제 return_CPS는 제어를 프로그램 끝으로 보내는 게 아니라 func1_CPS의 후속 작업으로 보낸다.

우리가 원하는 return_CPS의 행동 바로 그것이며 잘 작동한다.

문제는 이 방법을 쓰려면 매번 CPS함수를 만들 때마다 그 함수 안의 return_CPS를 새로 정의해야 한다는 거다. 이건 좀 많이 번거롭다.

애초에 우리가 가정한 언어는 함수 안에서 세미콜론만 보면 발작을 일으키며 죽는다.

더 좋은 방법이 있는데 바로 어떤 치환기 함수를 만들어 그걸 이용하는 것임. 그 치환기 함수는 callCC라고 불리며 다음과 같이 사용된다.

return_CPS에 의존하는 람다 함수를 만들고 그 안에 코드를 작성한 후 그걸 callCC에 보내면 callCC가 알아서 진짜 return_CPS를 만들어 넣어 준다.

이 경우 꼭 return_CPS라는 이름을 이용할 필요도 없는 것은 물론이다.

callCC는 다음과 같이 정의하면 된다.

말 그대로 필요한 return_CPS를 만들어서 첫 번째 인수로 전달된 함수에 넣어 주는 함수라는 것을 알 수 있다.

2. Continuation 모나드를 알아보자

사실 이번 글의 목표는 CPS 자체가 아니라 Continuation 모나드를 소개하는 것이었다.

모나드랑 do표기법에 대한 이야기가 많이 나오기 때문에 혹여나 아직 안 본 사람이 있다면 내가 전에 유동으로 쓴 이 글을 먼저 보고 오길 바람.

세상에 모나드 설명해준다는 놈 치고 제대로 설명해주는 놈이 없다는 건 나도 안다. 그래도 나는 나름대로 자신이 있는 편이다.

들어가서 보길 바라며 봐도 이해 안될 경우 상냥하게 욕박으면 겸허히 받아들인다.

(1) CPS 함수를 다르게 표현하기

T에서 U로 가는 f라는 함수가 하나 있다고 하자. 이 함수의 CPS버전은 타입이 이렇게 된다.

f_CPS : (T, U→R) → R

그런데 사실 f_CPS 를 꼭 이 타입으로 정의할 필요는 없음. 커링해서 아래와 같은 타입으로 만들어도 충분히 써먹을 수 있다.

아니 함수형 언어에서는 웬만해선 모든 함수를 커링하니까 오히려 이렇게 정의하는게 디폴트다.

f_CPS : T → ((U→R)→R)

보다 일반적으로는 이런 Continuation 처리기 타입이 따로 있을 수도 있을 것이다.

Cont〈R, T〉

구현은 ((T→R)→R)타입을 감싸는 래퍼 타입으로 정의할 수도 있고 그냥 ((T→R)→R)의 다른 이름으로 할 수도 있는데

이 글에서는 편의상 그냥 ((T→R)→R)의 다른 이름이라고 치겠음.

이제 f_CPS는 다음과 같은 타입의 함수가 된다.

f_CPS : T → Cont〈R, U〉

여기서 Cont, 또는 좀 더 정확하게는 Cont〈R, 〉이 바로 이번 글의 주제인 Continuation 모나드다.

(2) Continuation 모나드

이전 글에서도 설명했듯이 어떤 타입 컨스트럭터가 모나드가 되는지 알고 싶으면 lift와 unit, flat만 정의할 수 있는지 확인해보면 됨.

쉬우니까 코드 없이 그냥 말로 다 설명하도록 하겠다.

우선 lift를 보면 Cont〈R, 〉에 대한 lift함수는 다음과 같은 타입을 가져야 함.

lift : (T→U) → (Cont〈R, T〉→Cont〈R, U〉)

물론 여기서 Cont〈R, T〉는 ((T→R)→R)와 같은 타입이니까 그냥 (T→U) → (((T→R)→R)→((U→R)→R)) 타입의 함수만 만들면 된다.

그리고 이것은 아주 쉽게 만들 수 있다. 왜냐하면 T에서 U로 가는 함수가 있을 경우

U→R타입의 함수에 그걸 합성하면 T→R로 가는 함수가 나오니까 U→R에서 T→R로 가는 함수도 무조건적으로 만들 수 있으며

같은 이유로 U→R에서 T→R로 가는 함수가 있을 경우 ((T→R)→R에서 ((U→R)→R)로 가는 함수도 만들 수 있기 때문이다.

unit함수는 다음과 같은 타입을 가져야 함.

unit : T → Cont〈R, T〉

당연히 T타입의 값이 있으면 (T→R)에서 R로 가는 함수를 만들 수 있다. 설명할 가치도 없는 얘기다.

flat은 어떨까? 이 함수는 다음과 같은 타입을 가진다.

flat : Cont〈R, Cont〈R, T〉〉 → Cont〈R, T〉

언뜻 보기에는 이걸 어떻게 정의하나 싶을 수 있는데 역시 Cont〈R, T〉를 ((T→R)→R)로 치환해 놓고 보면 쉽다.

flat : ((((T→R)→R)→R)→R) → ((T→R)→R)

T→R에다가 앞에서 정의한 unit을 걸면 Cont〈R, T→R〉, 즉 ((T→R)→R)→R타입의 값이 나온다.

이걸 R로 만드는 함수가 인수로 주어져 있는데 T→R에서 R로 가는 함수를 만들지 못할 이유가 없다.

물론 Cont〈R, 〉이 실제로 엄밀한 의미에서 모나드가 되려면 lift와 unit, flat이 또 무슨 조건들을 만족시켜야 하긴 하지만

이전 글에서도 그 조건 설명 안했으니 넘어가겠음. 어차피 다 된다.

(3) Continuation 모나드 활용하기

이전 글에서도 설명했듯이 모나드를 쓰는 건 그걸 통해 확장된 함수를 정의할 수 있기 때문임.

그리고 그 확장된 함수들을 항상 같은 방법으로 쉽게 합성할 수 있기 때문이다.

Continuation 모나드의 경우 확장된 함수들은 _CPS붙은 함수들인데 이것들을 쉽게 합성할 수 있다 이말이다.

앞에서 정의해 본 powCompare_CPS를 모나드를 이용해서 다시 정의해 보자.

더러운 람다 중첩이 사라지고 CPS 함수들을 일반 함수마냥 쉽게 다룰 수 있게 되었다. 왜 이걸 굳이 모나드로 만든 건지 잘 알 수 있다.

CPS 함수의 형태가 바뀌었으니 치환기 callCC도 다르게 정의되어야 한다. 새로운 callCC는 이렇게 생겼다.

앞의 callCC와 비교해 보면 인자에 continuation을 보낼 필요가 없고 함수만 보내면 되어서 사용하기가 더 편해졌다.

continuation인자가 Cont〈R, T〉로 반환 타입과 합쳐져 있기 때문에 발생하는 현상이다.

새로운 callCC와 do표기법을 이용해서 func1_CPS도 다시 정의해 보자.

(하스켈의 경우 5번째 줄은 그냥 ret_CPS(0)라고만 써도 되지만 이 기능은 이전 글에서 설명하지 않았기 때문에 사용하지 않았다.)

5번째 줄의 ret_CPS(0)이 평가되는 순간 제어가 callCC블럭 밖으로 탈출한다는 것 하나만 이해하면 된다.

그거 하나만 이해해도 이걸 온갖 방법으로 창의적으로 써먹는데 아무런 문제가 없으니 굳이 실용적인 예제를 줄줄히 열거할 가치가 없다.

실용적인 예제따위 과감히 생략하고 넘어가도록 하겠다.

(4) 덤

CPS 가지고 놀면서 생각해 본 건데 callCC같은 경우 아무래도 아래로 점프하는 것밖에 못하기 때문에 한계가 있다.

위로 빽점프하는 것도 있어야 루프도 만들고 다양한 놀이를 할 수가 있다.

그럼 이게 아예 불가능한 거냐, 그건 아니고 원한다면 얼마든지 loop_CPS같은 함수도 만들 수 있다.

재귀의 원리를 응용하면 되는데 백문이 불여일견이라고 하니 그냥 아래의 예제를 보길 바람.

여기서 loop_CPS는 함수 첫줄로 돌아가는 아래 코드의 loop점프를 대신하는 역할을 한다.

물론 진짜로 이렇게 코드를 작성했다간 무한루프 돌다가 프로그램이 뻗는다.

이건 그냥 예를 든거고 실제로는 조건문이나 루프 탈출하는 다른 점프문과 함께 사용되어야 말이 되는 프로그램이 될거다.

callCC라고 return을 위한 치환기를 만들었듯이 loop을 위한 치환기도 하나 만들어 놓으면 꽤 유용할 것 같은데

설마 이런 간단한 걸 아무도 생각 못했을 것 같지는 않고 왜 아무도 만드려 하지 않는 건지 의문임.

생각해보니 어차피 부수 효과 없는 하스켈에서는 루프 돌아봐야 아무런 쓸데가 없긴 하다.

그래도 부수 효과 있는 언어에서라면 쓸만할 거라고 생각했는데 잘 모르겠다. 아무튼 이것으로 설명을 마무리하도록 하겠음.