2005-07-01 [長年日記]
λ. OCamlとタイプクラス
Haskellの一般的な実装(jhcを除く)では、dictionaly を追加的な引数として渡す形に変換することで部分コンパイルを実現しているし、最適化もそれなりに色々と出来ている。なので、OCamlでも同じようにすれば良いのにと思う。
言及されているメールで「That's a huge performance cost and it probably isn't too easy to optimise it away.」と書かれているのは、OCaml使いはこのレベルでは到底満足できないってことなのだろうか。
λ. ICPC国内予選
だるい、めんどい。
λ. 『四季 春』, 森 博嗣
を読んだ。森 博嗣 を読むのは久し振り。普通に面白かった。
2005-07-02 [長年日記]
λ. 『月光魔術団1 春の魔法使い』, 平井 和正
古本屋で見かけて、中学生のころ雑誌で紹介されていたのを思い出したので、読んでみた。犬神メイというキャラクタは多少面白いかもしれないが、文章のレベルが低すぎるな。
λ. 無記名投票での投票CO
人狼審問: (604)乾いた村の2日目に無記名投票での投票COの話が出ていた。メモ。
- 語り部 デボラ / (76)2005/06/23 13:07:05
- >>67
「無記名投票CO」について考えてみた。
・投票が複数あって、CO者の数が足りなかった場合、能力者が襲撃されたと考える事ができる。
しかし、後から「遅れて済まない、実はあと１人のCO者は俺だ」と出て来る事も十分考えられる（当然、その場合、彼は信用を勝ち取る努力をしなければならないが）。
また、複数投票があって（内訳が真によるもの１、人狼による１だったとする）後で真のみが名乗り出た場合、真は無用な疑いを被る事になる…。
λ. Backtracking, Interleaving, and Terminating Monad Transformers (Functional Pearl). Oleg Kiselyov, Chung-chieh Shan and Daniel P. Friedman and Amr Sabry
LtUより。
- 論文中のコード
- monad が strict だというのはどう定義されるのだろう?
- (2005-09-04 追記) 「runST (undefined >> return ())」 は Control.Monad.ST.Strict ではundefinedに、Control.Monad.ST.Lazy では()になるけど、これは関係ある?
- 「List as transformer can only be applied to commutative monads.」がちょっと良く分からない。
- (2005-09-07 追記) 単に「可換なモナドに適用した場合しかmsplitはちゃんと定義出来ない」ってことか。
- Prolog の cut は知ってるけど soft-cut なんてのもあったのか。
- (2005-11-01 追記) 「A *-> B ; C」か。そういえばそんなのもあったな。
(2005-09-30 追記) msplitは兎も角、interleaveやbindiはプリミティブとしてはイマイチ。例えば、「interleave a (interleave b c)」ではa,b,cは均等には実行されない。n個の計算を均等に実行するには結局msplitを使って別の関数を定義せざるを得ない。bindiもinterleaveの欠点を受け継いでいて、第一引数と第二引数の計算は均等には実行されない。……といって、どうすればいいかは良く分からんけど。
とりあえず、自分でもコンビネータをちょっと書いてみた。interleaveNはn個の計算を均等に実行するための関数、bindzは第一引数と第二引数の計算が均等(?)に実行されるbind。bindzは自然数の直積と自然数との全単射を作るときなんかに良くやるように、ジグザグに動く。
interleaveN :: LogicM m => [m a] -> m a interleaveN [] = mzero interleaveN ms = msplitL ms interleaveN bindz :: LogicM m => m a -> (a -> m b) -> m b bindz m f = loop m [] where loop m xs = do r <- msplit m case r of Nothing -> interleaveN xs Just (a,m') -> msplitL (f a : xs) (loop m') msplitL :: LogicM m => [m a] -> ([m a] -> m a) -> m a msplitL [] k = k [] msplitL (m:ms) k = do r <- msplit m case r of Nothing -> msplitL ms k Just (a, m') -> return a `mplus` msplitL ms (k . (m':))
2005-07-04 [長年日記]
λ. PArrows
PArrows is an arrows based parsing combinator library written in Haskell. The library is similar to Parsec, but arrows allow for more future optimizations.
メモ。モナドではなくArrowsをベースにすれば、Swierstra and Duponcheel のテクニックを使ってより効率的なパーサを書ける(参照: "Generalising Monads to Arrows")。自分もArrowsベースのパーサを書いたことはあるけど、こいつはJavaScriptのソースを生成できるのが面白いな。
(2005-09-28 追記) PArrow は Swierstra and Duponcheel のテクニックは使ってなかった。じゃ、どうしてParsecよりも速いんだろう?
λ. 今週のデスノート
シドウたん頭悪すぎて可愛い。萌える。
λ. 人狼審問 : (652)MMR出動だ！
ウケた。
2005-07-05 [長年日記]
λ. 安全保障論 (12)
今日の安全保障論は大塚海夫・一等海佐の講演だった。面白かった。
慶應が、「学問の府で現役自衛官を招くのは不適切」という訳の分からない理由で佐藤正久・一等陸佐の講演を中止した早稲田のような大学でなくて本当に良かった。
![[七夕っぽい?]](./images/20050707_0.jpg)
2005-07-12 [長年日記]
λ. 『さらば外務省!—私は小泉首相と売国官僚を許さない』, 天木 直人
を読んだ。はっきりいって下らない。
λ. Yicho: A Combinator Library for Program Calculation
Yicho is a monadic combinator library for supporting declarative specification of program transformation in Haskell. The combinator library uses higher-order patterns as first-class values which can be passed as parameters, constructed by smaller ones in compositional way, and returned as values. As a result, our library provides more flexible binding than simple ones, and enables more abstract and modular description of program transformation. Our library is developed by Template Haskell, a meta extension to Haskell 98.
メモ。
2005-07-13 [長年日記]
λ. 『経済物理学の発見』, 高安 秀樹
を読んだ。非常に面白い。ただ、著者のインフレに関する意見や政策的な主張にはあまり同意できなかったけれど。
2005-07-16 [長年日記]
λ. 人狼審問 : (625)憎しみの村
ここ2週間ほど参加していました。初の生存勝利なのでとても嬉しいです。エピローグに無事入れたときは緊張がほぐれたからか手が震えていました。
ケネス(hanasuiさん)が独り言でいいことを言っていたので引用。
占い師同士の論戦はＮＧだな。 論戦の勝者は真偽じゃなくて、 経験の有無で決まる。
- 関連リンク
2005-07-17 [長年日記]
λ. 人狼占い
某氏の日記より。狩人やったことないんだけど……
- さかいさんは 狩人 です！
狩人さんのあなたは、ズバリ「縁の下の力持ち」。普段はあまり目立ちませんが、ここぞというところで頼りにされるタイプです。黙々と体を張る姿を、誰かがちゃんと見ていますよ。
あなたは生まれつき特殊な力を持っていますが、その力は誰かを守るためだけに使いましょう。守ることを重んじるあなたには、いつか素敵な奇跡が起こるかもしれません。ラッキーワードは「機転」と「不言実行」。控えめに着実に経験を積んでいけば、確実に結果がついてきます。
さかいさんのモテ度は、51点です！
そんなあなたの本日の運勢はこちらです！
4位 ★狩人
地下にある店でお食事を
λ. 人狼審問 : (705)フルメタルジャケト村
みんなの大好きなフルメタルジャケットがテーマの村。ヲチしよう。
(2005-07-22 追記) 結局人数が集まらず廃村になってしまったようだ。残念。あと、軍曹といえば、バーチャルネットサージェント軍曹様３５歳もお勧め。
(2005-08-14 追記) (742)フルメタルジャケト村 は無事終了した模様。
λ. 『土地と日本人』 司馬遼太郎対談集
を読んだ。「司馬遼太郎、DQNだな」というのが最初の感想。資本主義だとか社会主義だとかそれ以前の問題。30年前の会話だとしても酷い。
2005-07-18 [長年日記]
λ. 『マンガ嫌韓流』
とりあえず予約。割とお勧め。韓国への反発を煽るつもりはないけど、韓国には「韓流」として喧伝されているような面だけでなく、こういった面もあるということは知っておくべきだと思う。まあ、まともな知識があったり、あるいはハン板やNAVERを見ている人には不要だろうけど。
- FAR EAST -極東-
- 作者のサイト
- 晋遊舎ONLINE: マンガ嫌韓流
- 出版社による公式サイト
- 脱・マンガ嫌韓流
- -
- 「嫌韓流」を韓国人が斬る・・・ 斬り!! :今だからこそ・・・ 韓国斬り !!
- -
- MyWiki.jp - マンガ嫌韓流のここがデタラメのここがデタラメ
- 「コモンズ社発行の『マンガ嫌韓流のここがデタラメ』に記載されている内容の間違いを指摘する為のページ」
2005-07-19 [長年日記]
λ. Central-European Functional Programming School
Varmo Vene: Signals and Comonads に興味があったのだけど、この講義の資料は公開されてないっぽいな。残念。……と思ったら、あった。Interp.tgz に含まれてるのか。後で読んでみよう。
- Varmo Vene: Signals and Comonads
-
「fby」は「followed by」の略で、「wvr」は「whenever」の略らしい。 ストリームを利用したプログラミングではよく出てくる演算子らしいけど、知らなくて最初何かと思った。
(2005-09-29 追記) 会場では Tarmo Uustalu1 and Varmo Vene. The Essence of Dataflow Programming (LtU) が資料として配布されていたそうで、そっちにはかなり詳しく書いてあった。面白い。
λ. るびま 0008 号
「おすすめのライブラリ」の話だけど、tsortはopen-uriやppほどじゃないけど何度か使ったことがある。少なくとも、resolve.rbよりは使ってる。
trapの話は知らかった。キャンセレーションポイントといえば Thread#kill や Thread#raise といったメソッドの問題をまず想像した。ちなみに、これは今非常によろしくなくて、例えばensureの中で実行がキャンセルされると悲惨なことに成りえる(e.g. [ruby-dev:23619])。[ruby-dev:23619]の問題に限って言えば、Mutex や ConditionalVariable をCで実装すれば解決できるのだけど、この問題の本質はRubyのスレッド/同期のプリミティブが compositionality を欠いているということなのだと思う。
それと、「だいたい、アプリケーションて 2 種類あると思うんですよ。IO をするスレッドというかプログラムと、計算をして黙り込んでいるプログラムがあると思うのですが、IO のほうは途中で止めるときは、自分でここは止まる可能性があると宣言するか、あるいはブロックするところで止まるのがいいのではないかと思うのですが。(中略) で、計算するほうはぷちっと殺してもいいことがありまして、それはそれでいきなり殺す、つまりキャンセレーションポイントを宣言しなくても殺せる意味で、この二つの使い方を両方サポートするにはどうしたらいいかということですかね」という点は興味深いな。
ちなみに、Haskellでは型によってIOアクションの実行と普通の計算を区別しているので、この問題には自然に対処出来ていると思う。IOアクションの実行に関しては普通にキャンセレーションポイントの概念を持っているのに対して、後者の普通の計算については(処理系的には)いつでもプチっと殺してしまえる。実際、STMモナド(see Composable memory transactions)では型によってIOアクションの実行が含まれないことが保障されているので、トランザクションに失敗した時点でプチっと実行をキャンセルして、後で再実行する。
「興味を持っているテーマ」のSQL(とRDB)のindexの話は面白いな。SQLのこうした発想は Data Structures Considered Harmful といった発想にも繋がっていたはず。(FIXME)
λ. 有限体GF(p)
ふと、有限体を扱うための簡単なライブラリが欲しくなったので、書いてみた(GF.hs)。有限体といっても、素体(prime field)だけで、拡大体(extension field)は扱えないけどね。
書いていて感じたのだけど、型クラスを compile-time prolog として使うと、本物の prolog との違いで結構はまるね。
それと、拡大体をこういうアプローチで扱うにはどうしたらよいのだろうか。原始多項式にどの既約多項式を使おうと結果は全て同型なわけで、既約多項式を明示するのは馬鹿らしい。標準的な既約多項式みたいなのはあるのだろうか? そして拡大体の元の標準的な表記法はあるのだろうか?
【2008-04-29 追記】 どう書く？orgの「法演算」のお題にnobsunが同様の方法を使って答えていたので、このコードも転載してみた。
2005-07-21 [長年日記]
λ. ブックバトン
佐野さんから何か回ってきた。僕は基本的に音楽を聴かない人なので、Musical Baton には答えられなかった*1けど、これなら答えられるな。(まだ書きかけ)
- 1. 何冊持ってるか？
- 高々有限冊。 数えたことはないけど手元にあるのは精々100冊程度ではないかと。
- 2. 今読んでいる本
- 読みかけの本は何冊かあるけど、今読んでいるのは『戦争請負会社』。
- 3. 最後に買った本
- 『迷宮百年の睡魔』(コミック)
- 4. 思い入れのある本
-
本に思い入れはありません……と言いたいけど、そうでもないな。 5冊に絞るのは難しいけど、印象に残っている本としては、こんな感じだろうか。
- 『よみがえる魔法の物語』
-
「はなはなみんみ」シリーズは小学生の頃の愛読書で、三作のうちで一番最初に読んだのがこの本でした。
- 『Conceptual Mathematics: A First Introduction to Categories』
-
圏論に触れた最初の本だし、初めて読んだ数学書(?)でもあります。
私が圏論や数学の面白さを知ったのは間違いなくこの本です。
- 『銀の三角』
- 『悪童日記』
- 『そして誰もいなくなった』
次点はこんな感じ。
- 5. バトンを投げる人
-
どんな本を読んできたのか聞いてみたい人を5人挙げさせてもらいました。 もし宜しければお願いします。 嫌だったら無視してください。
ψ 小熊善之 [書いたー。 5冊選ぶのが結構大変だった。]
ψ さかい [おー、ありがとうございます。 一体どんな本を読んだら小熊さんのような人間が出来るのかと期待していたのですが、期待に違..]
ψ 小熊善之 [東京に戻ってくる時に、25kg〜35kgの箱が80箱ありました。本だけで（笑）。その時からの増加分を考えると、多分あ..]
ψ ちゃた [こんな近くにはなはなみんみ読者がいたとは！しかも最終巻からって…]
ψ yuragi [答えましたよー。半分寝ながら(笑 中高生時代は乱読をしていたため記憶が定かでない部分は多いですが、とりあえず形にはな..]
ψ さかい [はなはなみんみ はもう内容はあまり覚えてないけど、当時は何度も読みました。 『よみがえる魔法の物語』から読んだのは何..]
2005-07-22 [長年日記]
λ. あるn(≧2)点を囲むような円があるとする。このとき、円をずらすことで、それらの点を全て囲んで、かつその内の2点が円周上にくるようにすることが出来る
反応が遅くなってしまって申し訳ない*1のですが、例の Circle and Points の問題で使った「あるn(≧2)点を囲むような円があるとする。このとき、円をずらすことで、それらの点を全て囲んで、かつその内の2点が円周上にくるようにすることが出来る」という性質について、sheepman さんから証明を頂きました。
なるほど、確かにそれで言えますね。シンプルで分りやすい証明だと思います。
それから、私はこの手の証明について良く知らないので、「数学の証明っぽくするには、点 A と円周との距離を d(A, S1) = inf{ |A - x| | x ∈ S1} で定義するだとか、円周は有界閉集合だから、inf を attain する点が存在するとか言えばいい」という点も「なるほど」と思いました。Sの肩に乗っている「1」は円の半径の1かな
*1 きっとこの辺りは音速が遅いのです ;-)
λ. Towards a monadic semantics of quantum computation, Thorsten Altenkirch
というのをたまたま読んだ。probabilistic computation をモナドで扱うのは自然な発想で理解できるのだけど、そこから先がいまいちよく分らなかった。量子計算について良く知らないんだから当たり前だが。
![\xymatrix{
& & & A \\
C \ar@{-->}[rr]_{\langle f_1, f_2\rangle} \ar@/^1pc/[urrr]^{f_1} \ar@/_1pc/[drrr]_{f_2} & & A\times B \ar[ur]_{\pi_1} \ar[dr]^{\pi_2} & \\
& & & B
}](tex/b5af5ec6d0a4982e073745f72f05eb79.png "\xymatrix{
& & & A \\
C \ar@{-->}[rr]_{\langle f_1, f_2\rangle} \ar@/^1pc/[urrr]^{f_1} \ar@/_1pc/[drrr]_{f_2} & & A\times B \ar[ur]_{\pi_1} \ar[dr]^{\pi_2} & \\
& & & B
}")
2005-07-24 [長年日記]
λ. can't compile Y-combinator (#1243982)
module Fix (fix) where
newtype T a = PsiInv{ psi :: T a -> a }
fix :: (a -> a) -> a
fix f = g (PsiInv g)
where g x = f (psi x x)
というコードをGHCでコンパイルしようとすると、GHCが停止しないという話。面倒くさくて報告していなかったんだけど、いい加減報告することにした。
…… known bug だったらしい(12.2. Known bugs or infelicitiesを参照)。うはwww、俺ハズカシスwwwwww
Secrets of the Glasgow Haskell Compiler inliner をざっと読んだ。負の位置に自分自身が出現するようなデータ型についてだけ処理を変えれば簡単に対処できると漠然と思ってたけど、Haskellがhigher-order polymorphismをサポートしていて、かつ種(kind)がvarianceを扱わない以上、それは確かに無理っぽいな。それと、mutual recursive なデータ型の存在は確かにまずそうだけど、どこが決定的に不味いのかまだ良くわからん……
【2006-01-18 追記】 ふと、Concurrent Clean 2.1.1 で以下のコードをコンパイルしてみた。 普通にコンパイル出来た。Concurrent Clean は GHCの直面した問題にはどう対処しているのだろうか? きっと、inlinerのアルゴリズムが違うということなんだろうが、どう違うのかに少し興味がある。
:: T a = PsiInv !((T a) -> a) psi :: (T a) -> (T a) -> a psi (PsiInv x) = x fix :: (a -> a) -> a fix g = h (PsiInv h) where h x = g (psi x x)
【2006-03-25 追記】 これは Agda の termination check の問題 に似ている気がするが、どうなのか?
【2010-05-21 追記】 NOINLINEプラグマを利用するとこの問題を回避できるとOlegさんに教えてもらった。 上の定義に合わせると，以下のようにすればOKだった。(GHC 6.12.1)
newtype T a = PsiInv (T a -> a)
{-# NOINLINE psi #-}
psi :: T a -> T a -> a
psi (PsiInv x) = x
fix :: (a -> a) -> a
fix f = g (PsiInv g)
where g x = f (psi x x)
λ. 『戦争請負会社』, P・W・シンガー(Peter W. Singer) 著, 山崎 淳 訳
読了。
本書は現代の軍事民営化の流れに関して非常に網羅的に捕らえている。 この軍事民営化を担っているのが「民営軍事請負企業」(PMF, PMC)で、今年五月に英国のハート・セキュリティ(Hart Security)社の社員である斎藤昭彦氏がイラクで武装勢力に拘束された事件で一躍有名になった感がある。 PMFはいわば現代の傭兵なのだが、「ならず者」「戦争の犬」というイメージからはほど遠い。なにより、PMFは法人企業であり、古典的傭兵の持たなかった財政的基盤と組織構造を持っている。そのためPMFは直接的な戦闘作戦だけでなく、戦略計画、情報収集、危険評価、兵站/補給などの作戦支援、高度な技術を要する兵器や機材の維持運営、教練等の多岐に渡るサービスを提供することが出来る。 私もPMFの存在は知っていたが、これほどまでに広範に利用されており、また各国軍隊にも必要不可欠なものになっているという事実は、衝撃以外の何者でもなかった。
PMFの勃興をもたらしたのは冷戦の終結とグローバリゼーションの進展である。 冷戦の終結に伴う軍隊の削減と国家の消滅により、軍事技能を持った労働力と大量の在庫兵器が市場に溢れ出すこととなり、PMFを支える原材料市場が生まれた。 また、冷戦の終結は大国から小国への援助/干渉を激減させ、弱体化した国家は軍事的対応能力を失うと同時に、軍事的空白地帯と化すことで紛争が増え、国家や(当該地域で活動する)企業のPMFへの需要が生まれた。また、先進国においても民営化と外注化への流れはPMFへの需要を生んだ。
PMFが切り開いた可能性は非常に魅力的なものであるが、同時に国際法上の問題、道徳上の問題、監視/規制の困難性、政府が議会の監視を迂回する方法として利用する可能性、etc...といった数多くの問題も指摘されている。 ともあれ軍事の民営化は止めることの出来ない流れであり、それを踏まえて影響を分析し、法整備などを急ぐ必要がある。
SFCの今学期の「安全保障論」の授業ではPMFについてはあまり取り上げていなかったけど、積極的に取り上げる価値のあるトピックだったのではないかと思う。この本をもっと早く読んでいたら、先日の大塚海夫一左の講演でも関連した質問をしただろう。「自衛隊は(特にイラクで)PMFを利用したことがあるか?」「今後利用する可能性があるか?」「退役した自衛官の進路は?」等々……
- Quotation
-
軍事民営化現象は軍事的能力が公開市場で買えることを意味する。しかもしばしば顧客が出せる限度額を下回る廉価で質が高いものが買える。(中略) 軍事的圧力は金さえあれば誰にでも手に入れられ、軍事力に関する限り、かつてあった障壁は低くなっている。別な言い方をすれば、PMFの意味は、鍬は今までよりも簡単に刀に鋳直せるということである。
(p.337)
λ. メビウス人狼 & ひぐらし人狼
メビウスプロジェクトで運営されている人狼クローン。今のところ参加するつもりはないけど、ルールの違いが面白い。
【2006-03-25 追記】 最近ログを少し読んでいるのだが、これ結構難しいな。
ψ 小熊善之 [日本のNGOやらで地雷除去や不発段処理に退役自衛官を擁している組織は幾つかありますよ。現役自衛官を出向させている例も..]
ψ オブジェクト [地雷除去や不発弾処理では国を挙げてもっと取り組めばいいと思うんですがね…… え？先進文化人が反対をした？ 本当です..]
ψ さかい [> 地雷除去や不発弾処理では国を挙げてもっと取り組めばいいと思うんですがね…… 地雷除去や不発弾処理は望ましいこと..]
ψ syd [＞…… known bug だったらしい 僕もHaskellスレに型チェッカの似たようなnontermination..]
ψ さかい [あー、Haskellスレでそれ書いたの私だったような……]
ψ syd [笑 やはり、そうだったか！どうもです。]
ψ さかい [笑 みんな結構Haskellスレみてるんですね。]
2005-07-25 [長年日記]
λ. 杉浦日向子さん逝去
コメディ「お江戸でござる」は好きでした。癌で1年8カ月前から闘病生活を続けていたそうで……残念でなりません。ご冥福をお祈りします。
λ. 『アルベルト・フジモリ,テロと闘う』, アルベルト・フジモリ(Alberto Fujimori) 著, 岸田 秀 訳
読了。
- Quotation
-
六十万もの人がテロの暴力のせいで故郷を離れ、国内難民となり、国家にも忘れ去られたのである。年老いたものは故郷に帰る夢を叶えることなく人生を終えた。死ななかった幼児は成長し、若者になり、リマに定着し始めた。
それらの流民はすべてを失ったが、希望だけは失わなかった。一九九〇年に私に票を投じてくれたのは彼らであった。私は、彼らとの公約に基づいて、テロ軍団をアンデス地域から追い出した。そして、流民が生まれ故郷へ帰れるようにするために最大限の努力をした。国家は今や、彼らの故郷の地は最早危険にさらされていないことを示し、彼らの生命の安全を保障できるようになった。
(p.181)
λ. １人で風呂に入ってたら姉が 〜めざせおねえぱい〜
一ヶ月以上かかってようやく27スレ目まで読み終わったけど、これ現在もまだ進行中なのね……
