ハクソク

世界を動かす技術を、日本語で。

インクリメンタル - インクリメンタル計算のためのライブラリ

2026年7月21日原文(github.com)

概要

  • Incremental は、効率的な更新が可能な計算構築を支援するライブラリ
  • 入力の変化に素早く対応する 自己調整型計算 に着想を得て開発
  • スプレッドシート的な大規模計算やGUIビューの構築に活用
  • 派生データの 同期性保証 や動的なデータフィルタリングにも有効
  • 詳細なドキュメントや入門記事、動画も提供

Incrementalライブラリの概要

  • Incremental は、複雑な計算ロジックを効率的に構築・管理するための OCamlライブラリ
  • Umut Acar らの研究「自己調整型計算（self-adjusting computations）」に着想を得て設計
  • 入力データが変更されたとき、必要な部分のみを 最小限で再計算 する仕組み
  • 大規模な計算や動的なデータ処理に適した設計

主な用途

  • スプレッドシート のような大規模計算のリアクティブな構築
  • GUIアプリケーション でのビュー構築や動的なデータ反映
  • ソースデータと派生データの 同期性維持
    • 例えば、 フィルタ処理 や マッピングの逆転 などの派生計算

ドキュメントとリソース

  • 公式ドキュメントは incremental/src/incremental_intf.ml にて提供
  • 非公式な入門記事や動画も存在
    • ブログポストでの 概要説明
    • 解説動画 による視覚的な理解促進

利用メリット

  • 入力変更時の効率的な再計算
  • アプリケーションの パフォーマンス向上
  • 複雑な依存関係を持つ計算処理の 保守性向上

参考リンク

  • 公式ドキュメント: incremental/src/incremental_intf.ml
  • 入門ブログ: Incremental 解説記事
  • 解説動画: Incremental の使い方紹介

Hackerたちの意見

俺が今まで完全に理解できなかったのは、これが観測可能なパターンとどう違うのかってことだ。観測可能なものでは、新しい値を入力に公開して、それを計算に伝播させて、新しく計算された値をリスナーに送ることができる。多分、変更検出や、変更がない場合の伝播を止める最適化があるんだろうけど（観測可能なものでもできるしね）。スタビライズコマンドも面白いよね、再計算する前に変更をまとめる方法として。ただ、これも観測可能なものでできることだし。デルタは主にイントロスペクションから来てるの？それとも、俺が見落としてるもっと根本的な何かがあるのかな？

└

大まかに言うと、観測可能なものにサブスクライブしてリッスンする感じだね。インクリメンタルは、計算と状態のDAGを横断するキャッシュみたいなもので、再計算が必要な部分だけを最適化して再計算することができる。ロン・ミンスキーの素晴らしいトークがここにあるよ: https://www.janestreet.com/tech-talks/seven-implementations-...

└

俺もそう考えてた。ぱっと見、依存関係トラッキングを伴うリアクティブプログラミングにすごく近い感じがする。実際の利点がAPIの使いやすさなのか、それとも通常の観測可能な実装では実用的でない最適化があるのか、ちょっと気になるな。

└

観測可能なパターンをどう定義するかによるね。ここでの基本的な要素は、遅延とグラフノード間の弱い接続だよ。ノードの値は観測されるときだけ具体化されるし、システムはライブな構造変更に柔軟なんだ。通常、特定のノードだけを観測する場合、グラフ全体を具体化する必要はないよ。それに、いつでも計算を停止できて、グラフを半具体化状態にして、入力に追加の変更を加えて、興味のあるノードの具体化を続けることができる。アルゴリズムがすべての変更を整理してくれるから。要するに、インクリメンタル計算はこれらの機能をカバーする用語に過ぎない。オブザーバーとサブスクライバーの観点から同じシステムを整理することもできるよ。クラシックなExcelスプレッドシートがこのアイデアの最良の例かもしれない。あと、俺のこのトピックに関する記事も見てみて: https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c...

└

