2001-11-22
λ. 読書
- 「X」第17巻
- CLAMP[著]
- 「天子な小生意気」第11巻
- 西森博之[著]
- 「少女革命ウテナ - 青の双樹」
- ビーパパス・さいとう ちほ[原作] さいとう ちほ[イラスト]
λ. X11R5 & exterm
/.Jの「国際化された XTerm を目指して」という記事のスレッドを読んで、X11R5の頃の事とかextermの事を知った。
というわけで、ftp://ftp.x.org/pub/R5/contrib-1.tar.Zをダウンロードしてきてextermのソースを入手。
過ぎ去った時間は取り戻せないし、これらが再び使われるようになることは多分無い。だからこそ、せめて記憶には留めておこうと思った。
λ. 今日の英語: use, boiled down
- What's the use of being citizen, if you don't get equal right?
- The editor-in-chief boiled down her lengthy report to just a few paragraphs.
2003-11-22
λ. 借りた本
- 『赤緑黒白』
- 『臨機応答・変問自在 2』
- 森 博嗣 [著]
- 『大人のための残酷童話』
- 倉橋 由美子 [著]
- 『犬儒派だもの』
- 呉 智英 [著]
λ. コンパイラの作り方
抽象機械のコードを出力するところまで読んだ。そういえば、レジスタが足らなくなったらどうするんだろう。
2004-11-22
λ. RegEx Tシャツ
「軽量言語の次はこれ！」らしいですよ。
http://explanation-guide.info/image/180px-Airkz_20040617_jon_regular_expression.jpg.html
λ. Bisimulation Algorithm
このままじゃ恥ずかしすぎるので、hyperset.rb(と未公開のHaskell版実装)を直そうと思いたったのだけど、また自分で考えると何か間違えそうなので、既存のアルゴリズムを探すことに。そこでGoogle先生に尋ねると A. Dovier, C. Piazza, and A. Policriti. A fast bisimulation algorithm. TR UDMI/14/00/RR, Udine, 2000. というのがあったので、これを使わせてもらおう。Non-Wellfounded な場合にはそうやってrankを定義できるのかぁ。なるほど、なるほど。
で、Haskellで試しにコードを書いてみようとしたのだけど、Paige-Tarjan の手続きを呼ぶとしか書かれてない部分があって困ってしまった。R. Paige and R. E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973-989, 1987. に書いてるらしいのだが、この論文Web上にはないし、調べるの面倒なので、試しにこれ抜きでやってみる。幾つかの例を試すとこれでも正しく動作しているように見えるが……ダメな例を早速発見。Ω={Ω} として、α = {Ω,φ} と β = {Ω,φ,{Ω,φ}} が区別できないな。この二つは共にrankが1で、rankがこれより小さいのはrankが−∞のΩとrankが0のφ。α,βは共にΩとφを含んでいるので、Ωとφによる分割だけではα,βは区別できない。同じrank内でさらに分割する必要があるけど、それにはどうしたら良いのかなぁ。うーむ。
何が足りないのかとしばし悩んで(足りないのは Paige-Tarjan の手続きに決まってるけど)、{{Ω},{φ},{α,β}} という分割(によって定義される同値関係)はstableでないことに気付く。
ちなみに、関係R⊆N×Nが与えられたとき、Nの分割Pの任意のブロックB1,B2に対して、B1⊆R-1(B2)とB1∩R-1(B2)=φのいずれかが成り立つとき、Pは関係Rに関してstableだという。あるいは、分割Pによって定義される同値関係を≡Pとして、(∀a,a',b∈N)((a≡Pa' ∧ a R b) ⇒ (∃b'∈N)(b≡Pb' ∧ a' R b')) という定義の方が直観的かな。
閑話休題。さっきの例だと N = {Ω,φ,α,β}, R = ∋ なので、P = {{Ω},{φ},{α,β}} だと、B1 = B2 = {α,β} としたとき、R-1(B2) = {y | x∈{α,β}, y∈N, y ∋ x} = {β} となってしまい、Pはstableな分割ではないことがわかる。maximal bisimulation はstableであるはずなので、この同値関係は大きすぎる(i.e. 分割が粗過ぎる)ことが判定できる。試しにstabilizationの処理を素朴に実装して見たら、αとβは区別できるようになったし、試した限りでは他の例でも正しく動いているように見える。
ということは、Paige-Tarjan の手続きってのはstabilizationのための効率的なアルゴリズムのことなのかな? (ぉぃ
……とか書いてたら、バークレイ大のCS 294-1: Model Checking, EE 219C: Computer-Aided Verificationという授業の講義資料に Graph Minimization というのを発見。まだ読んでないけどとても良さそう。
あと、A fast bisimulation algorithm の著者のサイト にC++のコードがあるのも発見。
2005-11-22
λ. Naxos Music Library (ナクソス・ミュージック・ライブラリー)
弟に教えてもらったサイト。月額1,890円でクラシックを聴き放題。無料で15分間試すことが出来る。俺は音楽をあまり聴かないので月額1,890円というのは微妙だけど、クラシックをよく聴く人だったらよさげかも。
【2006-04-23追記】 SFCでなら keio.ml.naxos.jp で利用できるようになったらしい。
関連
λ. A Cookbook for the Haskell XML Toolbox with Examples for Processing RDF Documents. Manuel Ohlendorf
をざっと読んだ。Haskell XML Toolbox (HXT) のデモンストレーションとしてRDF/XMLの処理を書く話。SPARQLのパーサ・処理系も実装してある。
2007-11-22
λ. OperaのiframeのcontentDocumentが変
MAD PEOPLE 用の発言ポップアップスクリプト が最近のOpera(Opera 9.21)で動かなくなっていたので調べたら、iframeの振る舞いが変わってしまっていた。 iframeからcontentDocumentでHTMLDocumentオブジェクトを取得し、その後そのiframeをremoveChildしたら、取得したオブジェクトがただのObjectになってしまって、HTMLDocumentとして操作できなくなってしまう。 昔のOperaはこんなことなかったんだけどなぁ。バグ?
ぐぐってみると、<URL:http://d.hatena.ne.jp/quaa/20070807#p1> に同じことが書いてあって、iframe.contentDocument.documentElement.ownerDocument として取得しておけば回避出来るようだ。
