素人くさいSICP読書会に参加し始めた．いま４章のLISPインタプリタのところ，4.2.2 遅延評価とメモ化を実装したメモ化しておけばfibonacciを (define (fib x) (if (みたいなナイーブな実装で書いてもちゃんと高速に動く...はずだが，なんか私が書いたものだ…

http://portal.acm.org/citation.cfm?id=504294&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749IBMのTRLの人が書いたらしい． 1. INTRODUCTION データベースのクエリ・ビューを，データが変わったときに動的に更新したい． 高速な手法も提案されている…

http://portal.acm.org/citation.cfm?id=103137&dl=GUIDE&coll=GUIDE&CFID=65531524&CFTOKEN=43210749この論文に書いてあるような言語を作ろうとしていたところだった． 1 . INTRODUCTION Incremental(Reactive) Computation のいろんな応用例 Program Devel…

Reactiveなプログラム例として，ゲームが載っている．次の5つの状態がある． Quiet: 「Insert Coin」と出ている画面 Start: Coin1個いれるとこの画面になる．「Ready」ボタンを押すまで待機 Wait : 「Ready」を押すとこの画面になり，ランダムな時間待たされ…

昨日の論文において「関数型言語は不動点計算に向かない，なぜならエンコードしなければならないから」的なことが書かれていたので，不動点アルゴリズムについて調べてみた 不動点アルゴリズムと収束性 これが繰り返しの４２番目のデータとして、表示される…

Reactive Functional Programming の論文を読んでみたけど，むずい． 1. Introduction The control structure needed for reactive programs is inherently iterative, not recursive. Reactiveなプログラムにはiterative（繰り返し？） な制御構造が必要で…

最近にわかにReactive(Incremental?) Programmingが流行っているきがするReactive Ruby : RubyでReactive Programmingしてみた 最近、実用的なコードばかり書いているので、もっと役に立たないコードを書くべきだと思い、 Reactive Rubyというライブラリを作…

CSVとか，RDBとか，XMLとかいろんなデータの寄せ集めにおいて，データの整合性をチェックする仕組みを模索していたら，「いいかげんなデータの整合性をチェックする」手法ではなくて「いいかげんな要求仕様の整合性をチェックする」手法がひっかかった． Han…

仕事で1000万件超のデータを扱っているという知り合いから，データベースについていろいろと聞いてみた． データベースを速くするコツは? DBサーバとアプリケーションサーバを分けると24時間かかっていたものが2時間になった おそらく，1つのタスクに集中し…

from ACM Computing Surveys (CSUR).サーベイ論文というのは名前には聞いていたがこれくらい徹底してやるものだったとは．いろんな言語における型の健全性を調べているのだが データベースの側面から，どういう型の性質が求められているか オブジェクト指向…

Dynamicの機構の似ているような違うような機構でFunctional Reactive Programming というものもある． 電子回路とかロボット制御に使われているらしい．ある瞬間における電圧とかアームの位置とかを，時間t の 微分方程式で表現するそうだ 4th International…

例の代入可能な関数型言語について， http://www.kmonos.net/wlog/83.html#_2259080315 http://d.hatena.ne.jp/NyaRuRu/20080314/p1 Mathematica は Dynamic と書くと自動的に値の更新を検出するらしい，要するにExcelぽくふるまうらしい一度標準出力(?)に表…

宣言された変数に対して，順番にアドレスを確保していくコンパイラ Parse> r "var a; var b; a=3; b=a+2;" Loading package parsec-2.0 ... linking ... done. Found value[ ["VarDecl","0"], ["VarDecl","1"], ["0","3","=","POP"], ["1","0","Read","2","+…

module Map where put :: (Eq k) => [(k,v)] -> k -> v -> [(k,v)] put nk nv = [(nk,nv)] put ((k,v):rest) nk nv = if (k==nk) then (nk,nv):rest else (k,v):(put rest nk nv) get :: (Eq k) => [(k,v)] -> k -> Maybe v get k = Nothing get ((k,v):rest…

ひさしぶりにParsecをいじってみた．前回，(http://d.hatena.ne.jp/hoge1e3/20080129) var a; a=3; var b; b=a+3; というプログラムがあったときに，a や b にアドレスを割り付けたい，と言ったので，この部分の実装をやろうとした，が失敗． var a; という…

久しぶりに JDTのソース を読み進めてみる，けど違うパッケージを読んでみるorg.eclipse.jdt.core.domDOM というとXMLとかHTML のものという印象が強いけど，やっぱりJava にもあるのか ... ... ... こんな感じで，クラスの中に field とか method とかを，…

Attribute Grammars を読んでみる．これの22ページあたりに出てくる文法をとりあげてみる． Symbol-table を毎回書かなければいけない add-item て？ 副作用があっていいの？ ::= program is Symbol-table() ), program), empty-table) ::= begin end Symbol…

上の例のかわりに Parse> r "var a; a=3; var b; b=a+3;" Found value[ [ ],["1001","3","=","POP"],[ ], ["1002","1001","Read","3","+","=","POP"] ] Parse> みたいに出したい．つまり，var a や var b のための領域(上では1001 と 1002 )を確保して，その…

Parsec で作る簡単なコンパイラ． 結局，字句解析のかわりに tok str というあやしいコンビネータ（str を読んで，その後ろのスペースをとばす） を定義 コード生成部は toCodable クラスを使う．これで，命令のリストが作られる． toCodable :: a -> CodeSt…

HaskellでtoString - 西尾泰和のはてなダイアリー にて，この前の 「Haskell で toStringを定義する方法 」を書いてくれた．確かにtoString は実装できるのだけど，すでに show という手段があるのだから， 通常はデフォルトのshow を使って ある一部のクラ…

代入式らしいものは書けるようになった．あと型クラスを使って toCode （コードを生成する関数）を実装してみる．うーんやっぱり 型なのに「instance」と書くのはまだ抵抗がある．あと Foo {bar:: Int} という記法は扱いがすごい面倒なことがわかった．特に…

Why Attribute Grammars Matter というページを見つけた．日付が01-07-05 なんだけど，これは 2001年7月5日か，2005年1月7日かわからない．まだ読み始めたばかりだけれど，中央付近にあるグラフがなんかあやしい．リスト構造の逆をたどるともっと柔軟にデー…

字句解析の方法がわからん，というかややこしすぎ．http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.htmlのセパレートスキャナってなんだろ．仕方なく spc とかいうあやしい文法をはさんでいる JavaでいうtoString の作り方がわからない show b::B…

ちょっとParsecをいじってみた．整数定数の足し算と引き算の式，変数宣言が書ける（宣言できるけど使えない）．計算をせずにASTだけを出力する． import Text.ParserCombinators.Parsec --main r :: String -> String r input = case parse source "lisp" in…

Sublinear-space evaluation algorithms for attribute grammars という論文を見つける．1987年もの．attribute grammar というのは死に絶えた技術なんだろうか，それはさておき ROOT -> exp exp.env = φ exp -> exp + exp exp1.val = exp2.val + exp3.val e…

パーサジェネレータって， パーサジェネレータの持つ言語（文法定義) JavaとかCとかの一般的な言語 という2重の言語が必要だなー，と思っていたら，これがあったことを思い出す．Parsec はパーサジェネレータじゃないから確かに単一の言語（Haskell)で書ける…

上の論文は，XQuery についても言及している．たぶんXML文書を変更したときに，XQueryに対する検索結果をインクリメンタルに変える，という仕組みも提供しているらしい．XQueryの文法をしらなかったのでこのへんを読んでみた． for $i in document("Tutorial…

Consistently updating XML documents using incremental constraint check queriesある XML 文書とそのXML Schema を与えて，XML文書の変更があったとき，XML Schemaを満たしているかどうかを，差分を検出して高速に行うものらしい．すべての言語をXML と X…

で，Haskell は詳しい構文を知らない．あと$ が出てくるとパースできなくなるへたれなので，構文糖を除きまくった苦い Haskell ができあがると予想． S := def* def := NAME '=' expr expr := elem+ elem := NUM | NAME | '(' expr ')' | lambda lambda := '…

いろんな言語でHaskell の処理系を作ってみるという企画．私はJavaで作るといって申し込んだけど，実は Java を用いて Tonyuで書かれたHaskell パーサを生成 Tonyu でがんばってグラフ簡約のアニメーション というのをできればやってみたい．