内部実装 | Lambda Prelude

Lambda Prelude が内部でどう動いているかをまとめたページ — AOT lowering、OCaml 5 effects ベースのスケジューラ、メソッドディスパッチ、型システム。本ページに載せる OCaml コード片はあくまで生成形の概形であって、生成器が出すバイト単位のものではない。実物が見たければ lambda-prelude build script.lp --emit (またはファイルに書き出すなら --out script.ml) を使う。

AOT lowering の歩き方

lambda-prelude build は Lambda Prelude のソースを OCaml ソースに変換し、その OCaml を ocamlopt に渡す。変換規則は単純で予測可能 — そのおかげで、生成された OCaml は読み手にとって読める形のまま残る。

クラスはレコード + 関数群になる

Object subclass: #Counter fields: (value).

Counter class >> of: n  = Counter fields: { value: n }.
Counter >> value        = value.
Counter >> inc          = Counter fields: { value: value + 1 }.

これに対応する OCaml はおよそ次の形になる。

type counter = { value : int }

let counter_of    (n : int)         : counter = { value = n }
let counter_value (self : counter)  : int     = self.value
let counter_inc   (self : counter)  : counter = { value = self.value + 1 }

クラス 1 つが OCaml のレコード型 1 つに対応する。インスタンスメソッドは self を第 1 引数に取るトップレベル関数として生成される。クラスメソッド (class >> で宣言したもの) もトップレベル関数だが、こちらはレシーバがクラス自身なので「渡す self」は存在しない。

fields: コンストラクタはレコード構築に対応し、Counter fields: { value: value + 1 } はレコード更新式 { value = self.value + 1 } になる。元の self は更新されない — 表層が約束している通り。

プロトコルは独立したデフォルト関数群になる

Protocol subclass: #Comparable requires: (#<).

Comparable >> > other    = other < self.
Comparable >> min: other = (self < other) ifTrue: [self] ifFalse: [other].

プロトコルは、満たすクラスに提供してもらうセレクタ (ここでは <) を宣言し、その上に残りのデフォルト実装を載せる形を取る。デフォルトメソッドは、その required 演算をパラメータとして受け取る関数として生成される。

let comparable_gt  (lt : 'a -> 'a -> bool) (self : 'a) (other : 'a) : bool =
  lt other self

let comparable_min (lt : 'a -> 'a -> bool) (self : 'a) (other : 'a) : 'a =
  if lt self other then self else other

具体クラスがプロトコルメソッドを呼んだとき、コンパイラはそのクラスの < を第 1 引数として埋め込む。やっていることは Haskell の辞書渡しと同じだが、より平坦 — 型クラスの階層をたどる必要はなく、プロトコル制約 1 つにつき明示的引数 1 つ、それだけ。

アクター `receive:` は型付きディスパッチクロージャになる

Counter class >> run: me count: n =
  me receive: {
    Inc      -> [:msg | Counter run: me count: n + 1].
    GetCount -> [:msg | msg reply ! n. Counter run: me count: n]
  }.

このクラス・タグディスパッチ表は、メッセージコンストラクタを場合分けするクロージャとして生成される。

let rec counter_run (me : actor) (n : int) : unit =
  let handler : type a. a message -> unit = function
    | Inc                 -> counter_run me (n + 1)
    | GetCount { reply }  ->
        Effect.perform (Send (reply, n));
        counter_run me n
    | _                   -> Effect.continue_with_no_match ()
  in
  Effect.perform (Receive handler)

一致しない分岐はスケジューラへ再送出する。スケジューラはそのメッセージをメールボックスに残し、次のハンドラ呼び出しで再試行する。これだけで選択受信が自然に成立する — スケジューラ側はクラス・タグの意味論を理解する必要すらなく、「このハンドラはメッセージを消費しなかったので、後でまた試す」とだけ判ればいい。

OCaml 5 effects 上のアクター

アクタープリミティブはエフェクト。スケジューラはエフェクトハンドラ。

type _ Effect.t +=
  | Spawn          : (actor -> unit) -> actor Effect.t
  | Send           : actor * any -> unit Effect.t
  | Recv           : actor -> any Effect.t
  | Recv_Selective : actor * recv_entry list -> (any * handler) Effect.t

Actor spawn: [:me | body] は Spawn を発行する。スケジューラはアクターレコード (mailbox + fiber state + monitor list) を確保し、body から新しい継続を作り、実行キューに積んで、アクターハンドルを呼び出し側に返す。

actor ! msg は Send を発行する。スケジューラは msg を対象のメールボックス末尾に追加する。対象が Recv で待機中なら起こす。

