제10장 사용자 정의 효과를 위한 효과 처리기

Chapter 10 Effect handlers for user-defined effects

---

• 10.1 예외에서 효과로
• 10.2 효과 처리기와 델리미트된 연속체
• 10.3 제어 역전
• 10.4 협력적 멀티스레딩
• 10.5 효과 처리기의 의미론
• 10.6 효과 처리기를 위한 CPS 변환
• 10.7 추가로 읽을거리

이 장에서는 사용자 정의 효과를 위한 효과 처리기(effect handler)를 설명한다. 이는 델리미트된 연속체(delimited continuation)와 예외를 결합한 제어 연산자이다. 효과 처리기는 Bauer and Pretnar (2015)가 프로그래밍 언어 구문으로 도입했으며, 그 기초가 되는 대수적 효과 이론은 장12에서 다룬다.

10.1 예외에서 효과로

예외를 이용한 오류 포착.장9에서 본 것처럼, 예외는 함수가 정상 결과를 반환하지 못하게 하는 오류를 보고하기 위해 자주 사용된다. 예를 들어, 다음은 문자열을 정수로 변환하고, 문자열이 정수로 인식되지 않으면 Conversion_error 예외를 발생시키는 OCaml의 parse_int 함수이다:

ocaml
type exn += Conversion_error: string -> exn

let parse_int s =
  match int_of_string_opt s with
  | Some n -> n
  | None -> raise (Conversion_error s)

예외는 type exn += … 구문을 사용해 선언하는데, 이는 예외 타입 exn을 새 Conversion_error 생성자로 확장한다는 뜻이다. 이 선언은 장9에서 사용한 exception Conversion_error of string 선언과 동등하지만, exn 타입이 확장 가능함을 강조하며 Conversion_error 예외 생성자의 타입을 보여준다.

parse_int를 사용해 문자열 리스트를 정수로 변환하고 그 합을 계산할 수 있다:

ocaml
let sum_stringlist lst =
  lst |> List.map parse_int |> List.fold_left (+) 0

let safe_sum_stringlist lst =
  match sum_stringlist lst with
  | res -> res
  | exception Conversion_error s ->
      printf "Bad input: %s\n" s; max_int

리스트 lst에 잘못된 문자열이 들어 있으면 Conversion_error 예외가 발생하여 sum_stringlist가 중단된다. 이 예외는 safe_sum_stringlist에서 처리되어 오류 메시지를 출력한 뒤 기본 결과를 반환한다.

효과를 사용해 오류를 고치기.앞의 예를 예외 대신 사용자 정의 효과로 다시 보자.

ocaml
type _ eff += Conversion_error: string -> int eff

let parse_int s =
  match int_of_string_opt s with
  | Some n -> n
  | None -> perform (Conversion_error s)

차이는 작다. 효과를 발생시킬 때는 raise 대신 perform을 사용하고, 효과 선언은 exn 타입 대신 eff 타입을 확장한다. 다만 eff 타입은 타입 매개변수를 가지며, Conversion_error 효과의 경우 int이고, 이는 효과의 반환 타입을 나타낸다. 더 중요한 차이는 효과를 처리하는 방식에서 나타난다:

ocaml
let sum_stringlist lst =
  lst |> List.map parse_int |> List.fold_left (+) 0

let safe_sum_stringlist lst =
  match sum_stringlist lst with
  | res -> res
  | effect Conversion_error s, k ->
      printf "Bad input: %s, replaced with 0\n" s;
      continue k 0

효과 처리기(match 구문의 effect 부분)는 효과의 값 Conversion_error s뿐 아니라 연속체 k도 받는다. 이 연속체는 Conversion_error 효과가 perform된 지점에서 계산을 다시 시작하는 데 사용할 수 있다. 여기서 처리기는 오류 메시지를 출력하고 값 0으로 연속체를 재시작한다. 그러면 parse_int는 0을 반환하고, sum_stringlist는 lst의 다음 원소들로 진행한다. 예를 들어:

# let n = safe_sum_stringlist ["1"; "xxx"; "2"; "yyy"]
Bad input xxx, replaced with 0
Bad input yyy, replaced with 0
val n : int = 3

효과를 포착하고 변환하기. 효과 처리기는 효과에 반응하는 방식에서 많은 자유도를 가진다. 따라서 동일한 효과를 수행하는 코드라도 서로 다른 처리기 안에서 실행될 때 매우 다른 동작을 보일 수 있다. 다음 예시는 Pretnar (2015)에서 가져온 것이다. 출력을 원할 때 수행되는 효과 Print를 생각해 보자.

ocaml
type _ eff += Print : string -> unit eff

