Archive for June, 2006

購入まんが

Posted by on Friday, 16 June, 2006
>二ノ宮知子『のだめカンタービレ』 > >かもされています。 > >まあそれはともかく、いつもどおりで感想が書きづらい。久々の海ネタなのに、のだめとイチャイチャするだけになっていたのにはどうかと思いましたよ。いいんだけど。 > >青緑百句オチとは思ってなかったんで、あそこは笑った。 > >椎名高志『絶対可憐チルドレン』 > >なんでおれこれ買ってるのかちょっとわからなくなってきた。まあ好きですけれど。今巻では、ボーイフレンドができるネタは面白かった。妙にさっぱりしたオチなのだが、まあそれはいいか。キューティハニーの歌を微妙に変えて著作権に配慮しているように見えて「大きな古時計」ではちゃんと JASRAC 許諾をもらっているあたりがわけわかりません。これは大丈夫だろうと思ってたのかなあ。 > >のだめカンタービレ #15 (15)/絶対可憐チルドレン 5 (5) >
Category: Uncategorized  
Comments closed

ポイントフリースタイルとかメモリの話とか

Posted by on Thursday, 15 June, 2006
>ついでにこちらにも。 >http://d.hatena.ne.jp/lethevert/20060613/p3 > 確かにさしたる意味はありません。しかし、なんというのかな、関数なんだから引数なんていちいち用意したくないわけですよ。めんどくさいし。なんとなくやる。そういうイメージかな。 > >こないだのは基本的にジョークなのですが、ごく短い関数はポイントフリースタイルの方が綺麗に思える、ということです。関数合成のセクションとか出てきたら考えなおした方がいいと思いますが。 > >あと >メモリの話 >なんですが、なかなか難しそうです。 Clean 入門を読むと、 Clean では文字列は文字の非ボックス配列だそうなのでまだマシかもしれませんが、 Haskell は(遅延)リストなんですよね。めちゃくちゃ効率が悪いのです。そこはちょっと羨ましく思う。 > >この辺を改善するものとして、 >PackedString > とか >ByteString > とかがあるんですが、やっぱり基本はリストなんですよ。アルゴリズムは書きやすいんですが。せめて必要に応じて文字列の部分は最適化してくれないかなあー。 > >ちなみに、機能あのあと追記で書いた SHA1 も、内部的には PackedString を使っています(ByteString の方が速いらしいんですが今んとこ標準ではないので)。それにより若干高速化されています。 > >で、えーと話がちょっとずれましたがなんだっけ。そうそうメモリマップですが、そういえば mmap って Haskell にないよね。なんか ByteString にあったような気がしたんだけど気のせいだったかなあ……。 >
Category: Uncategorized  
Comments closed

関数型オブジェクト指向のススメ

Posted by on Thursday, 15 June, 2006
> >http://d.hatena.ne.jp/lethevert/20060615/p3 >
それなんて OCaml？ > >……まあそれはともかく、オブジェクト指向は役に立つと思うけど、犬とか猫とかを動物から継承するみたいな話は確かにクソの役にも立たんと思います。 > >でも、動物の袋をブッ叩いてアヒルかどうか判断するのは、残念ながら便利だと思うので、動物愛護の精神には欠けているかもしれません。あれ、違うんだっけ元々は。 >
Category: Uncategorized  
Comments closed

YouTube からアニメが消えている

Posted by on Thursday, 15 June, 2006
>らしい。 >http://news4vip.livedoor.biz/archives/50690029.html >
「わからないのか？　イレギュラーなんだよ。やりすぎたんだお前はな！」 > >……って言ってみたかっただけっ！ > >ふつうに考えると「何を今更」というのが正常な反応であって、ショックを受けるほどのことでもないだろうという気も。「これで誰も使わなくなるだろ」系の反応があってなんだそりゃと思う。YouTubeはもともと、自分で撮影したホームビデオなんかを友達とかに見せあいっこするといったサービスなんですよ。みんな忘れてるけどさ。だから、運営者としては、アニメを削除して利用者が減るのは悲しくもあるけれども、元のサービスに立ち返るくらいの感じなんじゃね。 > >で、試みに「Gundam W」で検索してみたら、確かに各エピソードの映像はかなりばっさり消えていた。 OP/ED は残ってたけど、これも消えるのだろうか。マッドは残ってほしいところではあるが、さて。 >
Category: Uncategorized  
Comments closed

Haskell とメモリ