actor receive は Recv を発行し、スケジューラはメールボックス先頭 (FIFO) を返す。選択受信 receive: はハンドラ表を添えて Recv_Selective を発行する。スケジューラはメールボックスを先頭から末尾へ走査し、いずれかのハンドラに一致する最初のメッセージを消費して、アクターの継続をハンドラの戻り値で再開する。どのメッセージも一致しなければ fiber は待機する。(タイムアウト版は Recv_Selective_Timeout を発行する。)

スケジューラは小さく自立した OCaml コード — 実行キュー、ドメインプール、アクターごとのメールボックスキュー、エフェクトハンドラ。別の非同期ライブラリもモナドもなく、外部フレームワークが持つ I/O ループの上に乗っているわけでもない。

マルチドメインワークスティーリング

スケジューラは N 個の OCaml ドメイン (OCaml 5 の推奨に従い、典型的にコアあたり 1) の上で動く。各ドメインがローカル実行キューを持ち、アイドルなドメインはビジーな隣のドメインから仕事を盗む。ドメインを跨ぐメッセージ送信はメールボックスごとのロックフリー MPSC キュー経由なので、どのドメインからもコンシューマ側を待たせずに投入できる。

このスケジューラは AOT バイナリにも一緒にコンパイルされるので、まったく同一のマルチドメインワークスティーリング挙動になる — 別個の単一ドメインランタイムは存在しない。AOT を参照。

I/O 上の待機

TCP readLine:timeout: の中ではまずノンブロッキング read を試みる。EAGAIN が返ってきたら、スケジューラはそのファイルディスクリプタを「準備待ち集合」に登録して fiber を待機させ、別の仕事に切り替える。スケジューラのアイドル経路は Unix.select ベースのレディネスポーリングで Linux と Windows 共通に動く。OS が「読めるようになった」と通知してくると、スケジューラは待機していた fiber を起こし、read をやり直させる。呼び出し側からは「普通にブロックしているだけ」に見えるが、その間 OS スレッドは他のアクターを走らせている。

TLS も同じ作りで動く — TLSSocket >> readLine:timeout: は Tls.Engine を直接駆動する。エンジンは状態を 1 ステップ進めるたびに「バイトが欲しい (TCP 読込)」「書き出したい (TCP 書込)」「アプリケーションデータが出来た」のいずれかを返してくるので、それぞれ対応する I/O イベントで待機する。ハンドシェイク・アプリケーションデータの読込・書込はすべて別々の待機点で止まる。

メソッドディスパッチ

各呼出サイトは 2 つの形のいずれかに展開される。コンパイラは利用可能な中で最も安いものを選ぶ。

静的解決される送信 (一般的なケース)

レシーバがコンパイル時に特定でき、そのクラスでセレクタが一意に決まるなら、送信は直接 OCaml の関数呼び出しに展開される。仮想テーブルもインラインキャッシュもない、実行時コストゼロの呼び出し。

c := Counter of: 41.
c inc value printNl.

対応する OCaml は次のとおり。

let c = counter_of 41 in
print_endline (string_of_int (counter_value (counter_inc c)))

どの言語族で書こうとこれより速いディスパッチは作れない、という最速形。型がきちんと通っているコードのホットパスでは、メソッドディスパッチに費やすコストは事実上ゼロになる。

ランタイムディスパッチされる送信

レシーバをコンパイル時に特定できない場合 (Remote ref、perform:、リフレクション、プラグイン読込クラス) は、送信はランタイムディスパッチャ Eval.dispatch への呼び出しに展開される。インラインキャッシュは無い。ディスパッチはレシーバのクラスのメソッド表からセレクタを引き、cls_super 連鎖を Object まで辿る。

let dispatch (recv : value) (sel : selector) (args : value list) : value =
  let ci = class_of recv in
  match lookup_method ci sel with   (* メソッド表 + Object までの super 連鎖 *)
  | Some m -> invoke_method m recv args
  | None   -> does_not_understand recv sel

lookup_method はクラスの「セレクタ → メソッド」Hashtbl を引き、見つからなければ super 連鎖に落ちる。インラインキャッシュは現行版では意図的に対象外 — ツリーウォークのメソッド表が基準であり、レシーバが静的に特定できる箇所は AOT が検索そのものを消すので、ランタイムディスパッチャは推論が固定できなかったサイトだけを相手にする。

型システム

Hindley-Milner に 3 つの拡張: 型変数の プロトコル制約、アクター型の 行多相、レコードと Dict リテラルの インスタンス単位フィールド型。推論は完全、注釈は任意。

送信の解決 — 実行時送りは最後の答え