つまり、根本的にはただのグラフなんだけど、大規模で動的なグラフの変化を正しく効率的に計算する方法なんだ。ダイヤモンド型のサブグラフがあって、何百もの中間ノードに広がってから、また異なる「長さ」のパスを通って収束することを想像してみて。で、そのパスのいくつかが例えばmin(A, B)で、最大の側だけが変わるとしたら？ナイーブなオブザーバーアプローチだと、1) 潜在的に指数的な膨張を非常に非効率的に計算してしまうし、2) 「同時実行性」の問題が出るかもしれない。このライブラリは、グラフ構造を動的に変更し始めても、ほぼ最適で正確なものになるよ。でも、オブザーバーや他のアプローチでも同じことはできる。ほとんどは、パフォーマンスの崖を避けながら正しく実装するのがずっと難しいけどね。

└

https://www.scattered-thoughts.net/writing/an-opinionated-ma... これが景観をマッピングするのに役立つよ。

ゴールドマンは約30年前に同じアプローチでインストゥルメントの価格設定をしてたよ。俺はそこでの約13年間、"ノードパープリング"について長い議論をしたのを覚えてる。コンピュータサイエンスは進化してきたし、俺が見る限りこれはグラフアプローチじゃないけど、微分みたいなものは計算コストが高いから、理論的な最小回数に近づけるようにしたいよね。編集: 関連するHNの議論 https://news.ycombinator.com/item?id=36006737

└

そうそう、これが「バンクパイソン」を生み出したんだ。いい記事がここにあるよ: https://calpaterson.com/bank-python.html どうして問題になったのかのベストな説明がその段落にある。「新しく入った人たちは、特に特殊で必須の社内IDEを見た瞬間に辞めたくなるくらい、スピードを上げるのに異常に時間がかかる。数ヶ月経っても、新しい人たちはまだ基本的なことを学んでいる。違うことがたくさんあるからね。」俺がそこにいたときは、完全に理解するのに約2年半かかったな。新しいトレーニングが見つかるまで、あまり現代的な教育はなかった。最悪なのは、それを使ってUIを作ることなんだけど、新しいプロジェクトには承認されなかったんだよね。

ジェーンストリートのプロジェクトについていつも思ってたのは、研究やニッチなシステムに存在していたアイデアを、開発者が実際に使える形にパッケージ化してることだね。ライブラリを採用しなくても、デザインドキュメントは読む価値があることが多いよ。

数年前、データフロープログラミングにすごく興味があったんだ。多くの人がいろんな角度からこの問題にアプローチしてたと思う。この特定のライブラリは、ClojureのJavelinをすぐに思い出させたよ。[0] [0]: https://github.com/hoplon/javelin

最近、JavaScriptのUIフレームワークでは「シグナル」という名前でこの反応型プログラミングスタイルが人気だよ。標準化の提案がここにあるよ: https://github.com/tc39/proposal-signals#-javascript-signals... VueやSolidJS、Svelte、Ember、Angularなどのフレームワークで使われていて、React用の実装もいくつかあるよ。MobxやJotaiみたいなやつね。変更を伝播させたりDAGを評価するアルゴリズムもいくつかあって、SolidJS2はインクリメンタルに似た高さベースのアルゴリズムを使ってると思う。俺はInt32Arrayアリーナを使ってノードを割り当て、リンクリストで繋げる実装をいじってるんだ。O(依存エッジ)のGC負荷をかけずにね: https://github.com/justjake/dalien-signals/tree/dalien-signa... Rustでもいくつかあって、LeptosはUIフレームワークの例で、Salsaは一般的なインクリメンタルコンピューティングの例で、rust-analyzerで使われてるよ。こういうのを自動的に追跡される依存関係を持つビルドシステムとして見ることもできる。tupっていうビルドシステムがあって、ビルドジョブを計測してどのファイルを読んでいるかを検出して依存関係を確立するんだ。著者の面白い読み物もあるよ: https://gittup.org/tup/build_system_rules_and_algorithms.pdf、クラシックなBuild Systems à la Carteも見てみてね: https://www.microsoft.com/en-us/research/wp-content/uploads/...

└

別の注目すべき例: JetBrains Noria ( https://blog.jetbrains.com/fleet/2023/02/fleet-below-deck-pa... ) 著者たちが強調しているように、「Noriaはその本質的にはUIフレームワークではない。代わりに、インクリメンタル計算のためのプラットフォームだ。」でも、今はJetBrains Air IDEでGUIレンダリングを最適化するために使われているみたい。

Hacker Newsで議論の続きを見る