URL: https://blog.janestreet.com/fun-with-algebraic-effects-hardcaml/

대수적 효과로 즐기기 - 장난감 예제에서 Hardcaml 시뮬레이션까지

최근 저는 Jane Street에서 Hardcaml 시뮬레이션에 사용하는 라이브러리 중 하나인 Hardcaml_step_testbench 라이브러리를, 모나드를 사용하던 방식에서 OCaml 5의 새로운 기능인 대수적 효과(algebraic effects)를 사용하도록 포팅했습니다. 이 글에서는 대수적 효과가 무엇인지, 왜 모나드 대신 대수적 효과를 고려해야 하는지, 그리고 Handled_effect 라이브러리를 사용해서 실제로 어떻게 다루는지 살펴봅니다. 제가 믿게 된 한 가지는, 모나드로 할 수 있는 대부분의 일은 대수적 효과로 더 우아하게 할 수 있다는 점입니다.

대수적 효과는 원래 스레드 수준의 병렬성을 지원하는 OCaml 5에서, 범용 동시 실행을 위해 OCaml에 추가되었습니다. 그것을 Hardcaml 시뮬레이션에 재활용할 수 있다는 사실은, 이 언어 기능이 얼마나 잘 설계되었고 범용적인지 보여 줍니다.

저는 타입 이론 전문가가 아닌 사람의 관점에서 이 글을 씁니다. 기저 메커니즘을 완전히 이해하지 않고도 대수적 효과를 사용할 수 있다는 점이, 설계의 장점 중 하나입니다.

(라이브러리는 아직 GitHub에서 Oxcaml_effect라는 이름을 쓰고 있습니다. 현재 Handled_effect로 이름을 바꾸는 중입니다.)

모나드의 문제는 무엇일까?

모나드는 OCaml 프로그래머들이 오랫동안 계산을 모델링하는 데 사용해 왔습니다. Jane Street의 모나딕 Async 라이브러리는 동시성 프로그래밍에 사용되며, 우리 인프라의 많은 부분을 구동합니다. 그렇다면 왜 이를 대체하고 싶을까요?

이유 1: 모나드는 코드를 오염시키고 읽기 어렵게 만든다

모나드는 다음과 같은 타입 시그니처를 갖는다는 것을 떠올려 봅시다:

ocaml
(* This is part of the [Monad.S] module type *)
type 'a t

val return : 'a -> 'a t
val bind : 'a t -> f:('a -> 'b t) -> 'b t
val map : 'a t -> f:('a -> 'b) -> 'b t

숫자를 누적하는 데 도움을 주는 서버와 상호작용한다고 가정해 봅시다. Async의 Deferred.t 모나드를 예로 들면, 인터페이스는 대략 이렇게 생길 수 있습니다:

ocaml
type txn

val start_transaction : unit -> txn Deferred.t

val send_number : txn -> int -> unit Deferred.t

val wait_for_completion : txn -> int Deferred.t

이를 이용하는 코드는 다음처럼 작성할 수 있습니다:

ocaml
let send_numbers_to_server n =
  let%bind txn = start_transaction () in
  let%bind () =
    Deferred.for_ 0 ~to_:(n - 1) ~do_:(fun i ->
      let%bind () = send_number txn i in
      printf "Sent number %d\n" i;
      return ())
  in
  let%bind result = wait_for_completion txn in
  printf "Transaction done: %d!" result;
  return ()
;;

익숙하지 않은 분들을 위해 덧붙이자면, let%bind x = foo () in bar ()는 bind (foo ()) ~f:(fun x -> bar ())로 변환되는 문법 설탕입니다.

Async 모나드는 이 코드 전반에 퍼져 있습니다. 비동기 연산을 수행하는 부분마다 let%bind () =가 둘러싸고 있고, Deferred.t 타입에서 끝나도록 여기저기 시끄러운 return ()이 필요합니다. 또한 Deferred.List.iter(여기서는 Deferred.for_) 같은, 표준 라이브러리 함수의 “모나드 버전”을 써야 합니다. 왜냐하면 반드시 Deferred.t를 반환해야 하기 때문입니다. 한 번 모나드를 쓰기 시작하면 사실상 그 안에 갇히게 됩니다. 그 사용과 상호작용하는 모든 코드도 모나드를 고려해야 합니다. 번거롭습니다.