let print (s: string) : unit = perform (Print s)

let abc () = print "a"; print "b"; print "c"

처리기 없이 이 코드는 쓸모가 없다. abc()를 실행하면 포착되지 않은 Print 효과에서 멈춘다. Print 효과에 의미를 부여하는 처리기 안에서 실행해야 한다.

다음 처리기는 계산 f()를 실행하면서 Print 효과를 실제 단말 출력으로 바꾼다:

ocaml
let output (f: unit -> unit) : unit =
  match f () with
  | () -> print_newline()
  | effect Print s, k -> print_string s; continue k ()

예상대로 output abc는 단말에 abc를 출력한다. 다른 처리기는 f()가 일으킨 모든 Print 효과를 모아 문자열로 만들고 마지막에 이 문자열을 반환할 수도 있다:

ocaml
let collect (f: unit -> unit) : string =
  match f () with
  | () -> ""
  | effect Print s, k -> s ^ continue k ()

이제 collect abc는 문자열 "abc"를 반환한다. 타입의 변화에 주목하자. 계산 f는 여전히 unit -> unit 타입이지만, 처리기는 f()의 () 반환값을 빈 문자열로 바꾸고, continue로 생산된 문자열 값들을 모아 문자열을 만들어 낸다.

처리기가 Print 효과를 재방출(re-emit)하도록 선택할 수도 있다. 예를 들어, 다음 처리기는 계산 f가 생성하는 Print 효과의 순서를 뒤집는다.

ocaml
let reverse f =
  match f () with
  | () -> ()
  | effect Print s, k -> continue k (); print s

collect (fun () -> reverse abc)를 실행하면 문자열 "cba"가 반환된다. 또는 각 출력에 일련번호를 붙일 수도 있다:

ocaml
let number f =
  begin match f () with
  | () -> (fun lineno -> ())
  | effect Print s, k ->
      (fun lineno ->
         print (sprintf "%d:%s\n" lineno s);
         continue k () (lineno + 1))
  end 1

여기서도 타입 변화에 주목하자. 처리기는 int -> unit 타입이며, int 매개변수는 현재 줄 번호를 뜻한다. 처음 줄 번호 1에 적용된다.

깊은 처리기 vs. 얕은 처리기.효과 처리기는 “깊은(deep)” 것과 “얕은(shallow)” 것 두 종류가 있다. 깊은 처리기는 처리되는 계산이 정상 종료할 때까지 활성 상태를 유지한다. 효과를 잡아 continue로 연속체를 재시작하면 이후의 효과들도 계속 처리한다. 반면 얕은 처리기는 처리되는 계산이 정상 종료하거나 효과를 수행하는 즉시 사라지며, 재시작된 연속체가 수행하는 효과는 처리하지 않는다.

OCaml의 match…with effect 구문은 깊은 효과 처리기를 구현한다. 따라서 지금까지 본 예시는 모두 깊은 처리기를 사용한다. 얕은 처리는 OCaml의 Effect.Shallow 라이브러리에 함수 형태로 제공된다. safe_sum_stringlist 예제가 깊은 처리기 대신 얕은 처리기를 사용했다면,

safe_sum_stringlist ["1"; "xxx"; "2"]

는 여전히 xxx에 대한 오류를 교정하고 3을 반환할 것이다. 하지만

safe_sum_stringlist ["1"; "xxx"; "2"; "yyy"]

는 yyy에 대한 오류를 교정하지 못할 것이다. 얕은 처리기는 그 시점에 더 이상 활성 상태가 아니므로, 포착되지 않은 Conversion_error 효과에서 멈춘다.

10.2 효과 처리기와 델리미트된 연속체

효과 처리기는 재시작 가능한 예외 이상을 표현할 수 있다. 절8.5의 제어 연산자처럼, 효과 처리기는 일급 값으로 사용할 수 있는 델리미트된 연속체를 포착한다.

처리기가 포착하는 연속체. 효과 F에 대한 처리기가 식 e 주위에 있다고 하자:

ocaml
match e with effect F x, k -> h | …

e(또는 e가 호출하는 함수들)이 효과 F를 수행하면, 포착되어 k에 바인딩되는 연속체는 perform(F v) 식에서부터 e 평가의 끝까지 확장된다. 다시 말해, 처리기가 그 연속체의 구분자(delimiter) 역할을 한다.

연속체를 값 w에 적용하면, 즉 continue k w를 호출하면 e의 평가가 perform(F v)가 값 w를 반환한 것처럼 다시 시작된다. 지금까지의 예시에서 연속체 k는 처리기 h 안에서 적용되었다. 그러나 이 연속체는 일급 값이므로, 처리기 h가 그 연속체를 결과의 일부로 반환하거나 자료구조에 저장할 수도 있다. (예시는 절10.3과 절10.4 참조.)

