2002-12-07
λ. 補講が2つもあったのに寝坊して行けなかった。ダメだ……
λ. 関係ないが、「プレデター」って言ったら「リン・クロサワ」。
その通り!! たしか中尉でしたっけ?
λ. Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources
を読んだ。メモリ管理も奥が深いよね。
2004-12-07
λ. Hypersetの使い方
何か正しいExampleをとのことですが、Haskellレベルでの循環的な定義はサポートしてないので、循環的な定義をするには代わりに decorate :: (Ord u) => Graph -> Tagging u -> Decoration u や solve :: Ord u => SystemOfEquations u -> Solution u を使います。
decorate はグラフのデコレーションを求める関数です。グラフの表現はData.Graphのものを使っていて、デコレーションは頂点をインデックス、集合を要素とする配列として表現しています。Tagging u は子を持たない頂点に対して空集合ではなくurelementを割り当てるのに使うFiniteMapです。例えば、decorate (listArray (0,2) [[0,1,2],[],[]]) (unitFM 2 0) ! 0 とすると、A = {A,{},0} という集合が得られます。
solveの方は等式系(system of equations)の解を求める関数です。等式系は、左辺の変数をインデックス、右辺の集合を要素とする配列で表現しています。ただ、右辺の集合はurelementとして変数を追加しているので、型が Set u ではなく Set (Either u Var)) になってます。例えば A = {A,B,0}; B = {} という等式系は listArray (0,1) [fromList [Left (Right 0), Left (Right 1), Left (Left 0)], empty] となります(あんまりにもあんまりなので、何とかしたいなぁ)。これを x とすると、solve x ! 0 で先ほどと同じ集合 A = {A,{},0} が得られます。
λ. ミーティング
誰も集まってくれないのは何故。しょぼーん。
λ. 『NHKにようこそ! 2』, 大岩 ケンヂ [画], 滝本 竜彦 [原作]
を読んだ。
2006-12-07
λ. Applicative Programming with Effects by Conor McBride and Ross Paterson
Monad(Strong Monad)とArrowの間に位置する抽象化だとか、コンビネータのSとKを抽象化したものとかいう話は耳にしてたけど、期待していたよりも面白かった。以前に書いた行列のコードなんかは、これを使って整理できそうだ。
圏論の言葉でいうと Applicative は strong lax monoidal functor になっているということなのだが、(モナドでない)一般の関手の場合のstrengthの「standard equations」なんて知りませんから!(後で調べる)
<2007-03-04追記>
standard equations は
![\xymatrix{ I\otimes TA \ar[r]^\tau \ar[dr]_{l} & T(I\otimes A) \ar[d]^{T(l)} \\ & TA }](tex/16e31b29bc90814483d875df042cbbac.png "\xymatrix{ I\otimes TA \ar[r]^\tau \ar[dr]_{l} & T(I\otimes A) \ar[d]^{T(l)} \\ & TA }")
と
![\xymatrix{ (A\otimes B)\otimes TC \ar[rr]^\tau \ar[d]_\alpha && T((A\otimes B)\otimes C) \ar[d]^{T(\alpha)}\\ A\otimes (B\otimes TC) \ar[r]_{\mathrm{id}\otimes\tau} & A\otimes T(B\otimes C) \ar[r]_\tau & T(A\otimes (B\otimes C)) }](tex/25eba9f9b3159faaa11963eb91c4627d.png "\xymatrix{ (A\otimes B)\otimes TC \ar[rr]^\tau \ar[d]_\alpha && T((A\otimes B)\otimes C) \ar[d]^{T(\alpha)}\\ A\otimes (B\otimes TC) \ar[r]_{\mathrm{id}\otimes\tau} & A\otimes T(B\otimes C) \ar[r]_\tau & T(A\otimes (B\otimes C)) }")
の二つだろう
</2007-03-04追記>
それから「Note that B and FC swap places in the above diagram: strong naturality implies commutativety with pure computations.」という部分を理解するのにちと苦労した。
あと、最後のexerciseの「fmap swap (pure x ★ u) = u ★ pure x」の証明が案外面倒だった。もっと短く出来ないかな。
[lemma]
pure (f . g) <*> x
= {- homomorphism -}
pure (.) <*> pure f <*> pure g <*> x
= {- composition -}
pure f <*> (pure g <*> x)
fmap swap (pure x ★ u)
= {- definition of ★ -}
fmap swap (pure (,) <*> pure x <*> u)
= {- homomorphism -}
fmap swap (pure ((,) x) <*> u)
= {- definition of fmap -}
pure swap <*> (pure ((,) x) <*> u)
= {- lemma -}
pure (swap . ((,) x)) <*> u
= pure (\y -> swap (x,y)) <*> u
= pure (\y -> (y,x)) <*> u
= pure (\y -> (\f -> f x) ((,) y)) <*> u
= pure ((\f -> f x) . (,)) <*> u
= {- lemma -}
pure (\f -> f x) <*> (pure (,) <*> u)
= {- interchange -}
pure (,) <*> u <*> pure x
= {- definition of ★ -}
u ★ pure x
いや、「The Monoidal laws and the above definition of pure imply that pure computations commute past effects: fmap swap (pure x ★ u) = u ★ pure x」と言っているのだから、Applicativeの性質からではなく strong lax monoidal functor の性質から示すべきか。むむむ……
<2007-03-04追記> strengthを明示的に使ってはいないが、こんな感じか。
fmap swap (pure x ★ u)
= {- definition of pure -}
fmap swap (fmap (\_ -> x) unit ★ u)
= fmap swap (fmap (\_ -> x) unit ★ fmap id u)
= {- naturality of ★ -}
fmap swap (fmap ((\_ -> x)×id) (unit ★ u))
= fmap ((\y -> (y,x)) . snd) (unit ★ u))
= {- left identity -}
fmap (\y -> (y,x)) u
= {- right identity -}
fmap ((\y -> (y,x)) . fst) (u ★ unit)
= fmap (id × (\_ -> x)) (u ★ unit)
= {- naturality of ★ -}
fmap id u ★ fmap (\_ -> x) unit
= u ★ fmap (\_ -> x) unit
= {- definition of pure -}
u ★ pure x
</2007-03-04追記>
あと、「pure f <*> x1 <*> x2 <*> … <*> xn」を「iI f x1 x2 … xn Ii」と書けるようにする方法は Idiomatica.lhs に詳しい。しかし、こういうこと考えるやつは頭おかしいと思う……
λ. 『伝わる・揺さぶる!文章を書く』 (山田 ズーニー 著)
を読んだ。
2007-12-07
λ. A brainf*ck interpreter in Prolog
ふと、現実逃避にPrologでBrainf*ckの簡単なインタプリタを書いてみた。
brainfuck(Src) :- bf(Prog, Src, []), !, seq(Prog, []*[0], _).
bf([]) --> [].
bf([X|Y]) --> bf1(X), {!}, bf(Y).
bf(X) --> [_], bf(X).
bf1('>') --> ">".
bf1('<') --> "<".
bf1('+') --> "+".
bf1('-') --> "-".
bf1('.') --> ".".
bf1(',') --> ",".
bf1(w(X)) --> "[", bf(X), "]".
seq([], T, T).
seq([X|K], T1, T2) :- step(X, T1, T), seq(K, T, T2).
step('>', L*[X|R], [X|L]*R1) :- R=[_|_] -> R1=R ; R1=[0].
step('<', [X|L]*R, L*[X|R]).
step('+', L*[X|R], L*[Y|R]) :- X=255 -> Y=0 ; Y is X+1.
step('-', L*[X|R], L*[Y|R]) :- X=0 -> Y=255 ; Y is X-1.
step('.', L*[X|R], L*[X|R]) :- put_byte(X).
step(',', L*[_|R], L*[X|R]) :- get_byte(X).
step(w(W), T1, T2) :- while(W, T1, T2).
while(W, T1, T2) :-
T1=_*[0|_] -> T1=T2 ; seq(W, T1, T), while(W, T, T2).
多分一番メジャーなProlog処理系である SWI Prolog で実行してみる。
% pl
?- consult(brainfuck).
% brainfuck compiled 0.00 sec, 9,300 bytes
Yes
?- brainfuck("
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.").
Hello World!
Yes
?-
どうせなので、ファイルから読み込んで実行することも出来るようにしてみる。
brainfuck_file(FileName) :- readfile(FileName, X), !, brainfuck(X).
readfile(FileName, Str) :-
see(FileName), get_byte(B), readfile_loop(B, Str), seen.
readfile_loop(-1, []) :- !.
readfile_loop(H, [H|T]) :- get_byte(B), !, readfile_loop(B, T).
それはそうと、Brainf*ckって日本語訳するとやっぱり「脳姦」になるのだろうか? なんというか、氏賀Y太あたりの描くグロ絵を連想してしまって非常にアレでございます。(今回のエントリは実はこれを書きたかっただけ。← 最低です)
【2008-03-27】 WAMのindexing最適化によって不要になるカットを取り除いた。
2008-12-07
λ. 風邪でダウン中 (4)
熱も下がったし、お腹もだいぶ良くなってきたけど、相変わらずダウン中……
λ. ２次補正提出首相先送り表明 『ねじれ』足かせ 廃案回避へ苦渋
国会法の規定で通常国会は一月三十一日までに開会しなければならず、事実上、今国会は来年一月二十九日までしか延長できない。同二十九日までに「みなし否決→再可決」を行うには、関連法案を十一月三十日までに衆院通過させる必要があるが、既にそれは不可能だ。
二次補正を通常国会に先送りする理由がどうもわかり辛かった*1けど、こういう事情もあったのね。これは面白い。 そういえば、ちょっと前に「伊藤洋一のRound Up World Now!」か何かで、与野党の信頼関係が失われているのが問題というような意見があったが、これは与野党の信頼関係が失われていることによる実害の非常にわかりやすい例だと思った。
*1 もちろん、金融機能強化法改正案の通過が前提というのは、それはそうなんだけど……
λ. ゴーストシップ
ホラー映画としてはいまいちだったけど、殺戮のシーンは全般的に良かったな。 例のワイヤーのシーンだけでなく、鍋に劇物をドバドバ投入してるシーンとかも結構好きだ。
