日々の流転

λ. 사랑를주세요 (愛を下さい)

最近壊れ気味。課題とかが溜ってるので、あと数日は壊れ続ける予定。色々遅れて御免ね。> 関係各位

λ. 今日は「えなりかずきの子守歌」でまどろむという大失態をおかしました。ぐふっ。しかも、おかげで杉浦ひなこ先生の解説が聴けなかったしぃ。

λ. 情報数学Ⅰ

オートマトンの代数的表現である等式系(coalgebra)と言語関数について。「この授業の前半のハイライト」と言うだけあって、凄かった。

λ. ところで、昨日のリンク元を見て唖然とした。Googleで「向井　オートマトン」を検索して、この日記がトップに表示されているのは何かが間違ってるぞぉぉ〜!!!!

λ. メモ: Cのmb⇔wc変換 (昨日の続き)

この場合だと関係ないけど、mb→wcの変換でもmbsrtowcs()とかだとterminating NULまで変換しないと問題になる場合がある。それはmbが「部品」を符号化単位にしていてかつ不定長の連結を許すエンコーディングで、wcの単位が「部品」を結合したモノであるとき。terminating NULを省くと最後のwcを確定出来ない可能性がある。

λ. そういや、mbsnrtowcs(3)とwcsnrtombs(3)ってGNU拡張なのね。ちょっとショック。

λ. 改竄

11/6のこれで、TIS 620 が TIS 640になってたので修正。同じ間違いをするのは一体何度目だろう…　ついISO640を連想して間違えちゃうんだよなぁ。

λ. 帰納論理プログラミング

Progolの探索アルゴリズムについて。

λ. 研究会

NFSについての発表を聴いた。一番興味のあったロックの事についてはいまいち良く解らなかった。flock(2)は何故NFS上のファ イルのロックをしないのだろう。VFS層でファイルシステムが抽象化されるなら、flock(2)だってlockf(3)同様にlock出来て構わないと思うのに…　何か historical origins でもあるのかな。

λ. 朝は曇っていたのに午後から晴れてきた。眩しくて暖かくて気持ちが落ち込む。

λ. 言語の意味論

そうか、意味公準(MP, Meaning Postulate)ってそういう意味だったのね。わーい。やっと理解できたぞー

λ. 読書

『燃えよペン』

島本 和彦 [著]

λ. 今日の向井研

こないだ思いつきで「ひょっとして束(lattice)になるんじゃない?」とか言ったのだけど、本当に束になっていたそうだ。ちょっと感動。[追記] その後束ではない反例が見つかった。残念。

こないだの「力学系」という訳の由来としては、ダイナミックシステムというのは微分の概念と非常に深く結び付いていて、だから「力学」なのらしい。

λ. 帰り

帰りのバスで女の子が急に倒れてきて驚いた。随分顔色が悪かったので心配。

その後、片山さんとニューオリンズへ。何故か日本経済について議論する。

デコとシューヘイに会った。また同窓会とかしたいなぁ。

λ. ニューラルコンピューティング

なんか武藤先生がいつもと違ーうと思ったら、教室間違えてた。orz

グラフの平面化問題。頂点のどっち側にエッジがあるかを表すために、|V|×|E|×2のニューロンを割り当てればいいと考えてたのだけど、2次元から1次元に還元してしまうというのには気付かなかった。そうすれば問題がシンプルになるし、必要なニューロンの数も少なくなるもんなぁ。なるほど、なるほど。

ところで、n-Queenや4色問題を解くためのニューラルネットの motion equation を自分でも考えてみたけど、結局のところ俺は motion equation がいまいち分ってないんだよなぁ。「発火によって制約条件に近づくなら正に、そうでない時に負になるように組み立てる」というのは自明だし、これまでの例ではそれは簡単だった。だけど、制約条件の複数の表現方法の内でどれが優れているのか、また複数の制約条件をどのように組み合わせるかとった点がピンとこない。また hill-climbing の項をどう選択するのかもピンとこない。このあたりって結局ヒューリステックでしかないのだろうか?

それはそうと、NP問題のNPをNon-Polynomialと説明するのはどうかと思った。

λ. The Ring

テレビでたまたまやってたので見た。やっぱり小説が一番怖かったなぁ。

• http://www.thering.jp/
• http://www.ring-themovie.com/

λ. 『風の大陸　氷の島1』, 竹河 聖

読んだ。

λ. 紅葉＠SFC

λ. プラグインの不正な操作

Naxosの音楽を聴いているFirefoxのウィンドウを閉じると、上記のようなダイアログが出てFirefoxの動作がおかしくなることがある。これは困る。

Windows Media Player のバージョンは10.00.00.4036。 Firefox のバージョンは1.5.0.7。

λ. Programs, grammars and arguments: a personal view of some connections between computation, language and logic by J. Lambek

