素人くさいSICP読書会
素人くさいSICP読書会に参加し始めた．
いま４章のLISPインタプリタのところ，4.2.2 遅延評価とメモ化を実装した
メモ化しておけばfibonacciを
(define (fib x) (if (< x 2) 1 (+ (fib (- x 1)) (fib (- x 2)) ) ) )
みたいなナイーブな実装で書いてもちゃんと高速に動く...はずだが，なんか私が書いたものだけちゃんとメモ化できてなかったので，まさにfibonacci的な遅さになっていった．ダウンロードしてきた実装まるぱくりではいかんようだ．
(fib 5) =>8 cpu time: 47 real time: 16 gc time: 0 (fib 10) =>89 cpu time: 266 real time: 250 gc time: 0 (fib 15) =>987 cpu time: 2812 real time: 2812 gc time: 0 (fib 20) =>10946 cpu time: 31516 real time: 58484 gc time: 406 (fib 25)
IT系ニュースサイトにSchemeの記事をぜひ
帰りがけに参加者とお話．日経BPの記者の方だった．さすがに普段Schemeを仕事で使うことはないらしい....と思っていたけど，Haskellの記事もあるから，そのうちSchemeの記事もぜひのっけてもらいたいものだ．
[論文] Incremental Computation of Complex Object Queries
http://portal.acm.org/citation.cfm?id=504294&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749
IBMのTRLの人が書いたらしい．
2. Comprehension Query Notation
Comprehenstion て List Comprehension の Comprehension のこと．SQLのクエリを内包表記に直して議論しますよー，という下準備
{e | v<- e' }
{x | f(x) } ( f: X->bool )
前回に引き続き，ここでもbagだのsetなどが登場．
3. Problems with Incremental Computation
基本アイデアは
- f(E) = {x*x| x<-E }
として，
- E={1,2}
だったときに
- E'={1,2,3}
となったら
- ΔE={3}
として，f(ΔE) を再計算して，もとのf(E)にくっつけちゃえ，というもの
でも，この方式はEがbagやsetでないと使えない．primitiveな値の場合はどうしよう，
あと，
- E={-4,1,4}
- f(E)={16,1}
のとき，4を削除してもやっぱり
- f(E)={16,1}
なので，削除や追加などの変更捜査と，実際のクエリの変動は一致しないから面倒．
という問題提起．
4．Translation Into Collection
上の1個めの問題に対応するために，primitiveな値もむりやりbagにおきかえてしまえ，という変換をかます
- x を {x} に変換
- {x}+{y} を {x'+y'| x'<-x, y'<-y }に変換．なんかリストモナドぽい
あと，オブジェクト {name:"John", age:32} は[ (name, {"John"}) , (age ,{32}) ] だそうだ．
この場合，32 を 33にしたければ，32をbag(set)から削除して，33 を追加しなおすという操作をすることになる．
5. Incremental Computation of Comprehension Instances
さっきの
- E={-4,1,4}
- f(E)={16,1}
の問題を何とかする方法．
内包表記の式にもとづき依存関係のツリーを作っておいて，変更があったときはツリーをたどる，というオーソドックスな？やりかた．
6. Update Propagations
- Strict Update (自分自身を更新-> 自分に依存している値(dependents)をたどって更新させる）
- Lazy Update(自分の分はフラグを立てるだけでおいといて，dependentsから先に更新を依頼．自分自身は最後に更新．ただし更新の過程でdependents によって自分自身が先に更新されるかも）
- Hybrid Update （両者のいいとこどり？）
8． Evaluation
日本人の論文なのでEvaluationがしっかり．というか他国の論文てEvaluationないのに通っているのが多いので不思議．
- 自分で書いたIncremental Evaluationによるクエリ更新のプログラムと，自動生成したものとを比較．
- ある程度の規模のOODBに対して，データを追加削除変更した場合のビューの再計算速度を測定
- で，提案手法のほうが数倍遅い．
うーん，たぶん提案手法のほうが楽にかけるから，ちょっと遅くても楽できるでしょ，といわなきゃいけないんだろうけど，コード量とかに関する議論がない．
[論文] 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とかどうする？という議論．
Reactive Functional Programming その後
Reactiveなプログラム例として，ゲームが載っている．次の5つの状態がある．
- Quiet: 「Insert Coin」と出ている画面
- Start: Coin1個いれるとこの画面になる．「Ready」ボタンを押すまで待機
- Wait : 「Ready」を押すとこの画面になり，ランダムな時間待たされる
- React ： 「Stop」を押せ！ という画面になる
- End : 「Stop」を押した後の画面．反応するのにかかった時間が表示される
これ，ようするにオートマトン．こういう状態機械を関数型言語であらわす，みたいな話で，どうもStateモナドなどと関係ありそう，だけどReactive Programming，Reactiveなコンパイラの話とは関係なさそうなので，この論文は保留かな．
不動点アルゴリズム
昨日の論文において「関数型言語は不動点計算に向かない，なぜならエンコードしなければならないから」的なことが書かれていたので，不動点アルゴリズムについて調べてみた
これが繰り返しの４２番目のデータとして、表示される。およそ、解が出るまでに数百回の繰り返しが必要になる。
(中略）
人口単体上にあるのか基本単体上にあるのかを区別している。
(中略）
資本と労働、貿易の各超過需要と税と貯蓄に関する超過収入が計算されている
んー，なんか経済とかの計算に使うのかな？となると昨日のcpoはCost-per-orderかもしらん（msakaiさんより：Complete Partial Orderだそうです．）
反復改良法
これを用いた sqrt, fixed-point の実装：
これは，どうもニュートン法のにおいがする．たしかに点が動かなくなるまで繰り返すのがニュートン法だ．
Haskell で難なく書いている．
cbrt e x = iter 1.0 x x where iter old new x | good old new = new | otherwise = iter new (improve new x) x improve g x = (x / g^2 + 2 * g) / 3 good old new = abs (1 - old / new) < e
あ，この「ループを末尾再帰とテンポラリ引数 old とか new とかで無理やり再現」が「エンコード」と主張しているのかも．
Reactive Programming と Fixed-Point
Reactive Functional Programming の論文を読んでみたけど，むずい．
1. Introduction
The control structure needed for reactive programs is inherently iterative, not recursive.
Reactiveなプログラムにはiterative（繰り返し？） な制御構造が必要で，再帰はあまり必要でない．
1.1 Mathematical models for programming
The models in common use in programming are cpo models of computational domains. These allow us to calculate solutions to recursive equations. However, these models
don't help much to abstract away detail - they force us to encode it.
....
The theory of cpo models is difficult to apply - its logic is based upon the principle of computational (or fixed-point) induction. ....
The structure ... is just function definitions written in terms of recursive equations. It seems inadequate.（数学的）なモデルの利用例は CPO モデルである．漸化式を解くのに用いられる．しかし抽象化に向かない． そのモデルをエンコードしなければならないから．
CPOモデルは不動点計算を用いている．再帰を使って表現するのは難しい．
なんか不動点計算とかでてきたのでそっちから勉強しないといけない気がした．
あとCPOてなにー
- cost-per-order?
- Cost of Process Ownership ?
Reactive Programming と XML Validation
最近にわかにReactive(Incremental?) Programmingが流行っているきがする
Reactive Ruby : RubyでReactive Programmingしてみた
最近、実用的なコードばかり書いているので、もっと役に立たないコードを書くべきだと思い、 Reactive Rubyというライブラリを作ってみました。
(略)
で、何に使えるの？何に使えるんでしょうね？
最近読んだ論文から「こんな活用例あるよー」とコメントしたが，実は論文のなかみを真面目に読んでいなかったので読んでみた
Consistently Updating XML Documents using Incremental Constraint Check Queries
1. Introduction
XML Documentが更新されるときに，DTDやスキーマで規定される制約との整合性が保たれているかどうかをチェックしたい．
DB2などのDBMSに付属しているものもあるけど，それはRDBにマッピングされることを前提としている．RDBの整合性チェックを借りているだけ
Native XMLでの整合性チェックをIncremental(Reactive?)にしたい
2. Modeling
XML Schemaの紹介(ここはまだ定式化の部分なので提案はない）
3. XML Query Update language
XQuery に UPDATE を拡張したものらしい， というか，XQueryてこんなんだっけ
ちなみに，UPDATEの例はこれ....あいかわらず割り算やっているように見える．
FOR $p in document(“juicers.xml”)/juicer, $c in $p/cost[1] UPDATE $p { DELETE $c } }
5． Application Of Constraint rules for update cases
実装．削除したときの整合性のチェックは次の2つの関数を用いて行う
- getChildMinOccur($document, $parentName ,$childName )
- isDeletable($child, $childPath, $minOccur)
(原文の関数名は違う．わかりやすい名前に変更)
さっきのupdate式に埋め込むと：
FOR $p in document(“juicers.xml”)/juicer, $c in $p/cost[1] LET $constraint = getChildMinOccur(“juicers.xsd”,“juicer”,“cost”) UPDATE $p { WHERE isDeletable($c,$p/cost,$constraint) UPDATE $p { DELETE $c } }
6. Safe update Queries Generation
上のような検査式を自動生成する方法．ここが面白いはずなんだけど参考文献見ろで半ページで終わっている．SAXEていうシステムで使っているらしいけど検索してもすぐにはでない．SAXとは関係ない？
7. Performance
次の2つをinsert delete rename replace 別で対決
- （提案手法）スキーマチェックをするupdate Queryにかかる時間 + そのQuery を生成する時間
- （従来手法）ナイーブなupdateにかかる時間 + フルValidationにかかる時間
結果は....提案手法の大敗！ちなみにQuery生成の時間を取り除いても負け
そのあと書かれている敗者の弁がどうも読み取れない
this does not mean that a safe Update-XQuery is inefficient．
....
the safe Update-XQuery is a one step process where updates
are only performed once the updates are deemed safe so that
all the attempts for invalid updates will be prevented.
....
The execution of non-safe Update-XQuery ...
may need to iterate several times between attempting updates
and then verifying if the updates leave the XML document in a consistent
state.(訳)
こっ，これは決してsafe update(提案手法)が役にたたないのではなくて，
safe update は，ひとたびupdateが安全だとみなされれば，
updateが行われて，安全でないすべてのupdateは防止される．
一方non-safe なupdate(従来手法）はupdateの間に何度も繰り返して，
それからupdateの内容が整合性を保っているかをチェックするのだっ．
多分訳がぐだぐだなのだろう．多分．