만약 OxCaml 대수적 효과로 만들어진 가상의 Async 라이브러리가 있다면, 코드는 대략 이런 모습이 될 수 있습니다:

ocaml
let send_numbers_to_server (h : Deferred.Handler.t) n =
  let txn = start_transaction h in
  for 0 to n - 1 do
    send_request h txn i;
    printf "Sent number %d\n" i;
  done;
  let result = wait_for_completion h txn in
  printf "Transaction done: %d!" result;
;;

특별한 let% ppx도 없고, return도 없고, 모나드 맛이 나는 표준 라이브러리 함수도 필요 없으며, 전체 함수는 호출자가 특별히 취급할 필요가 없는 일반 값(normal value)을 반환합니다.

이유 2: 언박스드 타입과 로컬 모드를 사용할 수 없다

모나드는 OxCaml의 유용한 기능들, 특히 언박스드 타입(unboxed types)과 로컬 모드(local mode)를 쓰기 어렵게 만듭니다.

다음 코드를 보세요:

ocaml
open Core 
open Unboxed

(* Assume [Bar] is some module that implements Monad.S and some utility functions *)
module Bar : sig
  include Monad.S
  
  val do_stuff : unit -> unit t
end

type foo =
  { a : int
  ; b : int
  }

let do_thing () =
  let foo @ local = { a = 1; b = 2 } in
  let%map x = Bar.do_stuff () in
  F64.of_int (foo.a + foo.b)
;;

위 코드는 컴파일되지 않습니다! 이유를 이해하려면, PPX 전처리를 거친 후 코드가 어떻게 생기는지 보겠습니다:

ocaml
let do_thing () =
  let foo @ local = { a = 1; b = 2 } in
  Bar.map (Bar.do_stuff ()) ~f:(fun () ->
    F64.of_int (foo.a + foo.b)
  )
;;

OxCaml은 타입에는 레이아웃(layout)을, 값에는 모드(mode)를 도입합니다. 레이아웃은 타입의 메모리 표현과 관련된 여러 종류가 있는데, 여기서는 범위를 벗어납니다. 이 예에서는 OCaml 기본 메모리 표현과 하위 호환되는 레이아웃, 즉 value 레이아웃을 사용합니다. 반면 모드는 값의 성질을 추적합니다. 여기서 모드는 값이 호출자의 스택에 할당되었는지(호출자의 영역에서만 생존) 아니면 전역 힙에 할당되었는지(가비지 컬렉터가 관리)를 추적합니다.

레이아웃과 모드 주석을 추가하면, Bar.map은 다음과 같은 시그니처를 갖습니다:

ocaml
val map
  : ('a : value) ('b : value) .
    'a t @@ global -> f:('a -> 'b) @@ global -> 'b @@ global

여기에는 두 가지 문제가 있습니다:

• foo 레코드는 로컬로 할당됩니다. 즉, f는 클로저 환경에서 이를 캡처할 수 없습니다. f는 전역으로 할당되어야 하기 때문입니다.
• 클로저 f의 반환값은 value 레이아웃을 갖습니다. 그런데 F64.of_int의 반환 타입인 F64.t는 불행히도 value 레이아웃과 호환되지 않는 float# 타입입니다.

Jane Street의 Tools & Compilers 그룹은 ppx_let에서 f가 로컬로 할당된 클로저가 되도록 허용하는 방식으로 어느 정도 우회하려는 작업을 하고 있습니다. 많은 경우에는 충분히 좋은 해결책이지만, 로컬 할당 클로저를 둘 수 없는 경우에는 그렇지 않습니다. 예를 들어 Async는 클로저가 전역으로 할당되어야 합니다. 클로저 자체가 Async 스케줄러에 스케줄링할 작업(task)으로 전달되기 때문입니다. 또한 위 두 문제 중 첫 번째만 실제로 해결합니다.