型システムは実装ではなく規範仕様として定義されており、そこで表明されている立場はこうだ: 決められるものは検査し、決められないものは実行時に回し、プログラムが既に一意にしたものは実行時に回さない。

レシーバの型が判っていれば、シグネチャはその形から引く。Class[C] なら C のクラス側メソッド、C なら C のメソッドと、次に C が実装するプロトコル、Remote[C] なら Remote 自身のメソッドと、次に C のメソッド。ユーザ定義のクラス階層は無いので辿る鎖も無い — セレクタはクラス自身か、それが実装するプロトコルか、普遍メソッドを持つ Object の上に見つかる。

レシーバがまだ型変数のままなら、次の順で決めにいく。

Object — Object がそのセレクタを宣言していれば、それがシグネチャ。普遍メソッドなのでレシーバに何の制約も課さない。
既に担っているプロトコル — その型変数の制約のどれかがセレクタを宣言していれば、それ。
プロトコル誘導 — その位置から見えるプロトコルのうち、セレクタを宣言するものがちょうど 1 つなら、レシーバはそれを実装する値である。送信がレシーバについて主張したのはまさにそのことだ。2 つ以上あれば曖昧なので、注釈でどちらの意味かを示す。
答えるクラスが 1 つだけ — そのセレクタに答えるクラスがちょうど 1 つなら、レシーバはそのクラスの値。部分型も、代わりに意味しうる別の定義も無い。解決できなかった比較の後でも検査が続くのはこれによる — ifTrue:ifFalse: に答えるのは Boolean だけなので、そのレシーバは Bool になり、2 つの分岐が突き合わされる。
引数が決める — 複数のクラスが答えるなら、与えられた引数をそれぞれに当ててみて、受け付けるものがちょうど 1 つならそれが意図されたもの。n < 2 がその典型で、Integer の < は Int を取るが、Float と String のものは取らない。
どれでも決まらなければ、その送信だけが実行時に回る。

ブロック呼び出しのセレクタ (value: / value:value: …) は決して実行時送りにならない — レシーバは対応するアリティのブロック型と単一化されるので、パラメータ越しに呼ばれるコールバックでも引数の数は検査される。

プロトコル制約付き多相

Comparable >> max: の推論型は概略次のとおり。

∀α. Comparable α ⇒ α → α → α

Comparable を満たすクラス (= < を実装するクラス) なら追加宣言なしに max: を使える。プロトコル制約はコンパイル時に強制される。

"Counter は Comparable を満たすのでコンパイル可"
(Counter of: 3) max: (Counter of: 7).

"String は Comparable を宣言していないのでコンパイル失敗"
'abc' max: 'def'.

String のクラス宣言の protocols: に Comparable を加えれば 2 つ目もコンパイルが通る。max: 自体には触れない。

アクター行多相

アクターの receive: はメッセージクラスの集合を受ける。アクター参照の型はその集合を行として運ぶ。

counter : Actor { Inc, GetCount | ρ }

| ρ の部分が行変数 — このアクターが追加で受け取りうるメッセージクラスの集合を表し、使用箇所から推論される。行も単一化に参加する: 別のコードが counter に Boom を送ろうとすると、推論は Boom を ρ に取り込もうとする。counter の実ハンドラがそれを受け取らないなら単一化は失敗し、ビルドは拒否される。

実例で言うと、counter に Inc を送るのは型が通る。Inc と GetCount しか受けない counter に Boom を送ると、コンパイル時にその送信行を指してエラーが出る。

レコードと Dict のフィールド型

ユーザクラスのインスタンスと Dict リテラルは、フィールド / キーの型を行として持ち、構成サイトごとに推論される。

Cls fields: { k: v, ... } は TInstR(Cls, { k: v の型, ... }) として型付けされ、クラスのインスタンスメソッドは self の型にメソッド単位のフィールド行を持つ。だからフィールド読み出しはコンストラクタが入れた型をそのまま返す。行は構成サイトごとなので、同じクラスでもインスタンスごとに別の型で読める — (Box of: 42) get は Integer、(Box of: 'hi') get は String。String で作った Box のフィールドを Integer として使えばコンパイルエラーになる。名前的境界をまたぐ — 素のクラス名で注釈した引数や戻り値 (TInst Cls) — とフィールド型は忘れられ、インスタンスだけが流れる。

Dict from: { k: v, ... } リテラルはキーで型付けされ、d at: 'age' はキー age の値型を返す。この精度は、レシーバが型付きリテラルの形のままで、アクセスキーがキー集合中の文字列リテラルである間だけ成り立つ。キーが計算値になる・素の Dict 型のスロットに入る・2 つの型付き dict が単一化される (例: 1 つの Array にまとめる) と失われる。異種混在の dict が普通なので、キーごとの型がユニオンに統合されることはない。

