インクリメンタルコンピューティング

増分計算（増分計算とも呼ばれる）は、データが変更されるたびに、変更されたデータに依存する出力のみを再計算することで時間を節約しようとするソフトウェア機能です。 ^[1]^[2]^[3]増分計算が成功すると、新しい出力を単純に計算するよりも大幅に高速になります。たとえば、スプレッドシートソフトウェアパッケージは、再計算機能で増分計算を使用して、変更されたセルに（直接的または間接的に）依存する数式を含むセルのみを更新する場合があります。

増分コンピューティングが、さまざまなコード部分に対して自動的に実装できるツールによって実装される場合、そのツールは最適化のためのプログラム分析ツールの例です。

静的と動的

インクリメンタルコンピューティング手法は、大きく分けて 2 種類のアプローチに分けられます。

静的アプローチでは、手動設計とリファクタリング、または自動プログラム変換などを使用して、従来のプログラム P から増分プログラムを導出しようとします。これらのプログラム変換は、入力または入力変更が提供される前に行われます。

動的アプローチは、特定の入力 (I1) に対するプログラム P の実行に関する情報を記録し、入力が (I2 に) 変化したときにこの情報を使用して出力を更新します (O1 から O2 に)。図は、プログラム P、増分プログラムの中核となる変更計算関数 ΔP、および入力と出力のペア I1、O1 と I2、O2 の関係を示しています。

専門的なアプローチと汎用的なアプローチ

インクリメンタルコンピューティングへのアプローチには、特殊なものもあれば、汎用的なものもあります。特殊なアプローチでは、プログラマーが、変更されていないサブ計算を保存するために使用するアルゴリズムとデータ構造を明示的に指定する必要があります。一方、汎用的なアプローチでは、言語、コンパイラ、またはアルゴリズム技術を使用して、非増分プログラムに増分動作を与えます。^[4]

静的メソッド

プログラム派生商品

計算と潜在的な変化が与えられた場合、変化が起こる前（事前微分）と変化の後に（事後微分）コードを挿入して、を再実行するよりも速くの値を更新することができます。Paigeは、SUBSETLでプログラムの形式的微分化の規則のリストを書き留めています。^[5] $C=f(x_{1},x_{2},\dots x_{n})$ $x_{j}:=\Delta _{x_{j}}$ $C$ $f$

メンテナンスを表示

DBToasterなどのデータベースシステムでは、ビューはリレーショナル代数で定義されます。増分ビューメンテナンスは、リレーショナル代数を静的に分析して、行の挿入などの小さな更新がある場合にビューを迅速に維持する更新ルールを作成します。^[6]

動的メソッド

増分計算は、再計算が必要な可能性のあるすべてのデータ要素とその依存関係の依存関係グラフを構築することで実現できます。 1 つの要素が変更されたときに更新する必要がある要素は、グラフの依存関係の推移閉包によって決まります。つまり、変更された要素から別の要素へのパスがある場合、後者は更新される可能性があります (変更が最終的に要素に到達するかどうかによって異なります)。依存関係が変更された場合、またはシステムに要素が追加または削除された場合、依存関係グラフを更新する必要がある場合があります。これは実装によって内部的に使用され、通常はユーザーに表示する必要はありません。

依存関係を追跡できる重要な値のサブセット（集計結果など）を特定し、他の従属変数を段階的に再計算することで、すべての可能な値にわたる依存関係をキャプチャすることを避けることができます。これにより、追跡する依存関係情報の量と、入力の変更時に実行される再計算の量のバランスが取れます。^[7]

部分評価は、増分コンピューティングの最も単純なケースを自動化する方法と見なすことができます。この方法では、プログラムデータを、プログラムの入力に基づいて変化するものと変化しないものの 2 つのカテゴリに分割しようとします (変更の最小単位は、単に「変化する可能性のあるすべてのデータ」です)。部分評価は、他の増分コンピューティング手法と組み合わせることができます。

依存関係グラフにサイクルがある場合、グラフを1回通過するだけでは固定点に到達できない場合があります。場合によっては、システムの完全な再評価は増分評価と意味的に同等であり、理論的ではないとしても実際にはより効率的である可能性があります。^[8]