연속체의 타입. OCaml에서 위 예의 연속체 k의 타입은 (α, β) continuation이다. 여기서 α는 연속체가 기대하는 값의 타입이고, β는 연속체가 산출하는 결과의 타입이다. 타입 α는 효과 F의 타입 α eff에 의해 결정된다. 타입 β는 처리되는 식 e의 타입과 같다. 요약하면:

handled effect:    F : α eff
handled expression: e : β
continuation:      k : (α, β) continuation
raising:           perform : α eff → α
restarting:        continue : (α, β) continuation → α → β

OCaml에서의 선형 연속체.OCaml의 효과 처리기 구현에는 하나의 제약이 있다. 연속체는 정확히 한 번만 사용하는, 즉 선형(linear)이어야 한다. 다시 말해, 효과 처리기가 포착한 연속체 k는 continue k v로 한 번만 재시작할 수 있다. continue를 두 번째로 k에 적용하면 특별한 예외가 발생한다. 또한 연속체 k를 재시작할 필요가 없다면 자원을 올바르게 정리하기 위해 예외 값을 e와 함께 discontinue k e로 명시적으로 폐기해야 한다.

이 선형성 제약은 효과 처리기 개념의 본질적인 부분은 아니다. Eff나 Koka처럼 연속체를 여러 번 적용할 수 있게 지원하는 구현도 있다. 그러나 OCaml의 선형 연속체는 OCaml 컴파일러가 수행하는 여러 최적화와 호환되며, 연속체를 여러 번 실행할 수 있을 때는 이러한 최적화가 무효화된다. 또한 선형 연속체는 여러 스택 간 전환으로 효율적으로 구현할 수 있어, 호출 스택 일부 복사의 비용을 피할 수 있다. 다시 효과 F에 대한 처리기가 식 e 주위에 있다고 하자:

ocaml
match e with effect F x, k -> h | …

그림10.1에 나타난 것처럼, 처리기는 초기 스택 S에서 실행된다. 처리기는 처리되는 식 e를 실행하기 위해 새 스택 S′를 만든다. e가 효과 F를 수행하면, 제어는 스택 S에서 실행 중인 처리기 h로 되돌아간다. 델리미트된 연속체 k는 스택 S′ 자체로 표현된다. k를 continue k v로 재시작하면 S′로 다시 전환되어 e의 실행을 재개한다. e가 정상 종료하거나 discontinue로 연속체 k가 폐기될 때까지 실행은 S′와 S 사이를 번갈아 오가며, 이때 보조 스택 S′는 해제된다. k가 선형으로 사용되므로, 스택 S′는 제자리에서 수정될 수 있고, 향후 수정으로부터 보호하기 위해 복사할 필요가 없다.

10.3 제어 역전

효과 처리기는 내부 이터레이터 및 기타 고계 함수에서 제어를 손쉽게 뒤집어 외부 이터레이터와 제너레이터로 바꾸게 해 준다.

내부 이터레이터에서 함수형 외부 이터레이터로.절7.2의 예시를 이어, 이진 트리 타입과 트리의 각 값에 주어진 함수를 적용하는 내부 이터레이터를 다시 보자:

ocaml
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

절4.1의 용어를 따르면, 다음은 트리에 대한 내부 이터레이터이다:

ocaml
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_enumerator를 도출하고자 한다. 기대하는 타입은 다음과 같다:

ocaml
type 'a enum = Done | More of 'a * (unit -> 'a enum)
val tree_enumerator : 'a tree -> 'a enum

트리의 각 원소에 대해 아래에서 정의하는 Next라는 효과를 perform하면 된다. 그러면 Next의 처리기가 원하는 열거 값을 만들어 낼 것이다.

ocaml
let tree_enumerator (type elt) (t: elt tree) : elt enum =
  let module M = struct
    type _ eff += Next : elt -> unit eff
  end in
  match tree_iter (fun x -> perform (M.Next x)) t with
  | () -> Done
  | effect M.Next x, k -> More(x, continue k)

지역 모듈 M을 사용하여 각 tree_enumerator 호출에 지역적인, 신선한 Next 효과를 만들고, 트리 원소의 타입 elt에 맞춘다. 그런 다음 tree_iter를 사용해 트리 t의 각 원소 x에 대해 효과 Next x를 perform한다.

처리기에는 두 경우가 있다. tree_iter가 정상적으로 반환하면 트리 순회가 끝난 것이고 더 이상 반환할 트리 원소가 없으므로 Done을 반환한다. tree_iter가 Next x 효과를 수행하면, 값 x와 부분 적용 continue k로 얻은 함수를 담은 More 생성자를 반환한다. 이 함수가 적용되면, tree_iter 순회는 중단했던 곳에서 재시작되어 더 많은 트리 원소를 생성하다가 결국 멈춘다.

이 코드는 절7.2의 tree_enumerator 예와 논리가 같다. 다만 그 예에서는 내부 이터레이터 tree_iter가 CPS로 작성되어, 반복되는 함수가 자신의 인자로 연속체에 접근했다. 여기서는 tree_iter를 직접 스타일로 작성하고, 효과 처리기를 사용해 연속체를 포착한다.

내부 이터레이터에서 명령형 제너레이터로.순수 함수형 열거 대신, 파이썬 제너레이터 스타일로 내부 가변 상태를 이용해 트리의 원소를 하나씩 생성할 수도 있다:

ocaml
let tree_generator (type elt) (t: elt tree) : unit -> elt =
  let module M = struct
    type _ eff += Next : elt -> unit eff
  end in
  let rec next = ref (fun () ->
    match tree_iter (fun x -> perform (M.Next x)) t with
    | () -> raise StopIteration
    | effect M.Next x, k -> next := continue k; x) in
  fun () -> !next()

내부 레퍼런스 next는 unit -> elt 타입의 함수를 담는다. 이 함수가 호출될 때마다 트리의 다음 원소를 반환하고, 트리 순회를 계속할 수 있도록 next를 갱신한다. 초기의 next 함수는 tree_iter (fun x -> perform (Next x)) t 주위에 처리기를 설치한다. 이 처리기는 Next 효과를 포착하여, 트리 순회를 재시작하도록 next를 갱신하고, 현재 트리 원소를 반환한다. 트리의 모든 원소가 반환되고 나면 StopIteration 예외가 발생한다.

일반적인 제어 역전.위 접근법은 트리 순회나 내부 이터레이터에만 국한되지 않는다. 임의의 계산을 파이썬 스타일의 명령형 제너레이터나 함수형 열거자로 바꾸는 데 사용할 수 있다. 해당 계산은 외부로 값을 보낼 때 사용할 함수 yield를 매개변수로 받는다. 예를 들어, [−n, n] 구간의 모든 수를 보내는 함수는 다음과 같다:

ocaml
let numbers n ~yield =
  yield 0;
  for i = 1 to n do
    yield i; yield (-i)
  done

인자로 받은 값을 출력하는 함수를 주어 시험해 볼 수 있다:

ocaml
numbers 10 ~yield:(printf "%d\n")

다음의 일반 함수를 사용하면 이를 파이썬 스타일 제너레이터로 바꿀 수 있다:

ocaml
let generator (type elt)
    (f: yield:(elt -> unit) -> unit) : unit -> elt =
  let module M = struct
    type _ eff += Next : elt -> unit eff
  end in
  let rec next = ref (fun () ->
    match f ~yield:(fun x -> perform (M.Next x)) with
    | () -> raise StopIteration
    | effect M.Next x, k -> next := (fun () -> continue k ()); x) in
  fun () -> !next()

함수형 열거자로도 만들 수 있다:

ocaml
let enumerator (type elt)
    (f: yield:(elt -> unit) -> unit) : elt enum =
  let module M = struct
    type _ eff += Next : elt -> unit eff
  end in
  match f ~yield:(fun x -> perform (M.Next x)) with
  | () -> Done
  | effect M.Next x, k -> More(x, fun () -> continue k ())

10.4 협력적 멀티스레딩

사용자 정의 효과와 효과 처리기를 사용하면 협력적 멀티스레딩을 라이브러리로 손쉽게 구현할 수 있다. 많은 동기화 및 통신 메커니즘을 효과로 쉽게 표현할 수 있고, 특히 OCaml의 선형 연속체와 스택 전환 기반 구현 덕분에 성능도 좋다.

스폰과 양보.절7.3과 절8.3에서처럼, 세 개의 함수로 멀티스레딩을 소개한다: 새 스레드에서 계산 f()를 시작하는 spawn f, 호출한 스레드를 일시 중단하고 다른 스레드를 재시작하는 yield, 현재 스레드를 중단하는 terminate. 아직 스케줄링 알고리즘을 정하지 않았으므로, 이 세 함수를 효과를 발생시키는 것으로 구현한다:

ocaml
type _ eff +=
  | Spawn : (unit -> unit) -> unit eff
  | Yield : unit eff
  | Terminate : unit eff

let spawn f = perform (Spawn f)
let yield () = perform Yield
let terminate () = perform Terminate

이 함수들의 실제 동작은 run f라는 효과 처리기에 의해 결정된다. 이 처리기는 멀티스레드 계산 f()를 둘러싸고, Spawn, Yield, Terminate 효과를 처리하며, 스레드를 스케줄링한다. 준비된 스레드의 큐를 unit -> unit 함수들로 표현한다.

ocaml
let runnable : (unit -> unit) Queue.t = Queue.create()
let suspend f = Queue.add f runnable
let restart () =
  match Queue.take_opt runnable with
  | None -> ()
  | Some f -> f ()

스케줄러는 다음과 같다:

ocaml
let rec run (f: unit -> unit) =
  match f() with
  | () -> restart()
  | effect Spawn f, k -> suspend (continue k); run f
  | effect Terminate, k -> discontinue k Exit; restart ()
  | effect Yield, k -> suspend (continue k); restart ()

현재 실행 중인 스레드가 종료하거나 Terminate 효과를 수행하면, runnable 큐에서 첫 번째 준비된 스레드를 재시작한다. 준비된 스레드가 없다면 마지막 실행 스레드가 종료하는 것이므로 전체 멀티스레드 계산이 끝난다.

현재 실행 중인 스레드가 Yield 효과를 수행하여 실행을 중단하려 하면, 현재 스레드를 양보 지점 바로 뒤에서 재시작하는 unit -> unit 함수인 continue k를 준비된 스레드로 큐에 넣고, 다른 준비된 스레드를 재시작한다. 준비된 스레드가 없다면 방금 자신을 중단시킨 스레드를 다시 재시작한다.

마지막으로 Spawn f 효과가 수행되어 새 스레드의 생성이 요청되면, 스케줄러는 현재 실행 중인 스레드를 중단시키고 f에 제어를 넘긴다. f() 실행 중에 발생하는 효과들이 올바르게 처리되도록, 단순히 f()가 아니라 run f를 사용해야 한다.

다른 스케줄링 전략을 선택할 수도 있다. 예를 들어, f를 나중에 실행하도록 저장하고 현재 스레드가 계속 실행되도록 할 수 있다:

ocaml
| effect Spawn f, k -> suspend (fun () -> run f); continue k ()

이 간단한 스케줄러만으로도 직접 스타일로 작성된 여러 스레드의 실행을 상호교차(interleave)할 수 있다:

ocaml
let process name count =
  for n = 1 to count do
    printf "%s%d " name n; yield ()
  done

let _ =
  run (fun () ->
    spawn (fun () -> process "A" 5);
    spawn (fun () -> process "B" 3);
    process "C" 6)

이 코드는 A1 B1 A2 C1 B2 A3 C2 B3 A4 C3 A5 C4 C5 C6을 출력한다.

통신 채널.이제 스레드가 값을 교환하면서 실행을 동기화할 수 있게 해 주는 통신 채널을 추가하자. 값 타입 α를 운반하는 통신 채널 타입 α channel, 채널을 만드는 함수 new_channel, 값을 채널로 보내거나 채널에서 값을 받는 함수 send와 recv를 제공한다. π-칼큘러스 스타일의 “래데부(rendez-vous)” 통신을 구현한다: 채널에서의 send는 같은 채널에 대해 다른 스레드가 recv를 호출할 때까지 블록된다. 그러면 값이 전달되고 양쪽 스레드가 재시작된다.

각 채널은 두 개의 큐로 구성된다. 하나는 send 연산에서 블록된 스레드 큐, 다른 하나는 recv 연산에서 블록된 스레드 큐이다. 언제나 이들 중 적어도 하나는 비어 있다.

ocaml
type 'a channel = {
  senders: ('a * (unit, unit) continuation) Queue.t;
  receivers: ('a, unit) continuation Queue.t
}

let new_channel () = {
  senders = Queue.create();
  receivers = Queue.create()
}

send와 recv 연산은 스케줄러가 처리해야 하므로 효과로 바꾼다.

ocaml
type _ eff +=
  | Send : 'a channel * 'a -> unit eff
  | Recv : 'a channel -> 'a eff

let send ch v = perform (Send(ch, v))
let recv ch = perform (Recv ch)

Send와 Recv 효과를 처리하려면 스케줄러에 두 가지 경우를 추가한다:

ocaml
let rec run (f: unit -> unit) =
  match f () with
  ...
  | effect Send(ch, v), k -> begin
      match Queue.take_opt ch.receivers with
      | Some rc -> suspend (continue k); continue rc v
      | None -> Queue.add (v, k) ch.senders; restart()
    end
  | effect Recv ch, k -> begin
      match Queue.take_opt ch.senders with
      | Some (v, sn) -> suspend (continue sn); continue k v
      | None -> Queue.add k ch.receivers; restart()
    end

현재 스레드가 채널 ch에 값 v를 보낸 경우, 해당 채널에서 값을 기다리는 스레드가 하나 이상 있다면 그 중 하나 rc를 receivers 큐에서 꺼내 값을 v로 재시작한다. 반대로 채널 ch에서 값을 기다리는 스레드가 없다면, 현재 스레드를 ch의 senders 큐에 넣고 다른 스레드를 재시작한다.

채널 ch에서 값을 받는 것도 유사하다. 값을 보내기를 기다리는 스레드 sn이 하나 이상 있다면, 스레드 sn을 준비 상태로 만들고 현재 스레드에는 v를 반환한다. 보낸 쪽이 없으면 현재 스레드를 중단시키고 receivers 큐에 추가한 뒤 다른 스레드를 재시작한다.

위 스케줄러는 받는 쪽(recv)에게 보내는 쪽(send)보다 우선순위를 준다. (두 Some 경우를 비교하라.) 다른 스케줄링 결정은 쉽게 구현할 수 있다.

프로미스.스레드 간 통신의 또 다른 메커니즘은 프로미스(promises)이며 퓨처(futures)라고도 부른다. 프로미스는 계산 중인 값으로, 나중에 모든 스레드가 이용할 수 있게 된다. 프로미스는 현재 값(초깃값은 None)과 이 값을 기다리는 스레드들의 리스트로 표현한다:

ocaml
type 'a promise = {
  mutable value: 'a option;
  mutable waiters: ('a, unit) continuation list
}

let new_promise () : 'a promise = { value = None; waiters = [] }

프로미스에는 두 가지 연산이 있다. await는 프로미스의 값이 사용 가능해질 때까지 블록했다가 그 값을 반환하고, notify는 프로미스의 값을 설정한다. 관례대로 이 연산들도 효과로 표현한다:

ocaml
type _ eff +=
  | Await : 'a promise -> 'a eff
  | Notify : 'a promise * 'a -> unit eff

let await (p: 'a promise) : 'a = perform (Await p)
let notify (p: 'a promise) (v: 'a) : unit = perform (Notify(p, v))

프로미스의 한 가지 사용처는 새 스레드에서 값을 비동기적으로 계산하는 것이다. 계산 결과는 프로미스를 통해 제공된다.

ocaml
let async (f: unit -> 'a) : 'a promise =
  let p = new_promise() in
  spawn (fun () -> f () |> notify p);
  p

관례대로 두 연산을 구현하기 위해 run 처리기에 경우를 추가한다:

ocaml
let rec run (f: unit -> unit) =
  match f () with
  ...
  | effect Notify(p, v), k ->
      p.value <- Some v;
      List.iter (fun p -> suspend (fun () -> continue p v)) p.waiters;
      p.waiters <- [];
      suspend (continue k); restart ()
  | effect Await p, k ->
      match p.value with
      | Some v -> continue k v
      | None -> p.waiters <- k :: p.waiters; restart()

Await 효과는 값이 이미 정해져 있으면 그 값을 반환하고, 아니면 해당 프로미스를 기다리는 리스트에 호출 스레드를 추가하고 다른 스레드를 재시작한다. Notify 효과는 프로미스의 값을 설정하고, 그 값을 가지고 기다리는 모든 스레드를 재시작한다.

겹치는 I/O.효과 처리기로 구현한 협력 스레드의 설득력 있는 사용처는 입출력 연산의 겹침(overlapping)이다. 스레드들은 I/O 연산을 시작해 두고, 연산이 완료될 때까지 중단(suspend)될 수 있다. 이렇게 하면 한 번에 하나의 스레드만 실행되지만, 많은 I/O 연산이 동시에 진행된다. 이 접근의 교과서적 구현은 Dolan et al. (2017)에 설명되어 있다. Eio OCaml 라이브러리(https://github.com/ocaml-multicore/eio)는 이 접근의 산업 수준 구현을 제공한다.

10.5 효과 처리기의 의미론

이제 효과 처리기의 작동(운영) 의미론을 제시한다. 다음과 같은 FUN 언어의 확장을 고려하자:

Expressions: e ::= c ∣ x ∣ λ x . e ∣ e1 e2
            ∣ perform e          perform the effect e
            ∣ handle e with e_ret, e_eff   handle effects in e

식 perform e는 현재 평가를 중단하고, 가장 안쪽의 handle로 분기한다.

식 handle e with e_ret, e_eff는 본문 e를 평가한다. e가 효과를 수행하지 않고 값 v로 평가되면, e_ret 가지가 v에 적용된다. e가 효과 f를 수행하면, 다른 가지 e_eff가 (f, k)에 적용되는데, 여기서 f는 효과의 값이고 k는 handle에 의해 경계가 정해진 perform의 연속체다.

효과 처리기의 축약 의미론은 델리미트된 연속체(절8.6)와 예외(절9.2)의 의미론과 가깝다. 전체 축약 문맥 C에 더해, 연속체를 구분하는 데 도움을 주는 처리기 없는 문맥 D를 사용한다:

Reduction contexts: C ::= [ ] ∣ C e ∣ v C ∣ perform C ∣ handle C with e_ret, e_eff
Handler-free contexts: D ::= [ ] ∣ D e ∣ v D ∣ perform D

그 다음 handle에 대해 다음 두 가지 머리-축약 규칙을 갖는다:

handle v with e_ret, e_eff
  →ε e_ret v

handle D[perform v] with e_ret, e_eff
  →ε e_eff (v, λx. D[x])

부분 문맥 D가 효과 처리기 e_eff에 효과 값 v와 함께 전달되는 델리미트된 연속체 λx. D[x]가 되는 점에 주목하라.

위 두 번째 규칙은 “얕은” 종류의 효과 처리, 즉 효과를 처리한 뒤 처리기가 사라지는 경우를 묘사한다. “깊은” 종류의 효과 처리는 연속체 D 주위에 처리기를 재설치함으로써 얻어진다:

handle D[perform v] with e_ret, e_eff
  →ε e_eff (v, λx. handle D[x] with e_ret, e_eff)

얕은 처리기에 대한 축약 규칙을 예외 처리기(절8.6)와 델리미트된 연속체의 제어 연산자(control0 종류, 절9.2)의 규칙과 비교해 보자:

handle D[perform v] with e1, e2
  →ε e2 (v, λx. D[x])

try D[raise v] with x -> e2
  →ε e2 [x := v]

delim(D[capture (λk. e)])
  →ε (λk. e) (λx. D[x])

예외 처리기는 문맥 D를 연속체로 포착하지 않는 효과 처리기임을 볼 수 있다. 델리미트된 연속체의 제어 연산자는 효과 처리기와 같은 연속체를 포착한다. 그러나 이 연속체를 받는 식은 프로그램에서 서로 다른 장소로부터 온다. 효과 처리기는 처리기에서 연속체를 받고, 델리미트된 연속체는 capture에서 연속체를 받는다. 형식적 의미론에서의 이 작은 차이가 프로그래밍 스타일과 편의성에서 큰 차이를 낳는다. 종종 효과를 수행하는 장소보다는 효과를 처리하는 장소에서 무엇을 할지 결정하는 편이 더 자연스럽고 유연하다.

10.6 효과 처리기를 위한 CPS 변환

Hillerström et al. (2020)은 절8.8에 기술된 델리미트된 제어 연산자의 CPS 변환을 확장하여, 효과 처리기의 CPS 변환을 정의한다. 델리미트된 제어의 경우, n개의 구분자 안에 중첩된 식 e의 변환 𝒞(e)는 인자로 n+1개의 델리미트된 연속체 k0, …, kn을 받는다. 효과 처리기를 지원하기 위해, Hillerström et al. (2020)은 절9.3의 이중 배럴드(double-barreled) CPS와 이 접근을 결합한다. 각 델리미트된 연속체 ki를 정상 반환 값을 위한 연속체 ki와 수행된 효과를 위한 연속체 hi로 분할한다. 따라서 n개의 효과 처리기 안에 중첩된 식 e의 CPS 변환 𝒞(e)는 총 2n+2개의 연속체에 적용되어야 한다:

𝒞(e) k0 h0 k1 h1 … kn hn

여기서 ki는 정상 연속체이고 hi는 효과 처리 연속체이다.

핵심 FUN 언어에 대해서는, CPS 변환은 절6.5의 익숙한 호출-순서(call-by-value) 변환이다:

𝒞(c)              = λk. k c
𝒞(x)              = λk. k x
𝒞(λx. e)          = λk. k (λx. 𝒞(e))
𝒞(e1 e2)          = λk. 𝒞(e1) (λv1. 𝒞(e2) (λv2. v1 v2 k))
𝒞(if e1 then e2 else e3)
                  = λk. 𝒞(e1) (λv1. if v1 then 𝒞(e2) k else 𝒞(e3) k)

변환된 항들은 첫 번째 값 연속체(위에서 k0로 표기)만 다룬다는 점에 유의하라. 𝒞(e)가 2n+2개의 연속체에 완전히 적용되면, 나머지 2n+1개의 연속체는 FUN 핵심 구성 요소의 변환에 의해 영향을 받지 않는다. 예를 들어, 상수 c의 완전 적용된 변환은 다음과 같다:

𝒞(c) k0 h0 k1 h1 … kn hn
  = (λk. k c) k0 h0 k1 h1 … kn hn
  → k0 c h0 k1 h1 … kn hn

식의 값 c에 첫 번째 정상 연속체 k0가, 그리고 나머지 연속체 스택이 적용됨을 볼 수 있다.

효과 수행에 대한 CPS 변환은 다음과 같다:

𝒞(perform e) = 𝒞(e) (λf. λk. λh. h (f, λx. k x h))

변환된 코드는 먼저 e를 효과의 값 f로 평가한다. 그런 다음 연속체 스택에서 첫 번째 값 연속체 k와 첫 번째 효과 연속체 h를 팝(pop)하여, h에 쌍 (f, λx. k x h)를 적용한다. 여기서 λx. k x h는 부분 연속체 k를 함수로 감싼 것으로, 효과 처리기가 사용할 준비가 되어 있다. 이 함수가 적용되면, k는 자신의 첫 번째 연속체로 h를 받는다. 이는 깊은 효과 처리를 구현한다. 즉 현재의 효과 처리기 h가 연속체가 재시작될 때에도 그대로 남는다.

예를 들어, f가 상수인 perform f를 생각해 보자:

𝒞(perform f) k0 h0 k1 h1 … kn hn
  = (λk. k f) (λf. λk. λh. h (f, λx. k x h)) k0 h0 k1 h1 … kn hn
  →* h0 (f, λx. k0 x h0) k1 h1 … kn hn

나중에 연속체 함수 λx. k0 x h0는 값 v에 대해, 다른 연속체 스택 k′0 h′0 … k′m h′m에서 재시작될 수 있다:

(λx. k0 x h0) v k′0 h′0 … k′m h′m
  →* k0 v h0 k′0 h′0 … k′m h′m

연속체 k0는 perform f가 v를 반환한 것처럼, 원래의 효과 처리기 h0(깊은 처리 때문에)와 새로운 연속체 스택을 이어 받은 상태로 호출된다.

마지막으로, 효과 처리기에 대한 CPS 변환은 다음과 같다:

𝒞(handle e with e_ret, e_eff)
  = 𝒞(e) (λv. λh. 𝒞(e_ret) v) 𝒞(e_eff)

효과 처리기는 𝒞(e)를 평가하기 전에 두 개의 연속체를 연속체 스택에 추가한다. 값 연속체 λv. λh. 𝒞(e_ret) v는 (새 처리기 연속체) h를 스택에서 팝하고 e_ret를 평가한다. 효과 연속체는 처리기 식 e_eff의 변환 그 자체이다.

e가 효과를 수행하지 않고 상수 c로 축약되는 경우의 평가를 보자:

𝒞(handle e with e_ret, e_eff) k0 h0 … kn hn
  = 𝒞(e) (λv. λh. 𝒞(e_ret) v) 𝒞(e_eff) k0 h0 … kn hn
  →* (λv. λh. 𝒞(e_ret) v) c 𝒞(e_eff) k0 h0 … kn hn
  →* 𝒞(e_ret) c k0 h0 … kn hn

e가 효과를 수행하는 경우, perform는 효과 연속체, 즉 𝒞(e_eff)를 효과 값과 연속체 값의 쌍 (vf, kf)에 적용한다. 그 결과로 다음을 평가한다:

𝒞(e_eff) (vf, kf) k0 h0 … kn hn

이는 e_eff를 (vf, kf)에 적용하는 것과 같다.

10.7 추가로 읽을거리

Pretnar (2015)의 튜토리얼은 효과 처리기로 프로그래밍하는 좋은 입문서다. Dolan et al. (2017)과 Hillerström (2021, chapter 2)은 절10.4의 멀티스레딩 예를 확장하여, 스케줄러와 운영체제 서비스를 효과 처리기로 작성하는 것을 보여 준다.

효과 처리기는 현재 주류 언어 중에서는 OCaml(https://ocaml.org)이 지원하며, 실험적 언어인 Eff(https://www.eff-lang.org/), Effekt(https://effekt-lang.org/), Koka(https://koka-lang.github.io)가 지원한다. 또한 하스켈, 자바스크립트 등 다른 언어에서도 라이브러리 형태로 일부 효과 처리를 제공한다. Sivaramakrishnan et al. (2021)은 OCaml에서의 효과 처리기의 설계와 구현을 설명한다. Koka의 설계와 구현은 Leijen (2014), Leijen (2017), Xie and Leijen (2021)에서 다루고 있다.

---