rpfさんのmixi日記に書いてあったC-monoidは何だろうと思って検索したら発見した論文。しかし、こうしてみると Lambek は色々やってるねぇ。古き良き計算機科学者というかなんというか。

「The natural numbers object may be constructed in a model of polymorphic λ-calculus as a retract of Π_X (X^X)^(XX) ≅ Π_X X^(XX+1) where Π_X is a kind of formal product in a CCC.」という部分が分からん。formal product というのはその圏の対象をインデックスにするような直積のことだと思うが、正確な定義は?

【2007-10-27追記】 数学ガール(結城 浩) の p.200 で「(2⁰+2¹+2²+…)・(3⁰+3¹+3²+…)」を形式的積と呼んでいた。ミルカさんによれば「この積は正の無限大に発散する。だから形式的積と言ったんだ」とのこと。

PERもまだイマイチ良くわからん。

多重線形代数(multiliner algebra)には構造規則(structual rules)が欠けているそうだけど、多重線形代数を知らないのでこれは後で調べるか。それから、「However, in Hopf algebras and in general production grammars the tensor product and its dual coincide.」という部分についても後で調べる。

λ. haskell-jpのアーカイブ

nobsunに協力していただき、haskell-jpメーリングリストのアーカイブを <URL:http://www.sampou.org/cgi-bin/w3ml.cgi/haskell-jp/> に作りました*1。 ご活用ください。

λ. パーセンテージ

たとえば、最近の銀行の利息は0.1％くらいまで下がっているが、これなどは、1/1000と分数でいった方が直感的にわかりやすいのではないだろうか。パーセントを用いているのに、そのうえ少数を使うのは、いかがかと思う。しばらくは好景気にはならないだろうから、この際、利息には千分率のパーミルを使う習慣にしてはどうだろう？

金利の差分等については、0.01%を表すベーシスポイント(basis point, bp)が普通に使われていると思うが。

λ. 『大学の話をしましょうか—最高学府のデバイスとポテンシャル』 森 博嗣

読了。

λ. “Asynchronous Exceptions in Haskell” Simon Marlow, Simon Peyton Jones, Andrew Moran and John Reppy

• <URL:http://doi.acm.org/10.1145/378795.378858>
• 著者版

割り込み・メモリ不足・タイムアウトといった、プログラムそのものの意味とは直接関係せずに発生するような例外を非同期的例外という。 非同期的例外は A semantics for imprecise exceptions でも一応扱われていたが、この論文では、非同期的例外の一種として、あるスレッドから別スレッドへの例外の送出を、より積極的にスレッド間のシグナリング機構ととして活用できるようにする。

あるスレッドから別のスレッドを殺したり例外を送出したりというのは、予期しないところで実行が中断することによって不変条件が成り立たなくなってしまう可能性などがあり、手続き型言語では色々悩ましい問題があった。一方、関数型言語では、プログラムの大部分を占める純粋な計算に関してはこのような問題はなく、そのため別スレッドへの例外の送出を積極的に活用しやすい素地がある。

もちろん、IOアクションの実行、特にスレッドの同期に関わる部分では手続き型言語の場合と同じ問題がある。この論文では例外の受け取りを遅延する状態でアクションを実行する block :: IO a -> IO a, 例外を受け取れる状態でアクションを実行する unblock :: IO a -> IO a という関数を利用してそのあたりの問題を扱う。

アクション二つを並行に実行して、どちらか先に結果を返した方を全体の結果にするようなeitherアクション、それからeitherを利用して書かれたtimeoutの実装がかっこよかった。今GHCに合わせると以下のような感じ。

import Prelude hiding (either, catch)
import Control.Exception
import Control.Concurrent

data EitherRet a b = A a | B b | X SomeException

either :: IO a -> IO b -> IO (Either a b)
either a b = do
  m <- newEmptyMVar
  block $ do
    a_id <- forkIO $ catch (do r <- unblock a
                               putMVar m (A r))
                           (\e -> putMVar m (X e))
    b_id <- forkIO $ catch (do r <- unblock b
                               putMVar m (B r))
                           (\e -> putMVar m (X e))
    let loop = catch (takeMVar m)
                     (\e -> do
                        throwTo a_id (e :: SomeException)
                        throwTo b_id e
                        loop)
    r <- loop
    killThread a_id
    killThread b_id
    case r of
      A r -> return (Left r)
      B r -> return (Right r)
      X e -> throwIO e

timeout :: Int -> IO a -> IO (Maybe a)
timeout t a = do
  r <- either (threadDelay t) a
  case r of
    Left _ -> return Nothing
    Right a -> return (Just a)

λ. Project Euler レベル3

Project Euler で100問を解き、レベル3になった。正六面体から正八面体に進化した。 記念すべき100問目は Problem 108 。