既存のシステム

コンパイラと言語のサポート

自動増分化（「自己調整計算」や「適応型関数プログラミング」とも呼ばれる）、^[9] Delta ML、Haskell Adaptive
コーネルシンセサイザージェネレーター^[10]
IceDust - カスタムドメイン固有言語。

フレームワークとライブラリ

Adapton ^[11] - 複数の言語で実装されている
一方向データフロー制約 (C++ でのリアクティブ計算)
差分データフロー
ジェーンストリートインクリメンタル
増分データログ ( LogicBlox )
インクリメンタルプロローグ（XSB）^[12]
ドメイン固有のアプローチ:
- 増分型チェック

アプリケーション

データベース（ビューのメンテナンス）
ビルドシステム
スプレッドシート^[13]
開発環境
財務計算
属性文法評価
グラフの計算とクエリ
GUI（例：ReactとDOM比較）
科学的応用

参照

参考文献

^ Carlsson, Magnus (2002). 「増分コンピューティングのためのモナド」。第7 回 ACM SIGPLAN 国際関数型プログラミング会議の議事録。ニューヨーク: ACM。pp. 26–35。doi :10.1145 / 581478.581482。ISBN 1-58113-487-8。
^ Umut A. Acar (2005). 自己調整計算(PDF) (博士論文).
^ Camil Demetrescu、Irene Finocchi、Andrea Ribichini (2011)。「データフロー制約によるリアクティブ命令型プログラミング」。第26 回 ACM 国際オブジェクト指向プログラミングシステム言語およびアプリケーション会議 (OOPSLA 2011) の議事録。ACM。pp . 407–426。arXiv : 1104.2293。doi : 10.1145 / 2048066.2048100。ISBN 978-1-4503-0940-0。
^ Yan Chen、Joshua Dunfield、Matthew A. Hammer、Umut A. Acar。純粋関数型プログラムのための暗黙的な自己調整計算。ICFP '11。pp. 129–141。2016年10月30日時点のオリジナルよりアーカイブ。 2018年3月12日閲覧。
^ ペイジ、ロバート (1981)。形式的微分化: プログラム合成テクニック。UMI リサーチプレス。ISBN 978-0-8357-1213-2。
^ Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). 「DBToaster: 動的で頻繁に更新されるビューの高次デルタ処理」. Proc. VLDB Endow . 5 (10): 968–979. arXiv : 1207.0137 . doi :10.14778/2336664.2336670. ISSN 2150-8097.
^ Mugilan Mariappan、Keval Vora (2019)。「GraphBolt: ストリーミンググラフの依存関係駆動型同期処理」。European Conference on Computer Systems (EuroSys'19)。pp. 25:1–25:16。doi : 10.1145 /3302424.3303974。
^ Kimberley Burchett、Gregory H. Cooper、Shriram Krishnamurthi (2007)。 「 Lowering: 透過的な機能的反応性のための静的最適化手法」。ACM SIGPLAN シンポジウム、部分評価とセマンティクスベースのプログラム操作。pp . 71–80。CiteSeerX 10.1.1.90.5866。ISBN 978-1-59593-620-2。
^ Hammer, Matthew A.; Acar, Umut A.; Chen, Yan (2009). 「CEAL」。2009 ACM SIGPLAN プログラミング言語の設計と実装に関する会議の議事録 - PLDI '09。p. 25。doi :10.1145 / 1542476.1542480。ISBN 9781605583921. S2CID 11058228。
^ Reps, Thomas; Teitelbaum, Tim (1984). 「シンセサイザージェネレータ」。第 1 回 ACM SIGSOFT/ SIGPLANソフトウェアエンジニアリングシンポジウム「実用的なソフトウェア開発環境 - SDE 1」の議事録。pp. 42–48。doi : 10.1145 /800020.808247。ISBN 978-0897911313。
^ 「Adapton: 増分計算のためのプログラミング言語抽象化」。adapton.org 。 2016年10月7日閲覧。
^ Saha, Diptikalyan; Ramakrishnan, CR (2005). 「テーブル化された Prolog の増分評価: 純粋論理プログラムを超えて」.宣言型言語の実際的側面. コンピュータサイエンスの講義ノート. 第 3819 巻. pp. 215–229. CiteSeerX 10.1.1.111.7484 . doi :10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.
^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: 構成可能な需要主導型増分計算(PDF) . PLDI.

[monads-for-incremental-1] Carlsson, Magnus (2002). 「増分コンピューティングのためのモナド」。第7 回 ACM SIGPLAN 国際関数型プログラミング会議の議事録。ニューヨーク: ACM。pp. 26–35。doi :10.1145 / 581478.581482。ISBN 1-58113-487-8。

[2] Umut A. Acar (2005). 自己調整計算(PDF) (博士論文).

[3] Camil Demetrescu、Irene Finocchi、Andrea Ribichini (2011)。「データフロー制約によるリアクティブ命令型プログラミング」。第26 回 ACM 国際オブジェクト指向プログラミングシステム言語およびアプリケーション会議 (OOPSLA 2011) の議事録。ACM。pp . 407–426。arXiv : 1104.2293。doi : 10.1145 / 2048066.2048100。ISBN 978-1-4503-0940-0。

[4] Yan Chen、Joshua Dunfield、Matthew A. Hammer、Umut A. Acar。純粋関数型プログラムのための暗黙的な自己調整計算。ICFP '11。pp. 129–141。2016年10月30日時点のオリジナルよりアーカイブ。 2018年3月12日閲覧。

[5] ペイジ、ロバート (1981)。形式的微分化: プログラム合成テクニック。UMI リサーチプレス。ISBN 978-0-8357-1213-2。

[6] Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). 「DBToaster: 動的で頻繁に更新されるビューの高次デルタ処理」. Proc. VLDB Endow . 5 (10): 968–979. arXiv : 1207.0137 . doi :10.14778/2336664.2336670. ISSN 2150-8097.