효과는 이 문제에 대한 멋진 해결책입니다. 효과는 전역으로 할당된 클로저가 필요해지는 상황을 피합니다. 특정 컨텍스트의 “환경(environment)” 관리 책임을 언어 런타임으로 옮기기 때문입니다. 덕분에 다양한 새로운 OxCaml 기능을 편리하게 사용할 수 있습니다.

효과에는 더 나은 스택 트레이스나 더 자연스러운 조합성(composability) 같은 다른 장점도 있습니다. (모나드 두 개를 합성해 본 적이 있다면 얼마나 고통스러운지 알 것입니다.)

비전문가를 위한 대수적 효과 입문

효과는 언어에 내장된 프리미티브로 생각할 수 있습니다. 어떤 계산의 제어 흐름에서 실행을 일시 중단하고 스케줄러/런타임에 제어를 넘기게 해 줍니다. 효과를 “수행(perform)”하면(자세한 내용은 뒤에서), 실행이 멈추고 핸들러가 연속(continuation) k를 받습니다. 이는 “perform 이후에 일어나려던 모든 것”을 나타내는 1급 값입니다. 그 다음부터는 let%bind 이후처럼 값을 가지고 계속 진행할 수도 있고, 예외를 던질 수도 있고, 연속을 저장해 두었다가 나중에 재개할 수도 있습니다.

먼저 간단한 예제를 살펴본 뒤, Hardcaml 시뮬레이션을 위한 더 복잡한 예제를 보겠습니다.

만약 OCaml 매뉴얼의 OCaml 효과를 어렴풋이 알고 있다면, 여기의 모습이 꽤 다르다는 것을 눈치챌 것입니다. 타입 안전한 OxCaml 효과 API는 기본 OCaml 효과 API와 다릅니다.

Handled_effect가 제공하는 API를 이해하기 위해 간단한 예제로 시작해 봅시다.

값을 증가시키거나 감소시키는 사소한 계산을 수행하는 라이브러리를 만들고 싶다고 합시다. 최종적으로 이런 코드를 쓰고 싶습니다:

ocaml
let computation (handler : E.Handler.t @ local) =
  let x = 1 in
  let y = E.perform handler (Plus_one x) in (* suspends here *)
  let z = E.perform handler (Minus_one y) in (* suspends here *)
  print_s [%message (x : int) (y : int) (z : int)]
;;

let%expect_test "" =
  run_computation computation;
  [%expect {| ((x 1) (y 2) (z 1)) |}]
;;

이것이 핵심 “비즈니스 로직”입니다. Plus_one이나 Minus_one이 어떻게 구현되었는지는 모릅니다. 단지 계산의 흐름을 구성할 뿐입니다. 모나딕 Async 관점에서 보면, 위 코드는 사용자가 let%bind로 점철된 코드를 작성하는 것과 비슷합니다. 실제 계산 수행(아래에서 다룸)은 Async 스케줄러가 사용자 코드를 뒤에서 해석하는 것과 유사합니다.

E.Handler.t 값(“효과 핸들러”)은, 효과 E에 대한 구현에 접근하기 위해 전달하는 객체로 볼 수 있습니다. (핸들러 인자에 @ local을 붙인 점에 주목하세요. 지금은 타입 안전성을 위해 로컬 주석이 필요하다는 것만 믿어 주세요. 글 마지막에서 그 이유를 설명합니다.)

다른 부분도 분해해 봅시다. 먼저 가능한 효과 연산(operation)들을 정의합니다. 이는 실행을 일시 중단할 수 있는 가능한 연산들을 지정하는 GADT입니다. 예를 들면 이렇게 생깁니다:

ocaml
open Core

module Effect_ops = struct
  (* One of the type arguments must specify the return 
     type of performing the effect; here, an int *)
  type 'a t =
    | Plus_one     : int -> int t
      (** An operation that when given [x], return [x + 1] *)
    | Subtract_one : int -> int t
      (** An operation that when given [x], return [x - 1] *)
end

