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.tActor 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 sellookup_method はクラスの「セレクタ → メソッド」Hashtbl を引き、見つからなければ super 連鎖に落ちる。インラインキャッシュは現行版では意図的に対象外 — ツリーウォークのメソッド表が基準であり、レシーバが静的に特定できる箇所は AOT が検索そのものを消すので、ランタイムディスパッチャは推論が固定できなかったサイトだけを相手にする。
型システム
Hindley-Milner に 3 つの拡張: 型変数の プロトコル制約、アクター型の 行多相、レコードと Dict リテラルの インスタンス単位フィールド型。推論は完全、注釈は任意。
プロトコル制約付き多相
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 が普通なので、キーごとの型がユニオンに統合されることはない。
なぜこれらの拡張なのか
これらの拡張により、アクター本体を普通のクラスメソッドとして書け、フィールド型付きのインスタンスを通常のコードに流せる — どれもプログラムの他の部分と同じ推論でチェックされる。専用の「アクター型チェッカ」もランタイム契約も導入しなくていい。アクターへのメッセージ送信はあくまで通常の型付き 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 スレッドは他のアクターを進めている。