[7] Mugilan Mariappan、Keval Vora (2019)。「GraphBolt: ストリーミンググラフの依存関係駆動型同期処理」。European Conference on Computer Systems (EuroSys'19)。pp. 25:1–25:16。doi : 10.1145 /3302424.3303974。

[8] ^ Kimberley Burchett、Gregory H. Cooper、Shriram Krishnamurthi (2007)。 「 Lowering: 透過的な機能的反応性のための静的最適化手法」。ACM SIGPLAN シンポジウム、部分評価とセマンティクスベースのプログラム操作。pp . 71–80。CiteSeerX 10.1.1.90.5866。ISBN 978-1-59593-620-2。

[HammerAcar2009-9] Hammer, Matthew A.; Acar, Umut A.; Chen, Yan (2009). 「CEAL」。2009 ACM SIGPLAN プログラミング言語の設計と実装に関する会議の議事録 - PLDI '09。p. 25。doi :10.1145 / 1542476.1542480。ISBN 9781605583921. S2CID 11058228。

[RepsTeitelbaum1984-10] Reps, Thomas; Teitelbaum, Tim (1984). 「シンセサイザージェネレータ」。第 1 回 ACM SIGSOFT/ SIGPLANソフトウェアエンジニアリングシンポジウム「実用的なソフトウェア開発環境 - SDE 1」の議事録。pp. 42–48。doi : 10.1145 /800020.808247。ISBN 978-0897911313。

[11] 「Adapton: 増分計算のためのプログラミング言語抽象化」。adapton.org 。 2016年10月7日閲覧。

[SahaRamakrishnan2005-12] Saha, Diptikalyan; Ramakrishnan, CR (2005). 「テーブル化された Prolog の増分評価: 純粋論理プログラムを超えて」.宣言型言語の実際的側面. コンピュータサイエンスの講義ノート. 第 3819 巻. pp. 215–229. CiteSeerX 10.1.1.111.7484 . doi :10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.

[adapton-pldi2014-13] Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: 構成可能な需要主導型増分計算(PDF) . PLDI.