(* We invoke the Handled_effect `Make` functor on our 
   module to Effect-ify it. *)
module E = Handled_effect.Make (Effect_ops)

모듈 E는 효과를 다룰 때 사용자가 주로 상호작용하는 모듈입니다. 많은 함수와 타입이 있으며, 예제에서 살펴볼 것입니다. 아래는 우리가 구성한 E 모듈의 매우 단순화한 인터페이스입니다:

ocaml
module E : sig
  module Handler : sig
    type t
  end
 
  (** Performs an operation in the context of running a computation. *)
  val perform : Handler.t @ local -> 'a Effect_ops.t -> 'a @ once unique
 
  (** Evaluates a computation *)
  val run : (Handler.t @ local -> 'a) -> 'a Result.t
  
  module Result : sig
    type ('a, 'e, 'es) t =
      | Value : 'a -> ('a, 'e, 'es) t
        (** This is returned when the computation is finished. *)
      | Exception : exn -> ('a, 'e, 'es) t
        (** The computation raises an unhandled exception. We'll 
            ignore exceptions for the purposes of this blog post. *)
      | Operation :
          ('o, 'e) op  * ('o, 'a, 'e, 'es) continuation
          -> ('a, 'e, 'es) t
        (** This is returned when the computation calls 
            [E.perform operation]. The first argument is the operation 
            in question, and the second argument is a continuation object 
            that can be used to resume execution of the computation with 
            the result.
        *)
  end
end

따라서 효과를 사용할 때는 사실 두 가지를 생각하게 됩니다:

• 계산(computation) — 비즈니스 로직입니다. 계산의 타입 시그니처는 E.Handler.t @ local -> 'a이며, 'a는 전체 계산의 반환값입니다.
• 연산 핸들러(operation handlers) — 연산이 무엇을 의미하는지 해석하는 코드입니다.

계산이 E.perform을 호출하면 실행은 연산 핸들러로 점프합니다. 연산 핸들러에서 Handled_effect.continue k를 호출해 연속(continuation)을 이용하여 계산 실행을 재개합니다.

계산 작성 자체는 보통 어렵지 않으며, 효과 없이 일반 코드를 쓰는 것과 크게 다르지 않습니다. 대부분의 복잡성은 연산 핸들러를 작성하는 데 있습니다. 이 예제에서는 다음과 같습니다:

ocaml
let rec handle_computation_result (result : (_, _) E.Result.t) =
  match result with
  | Value result ->
    (* The computation has reached the end and returned the result *)
    result
  | Operation (op, k) ->
    (* If we're here, the effect has suspended. The [op] type is the set of
       operations the computation can perform as expressed by our [Effect_ops]
       type. [k] is a continuation that the user can use to resume the
       computation execution with [Handled_effect.continue]
    *)
    (match op with
     | Plus_one x ->
       handle_computation_result (Handled_effect.continue k (x + 1) [])
     | Subtract_one x ->
       handle_computation_result (Handled_effect.continue k (x - 1) []))
  | Exception exn ->
    (* In real examples, we would do smarter things with exceptions, but to keep
       these examples easy to follow, we simply reraise them.
     *)
    raise exn
;;

let run_computation (type a) (computation : E.Handler.t @ local -> a) : a =
  handle_computation_result (E.run computation)
;;

Hardcaml_step_testbench 라이브러리는 Hardcaml에서 FPGA 시뮬레이션을 위해 사용하는 라이브러리입니다. 우리는 수년간 이 라이브러리로 FPGA 회로를 시뮬레이션해 왔습니다. 최근 이 라이브러리에 효과 기반 API 지원을 추가했습니다. 이는 효과가 완전히 의도된 도메인이 아닌 곳에서도 무엇을 얻을 수 있는지 보여 주는 좋은 시연입니다.

이 글에서는 이 라이브러리의 핵심 동작을 흉내 내는 예제 코드를 통해 효과적 API를 보여 주겠습니다. 실제 라이브러리는 훨씬 더 많은 기능을 갖고 있지만, 장난감 구현으로도 핵심 아이디어는 설명할 수 있습니다.

디지털 회로는 추상적으로, 매 타임스텝마다 입력을 소비하고 출력을 원자적으로 생성하는 상태ful 컴포넌트로 볼 수 있습니다. 하드웨어 설계자는 이 타임스텝을 클럭 사이클(clock cycle)이라고 부르는데, 물리적으로는 회로에 공급되는 클럭 신호에 대응합니다. 소프트웨어 프로그램과 중요한 차이는, 회로가 더 높은 수준의 애플리케이션 기능을 수행하고 있든 아니든 입력과 출력은 매 클럭 사이클마다 소비된다는 점입니다.

(디지털 설계 엔지니어 분들을 위해 덧붙이면, 여기서는 동기식 단일 클럭 도메인(synchronous single clock-domain) 회로 시뮬레이션으로 제한합니다. 여러 클럭 도메인을 다루는 트릭도 있지만, 여기서 논의하는 핵심에는 중요하지 않습니다.)

이런 디지털 회로를 FPGA에 컴파일하는 데는 보통 몇 시간(ASIC는 몇 달에 더 가깝기도) 정도 걸릴 수 있습니다. 우리는 테스트벤치와 하드웨어 변경에 대해 더 빠른 피드백을 얻고 싶기 때문에, 이런 회로에 대한 시뮬레이션을 작성합니다.

디지털 회로 시뮬레이션을 실행할 때는, 서로 상호작용하는 두 컴포넌트를 동기화하려고 합니다:

• 회로 자체
• 회로와 동기화하고 상호작용하는 테스트벤치 스레드들

테스트벤치와 시뮬레이션된 회로의 실행 흐름은 대략 다음과 같습니다:

실제로는 테스트벤치에서 여러 실행 스레드를 두는 경우가 많습니다. 디지털 회로는 때때로 복잡하고(대부분) 서로 분리된 부분을 갖기도 하며, 각 테스트벤치 스레드가 이를 개별적으로 상호작용하고 싶어하기 때문입니다.

이 글에서는 몇 가지 단순화를 하겠습니다:

• 사용자가 계산을 실행할 때, 모든 동시 작업(concurrent tasks)은 그 시점에 이미 알려져 있어야 한다.
• 모든 계산은 반환값이 없어야 한다(즉 unit을 반환).

그렇다면 효과 이전(pre-effects) 세계에서 무엇이 까다로울까요? cycle ()이 동기화 지점을 의미한다고 할 때, 다음 두 계산을 인터리브(interleave)하고 싶다고 상상해 봅시다:

ocaml
[ (fun () ->
     for i = 0 to 2 do
       cycle ();   (* Synchronization point *)
       printf "foo %d\n" i;
     done)
; (fun () ->
     for i = 0 to 2 do
       cycle ();   (* Synchronization point *)
       printf "bar %d\n" i;
     done);
]

효과 이전 세계에서는 이를 할 수 있는 유일한 방법이 클로저를 사용하는 것입니다. cycle 호출 이후의 실행 부분을 표현하는 실용적인 방법이 없기 때문에 클로저가 필요합니다.

이를 가장 인체공학적으로(ergonomic) 만드는 방법이 바로 모나드입니다. 다음처럼 생긴 계산 모나드를 상상할 수 있습니다:

ocaml
type 'a t =
   | Return : 'a -> 'a t
   | Bind   : ('a t * ('a -> 'b t)) -> 'b t
   | Cycle  : unit t
   
val cycle : unit -> unit t

val run_computations : (unit -> unit t) list -> unit

run_computations의 구현은 상당히 복잡해서 여기에는 포함하지 않겠습니다. (너무 복잡하다는 점 자체가 효과를 쓰게 하는 동기 중 하나입니다.) 대략적인 직관은 다음과 같습니다:

• 계산의 머리(head)에서 시작해 Bind(Cycle, f) 지점까지 평가합니다. 그 뒤 f 클로저를 따로 저장해 둡니다. 평가가 Return ()에 도달하면, 그 계산은 완료로 표시합니다(이 경우 저장할 클로저가 없습니다).
• 다음 계산으로 이동해서 같은 일을 합니다. 리스트 끝까지 반복합니다.
• 모든 계산이 끝날 때까지 이 과정을 반복합니다.

이를 종합하면, 테스트벤치 러너의 모나드 버전은 다음처럼 보일 수 있습니다:

ocaml
run_computations 
  [ (fun () ->
      for_ 0 ~to_:2 ~do_:(fun i ->
        let%bind () = Step.step () in
        printf "foo %d\n" i;
        Step.return ()))
  ; (fun () ->
      for_ 0 ~to_:2 ~do_:(fun i ->
        let%bind () = Step.step () in
        printf "bar %d\n" i;
        Step.return ()))
  ]
  [%expect
    {|
    foo 0
    bar 0
    foo 1
    bar 1
    foo 2
    bar 2
    |}]

물론 이는 앞서 이야기한 모나드의 문제를 모두 갖고 있습니다. 하지만 효과 이전 세계에서는 동기화 지점(synchronization point)이라는 개념을 지원할 다른 방법이 없습니다.

OxCaml 효과를 사용하면, “앞으로 남은 계산”을 1급으로 표현할 수 있습니다. 다음과 같은 API를 만들 수 있습니다:

ocaml
module Handler : sig
  type t
end

val run_computations : (Handler.t @ local -> unit) list -> unit

val step : Handler.t @ local -> unit

위 코드는 훨씬 깔끔하게 작성할 수 있습니다:

ocaml
let%expect_test "" =
  run_computations
    [ (fun h ->
        for i = 0 to 2 do
          step h;
          printf "foo %d\n" i
        done)
    ; (fun h ->
        for i = 0 to 2 do
          step h;
          printf "bar %d\n" i
        done)
    ];
  [%expect
    {|
    foo 0
    bar 0
    foo 1
    bar 1
    foo 2
    bar 2
    |}]
;;

이 API에서 흥미로운 점은 이것입니다. 계산이 step을 호출할 때마다, 해당 계산은 동기화 지점으로서 제어를 “스텝 런타임(step runtime)”에 양도합니다. 그리고 모든 스레드가 각각의 동기화 지점에 도달할 때까지 기다립니다. 이는 각 테스트벤치 계산이 서로의 작업을 명시적으로 조율하지 않고도, _같은 상태의 회로_와 독립적으로 상호작용할 수 있게 해 주는 매우 강력한 기능입니다. 동기화 지점에서, 기저의 회로 시뮬레이터는 계산들을 재개하기 전에 회로를 한 스텝 전진시킵니다. Handled_effect 라이브러리를 사용하는 고수준 프로그래머 관점에서는 내부가 어떻게 동작하는지 알 필요가 없습니다.

그렇다면 위 코드를 실제로 효과로 구현하려면 어떻게 해야 할까요?

앞과 마찬가지로 먼저 효과 연산을 정의합니다. 여기서는 런타임에 제어를 양도하는 연산이 필요하므로 Step 연산을 수행합니다. 또한 사용자가 호출할 step 함수를 정의합니다.

ocaml
module Effect_ops = struct
  type 'a t = Step : unit t
end

module E = Effect.Make (Effect_ops)
module Handler = E.Handler

(* val step : Handler.t @ local -> unit *)
let step (h : Handler.t @ local) = E.perform h Step

그 다음, 계산 실행 상태를 추적하는 어떤 상태 추적기를 정의합니다. 이를 Thread_state.t 타입으로 캡슐화합니다. 여기서 트릭은, 계산이 효과를 수행할 때 연속을 즉시 호출할 필요가 없다는 점입니다. 여러 동시 계산이 진행 중일 수 있고, 여러 연속이 존재할 수 있습니다.

ocaml
module Thread_state = struct
  type t =
    | Unstarted of (Handler.t @ local -> unit)
    | Running of (unit, unit, unit) E.Continuation.t Unique.Once.t
      (** When the computation state is [Running], it means the computation called
          [step] and has suspended its execution. It will synchronize with all other
          computations at their respective calls to [step] before advancing.

          The continuation object has the unique mode, which means the compiler verifies
          that it can only be used exactly once. [Unique.Once.t] is used here
          to cross the continuation into the aliased mode (it can be used multiple
          times, which is the default in OCaml) to defer this check into runtime
          rather than compile time. The exact details of how it works are not too
          important for the purposes of this blog post.
        *)
    | Finished

  let handle_result (result : (unit, unit) E.Result.t @ once unique) =
    match result with
    | Value () ->
      Finished
    | Exception e ->
      Exn.reraise e "Step raised exn"
    | Operation (op, k) ->
      (match op with
       | Step -> Running (Unique.Once.make k))
  ;;

  (* Advance the computation until it calls [step] *)
  let run_until_step t =
    match t with
    | Unstarted computation ->
      handle_result (E.run computation)
    | Running k_uniq ->
      handle_result (Handled_effect.continue (Unique.Once.get_exn k_uniq) () [])
    | Finished -> Finished
  ;;
end

이 모든 조각을 합치면 run_computations 함수를 구현할 수 있습니다.

ocaml
let run_computations (computations : (E.Handler.t @ local -> unit) list) =
  let states =
    Array.map (Array.of_list computations) ~f:(fun computation ->
      Thread_state.Unstarted computation)
  in
  while
    Array.exists states ~f:(function
      | Finished -> false
      | Unstarted | Running _ -> true)
  do
    Array.map_inplace states ~f:Thread_state.run_until_step
    (* In practice, we will advance time on the underlying circuit being simulated. *)
  done
;;

이는 실제 동작의 단순화 버전이지만, 크게 다르지 않습니다! 여기에서 빠진 유일한 프리미티브는 spawn인데, 이는 계산이 추가 계산을 생성(spawn)할 수 있게 해 줍니다. 이것 또한 대수적 효과로 구현할 수 있습니다.

OxCaml의 타입 안전성 보장, 또는 왜 핸들러는 로컬 모드를 갖는가?

Locality and Effect Reflection 논문은 타입 안전한 효과를 위해 왜 시스템이 로컬 모드를 사용하는지에 대한 형식적 논증을 제시합니다. 여기서는 짧고 직관적인 설명을 시도해 보겠습니다.

효과 E를 사용하는 계산을 E.Handler.t @ local -> 'a로 정의한다고 했습니다. 이런 계산에 E.run을 호출하면, E.perform 호출을 가로채 연산 핸들러로 제어를 넘길 수 있는 환경에서 함수를 평가합니다. 즉, E에 대한 효과 핸들러를 등록한 컨텍스트 밖에서 임의로 E.perform을 호출할 수는 없습니다.

만약 핸들러에 local 주석이 없는 E.Handler.t -> 'a 타입의 계산을 실행할 수 있다면, 다음과 같이 잘못 정의된 로직을 표현할 수 있습니다:

ocaml
let global_handler = E.run (fun h -> h) in
E.perform global_handler operation

E.run 내부에서는 적절한 효과 연산 핸들러가 있는 컨텍스트에 있습니다. 그런데 E.perform global_handler operation을 호출하면 무슨 일이 일어날까요? 그 시점에는 더 이상 E가 핸들되지 않습니다!

@ local이 이를 막아 줍니다. 위 코드는 모드 오류(mode error)로 인해 컴파일 에러가 납니다.

ocaml
(* File "fail_compilation_example.ml", line 82, characters 39-40: This value is local but is
   expected to be global.
                                     |
                                     |
                                     | *)
let global_handler = E.run (fun h -> h) in
E.perform global_handler operation

마무리

이 글이 많은 경우에 효과가 모나드보다 낫다는 점을 설득하는 데 도움이 되었고, Handled_effect 라이브러리를 한번 살펴볼 가치가 있다는 생각을 갖게 했으면 합니다.

Fu Yong은 Imperial College에서 전기전자공학(EE) 석사(MEng)를 마친 뒤 2019년에 Jane Street의 FPGA 그룹에 합류했습니다.