CPS로 들어가면, 다시는 돌아오지 못한다

CPS, 즉 연속 전달 스타일(continuation-passing style)은 프로그램, 특히 함수형 프로그램을 위한 중간 표현(IR)이다. SML과 Scheme 같은 언어의 컴파일러에서 사용된다. 그 유용성의 상당 부분은 꼬리 호출과 call/cc 같은 비지역 제어 흐름을 지원한다는 데서 나오지만, SSA(static single assignment)가 종종 그러하듯 최적화 대상으로도 사용할 수 있다.

CPS에는 두 가지 규칙이 있다. 첫째, 함수/연산자의 인자는 항상 사소(trivial) 해야 한다. 둘째, 함수 호출은 반환하지 않는다. 여기서 많은 것들이 따라 나온다.

이 글에서는 작은 Scheme 유사 언어에서 출발해 간단한(Plotkin1) CPS 변환을 만들어 CPS를 소개한다. IR에 대한 몇 가지 최적화를 개략적으로 살펴본 다음, 실제 실행을 위해 IR을 컴파일하는 흔한 방법 몇 가지를 보겠다.

Mini-Scheme

정수가 있다: 5

정수에 대한 몇 가지 연산이 있다: (+ 1 2), (< 3 4) (1 또는 0을 반환)

변수를 바인딩할 수 있다: (let ((x 1)) x) / (letrec ...) ?

단일 매개변수 함수를 만들 수 있다2: (lambda (x) (+ x 1)) 그리고 변수들을 클로저로 캡처할 수 있다

함수를 호출할 수 있다: (f x)

분기할 수 있다: (if (< x y) x y) (0과 1을 불리언으로 쓰기로 했다고 가정)

How do I…?

우리는 cps라는 재귀 함수를 점진적으로 구현할 것이다. 언어의 쉬운 형태들부터 시작해 차근차근 확장해 나간다. 많은 사람들은 Scheme으로 Scheme 컴파일러를 구현하는 것을 좋아하지만, 내게는 준인용(quasiquote)이 모든 것을 필요 이상으로 까다롭게 만들고 교훈을 흐린다고 느껴서, 여기서는 Python으로 한다.

이렇게 하면 코드와 데이터가 깔끔하게 분리된다. Python 코드는 컴파일러이고, S-표현식은 Python 리스트에 기대겠다. 다음은 몇 가지 Scheme 프로그램이 Python 리스트로 어떻게 보일지에 대한 예시다:

5

["+", 1, 2]

["let", [["x", 1]], "x"]

["lambda", ["x"], ["+", "x", 1]]

cps 함수는 인자 두 개를 받는다. 첫 번째 인자 exp는 컴파일할 표현식이다. 두 번째 인자 k는 연속(continuation) 이다. 우리는 값으로 무언가 를 해야 하지만, CPS는 함수가 절대 반환하지 않도록 요구한다. 그럼 어떻게 할까? 물론 다른 함수를 호출한다.

이는 cps의 최상위 호출이 print-to-screen이나 write-to-file 같은 유용한 최상위 연속을 받는다는 뜻이다. cps의 모든 하위 호출은 그 연속, 합성된 연속, 또는 연속 변수 중 하나를 받게 된다.

cps(["+", 1, 2], "$print-to-screen")
# ...or...
cps(["+", 1, 2], ["cont", ["v"], ...])

그래서 연속은 그저 또 다른 함수다. 어느 정도는.

연속으로 쓸 실제 1급 함수를 생성하는 것도 가능하지만, 종종 CPS IR을 분할(partition) 하여 이를 분리하는 편이 유용하다. 모든 실제(사용자) 함수는 마지막 매개변수로 연속을 받는데(반환 값을 넘겨주기 위해), 임의로 탈출할 수 있다. 반면 모든 연속은 생성되어 스택처럼 할당/해제된다. (원한다면 네이티브 스택을 사용해 구현할 수도 있다. Might의 페이지에서 “Partitioned CPS”와 “Recovering the stack”을 보라.)

이 때문에 IR 함수 형태

["fun", ["x",
"k"], ...]

를 IR 연속 형태 `[