함수형 언어에서 CPS(Continuation-Passing Style)와 변형 기법을 활용해 컨티뉴에이션을 노출하고 조작하는 실전 프로그래밍을 다룹니다. 이터레이터, 비동기·동시성, 예외, 백트래킹, 생성·필터링·카운팅 같은 고급 제어 구조를 라이브러리 차원에서 구현하는 방법을 예제와 함께 설명합니다.
직전 장인 6장에서는 함수형 언어의 축약 전략을 명시화하는 CPS 변환을 통해 의미론적 장치로서의 CPS를 소개했다. 이 장에서는 CPS 및 그 변형이 함수형 언어에서 유용한 프로그래밍 기법이기도 하다는 점을 보이며, 함수가 자신이 호출될 때의 컨티뉴에이션에 접근할 수 있게 한다. 이를 통해 제너레이터, 코루틴, 백트래킹 등 다양한 고급 제어 구조를 어떤 함수형 언어에서든 라이브러리 함수로 구현할 수 있다.
CPS의 정의적 특징은 함수가 결과를 보통 방식으로 반환하지 않고, 항상 추가 인자로 주어진 컨티뉴에이션에 결과를 전달한다는 점이다. 예를 들어, 표준 직접 스타일로 작성한 OCaml의 순진한 팩토리얼 함수는 다음과 같다:
ocamllet rec fact n = if n = 0 then 1 else n * fact (n-1)
CPS에서는 이 함수가 추가 인자 k를 받는데, 이는 계산 결과를 넘겨 호출할 컨티뉴에이션이다:
ocamllet rec cps_fact n k = if n = 0 then k 1 else cps_fact (n-1) (fun r -> k (n * r))
형의 변화에 주목하라. 직접 스타일 함수는 int → int 이지만, CPS 함수는 ∀ α . int → (int → α) → α 이다. 여기서 α는 컨티뉴에이션의 최종 결과 타입이며, cps_fact에 전달되는 컨티뉴에이션에 의해 결정된다.
위의 cps_fact 함수는 6.5절의 호출-구값(call-by-value) CPS 변환을 fact 정의에 적용해 기계적으로 얻을 수 있다. 그러나 CPS 변환은 전체 프로그램에 적용하도록 설계된 반면, CPS 프로그래밍은 종종 선택적으로 컨티뉴에이션을 도입한다. 즉, 모든 함수가 아니라 CPS의 이점을 받는 함수에만 컨티뉴에이션을 추가한다. 예를 들어 cps_fact의 모든 호출자를 CPS로 바꾸는 대신, 일부 호출자는 직접 스타일로 남겨 cps_fact n (fun r -> r)를 fact n과 동등하게 호출할 수 있다.
왜 함수를 CPS로 작성할까? 하나의 이유는 CPS로 작성된 재귀 함수는 상수 스택 공간에서 실행된다는 점이다. 모든 재귀 호출이 꼬리 호출이기 때문이다. 이는 상수 전체 공간에서 실행된다는 뜻은 아니다. 직접 스타일에서 스택에 할당될 활성 레코드는, CPS에서는 (함수 클로저 형태로) 힙에 할당된다. 그럼에도 언어 구현이 스택 크기를 인위적으로 제한하는 경우, 스택 대신 힙을 사용하는 것이 유리할 수 있다.
하지만 CPS로 프로그래밍하는 주된 동기는 구현상의 고려와는 별개로, 단지 최종 결과로 컨티뉴에이션을 호출하는 것 이상의 방식으로 컨티뉴에이션을 조작할 수 있는 능력을 CPS 함수에 부여하기 위함이다.
ocamltype 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
다음은 트리를 순회하는 내부 이터레이터(4.1절의 용어; 링크)이다:
ocamllet rec tree_iter (f: 'a -> unit) (t: 'a tree) = match t with | Leaf -> () | Node (l, x, r) -> tree_iter f l; f x; tree_iter f r
이제 tree_iter와 인자 f에 컨티뉴에이션 인자를 추가해 CPS로 다시 써 보자:
ocamllet rec tree_iter (f: 'a -> (unit -> 'b) -> 'b) (t: 'a tree) (k: unit -> 'b) = match t with | Leaf -> k () | Node (l, x, r) -> tree_iter f l (fun () -> f x (fun () -> tree_iter f r k))
위 타입이 보여주듯, 함수 f는 트리 원소 x뿐만 아니라, x 다음에 오는 트리 원소들의 순회를 캡처한 컨티뉴에이션도 인자로 받는다. f를 표준 CPS로 작성하면 x에 대해 무언가를 한 뒤 k를 호출한다. 예를 들어 다음과 같다:
ocamltree_iter (fun x k -> print_int x; k ()) some_tree (fun () -> ())
하지만 f는 k를 다르게 사용할 수 있다. 예를 들어 k를 나중에 쓰기 위해 참조에 저장하면, 파이썬식 제너레이터(명령형 외부 이터레이터)를 트리 위에 얻을 수 있다:
ocamllet tree_generator (t: 'a tree) : unit -> 'a = let rec next = ref (fun () -> tree_iter (fun x k -> next := k; x) t (fun () -> raise StopIteration)) in fun () -> !next ()
tree_generator t가 반환한 생성 함수를 처음 호출하면, tree_iter가 트리 순회를 시작하고, 트리의 가장 왼쪽 원소 x에 대해 fun x k -> ...를 호출한다. 이 함수는 next 참조에 순회의 컨티뉴에이션을 저장한 뒤 x를 호출자에게 반환한다. 그 다음부터 생성 함수를 호출할 때마다, 순회가 멈춘 지점부터 다시 시작하여, 중위 순회에서 다음 원소에서 멈추고 그 값을 반환한다.
또한 tree_iter 함수로부터 순수 함수형 외부 이터레이터도 얻을 수 있는데, 결과를 필요할 때 계산되는 리스트로 만든다:
ocamltype 'a enum = Done | More of 'a * (unit -> 'a enum) let tree_enumerator (t: 'a tree) : 'a enum = tree_iter (fun x k -> More (x, k)) t (fun () -> Done)
비어 있지 않은 트리 t에 대해 tree_enumerator t를 호출하면 More(x, k)를 반환하는데, 여기서 x는 t의 가장 왼쪽 원소이며, k에 ()를 적용하면 t의 다음 원소들을 열거한다.
CPS로 작성된 계산은 프로그램 어디에서든 자신을 일시 중단할 수 있다. 방법은 컨티뉴에이션을 전역 데이터에 저장하고 제어를 완전히 반환하는 것이다. 스케줄러나 GUI 같은 외부 에이전트가 적절한 때에 그 컨티뉴에이션을 다시 시작할 수 있다.
CPS로 작성한 GUI 애플리케이션에서의 대화 상자를 생각해 보자:
ocamldialog_box_yesno (sprintf "%s already exist.\nDo you want to replace it?" filename) (function Yes -> ... | No -> ...)
함수 dialog_box_yesno는 주어진 컨티뉴에이션을 “Yes”와 “No” 버튼의 콜백으로 연결한 뒤, 메인 이벤트 루프로 제어를 반환할 수 있다. 이렇게 하면 대화 상자가 떠 있는 동안에도 GUI가 반응성을 유지한다.
이 패턴을 일반화하면, CPS 계산을 위한 협력적 멀티스레딩을 쉽게 구현할 수 있다. 일시 중단된 스레드는 unit -> unit 컨티뉴에이션으로 표현되어 ready라는 전역 큐에 저장된다. schedule 함수는 이러한 일시 중단된 스레드 중 하나를 재시작한다.
ocamllet ready : (unit -> unit) Queue.t = Queue.create () let schedule () = match Queue.take_opt ready with | None -> () | Some k -> k ()
스레딩 라이브러리는 세 가지 연산을 제공한다. yield는 호출한 스레드를 일시 중단하고 다른 스레드를 재시작한다. terminate는 호출한 스레드의 실행을 종료하지만 다른 스레드는 계속 실행되게 한다. spawn f는 계산 f()를 새 스레드에서 시작한다.
ocamllet yield (k: unit -> unit) = Queue.add k ready; schedule() let terminate () = schedule () let spawn (f: unit -> unit) = Queue.add f ready
주의할 점은, yield가 컨티뉴에이션을 인자로 받으므로 호출자는 CPS로 작성되어야 한다는 것이다. 예를 들어, 다음은 1부터 count까지 정수를 주어진 접두사와 함께 출력하고, 각 출력 후에 제어를 양보(yield)하는 프로세스다:
ocamllet process name count = let rec proc n = if n > count then terminate () else begin printf "%s%d " name n; yield (fun () -> proc (n + 1)) end in proc 1
프로세스를 단독으로 실행하면 순차적으로 동작한다. 예를 들어 process "A" 5는 A1 A2 A3 A4 A5를 출력한다. 여러 프로세스를 동시에 실행하면, yield 지점에서 실행이 교차(interleave)된다. 예를 들어,
ocamlspawn (fun () -> process "A" 5); spawn (fun () -> process "B" 3); process "C" 6
는 C1 A1 B1 C2 A2 B2 C3 A3 B3 C4 A4 C5 A5 C6을 출력한다.
CPS로 작성한 함수는 하나의 컨티뉴에이션 대신 여러 컨티뉴에이션을 받을 수 있다. 각 컨티뉴에이션은 함수에서 빠져나오는 서로 다른 방식을 나타내며, 이는 Fortran 77 서브루틴의 여러 반환 지점과 유사하다(3.4절 참조: 링크). 예를 들어, 다음은 실근이 있는 경우와 그렇지 않은 경우를 각각 위한 두 개의 컨티뉴에이션을 받는 2차 방정식 풀이기다:
ocamllet quadratic a b c k1 k2 = let d = b *. b -. 4. *. a *. c in if d < 0.0 then k2 () else begin let d = sqrt d in let x1 = (-. b +. d) /. (2. *. a) and x2 = (-. b -. d) /. (2. *. a) in k1 x1 x2 end
또한 두 근 x1과 x2를 페어 (x1, x2)로 넘기는 대신, 컨티뉴에이션 k1의 두 개의 인자로 넘기도록 선택했다. 이렇게 하면 여러 결과를 이 방식으로 반환할 수 있음을 보여 준다. quadratic의 전형적인 사용은 다음과 같다:
ocamlquadratic a b c (fun x1 x2 -> printf "Solutions: %g %g\n" x1 x2) (fun () -> printf "No real solutions\n")
성공 케이스와 실패 케이스를 위한 두 컨티뉴에이션을 사용하는 이 기법은, _이중총(double-barreled) CPS 변환_의 변형을 통해 구조적 예외를 구현하는 데 쓸 수 있다. 자세한 내용은 9.3절을 보라.
예외와 마찬가지로, Prolog식 백트래킹도 성공과 실패를 위한 두 컨티뉴에이션으로 구현할 수 있다. 실패 컨티뉴에이션은 마지막 선택 지점으로 백트래킹을 유발한다. 예외와의 주된 차이는, 성공 컨티뉴에이션이 반환 값뿐 아니라 실패 컨티뉴에이션을 인자로 받는다는 점이다.
예를 들어 정규식 매칭을 생각해 보자. 정규식 파서는 단어 w(문자 리스트)와 두 컨티뉴에이션 k_succ, k_fail을 받는 함수다. 만약 w가 w = w1 · w2로 분해되어 w1이 정규식과 매치된다면, k_succ에 w2(남은 입력)와 k_fail을 적용한다. 그렇지 않으면 k_fail을 호출한다. 이는 다음 OCaml 타입에 반영되어 있다:
ocamltype 'a parser = char list -> 'a success -> 'a failure -> 'a and 'a success = char list -> 'a failure -> 'a and 'a failure = unit -> 'a
여기 단일 문자(char), 빈 단어(epsilon), 공집합 언어(empty)에 대한 파서가 있다:
ocamllet char c : 'a parser = fun w succ fail -> match w with | c' :: w' when c' = c -> succ w' fail | _ -> fail () let epsilon : 'a parser = fun w succ fail -> succ w fail let empty : 'a parser = fun w succ fail -> fail ()
다음은 정규식 r과 r′에 대한 파서가 주어졌을 때, 이어붙이기(r · r′), 선택(r ∣ r′), 반복(r*)의 파서를 구성하는 파서 결합자들이다:
ocamllet seq (r: 'a parser) (r': 'a parser) : 'a parser = fun w succ fail -> r w (fun w' fail' -> r' w' succ fail') fail let alt (r: 'a parser) (r': 'a parser) : 'a parser = fun w succ fail -> r w succ (fun () -> r' w succ fail) let rec star (r: 'a parser) : 'a parser = fun w succ fail -> r w (fun w' fail -> if List.length w' < List.length w then star r w' succ fail else fail ()) (fun () -> succ w fail)
반복 star r는 항상 성공한다. r을 한 번 매치한 뒤 다시 star r를 매치하거나, 빈 문자열을 매치하기 때문이다. 다만 r을 매치할 때에는 입력의 최소 한 글자를 매치했음을 보장해야 하므로, List.length w' < List.length w를 검사하고 실패하면 백트래킹한다.
위 star r의 구현은 탐욕적(greedy) 전략을 따른다. 가능한 한 많이 r을 매치한 뒤, 실패하면 되돌아간다. 다음은 탐욕적이지 않은(non-greedy) 전략을 따르는 대안 구현으로, 가능한 한 적게 r을 매치하려고 시도한다.
ocamllet rec star (r: 'a parser) : 'a parser = fun w succ fail -> succ w (fun () -> r w (fun w' fail -> if List.length w' < List.length w then star r w' succ fail else fail ()) fail)
어떤 단어가 정규식과 매치되는지 판정하려면, 실패 컨티뉴에이션이 false를 반환하고, 성공 컨티뉴에이션은 모든 문자가 매치되면 true를, 아니면 백트래킹하게 하는 방식으로 파서를 호출한다:
ocamllet matches w r = r w (fun w' fail -> if w' = [] then true else fail ()) (fun () -> false)
백트래킹이 필요한 예로, 단어 w = ab를 (a ∣ a.b)에 매칭하는 경우를 보자. 첫 번째 대안 a는 부분 매치만 만들어 b를 남긴다. 두 번째 대안 a.b를 시도하려면 백트래킹이 필요하며, 이 대안은 w를 완전히 매치한다.
표준 CPS로 작성된 함수는 인자로 받은 컨티뉴에이션의 반환 값을 들여다보지 않는다. 함수는 컨티뉴에이션을 꼬리 위치에서 호출하거나, 다른 컨티뉴에이션으로 감쌀 뿐이다. 이는 함수의 타입에도 반영되어, 종종 컨티뉴에이션의 반환 타입에 다형적이다. 7.1절의 cps_fact 예에서 보았던 것처럼 말이다(링크).
어떤 응용에서는, 함수가 컨티뉴에이션이 반환하는 값을 사용해—컨티뉴에이션이 받은 결과의 적합성에 관한 피드백처럼—의사 결정을 하는 것이 유용할 수 있다. 예를 들어, 컨티뉴에이션이 불리언을 반환하고, true는 “네가 준 결과가 맞다”, false는 “다른 결과를 달라”를 의미하도록 할 수 있다.
위 정규식 매칭 예를 이 스타일로 다시 써 보자. 이제 파서는 char list -> bool 타입의 단일 컨티뉴에이션을 갖는데, 남은 입력 단어(매치되지 않은 접미사)를 인자로 받아 그것이 인식되면 true를, 아니면 false를 반환한다. 파서 자신은 입력 단어가 완전히 매치되면 true를, 아니면 false를 반환한다.
ocamltype parser = char list -> (char list -> bool) -> bool let char c : parser = fun w k -> match w with | c' :: w' when c' = c -> k w' | _ -> false let epsilon : parser = fun w k -> k w let empty : parser = fun w k -> false let seq (r: parser) (r': parser) : parser = fun w k -> r w (fun w' -> r' w' k) let alt (r: parser) (r': parser) : parser = fun w k -> r w k || r' w k let rec star (r: parser) : parser = fun w k -> r w (fun w' -> List.length w' < List.length w && star r w' k) || k w let matches w (r: parser) : bool = r w (fun w' -> w' = [])
7.5절의 코드에서는 실패 컨티뉴에이션을 호출해 백트래킹을 유발했지만, 여기서는 false를 반환해 유발한다. 불리언 “또는”(|| 연산자)은 첫 번째 대안이 실패한 경우 다른 대안을 시도하는 데 쓰인다.
컨티뉴에이션이 해를 찾았는지 여부를 나타내는 불리언을 반환하는 대신, 가능한 해의 개수를 세는 정수를 반환하게 할 수도 있다. 이 스타일에서는, 기본 함수들이 여러 가능성을 열거하여 컨티뉴에이션에 넘기고, 그 반환된 개수들을 합한다.
예를 들어, 다음은 불리언 값을 열거하는 함수와, lo부터 hi까지의 정수를 열거하는 함수다:
ocamllet bool k = k false + k true let rec int lo hi k = if lo <= hi then k lo + int (lo + 1) hi k else 0
int 제너레이터를 사용해, 6면체 주사위 3개를 던진 모든 경우를 열거하고, 합이 16 이상인 경우의 수를 셀 수 있다(정답은 10이다).
ocamlint 1 6 (fun d1 -> int 1 6 (fun d2 -> int 1 6 (fun d3 -> if d1 + d2 + d3 >= 16 then 1 else 0)))
좀 더 흥미로운 예로, 높이가 h인 모든 AVL 균형 이진 트리를 열거하고, 컨티뉴에이션 k로 그것들을 계측(measure)할 수 있다:
ocamllet rec avltree h k = if h < 0 then 0 else if h = 0 then k Leaf else avltree2 (h-1) (h-1) k + avltree2 (h-2) (h-1) k + avltree2 (h-1) (h-2) k and avltree2 hl hr k = avltree hl (fun l -> avltree hr (fun r -> k (Node (l, 0, r))))
AVL 트리에서는 한 노드의 두 서브트리 높이 차가 최대 1이어야 한다. 따라서 높이가 h인 트리의 두 서브트리 높이는 각각 h−1, h−1 또는 h−1, h−2 또는 h−2, h−1이다. 보조 함수 avltree2는 값 0을 가진 노드(비어 있지 않은 트리)를 생성하되, 왼쪽과 오른쪽 서브트리의 높이가 각각 hl, hr가 되게 한다. avltree 4 (fun _ -> 1)을 평가하면, 높이 4인 AVL 트리가 315개 있음을 알 수 있다.
마지막으로, 정수 개수 대신 [0,1] 범위의 부동소수점 수로 확률을 반환하게 할 수도 있다. 이때 컨티뉴에이션 k는 함수들이 열거하는 다양한 가능성에 대한 ‘측도(measure)’ 역할을 한다. 예를 들어, 다음은 불리언과 [lo, hi] 범위의 정수에 대한 열거자를, 개수 대신 측도를 사용해 정의한 것이다:
ocamllet bool k = 0.5 *. (k false +. k true) let int lo hi k = let rec sum i = if i <= hi then k i +. sum (i + 1) else 0.0 in sum lo /. float (hi - lo + 1)
그 다음, 6면체 주사위 3개를 던져 합이 정확히 15가 될 확률을 다음과 같이 계산할 수 있다(정답은 약 4.6%).
ocamlint 1 6 (fun d1 -> int 1 6 (fun d2 -> int 1 6 (fun d3 -> if d1 + d2 + d3 = 15 then 1.0 else 0.0)))
Friedman and Wand (2008)의 5장과 6장에서는, 특히 예외나 동시성을 특징으로 하는 언어의 인터프리터 작성과 관련하여 컨티뉴에이션으로 프로그래밍하는 다른 예들을 다룬다.
CPS는 RABBIT(Steele, 1978)과 SML/NJ(Appel, 1992) 컴파일러처럼, 함수형 언어용 최적화 컴파일러의 중간 표현으로도 사용할 수 있다. Kennedy (2007)는 CPS 기반 중간 표현에서 수행하기 쉬운 고급 컴파일러 최적화를 논한다.