一般化の単位は依存グループ

メソッドの一般化はモジュール単位ではなく、呼び出しグラフの強連結成分 — 依存グループ — 単位で、呼ばれる側から順に行う。だから同じファイルの中でヘルパを 2 つの異なる型で呼んでも、そのヘルパは多相のまま残る。ヘルパを共有することがモジュールの切り方を決めてしまう、ということが無くなる。相互再帰は 1 つの成分になるので、従来どおり同じグループとして一緒に一般化される。

ルートクラスの拡張

Object に定義したメソッドは多相な self を取り、組み込みの普遍メソッドと同じくどのレシーバにも送れる。ルートクラスはどのモジュールからでも拡張できるが、ディスパッチを曖昧にしないために 2 つの制約が付く: Object が既に答えるセレクタは再定義できない。同じセレクタを 2 つのモジュールが Object に定義することもできない。

束縛は本体より先に型が付く

x := expr. body も [:x | body] value: expr も、本体を読む前に x を expr の型に結び付ける。だから x への送信は、x が実際に保持しているクラスに対して検査される — そのクラスが持たないセレクタも、構築時の型と食い違う使い方も、実行時に驚かされるのではなく、書いたその行でコンパイルエラーになる。高階メソッドに渡すブロックもレシーバ側から同じように型が付く: (anArray collect: [:x | ...]) の x は、ブロックを読む前に要素型へ束縛される。

型付きの不変更新

inst copyWith: { field: value, ... } は、名前を挙げたフィールドだけを差し替え、残りをそのまま引き継いだ新しいインスタンスを返す。フィールド名はクラス宣言に対して、値はそのフィールドの型に対して検査される — リフレクティブな atField:put: にはできないことだ。1 つのレコードに持たせたアクター状態が、更新可能なフィールドごとにコンストラクタ呼び出しを要求することはもう無く、そのために可変性を持ち込む必要も無い。

なぜこれらの拡張なのか

これらの拡張により、アクター本体を普通のクラスメソッドとして書け、フィールド型付きのインスタンスを通常のコードに流せる — どれもプログラムの他の部分と同じ推論でチェックされる。専用の「アクター型チェッカ」もランタイム契約も導入しなくていい。アクターへのメッセージ送信はあくまで通常の型付き send で、プロトコル多相が「1 つのハンドラで複数の具体レシーバに対応する」ことを支える。

標準ライブラリのデータ構造

中核ライブラリの非自明な選択は次の 2 つ。

Dict は HAMT

Dict は hash-array-mapped trie で、永続データ構造として作ってある: at:put: は新しい Dict を返し、その内部で旧構造と O(log₃₂ N) の経路だけを共有する。更新が走っても、並行している read は無効化されない — アクターがループ引数として count: n で次の状態を渡している間に、別の fiber が古いスナップショットへの参照を握っている、という場面で効いてくる。

Array は 32-way 永続 trie

Array も同じ作り — 幅の広い永続ベクターで、更新は O(log₃₂ N)、典型ケースのインデキシングは定数倍が小さい。永続性の性質は Dict と同じ。

これらのデータ構造があるからこそ、Lambda Prelude の「既定で不変」な表層をバックエンドサービスの規模で動かせる — 10 000 件のメッセージを受け取るアクターが、10 000 エントリのテーブルをループ引数としてそのまま転送できる。実際にコピーは走らない。

TLS ブリッジ

Tls.Engine は ocaml-tls ライブラリが提供する、純 OCaml の TLS 状態機械。Lambda Prelude はこれをラップして、状態進行はエンジンに任せつつ、I/O 待ちはそのスケジューラ上で待機する形で繋ぎ込んでいる。

呼出側                   Engine                  TCP socket
──                       ──────                  ──────────
TLSSocket readLine:
  → wants_app_data
                        next_event
                          → WantsRead
  ← TCP fd readable で待機
                          ← バイト到着
                        handle_bytes
                          → ProduceAppData
  ← バイトを呼出側へ返却

エンジンが wants_read / wants_write を返してきたとき、呼び出し fiber は対応する I/O wait で待機する。エンジン本体はユーザ空間で同期的に走る — 専用 TLS スレッドもコールバックベース I/O も持ち込んでいない。

ハンドシェイク・アプリケーションデータの読込・書込・接続終了、この 4 フェーズすべてが同じ形を取る。だからこそ、遅い TLS 上流がスケジューラを止めることはない — エンジンがバイトを欲しがるたびに fiber が待機し、その間 OS スレッドは他のアクターを進めている。