Posted by on Wednesday, 14 June, 2006
>関数型言語脳に侵されていると、メモリ効率とかは比較的どうでもいいという考え方になってくる。そういうことは処理系が考えればいいので、プログラマはあんまり気にしなくてよくなる。 > >のだが、さすがにどうかと気になるところもあって、その辺の話。 > > >Crypto > というライブラリには MD5 値を計算する Data.Digest.MD5 というモジュールがあるのだが、ここで用意されているのは hash :: > >こないだの akr さんの発表ではないが、 MD5 値はファイルに対して計算することが多い。たとえば、現在あるディレクトリのなかのファイルの MD5 値を次々に計算していくというプログラムは次のようになるだろう。 > >import Control.Monad
import Data.Digest.MD5
import System.Directory

getHash fname =
do flag <- doesDirectoryExist fname
unless flag $ do c <- readFile fname
hash c `seq` return ()
main = do d <- getDirectoryContents "."
mapM_ getHash d > >この場合、ファイル全体の文字列を持つことになってしまう。確かに本来的には必要ないが、ちゃんと GC できないようで、利用するメモリ量は際限なく増えていき、ロードアベレージが上昇していく。これでは、さすがに使いものにならない。 > >で、 ruby だとこう書ける。 > >require 'digest/md5'

Dir.new(".").each do |fname|
unless FileTest.directory?(fname)
dgst = Digest::MD5.new
File.open(fname) do |fio|
buf = ""
dgst << buf while fio.read(256, buf)
end
end
# puts dgst.hexdigest
end > >これは Ruby リファレンスマニュアルからの借用。ファイルごとに MD5 オブジェクトが作られるのがちょっと嬉しくないがそれはさておき、この方式だとファイルまるごとを持つ必要がなく、実際、ほとんどメモリも必要とせずに動作を完了する。 > >MD5Aux の中からもうちょっと使い勝手のいい部分を取り出し、適当な文字列の断片を追加していく方式が望ましいように思うのだが、さて、どうしたものか。 > >追記: とりあえず SHA1 のコードを見たらわかったので、それをもとに作ってみた→ >http://www.city5.org/haskellprog/SHA1.hs >。短いコードではじゃっかん遅くなるが、ある程度の長さであれば文句なしに速くなった(いろいろ無駄を省いたからだろうけど、速いのは)。あと、速くなったといっても他言語にくらべれば重たいので、実用的にはやっぱ OpenSSL とかを使った方がいいのかなー。 >

Category: Uncategorized  
Comments closed

ポイントフリースタイル

