HVM（Higher-order Virtual Machine）

HVM

HVM (Higher-order Virtual Machine) は Kindelia による関数型言語のコンパイルターゲット/ランタイム（Rust 実装）。遅延評価・GC レス・並列化を特徴とし、特定ケースで GHC より指数的に高速。

仕組み

• Interaction Net / beta-optimal に基づく。Lamping の Abstract Algorithm を SIC ベースの効率的フォーマットで実装し、グラフ表現より約50倍高速化。
• 全オブジェクトは1箇所にしか存在せず、グローバル GC が不要（Rust のように）。複数参照は borrow ではなく lazy clone primitive で扱い、読まれるまでゼロコストの .clone() をレイヤーごとに on-demand で行う。
• スコープを抜けると即座にメモリ解放でき、atomic を最小化できるため並列化が単純。
• 書き換えはTRS。ユーザ定義規則 + プリミティブ規則（App-Lam、Dup-Ctr、Dup-Lam、App-Sup、Op2 等）。コンパイラが dup（複製）を挿入し全変数を1回出現に正規化。superposition {a b} でλ本体の計算を共有する。

ベンチマーク観察

• 関数合成 $f^{2^N}(x)$ は HVM で $O(N)$、GHC で $O(2^N)$。並列な Tree Sum / QuickSort（木を返す形）で大幅高速化。
• 一方、逐次 List Fold は GHC と同等で、HVM は VM でありコンパイラではない点（実行時 fusion）が GHC との比較を難しくする、という議論もある。

関連

• 理論はoptimal-reduction・lambda-calculus、比較対象はhaskell-ghc。
• _moc-prog-lang