[論文] INC: A Language for Incremental Computations
http://portal.acm.org/citation.cfm?id=103137&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749
この論文に書いてあるような言語を作ろうとしていたところだった．
1 . INTRODUCTION
Incremental(Reactive) Computation のいろんな応用例
- Program Development Environment / Cornell Synthesizer : 大昔のEclipse みたいな仕組み
- スプレッドシート Excelは代入可能な関数型言語だからね
- グラフィックエディタ． JavaFXで作るRIA的なつかいかた
A program written in INC is written the same way one writes a program in any other language. The compiler generates an implementation that is tailored to the assumption of incremental execution.
INCで書いたプログラムはほかの(関数型？）言語で書くのと同じ方法で書かれている．しかし，INCコンパイラはincremental に計算するようなコードを出す
2. RELATED WORK
These systems usually rely on ad-hoc techniques or heuristics that, through experience, tend to minimize the amount of computation that needs to be repeated on each iteration.
先行研究ではIncremental 計算は用途にあわせててきとーにつくっていたので，
- アプリケーション非依存
- Incrementalなプログラムを自動生成する
- (?) coarse-grain と fine-grain をサポート
- (?) static と incremental complexity
3. AN OVERVIEW OF INC
- その代り，リスト処理の組み込み関数がやたら豪華．Map,Fold,Filterはもちろん，Diff(集合の引き算)Partition(同値類生成) とか，EqualJoin(SQLのInnerJoin)相当の関数まで組み込み（というか組み込んでおかないとユーザ側では定義できないから．なぜなら再帰が使えないから）
- bag とset の2種類があって，bagは重複可能な集合（たぶんリストのかわり），setは普通の集合
- TransitiveClosure という組み込み関数 → 親子関係(child,parent)の集合を放り込むと，(child,ancestor)の集合を生成する．たぶんスコープの上下関係を処理したいからだろう
- さらに，なんと型や変数の解決を組み込み関数にしているっぽい
Resolution: ([Decl], [Ref], Nestings) -> ( resolved, unresolved ) resolved: [ (Decl,Ref) ] unresolved: [Ref] data Decl = Name [Attr] Scope Attr は型などの属性情報，Scope はどのスコープにて定義されているかをあらわす data Ref = Name Scope Scope はどのスコープから参照されているかをあらわす data Nestings = Scope Scope 1個めのスコープは， 2個目のスコープの直近の親である
4. MAKING INC PROGRAMS INCREMENTAL
効率の評価．「incrementalな計算は，最初から計算しなおすよりも必ず速く計算できる」ことを証明しているらしい．未読．
4.4 Exampleいくつか（P18)
たとえば，Example4 Program Resolution では，あるブロックbに新しい変数宣言をいれた場合に必要な計算量をもとめている．
- incrementalなコンパイラの場合 ： O(A+B)
- 普通のコンパイラの場合： O(B+V)
- Bは bの内側にあるブロックの数
- Vは それらのブロックから参照している変数の数
- Aは それらの変数のうち，新しい変数によって影響をうける変数の数 (A<<<
... 影響を受けるかどうかの判定にどれくらいのコストがかかるのか，というのは考えなくていいのかな
あと，属性文法（AG)についての欠点がついでにあげられている
Furthermore, INC contains no copy rules, another source of inefficiency in AGs.
copy rules というのは多分，Attribute Grammar では，スコープの情報とかをどんどん下位の構文要素に渡していくことだろう．こんな参考文献もあるし．
14. HOOVER, R. Dynamically bypassing copy rule chains in attribute grammars. In 13th ACM Symposium on Principles of Programmmg Languages. ACM, Jan. 1986.
4.5 Incremental Algorithm
組み込み関数(Diff, Choice, Map, Reduce)などの実装
5. COMPLEX DATA TYPES
bagの中にbagを入れた場合，Diffとかどうする？という議論．
