일부 함수형 언어가 제공하는 제어 연산자(call/cc, J, delimited continuations 등)를 통해 컨티뉴에이션을 캡처·조작·재시작하는 방법, 이를 활용한 예외·협력적 스레드·백트래킹 같은 제어 구조의 라이브러리 구현, 그리고 CPS 변환과 환원/운용 의미론을 통한 정식 의미 부여를 다룬다.
URL: https://xavierleroy.org/control-structures/book/main010.html
Title: Chapter 8 Control operators
제어 연산자는 일부 함수형 언어가 제공하는 언어 구성요소로, 식이 자신의 컨티뉴에이션을 캡처하고, 그것을 일급 값으로 조작한 뒤, 나중에 다시 시작할 수 있게 해준다.
제어 연산자를 사용하면 고급 제어 구조(예외, 백트래킹, 협력적 스레드 등)를 라이브러리 함수로 프로그래밍하고, 이를 직접 양식(direct style)으로 작성된 프로그램에서 사용할 수 있다. 제어 연산자가 있으면, 사용자 정의 고급 제어 구조를 쓰기 위해 프로그램 전체를 연속 전달 양식(continuation-passing style, CPS)으로 다시 작성할 필요가 없다. 이는 장7에서 했던 방식과 대조적이다.
최초로 출판된 제어 연산자는 Landin (1965)가 Algol 60을 자신의 ISWIM 언어로 번역해 의미론을 제시한 작업에서 등장한다.
ISWIM은 현대의 모든 엄격(strict) 함수형 언어(Scheme, Common Lisp, SML, OCaml 등)의 선구자다. 이는 콜바이밸류 람다 계산에 원시 데이터 타입과 연산을 확장한 것이다. 람다 계산과 달리, 그리고 초기 Lisp 시스템과는 달리, ISWIM은 함수 추상 내의 자유 변수에 대해 정적 스코핑을 보장한다. ISWIM의 의미론은 SECD라는 추상 기계를 사용해 운용적(operational) 방식으로 정의된다(Landin, 1966). SECD는 자유 변수의 정적 스코핑을 가지는 일급 함수를 함수 클로저로 표현한, 함수형 언어의 최초 구현이었다.
Landin (1965)는 ISWIM으로의 번역을 통해 Algol 60을 설명하는 개요를 제시한다. 여러 함수 환경 간에 공유되는 가변 변수를 다루기 위해 Landin은 ML 스타일의 참조(reference)를 추가한다. 비지역적(non-local) goto 점프를 다루기 위해 J(“jump”의 J)라는 제어 연산자를 추가한다.
J 연산자는 C나 Java 같은 언어의 return 문을 일반화한 것으로 생각할 수 있다. J(λ x . e)v의 평가에서는 (λ x . e)v의 값을 계산하고, 현재 함수의 본문에서 남은 계산을 건너뛰어, 그 값을 현재 함수의 호출자에게 직접 반환한다. 예를 들어 다음을 보자:
let f = λ n.n + J(λ x . e)x × 2)3 in f 4
J(λ x . x × 2)3을 평가하면 f 4의 결과로 6 = 3 × 2를 반환하며, n + …의 계산은 무시한다. Thielecke (1998)는 J 연산자를, 인자로 받는 함수(여기서는 λ x . x × 2)를 수정하여, 수정된 함수가 더 이상 호출된 지점으로 돌아가지 않고 둘러싼 함수(여기서는 λ n …)가 호출된 지점으로 돌아가게 만드는 것으로 설명한다.
특수한 경우로, J(λ x . x)v는 C나 Java에서의 return v처럼 동작한다. 예를 들어, 정수 n의 절댓값을 반환하는 난해한(우회적인) 방법은 다음과 같다:
λ n.−(if n>= 0 then J(λ x . x)n else n)
이는 다음 C 코드의 ISWIM 상응물이다:
int abs(int x) { if (x >= 0) return x; return -x; }
J 연산자는 Algol 스타일의 레이블과 goto 문을 인코딩하는 데 사용할 수 있다.
begin s 1; L: s 2 end⇝⎛ ⎝λ z . let rec L = J(λ z . s 2) in s 1; L( )⎞ ⎠( )
goto L⇝L( )
레이블 L은, L을 정의하는 블록 밖으로 점프하는 unit → unit 함수가 된다. 레이블 L을 정의하는 블록은, unit 값을 즉시 적용하는 unit → unit 함수가 되고, 여기서 L은 레이블이 붙은 문장 s 2를 실행한 뒤 함수를 빠져나가는 함수에 바인딩된다. s 2가 L로 점프할 수 있도록 L의 바인딩은 재귀적이다.
섹션6.3에서 설명한, 컨티뉴에이션 기반 지시적 의미론과 이 goto 번역을 비교해 보자. 두 경우 모두, 레이블은 레이블이 붙은 문장을 실행하고 레이블을 정의하는 블록을 빠져나가는 함수로 해석된다. J 제어 연산자 덕분에, 이 번역에서는 컨티뉴에이션이 암묵적으로 남아 있지만, 지시적 의미론에서는 지시 함수의 추가 매개변수로 명시적으로 드러난다.
가장 잘 알려진 제어 연산자는 Scheme 언어의 “call-with-current-continuation”으로, 흔히 call/cc 또는 callcc로 줄여 부른다. 이는 식이 자신의 컨티뉴에이션을 함수 형태로 캡처할 수 있게 한다. 이 연산자는 문헌에서 여러 이름으로 등장했다: Reynolds (1998)에서는 escape(원래 1972년 출판), Sussman and Steele (1975)에서는 catch와 throw, 그리고 Scheme 언어에서는 1982년경에 call-with-current-continuation.
식 callcc(λ k . e)는 다음과 같이 평가된다:
위의 설명은 컨티뉴에이션이 추상 값이고, 그것을 호출하기 위해 throw 연산자가 필요한 ML 계열 언어에서의 관례를 따른다. Scheme에서는 throw 연산자가 없다: 컨티뉴에이션이 함수이며, 단순히 적용해서 호출할 수 있다.
예를 들어, 섹션8.1에서 언급한 정수 n의 절댓값을 구하는 우회적 방식은, callcc와 throw를 사용하면 다음과 같이 쓸 수 있다:
let abs n = callcc (fun k -> - (if n >= 0 then throw k n else n))
n이 음수가 아니라면, throw k n 구성은 abs에서 곧바로 n을 반환하고, “부호 반전” 연산은 건너뛴다.
좀 더 흥미로운 예를 보자. 이진 트리 같은 자료구조에 대한, 명령형 내부 이터레이터가 있다고 하자:
tree_iter : ∀ α, (α → unit) → α tree → unit
callcc를 사용해, 이 이터레이터로 트리를 순회하면서, 술어 pred를 만족하는 원소를 찾자마자 멈추고, 그 원소를 반환할 수 있다:
let tree_search (pred: 'a -> bool) (t: 'a tree) : 'a option = callcc (fun k -> tree_iter (fun x ->if pred x then throw k (Some x)) t; None)
callcc가 캡처하고 k에 바인딩하는 컨티뉴에이션은 tree_search 호출의 컨티뉴에이션이다. 트리 t의 어떤 원소도 pred를 만족하지 않으면, 순회 tree_iter는 정상 종료하고 호출자에게 None을 반환한다. 반대로, 순회가 pred x가 참인 원소 x에 도달하면, 컨티뉴에이션 k가 Some x를 인자로 호출되어 순회를 중단하고, tree_search pred t의 값으로 Some x를 반환한다.
let tree_search (type a) (pred: a -> bool) (t: a tree) : a option = let exception Found of a in try tree_iter (fun x ->if pred x then raise (Found x)) t; None with Found x -> Some x
예외와 달리, callcc는 계산을 일시 중단했다가 나중에 다시 시작할 수 있는 능력도 제공한다. Some x 결과를 만들어내는 지점에서, 순회의 컨티뉴에이션을 캡처하는 두 번째 callcc를 추가해 보자:
let tree_search (pred: 'a -> bool) (t: 'a tree) : ('a * unit cont) option = callcc (fun k -> tree_iter (fun x ->if pred x then callcc (fun k' -> throw k (Some(x, k')))) t; None)
이제 tree_search의 호출자는 pred를 만족하는 첫 번째 원소 x뿐 아니라, k’라는 컨티뉴에이션도 받는다. 이 컨티뉴에이션을 호출하면 중단했던 지점에서 순회를 재개하며, pred를 만족하는 트리의 다음 원소를 찾아 다시 tree_search가 반환되게 한다. 예를 들어:
match tree_search pred t with | None -> printf "Done\n" | Some(x, k') -> printf "Found %d\n" x; throw k' ()
재귀가 없음에도, 이 코드는 pred를 만족하는 t의 모든 원소를 하나씩 출력하고, 마지막에 “Done”을 출력한다. 원소 x가 발견될 때마다, 그것을 출력하고 k’ 컨티뉴에이션을 호출하여, tree_search pred t의 다음 결과로 매치를 재시작한다. 매치는 tree_search가 None을 반환할 때에만 종료된다.
이제 callcc를 사용해 라이브러리로 정의할 수 있는 제어 구조의 예로, 예외, 협력적 스레드, 그리고 백트래킹을 통한 비결정성을 세 가지 보여준다.
예외.예외 처리기는 예외 디스크립터를 기대하는 컨티뉴에이션으로 표현할 수 있다. (OCaml에서 예외 디스크립터는 타입 exn을 가지며, exn 값을 기대하는 컨티뉴에이션의 타입을 exn cont라 쓰겠다.) 활성 처리기의 스택을 전역 변수로 유지한다:
let handlers : exn cont Stack.t = Stack.create()
예외를 발생시키기 위해, 이 스택에서 처리기를 pop하고, 주어진 예외 값으로 그 처리기를 재시작한다:
let raise exn = if Stack.is_empty handlers then fatal_error "unhandled exception"; throw (Stack.pop handlers) exn
다음의 trywith body handler는 OCaml의 try body() with exn -> handler exn와 동등하다: body()를 평가하고, 그 평가 중 발생한 예외를 잡아 handler에 전달한다.
let trywith body handler = callcc (fun k1 -> handler ( callcc (fun k2 -> Stack.push k2 handlers; let res = body() in ignore (Stack.pop handlers); throw k1 res)))
컨티뉴에이션 두 개가 캡처된다: body()가 정상 종료했을 때 그 값을 반환할 k1, 그리고 예외 값을 handler로 전달할 k2. 후자 k2는 body()의 평가 기간 동안 처리기 스택에 푸시된다. body()가 정상 반환하면 handler는 호출되지 않는데, throw k1 res가 handler의 적용을 건너뛰기 때문이다; handler는 k2 컨티뉴에이션이 throw될 때, 즉 예외가 발생했을 때에만 호출된다.
협력적 멀티스레딩.다음 협력적 스레드 구현은 섹션7.3과 유사하지만, 핵심 차이는 yield가 자신의 컨티뉴에이션을 명시적 인자로 받는 대신 callcc로 회수한다는 점이다.
let ready : (unit -> unit) Queue.t = Queue.create () let schedule () = match Queue.take_opt ready with | None -> () | Some k -> k () let yield () = callcc (fun k -> Queue.add (fun () -> throw k ()) ready; schedule()) let terminate () = schedule () let spawn (f: unit -> unit) = Queue.add f ready
그 결과, yield의 호출자들은 CPS로 작성할 필요가 없다: 평범한 명령형 계산인 직접 양식으로 작성하면 된다. 예를 들어, 매 출력마다 제어를 양보(yield)하면서, 1부터 count까지 정수를 주어진 접두사와 함께 출력하는 프로세스는 다음과 같다:
let process name count = for n = 1 to count do printf "%s%d " name n; yield () done; terminate ()
여전히 여러 프로세스의 실행을 교차(interleave)할 수 있다:
spawn (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을 출력한다.
선택 지점과 백트래킹.Prolog 스타일의 해 탐색은, 비결정적 함수 프로그램으로 제시할 수 있다: choice는 여러 가능성 중 하나를 선택하는데, 이후의 주장(assertion)들이 만족되도록 선택한다. 다음은 예시(경의: Matt Might): 변의 길이가 정수인 직각삼각형 a, b, c를 찾아보자.
let a = choose [1;2;3;4;5;6;7] in let b = choose [1;2;3;4;5;6;7] in let c = choose [1;2;3;4;5;6;7] in(* Make sure that it is a right triangle ) assert_ (c * c = a * a + b * b); ( Force side a to be the shortest side ) assert_ (a < b); ( Print the solution found *) printf "%d %d %d\n" a b c
이는 백트래킹으로 구현할 수 있다: 실패한 assert_는 마지막 choose 지점으로 되돌아가, 프로그램이 제공한 대안 리스트에서 다음 값을 고르게 하고, 그 이후의 계산을 다시 실행시킨다. 리스트가 소진되면, 실행은 이전 choose 지점으로 백트래킹한다. 단위 값을 기대하는 컨티뉴에이션으로 표현되는 백트래킹 지점들의 스택을 유지한다:
let backtrack : unit cont Stack.t = Stack.create() let fail () = throw (Stack.top backtrack) () let assert_ b = if not b then fail ()
fail 함수는 마지막 백트래킹 지점으로 점프한다. 예외의 raise와 달리, fail은 백트래킹 지점을 스택에서 제거하지 않는데, 미래에 그 지점으로 다시 백트래킹할 수도 있기 때문이다. 단언 검사(assert_ 함수)는 불리언 조건이 거짓이면 단순히 실패한다.
let choose_aux l = callcc (fun k -> Stack.push k backtrack); match !l with | [] -> ignore (Stack.pop backtrack); fail () | hd :: tl -> l := tl; hd let choose (l: 'a list) : 'a = choose_aux (ref l)
choose 함수는 컨티뉴에이션을 캡처하여 백트래킹 스택에 푸시하기 위해 callcc를 사용한다. 이 컨티뉴에이션은 위의 match 구성으로 분기하며, 리스트 참조 l에서 다음 가능한 값을 하나 꺼내 리스트에서 제거한 뒤 반환한다. l이 비어 있으면, choose는 자신의 컨티뉴에이션을 백트래킹 스택에서 제거하고 fail을 호출하여, 이전 선택 지점으로 백트래킹하게 한다. 순 효과는 choose l이 l의 원소들을 나열하여, 호출자에게 하나씩 반환한다는 것이다.
CPS 변환.callcc에 의미를 부여하는 한 가지 방법은 CPS 변환을 수행해, 변환된 프로그램에서 컨티뉴에이션을 명시적으로 만드는 것이다. 섹션6.5의 콜바이밸류 CPS 변환부터 시작하자:
𝒞(c)= λ k . k c 𝒞(x)= λ k . k x 𝒞(λ x . e)= λ k . k(λ x . 𝒞(e)) 𝒞(e 1 e 2)= λ k . 𝒞(e 1)(λ v 1 . 𝒞(e 2)(λ v 2 . v 1 v 2 k)) 𝒞(if e 1 then e 2 else e 3)= λ k . 𝒞(e 1)(λ v 1 . if v 1 then 𝒞(e 2)k else 𝒞(e 3)k)
그리고 이를 callcc와 throw를 다룰 수 있도록 다음과 같이 확장한다:
𝒞(callcc e)= λ k . 𝒞(e)k k 𝒞(throw e 1 e 2)= λ k . 𝒞(e 1)(λ k 1 . 𝒞(e 2)(λ v 2 . k 1 v 2))
callcc e의 경우, 컨티뉴에이션 k가 “복제”된다: 한 번은 e의 인자로, 한 번은 f를 k에 적용한 결과의 컨티뉴에이션으로 사용된다. throw e 1 e 2의 경우, 컨티뉴에이션 k가 “폐기”된다: e 1을 평가해서 얻은 컨티뉴에이션 k 1로 실행이 계속된다. 이는 다른 언어 구성요소(변수, 추상, 적용)들의 CPS 변환과 대조적이다. 후자들은 컨티뉴에이션을 “선형”으로 사용한다: 각 k 매개변수는 정확히 한 번만 사용된다.
예를 들어, 섹션8.3의 협력적 멀티스레딩 라이브러리에 있는 함수 yield를 보자:
let yield () = callcc (fun k -> Queue.add (fun () -> throw k ()) ready; schedule())
CPS 변환과 “관리적 redex”의 단순화를 거치면 다음을 얻는다
let yield () k = Queue.add (fun () k' -> k ()) ready (fun () -> schedule () k)
함수 yield는 이제 자신의 컨티뉴에이션을 k라는 명시적 매개변수로 받는다. ready 큐에 푸시되는 함수는 자신의 컨티뉴에이션 매개변수 k’는 무시하고 k를 재시작한다.
환원 의미론.callcc의 의미론은 섹션5.5처럼, 문맥 하의 환원을 사용한 운용적 방식으로도 정의할 수 있다.
컨티뉴에이션과 환원 문맥은 밀접하게 관련된다: 프로그램 p가 p = C[e]로 분해될 수 있고, 여기서 C는 환원 문맥이며 e가 헤드 환원 규칙으로 환원될 수 있다면, p에서 e의 컨티뉴에이션은 정확히 λ x . C[x](x는 C에 의해 바인딩되지 않는 변수)이자, 즉 문맥 C를 함수로 구체화한 것이다. 따라서 callcc와 throw에 대해 다음 환원 규칙을 갖는다:
C[callcc(λ k . e)]→ C[(λ k . e)(λ x . C[x])] C[throw(λ x.k)v]→ (λ x.k)v
이 두 규칙은 헤드 환원 →ε이 아니다: 문맥 아래가 아니라 전체 프로그램에 적용된다.
callcc 규칙이 문맥 C를 복제하는 점에 주목하자. 한 번은 λ k . e의 인자로, 또 한 번은 (λ k . e)(λ x . C[x])의 문맥으로 사용한다. 마찬가지로 throw 규칙은 문맥 C를 완전히 폐기하고, (λ x.k)v 적용을 프로그램의 최상위로 끌어낸다.
예를 들어 다음 프로그램을 생각해 보자
p = 2 × callcc(λ k . 1 + throw k 0)
문맥 C = 2 × [ ]에 대해 callcc 규칙을 사용하면 다음과 같이 환원된다:
p→ 2 × (λ k . 1 + throw k 0)(λ x . 2 × x) → 2 × (1 + throw(λ x . 2 × x)0)
이 시점에서, 문맥 C = 2 × (1 + [ ])로 throw 규칙을 사용하면 다음을 얻는다
→ (λ x . 2 × x)0 → 2 × 0 → 0
callcc가 캡처하는 컨티뉴에이션은 “비한정(undelimited)”이다: 프로그램 실행의 끝까지 뻗는다. 이러한 컨티뉴에이션을 호출하면 값이 돌아오지 않는다. 마치 예외를 던지면 값이 돌아오지 않는 것과 같다.
컨티뉴에이션의 일부 응용(예: 섹션7.6의 “생성, 필터, 집계” 예시)에는 “한정(delimited)” 컨티뉴에이션이 필요하다. 한정 컨티뉴에이션은 호출되면 일반 함수처럼 값을 반환한다. 더 나아가, 프로그램 실행의 현재 지점 A에서 나중 지점 B까지의 계산을 나타내며, 프로그램 끝까지가 아니다. 문헌에서는 지점 B를 “프롬프트(prompt)”라고 부르고, 식의 평가 중 “프롬프트를 설정”하기 위해 delim이라는 특별한 구문을 제공한다.
다시 말해, 식 e의 비한정 컨티뉴에이션이 다음과 같은 함수라면
value of e ↦ value of the whole program
한정 컨티뉴에이션은 다음과 같은 함수다
value of e ↦ value of the enclosing delim expression.
경계 가능하고 합성 가능한 컨티뉴에이션을 다루기 위한 다양한 제어 연산자가 제안되어 왔다. 예: Felleisen (1988)의 control/prompt, Danvy and Filinski (1990)의 shift/reset, 그리고 장10에서 설명하는 효과 핸들러. 본 장에서는 경계를 설정하고 컨티뉴에이션을 캡처하기 위한 두 연산자를 delim과 capture로 표기한다.
이 컨티뉴에이션은 λ k . e의 인자로 전달되어, e의 평가 동안 k에 바인딩된다.
인위적인 예로, 다음 프로그램을 생각하자
p = 2 × delim(1 + capture(λ k . k(k 0)))
캡처되는 컨티뉴에이션 k는 λ x . 1 + x이다. 이는 capture(…)의 값 x를 이용해 delim(…)의 인자 값을 만들기 위해 해야 할 남은 계산을 나타낸다. 이어서 k(k 0)가 평가되어 값 2를 얻는다. 이 값은 delim(…)의 결과로 곧바로 반환된다. 따라서 전체 프로그램은 2 × 2 = 4로 평가된다. 좀 더 구체적으로, 다음 환원 수열을 가진다:
p→ 2 × delim((λ k . k(k 0))(λ x . 1 + x)) → 2 × delim((λ x . 1 + x)((λ x . 1 + x)0)) →+ 2 × delim 2 → 2 × 2 → 4
위에서 개괄한 capture의 의미론은 Felleisen (1988)의 control 연산자에 해당한다. 다음 섹션에서 논의하듯이, 다른 의미론도 제안되어 왔다.
다른 제안들은 다중 프롬프트를 지원하며, delim과 capture가 프롬프트 식별자를 인자로 받아, capture가 여러 프롬프트 중 어떤 것을 캡처할 컨티뉴에이션의 경계로 삼을지 선택할 수 있게 한다. 이는 Gunter et al. (1995)의 cupto 제안과, Kiselyov (2012)의 OCaml 확장 delim/cc가 그러하다.
비한정, 전체 프로그램 컨티뉴에이션이 환원 문맥과 밀접히 대응되듯, 한정 컨티뉴에이션은 delim이 없는 환원 “부분 문맥(subcontext)”과 밀접히 대응된다. 두 종류의 환원 문맥에 대한 다음 문법을 보자:
완전 환원 문맥: C::=[ ] ∣ C e ∣ v C ∣ if C then e 1 else e 2 ∣ delim C 프롬프트 없는 환원 문맥: D::=[ ] ∣ D e ∣ v D ∣ if D then e 1 else e 2
전체 프로그램 p를 p = C[delim D[e]]로 분해할 수 있고, 여기서 e가 헤드 환원될 수 있는 식이라면, 우리는 e의 한정 컨티뉴에이션을 식별한 것이다: 그것은 λ x . D[x], 즉 부분 문맥 D를 함수로 구체화한 것이다. D가 delim 구성을 포함하지 않는다는 사실은, 이 한정 컨티뉴에이션이 가장 가까운 둘러싼 delim에서 멈춤을 보장한다.
이 논의는 delim에 대한 두 가지 헤드 환원 규칙을 시사한다:
delim v→ε v delim(D[capture(λ k . e)])→ε … (여러 변형 가능, 아래 참조)
두 번째 규칙은 부분 문맥 D를 포함하지만, 이 두 규칙은 헤드 환원 규칙이다: 임의의 평가 문맥 C 아래에서도 적용될 수 있다.
첫 번째 규칙, delim v →ε v는 자명하다: 인자가 완전히 평가되어 더 이상 컨티뉴에이션을 캡처하지 않게 되면 delim은 삭제될 수 있다. capture의 의미론을 정의하는 두 번째 규칙은 문헌에서 연구된 네 가지 서로 다른 한정 제어 연산자에 상응하는 네 가지 변형을 가진다:
delim(D[capture(λ k . e)])→ε delim((λ k . e)(λ x . D[x]))(control) delim(D[capture(λ k . e)])→ε delim((λ k . e)(λ x . delim D[x]))(shift) delim(D[capture(λ k . e)])→ε (λ k . e)(λ x . D[x])(control0) delim(D[capture(λ k . e)])→ε (λ k . e)(λ x . delim D[x])(shift0)
규칙들은 두 측면에서(위의 강조 부분) 다르다: 캡처를 둘러싼 원래의 delim을 유지할지(control, shift) 제거할지(control0, shift0); 그리고 캡처된 컨티뉴에이션을 delim으로 감쌀지(shift, shift0) 말지(control, control0). 첫 번째 선택은 capture의 본문 e에 다른 capture 연산이 있을 때 중요하다. 두 번째 선택은 캡처된 컨티뉴에이션 안에 다른 capture 연산이 있을 때 중요하다.
특히, Felleisen (1988)의 control 연산자는 capture를 둘러싼 delim은 유지하지만, 캡처된 컨티뉴에이션을 새 delim으로 감싸지는 않는다. 이는 섹션8.5의 인위적 예에서 사용된 의미론이다.
반대로, Danvy and Filinski (1990)의 shift 연산자는 capture를 둘러싼 delim을 유지할 뿐 아니라, 캡처된 컨티뉴에이션을 새 delim으로 감싼다. 이는 프롬프트에 대한 일종의 정적 스코핑을 강제하며, shift 연산자에 대한 미세한 정적 타입 검사를 가능케 한다(섹션13.2 참조).
“제로” 형태(shift0, control0)는 프로그래밍에는 덜 편리하지만, 형식적 연구나 저수준 구현의 구성 요소로 더 적합하다. 특히, control, shift, shift0는 control0로 쉽게 정의할 수 있다.
섹션8.3의 연장선에서, 이제 한정 제어 연산자를 사용해 제어 역전, 백트래킹이 있는 비결정성, 그리고 생성과 집계를 구현하는 방법을 보여준다. 여기서는 capture 연산자에 대해 shift 의미론을 사용한다.
이터레이터의 제어 역전.섹션7.2와 같이, 이진 트리에 대한 내부 이터레이터를 생각하자:
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree let 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를 재사용해서 순수 함수적인 외부 이터레이터를 얻을 수 있다:
type 'a enum = Done | More of 'a * (unit -> 'a enum) let tree_enumerator (t: 'a tree) : 'a enum = delim (tree_iter (fun x -> capture (fun k -> More(x, k))); Done)
트리의 각 원소 x마다, capture 연산자가 컨티뉴에이션 k를 캡처하고, More(x, k)를 전체 delim 식의 값, 즉 tree_enumerator 함수의 결과로 반환하게 만든다. 컨티뉴에이션 k는 capture 식의 반환 지점—순회의 다음 단계—에서부터 한정된 식의 끝—최종 Done 값—까지 뻗는다. 따라서 컨티뉴에이션 k를 적용하면 tree_iter 순회가 재시작되어, 다음 More 열거 원소가 생성되거나, 순회가 끝나 tree_iter가 정상 종료하면 Done이 생성된다.
위의 제어 역전은 섹션7.2에서 보인 논리와 동일하다. 다만 tree_iter를 CPS로 다시 쓰지 않았다는 점이 다르다. 대신 직접 양식의 tree_iter를 그대로 사용하고, 필요한 컨티뉴에이션을 만들기 위해 capture와 delim에 의존한다.
선택 지점과 백트래킹.섹션8.3에서 소개한 Prolog 스타일의 탐색과 백트래킹을 위한 choose, fail, assert_는 한정 컨티뉴에이션으로 쉽게 구현할 수 있다:
let choose l = capture (fun k -> List.iter k l) let fail () = capture (fun k -> ()) let assert_ b = if not b then fail ()
비결정적 계산은 delim 구문으로 둘러싸야 한다:
delim (let a = choose [1;2;3;4;5;6;7] in let b = choose [1;2;3;4;5;6;7] in let c = choose [1;2;3;4;5;6;7] in assert_ (c * c = a * a + b * b); assert_ (a < b); printf "%d %d %d\n" a b c)
choose, fail, assert_가 캡처하는 계산은 이 함수들의 반환 지점에서 시작해 delim 블록의 끝까지 뻗는다. choose는 자신의 컨티뉴에이션을 List.iter로 대체하여, 가능한 각 값에 대해 한 번씩 컨티뉴에이션을 실행한다. 예를 들어 첫 번째 choose는 다음과 같이 된다
delim (List.iter (fun a ->let b = ... in ...) [1;2;3;4;5;6;7])
마찬가지로 fail ()은 choose[]와 동등하며, 자신의 컨티뉴에이션을 ()로 대체하여, delim으로 한정된 지점까지의 나머지 계산을 건너뛰고 다음 List.iter 라운드를 시작하게 만든다. 예컨대 assert_ (c * c = a * a + b * b)가 실패하면, assert_ (a < b)와 printf 문은 실행되지 않고, c의 다음 값이 시도된다.
섹션8.3의 callcc 기반 구현과 달리, 백트래킹 지점의 스택과 choose 지점의 현재 반복 상태를 표현하기 위해 가변 자료구조를 사용할 필요가 없다: choose와 fail이 구현한 한정 컨티뉴에이션의 합성만으로 현재 탐색 상태를 충분히 캡처할 수 있다.
생성과 집계(카운팅).섹션7.6은 정수 값을 반환하는 명시적 컨티뉴에이션을 사용해, 값의 집합을 생성하고, 각 값을 컨티뉴에이션에 통과시킨 뒤, 컨티뉴에이션이 반환하는 개수(예: 합)를 결합하는 방법을 보였다. 한정 컨티뉴에이션 연산자는 프로그램에서 컨티뉴에이션을 명시적으로 드러내지 않고도, 이 관용(패턴)을 직접 양식으로 쉽게 구현하게 해준다. 예를 들어, 다음은 불리언과 [lo, hi] 구간의 정수를 생성하는 두 생성 함수다.
let bool () = capture (fun k -> k false + k true) let int lo hi = capture (fun k ->let rec sum i = if i <= hi then k i + sum (i + 1) else 0 in sum lo)
int 생성기를 사용하여, 6면체 주사위 3개의 모든 던지기를 열거하고, 합이 16 이상이 되는 던지기의 개수를 셀 수 있다:
delim (let d1 = int 1 6 and d2 = int 1 6 and d3 = int 1 6 in if d1 + d2 + d3 >= 16 then 1 else 0)
이는 “d1을 [1,6]에서 하나 고르고, d2를 [1,6]에서 하나, d3를 [1,6]에서 하나 고른 다음, d1 + d2 + d3 ≥ 16이면 1, 아니면 0을 반환하라”고 읽힌다. 실제로는 d1, d2, d3의 가능한 모든 값을 시도한 뒤, 반환된 0/1 결과를 전부 합산한다.
생성 함수는 재귀적일 수도 있다. 예를 들어, 노드에 높이가 적힌, 높이 h의 이진 트리를 생성하는 함수는 다음과 같다.
let rec bintree h = capture (fun k ->if h < 0 then 0 else if h = 0 then k Leaf else if bool () then k (Node(bintree (h-1), h, bintree (int 0 (h-1)))) else k (Node(bintree (int 0 (h-2)), h, bintree (h-1))))
재귀 경우 h> 0에서는, 왼쪽 서브트리의 높이가 h − 1이고 오른쪽 서브트리의 높이가 ≤ h−1인 트리들과, 오른쪽 서브트리의 높이가 h − 1이고 왼쪽 서브트리의 높이가 <h−1인 트리를 분리하여 생성한다. 이렇게 하면 높이 h의 모든 트리를, 중복 없이 생성한다.
일반적인 용어 e의 CPS 변환은 하나의 컨티뉴에이션 k를 인자로 받는다. 이 컨티뉴에이션은 e의 평가가 끝나는 지점에서부터 프로그램 전체의 끝까지 뻗는다. 한정 컨티뉴에이션 연산자를 다루려면, 이 컨티뉴에이션 k를, 둘러싼 delim의 개수 n에 따라, 부분 컨티뉴에이션 k 0, …, k n의 목록으로 분해해야 한다. 컨티뉴에이션 k 0는 e의 평가가 끝나는 지점에서 첫 번째 둘러싼 delim까지, k 1은 그 다음 둘러싼 delim까지, …, k n은 프로그램 끝까지 뻗는다.
이 n+1개의 부분 컨티뉴에이션을 [k 0, …, k n] 리스트로 묶어, CPS 변환된 식에 하나의 인자로 전달할 수도 있다. 대신 Materzok and Biernacki (2011)는 컨티뉴에이션을 n+1개의 구분된 인자로, 커리 형태로 전달한다. 즉, n개의 delim으로 둘러싸인 식 e의 CPS 변환 𝒞(e)는 컨티뉴에이션 k 0, …, k n에 대해 n+1번 적용되어야 한다:
𝒞(e)k 0 k 1…k n
더 나아가, 컨티뉴에이션 k 0가 최종적으로 트리거될 때, 인자로 e의 값뿐 아니라 남은 컨티뉴에이션 k 1, …, k n도 기대한다. 즉, e가 제어 연산자를 사용하지 않고 상수 c로 환원된다면 다음이 성립해야 한다
𝒞(e)k 0 k 1…k n →*k 0 c k 1…k n
이는 표준 CPS 변환의 성질을 일반화한 것이다: e →*c이면 𝒞(e)k →*k c.
코어 언어 구성요소에 대해서는, 변환은 섹션6.5의 표준 콜바이밸류 변환이다:
𝒞(c)= λ k . k c 𝒞(x)= λ k . k x 𝒞(λ x . e)= λ k . k(λ x . 𝒞(e)) 𝒞(e 1 e 2)= λ k . 𝒞(e 1)(λ v 1 . 𝒞(e 2)(λ v 2 . v 1 v 2 k)) 𝒞(if e 1 then e 2 else e 3)= λ k . 𝒞(e 1)(λ v 1 . if v 1 then 𝒞(e 2)k else 𝒞(e 3)k)
커리드 함수 적용의 “마법” 덕분에, 𝒞(e)가 하나보다 많은 컨티뉴에이션에 적용되더라도 이 번역은 여전히 올바르다. 예를 들어 e가 상수 c라면,
𝒞(c)k 0 k 1…k n = (λ k . k c)k 0 k 1…k n → k 0 c k 1…k n
delim은 목록의 맨 위에 사소한(trivial) 컨티뉴에이션을 추가한다:
𝒞(delim e) = 𝒞(e)(λ x . λ k . k x)
e가 컨티뉴에이션을 캡처하지 않고 상수로 환원되면, 기대한 환원 수열을 얻는다:
𝒞(delim e)k 0 k 1…k n= 𝒞(e)(λ x . λ k . k x)k 0…k n →* (λ x . λ k . k x)c k 0…k n →*k 0 c k 1…k n
대칭적으로, capture 연산자는 첫 번째 컨티뉴에이션을 값으로 구체화하고, 컨티뉴에이션 목록에서 제거한다:
𝒞(capture (λ k . e)) = λ k . 𝒞(e)
이 정의로부터 다음을 얻는다
𝒞(capture (λ k.e))k 0 k 1…k n → 𝒞(e) [k := k 0]k 1…k n
즉, e의 평가는 가장 가까운 delim “이후”의 컨티뉴에이션인 k 1과 함께 계속된다. 해당 delim까지의 컨티뉴에이션 k 0는 e의 매개변수 k로 캡처된다. 이는 capture에 대한 control0 의미론을 구현한다.
Butterick (2025)의 “Continuations” 장은 Scheme에서 call/cc와 다른 제어 연산자를 탐구하기 위한 좋은 출발점이다. Friedman (1988)은 call/cc와 그 다양한 응용에 대한 고전적인 튜토리얼이다. Hillerström (2021)의 부록 A는 비한정 컨티뉴에이션과 한정 컨티뉴에이션 모두에 대해 제안된 다양한 제어 연산자를 통합적으로 소개한다.
callcc와 다른 제어 연산자의 효율적 구현은 어렵다. Clinger et al. (1999)는 일급 컨티뉴에이션과 전통적인 호출 스택을 결합하는 여러 접근을 기술한다. Gasbichler and Sperber (2002)는 한정 컨티뉴에이션이 callcc보다 효율적으로 구현될 수 있음을 보인다. Kiselyov (2012)는 본 장의 예시에 사용된, OCaml을 위한 한정 컨티뉴에이션 구현 delimcc를 설명한다. SML/NJ 컴파일러(Appel, 1992)는 CPS 변환과 스택 없는 구현을 사용해 callcc를 제로 비용으로 제공한다.