Posted by on Tuesday, 13 June, 2006
>2つのリストが等しいかどうかを比較したい。ただし、一方が他方より短い場合、短い方に合わせるとする。 “abcdef” == “abc” が等しいようなイメージ。こういうケースは結構あるんじゃないかと思う。 > >どうするかっていうといろいろやり方がある気がするが、単純には zipWith で作れる。なかなか面白い。 > >listEquals l1 l2 = and $ zipWith (==) l1 l2 > >さて、これをポイントフリースタイルで書きたい。つまり、引数の l1 とか l2 とかを消したい。 > >これが引数ひとつの場合は簡単だ。関数合成演算子の (.) があって、 > >f . g = \a -&gt; f (g a) > >になっているからこれを使う。上のように二引数だとどうだろう。実際に考えてみよう。まず、 > >c2 f g = \a1 a2 -&gt; f $ g a1 a2 > >と書くところから始めよう。 > >この定義から、まず a2 を削れることがわかるだろう。 > >c2 f g = \a1 -&gt; f . g a1 > >ここからがちょっとポイントだが、これは次のように書ける。 > >c2 f g = \a1 -&gt; (f.) $ g a1 > >この (f.) はセクションである。とすると、 a1 も追い出せる。 > >c2 f g = (f.) . g > >うむ。 > >したがって元の話題に戻ると、 > >listEquals = (and.) . zipWith (==) > >である。美しい。 > >さらにさらに。 g が3引数関数だとどうなるか。 > >c3 f g = \a1 a2 a3 -&gt; f $ g a1 a2 a3 > >これは、 > >c3 f g = \a1 a2 -&gt; f . g a1 a2 > >ゆえに > >c3 f g = \a1 a2 -&gt; (f.) $ g a1 a2 > >であるから、 c2 を使って、 > >c3 f g = c2 (f.) g = ((f.).) . g > >となる。 > >これを繰り返せば、任意の引数の数に対して、 (.) を使ってポイントフリースタイルで書けそうだ。逆に言うと、この形式のものは、 g が複数引数であるような関数合成であるということか。 > >ではつぎに、 f も引数を取るケース。 > >cb f g = \a1 a2 -&gt; f a1 (g a2)
= \a1 -&gt; f a1 . g > >ここまでは簡単だが、これはちょっと面倒くさい。 a1 を右側に持ってきたい。 flip が使えそうだ。 > >= \a1 -&gt; flip (.) g $ f a1
= flip (.) g . f > >では f が2引数だとどうなるか。 > >cb2 f g = \a1 a2 a3 -&gt; f a1 a2 (g a3)
= \a1 a2 -&gt; f a1 a2 . g
= \a1 a2 -&gt; flip (.) g $ f a1 a2
= \a1 -&gt; flip (.) g . f a1
= (flip (.) g .) . f > >んじゃさらに、 f の第一引数に関数 g が適用され、第二引数には関数 h が適用されるような場合。 > >branch f g h = \a1 a2 -&gt; f (g a1) (h a2)
= \a1 -&gt; f (g a1) . h
= \a1 -&gt; flip (.) h $ f (g a1)
= \a1 -&gt; flip (.) h $ (f . g) a1
= flip (.) h . (f . g) > >f も引数欲しい。 > >branch' f g h = \a1 a2 a3 -&gt; f a1 (g a2) (h a3)
= \a1 a2 -&gt; f a1 (g a2) . h
= \a1 a2 -&gt; flip (.) h $ f a1 (g a2)
= \a1 a2 -&gt; flip (.) h $ (f a1 . g) a2
= \a1 -&gt; flip (.) h . (f a1 . g)
= \a1 -&gt; flip (.) h . (flip (.) g (f a1))
= \a1 -&gt; flip (.) h . (flip (.) g . f) a1
= (flip (.) h .) . (flip (.) g . f) > >また、 h が2引数関数の場合。 > >branch'' f g h = \a1 a2 a3 -&gt; f (g a1) (h a2 a3)
= \a1 -&gt; (f (g a1) .) . h
= \a1 -&gt; ((f . g) a1 .) . h
= \a1 -&gt; flip (.) h ((f . g) a1 .)
= \a1 -&gt; flip (.) h ((.) ((f . g) a1))
= \a1 -&gt; flip (.) h (((.) . (f . g)) a1)
= flip (.) h . ((.) . (f . g)) > > >まとめ >: セクションに (.) を利用すると簡単に難読化できます。ポイントフリースタイルは、用法、用量を守って使いましょう。 > >……ところでこれ、合ってるのかな……。 >
Category: Uncategorized  
Comments closed

concurrent haskell

