hoge1e3の日記

トップページへ

2008-07-04

素人くさいSICP読書会

素人くさいSICP読書会に参加し始めた.

いま4章の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の記事もぜひのっけてもらいたいものだ.

2008-04-30

[論文] Incremental Computation of Complex Object Queries

http://portal.acm.org/citation.cfm?id=504294&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749

IBMのTRLの人が書いたらしい.


1. INTRODUCTION

データベースクエリ・ビューを,データが変わったときに動的に更新したい.

高速な手法も提案されているけど,FlatなRDB専用なので,OODBでも使えるものにしたい.

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 (両者のいいとこどり?)

7. Implementation

Cincom Visualworks 3.1 て何?

Smalltalkらしい

肝心のOODBは何をつかったか書いていない

8. Evaluation

日本人の論文なのでEvaluationがしっかり.というか他国の論文てEvaluationないのに通っているのが多いので不思議

  • 自分で書いたIncremental Evaluationによるクエリ更新のプログラムと,自動生成したものとを比較.
  • ある程度の規模のOODBに対して,データを追加削除変更した場合のビューの再計算速度を測定
  • で,提案手法のほうが数倍遅い.

うーん,たぶん提案手法のほうが楽にかけるから,ちょっと遅くても楽できるでしょ,といわなきゃいけないんだろうけど,コード量とかに関する議論がない.

9 Related Work

ここでも,提案手法の売りは値の「変更」らしい.「追加」や「削除」については既存手法でもやられているけど,さっきの無理やりなエンコードによってprimitiveな値の変更にも耐えられるようになった,といいたげ

あと,昨日の論文を引き合いにだして,「あんなにたくさん組み込み関数作っちゃって.うちはせいぜい1個だ」と言っていた.あっちはコンパイラ,こっちはDBMSなので一概にはいえない.


なんか,Incrementalな計算においてはsetだのbagだのという話に収束しているきがする.そうしたほうがやりやすい裏事情でもあるのかな.

2008-04-29

[論文] 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 のいろんな応用例

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 計算は用途にあわせててきとーにつくっていたので,

3. AN OVERVIEW OF INC

  • 再帰データとか再帰呼び出しはサポートしないらしい.「再帰とか豪華な機能を用意すると,incrementalを効率的にできないじゃん,だから許して」だそうだ.
  • その代り,リスト処理の組み込み関数がやたら豪華.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<<<<V)</li>

... 影響を受けるかどうかの判定にどれくらいのコストがかかるのか,というのは考えなくていいのかな

あと,属性文法(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とかどうする?という議論.

6. FUTURE DIRECTIONS

2008-04-26

不動点アルゴリズム

昨日の論文において「関数型言語は不動点計算に向かない,なぜならエンコードしなければならないから」的なことが書かれていたので,不動点アルゴリズムについて調べてみた

 これが繰り返しの42番目のデータとして、表示される。およそ、解が出るまでに数百回の繰り返しが必要になる。

(中略)

人口単体上にあるのか基本単体上にあるのかを区別している。

(中略)

資本労働、貿易の各超過需要と税と貯蓄に関する超過収入が計算されている

んー,なんか経済とかの計算に使うのかな?となると昨日の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 Functional Programming その後

Reactiveなプログラム例として,ゲームが載っている.次の5つの状態がある.

  • Quiet: 「Insert Coin」と出ている画面
  • Start: Coin1個いれるとこの画面になる.「Ready」ボタンを押すまで待機
  • Wait : 「Ready」を押すとこの画面になり,ランダム時間待たされる
  • React : 「Stop」を押せ! という画面になる
  • End : 「Stop」を押した後の画面.反応するのにかかった時間が表示される

これ,ようするにオートマトン.こういう状態機械関数型言語であらわす,みたいな話で,どうもStateモナドなどと関係ありそう,だけどReactive Programming,Reactiveなコンパイラの話とは関係なさそうなので,この論文は保留かな.

hnagoyahnagoya 2008/04/29 11:06 通りすがりの者で恐縮ですが、該当論文の「不動点」はhttp://en.wikipedia.org/wiki/Domain_theory
のような文脈でのfixed pointではないかという気が…数値計算でのfixed pointとは(うんと抽象的な理論のレベルではさておき)別物ではないかと。数値じゃなくて関数が不動点なんですよね。

hoge1e3hoge1e3 2008/04/29 20:26 ご指摘ありがとうございます.
やっぱりこれはfixed-point operator のようですね.ご紹介のページにcomplete partial orders(cpo) の話も出ていますし.勉強不足でした.

2008-04-24

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 ?

msakaimsakai 2008/04/26 23:16 この CPO は complete partial order です。

hoge1e3hoge1e3 2008/04/27 00:06 ありがとうございます.調べてみます