Posted by on Tuesday, 13 June, 2006
>Concurrent Haskell の動作をチェックしてみた。まず、いちばん基本となる関数が forkIO と forkOS で、どちらも IO () -> IO ThreadId の型を持つ。違いは、 forkIO は仮想機械レベルの並列計算なのに対して、 forkOS は OS のネイティブスレッドを使う。そのため、 forkOS の方は ghc を -threaded でコンパイルしないと動かないといった制約がある(runhaskell や ghci では動作しないようになっている)。そういった差はあるが、下記のレベルではどっちでも差はない。 > >というわけで、まずは動作例。 > >do forkOS (mapM_ (putStrLn "child") [1..10])
mapM_ (putStrLn "parent") [1..10] > >こいつは、子スレッドが10回「child」と書き出し、同時並列的に親が「parent」と書き出す。これは悪くないのだが、親は子の終了を待たないので、実際にこれをやると、 child がぜんぶ出力される保証がない(forkIO を使って対話環境で実行すると、親スレッドが終了したところでプロンプトに戻ってしまい、プロンプトで何かやると、次の計算に、前の子スレッドの実行が混ざるようになる)。 > >これじゃ困るのでスレッドの終了を待ちたい。ただ、 pthread の API と違って、 fork* の返り値である ThreadId はその目的には使えない。これには MVar を使う。 MVar は、「変数の置き場」みたいなもので、 IORef に似ているが、「何もない」状態にすることができる(IORef (Maybe a) に似てるか)。 MVar を読むと変数が「取られ」空になったりする。もし空なら、そのスレッドの動作はブロックするから、これを使えば子スレッドの終了を待つことができる。 > >do v &lt;- newEmptyMVar
forkOS (mapM_ (putStrLn.("child "++).show) [1..10] &gt;&gt; putMVar v 0)
mapM_ (putStrLn.("parent "++).show) [1..10]
takeMVar v > >newEmptyMVar は、空っぽの MVar を作る(初期値を指定する newMVar などもある)。 MVar に値を「置く」のが putMVar で、読み込むのが takeMVar だ。実際には、読み込むが値を「取る」ことをしない readMVar というのもある。 > >さて、こうやってスレッド間で通信をするわけだが、 MVar は1つの要素しか持たないという制約があるから、新しい値を置こうとするとブロックしたり、古い値を消すハメになったり、といった問題がある。なので、どんどん値を追加していく、いわばチャンネルが欲しいこともある。そのためのものが Chan だ。 > >do ch &lt;- newChan
forkOS (writeList2Chan ch [1..100])
loop ch
where loop ch = isEmptyChan ch &gt;&gt;= flip unless (readChan ch &gt;&gt;= print &gt;&gt; loop ch) > >Chan にも MVar と同じような API が用意されているが、特徴的なのは writeList2Chan というのがあることか。リストをまるごとチャンネルに書き出す処理を行っている。どうでもいいが、このサンプルで writeList2Chan を forkOS する意味はあんまりない。 > >ここで、1つのチャンネルを複数のスレッドから読み込むことを考える。同じものを読み込むわけだから、一方のスレッドで読むと、もう一方のスレッドでは、その次の要素が読まれる。つまり、値を奪いあうわけだ。だから、こうなる。 > >do v &lt;- newEmtpyMVar
ch &lt;- newChan
forkOS (writeList2Chan ch [1..10])
forkOS (loop "child" ch &gt;&gt; putMVar v 0)
loop "parent" ch
takeMVar v
where loop suf ch = isEmptyChan ch &gt;&gt;= flip unless (readChan ch &gt;&gt;= putStrLn.(suf++).show &gt;&gt; loop suf ch) > >parent と child が交互にあらわれるが、数値そのものは1〜10が1度ずつしか出ないことがわかるだろう。 > >さて、このままだと、複数のスレッドに同時に値を伝えるようなブロードキャストをするのがメンドくさい。この目的のため、チャンネルを複製することができる。 > >do v &lt;- newEmptyMVar
ch &lt;- newChan
ch' &lt;- dupChan ch
forkOS (writeList2Chan ch [1..10])
forkOS (loop "child" ch' &gt;&gt; putMVar v 0)
loop "parent" ch
takeMVar v
(loop の定義は略) > >child と parent のそれぞれが 1〜10を出力することがわかるだろう。 dupChan は空のチャンネルが作る。しかし、作られた新しいチャンネルともとのチャンネル、どちらかに書き込まれたデータはどちらのチャンネルからも読めるようになる。書き込み側では ch に書き込んでいるが、 ch' からもデータを読めるようになるわけだ。 > >ところで、 writeList2Chan は最近のマシンでは一瞬で終わってしまうので、 > >forkOS (writeList2Chan ch [1..10])
ch' &lt;- dupChan ch > >と順序を変えると、 dupChan で複製する前に書き込みが完了してしまって、 ch' は空のチャンネルになってしまい、 child は何も出力しない。 > >そういえば Control.Concurrent.STM というのもあるのだった。こちらは未見。 >
Category: Uncategorized  
Comments closed

NEWスーパーマリオブラザーズ

Posted by on Tuesday, 13 June, 2006
>オールクリア！　正直、ラスト近くはしんどかった。コインも8割方集めるくらいまではパズルっぽい楽しさがあるのだが、最後の取りこぼしはマメマリオとかカメとかにならないと取れないとかいった、ほとんど苦痛なやつばっかりなので。まあ、総合ではよくできたゲームだと思いますが。 >
Category: Uncategorized  
Comments closed

Google Earth on Linux

Posted by on Tuesday, 13 June, 2006
> >http://earth.google.com/download-earth.html >。おお。 > >……と思ってダウンロード→インストールしたのだが、スプラッシュが出たところで止まって動きません。何が悪いんだ。 >
Category: Uncategorized  
Comments closed

「関数的なアンテナ」に

Posted by on Monday, 12 June, 2006
>はてな日記で「scheme」「Haskell」「OCaml」というキーワードを含む日記のリストを追加した。ちょっと前に Ruby Hotlinks を見て同じようなことをやっているのを見て、「おーなるほど」と思ったのを真似した感じ。 > >Clean と ML (SML) は省かれているけど、それは差別でもなんでもなく、ノイズが多いことを懸念したため。 SML はキーワード化されてませんね。 > >で、 Haskell キーワードで調べると、図らずも RubyKaigi のレポートが出るわ出るわ(笑)。 >
Category: Uncategorized  
Comments closed