日々の流転

λ. 祖母に続いて親父まで入院。気鬱になる。

λ. いいこと

Linuxビボ〜ろくで、

お、あなたはちょうど本日100人目のお客様！
きっと今日はいいことありますぜ！

と言われる。いいことあるといいなぁ。

λ. イラクのサダム・フセイン元大統領が拘束されたそうだ。旧イラク政権の関係者は今後なんらかの形で裁かれることになるのだろうけど、出来ることならば東京裁判のような国際法を恣意的に濫用して勝者が敗者を裁く事態にはならないで欲しいものだ。

λ. ラスト・サムライ

を見てきた。

λ. Hugsの国際化

nobsunにExperimental Support of Unicode in Hugs Available for Testing というページを教えてもらったのでインストール。

ただ、日本語を含む文字列をshowしたときや:typeコマンドで表示しようとしたときにエスケープされてしまうのが悲しかったので、表示するようにするパッチを作った。

hugs98-Mar2005 用 (2005-03-22)

hugs98-Mar2005-unicode-display.diff

hugs98-Dec2003 用

hugs98-Dec2003-unicode-display.diff

パッチを作った後に Haskell98 report を確認したのだけど、リテラルに直接かけるのはASCIIだけなのか。ということは、このパッチでshowの定義を書き換えてるのは仕様には反するな。とすると、showと:typeコマンドでリテラルの表示が違うのもあれなので、showで非ASCII文字をエスケープするのなら、:typeでもエスケープというのが一貫性がありそうだ。でも、Hugsの:typeはもともとLatin-1を表示してたんだよなぁ……

[2005-03-22 追記] hugs98-Mar2005では:typeでLatin-1もエスケープされるように修正された。

λ. 『GOTH 』, 乙一 原作, 大岩 ケンヂ 画

を読んだ。へぇ、GOTHってこういう話だったんだ。小説も後で読もう。

λ. HaskellでScheme処理系を実装 (3)

末尾再帰で10000!を計算すると、とりあえずGuileと同じくらいのスピードは出てるのだけど、fib(30)を素朴な再帰で計算したらやたら遅かった。プロファイルをとってみたら total alloc が 13GBほど。そりゃ遅い気がする。

こんなにメモリを消費している理由を確認するためにVMのコンパイル結果を-ddump-stgでダンプしてみると、予想通り命令一ステップ実行するごとにletが……。最適化でアンパックされると思ってた引数/返り値のデータ構造を毎回ヒープに割り付けてるよ、うわーん。

色々と試してみると、GHC の worker wrapper transformation は、返り値の型がネストしたデータ構造だった場合にトップレベルしかアンパックしてくれないっぽいな。引数の方はネストしててもアンパックしてくれるから、これは CPR analyser の制限なのかな?　あと、正格性解析によって引数がアンパッカブルと判定される条件もいまいち良く分かってないんだよなぁ。

一応 single threaded な使い方はしてるはずだから、アンパックしてくれなくても single threadedness を検出して破壊的に更新してくれるってのでもいいんだけど……それも叶わないし、切ないね。Haskellにも linear type があればいいのにと初めて本気で思ったよ。

とか、ぐだぐた考えながら、自分でアンパックしたコードを書いてプロファイルを取ってみる。total alloc は 13GB から 4GB まで減り、実行時間が110秒から70秒に減った。また実行時間にしめるGC時間は20%から14%に減った。むー、思ったより速くならなかったな。まあスタックとかもリストで表現してるし、他にも色々と富豪なことしてるから、こんなものか。さて、どうしようかな。

λ. Constructed Product Result Analysis for Haskell, Clem Baker-Finch, Kevin Glynn, Simon Peyton Jones

.

λ. GHC の worker wrapper transformation への不満

(2005-09-11 追記) 上で「GHC の worker wrapper transformation は、返り値の型がネストしたデータ構造だった場合にトップレベルしかアンパックしてくれないっぽい」と書いたことについての簡単な具体例。GHCの worker wrapper transformation だと、内側のタプルがすぐ消費される場合でもヒープに割り当てられてしまう。

元のコード

test :: Int -> (Int, (Int,Int))
test x = (x,(x+1,x+2))

GHC の worker wrapper transformation

{-# INLINE test #-}
test :: Int -> (Int, (Int,Int))
test x = case wtest x of
         (# a, b #) -> (a, b)
 
wtest :: Int -> (# Int, (Int,Int) #)
wtest x = (# x, (x+1, x+2) #)

期待する worker wrapper transformation

{-# INLINE test #-}
test :: Int -> (Int, (Int,Int))
test x = case wtest x of
         (# a, b, c #) -> (a, (b, c))
 
wtest :: Int -> (# Int, Int, Int #)
wtest x = (# x, x+1, x+2 #)

(2005-09-16 追記) ちなみに、GHCではIO型は「newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))」と定義されているので、IO型を返すような関数は同じ制約を受ける。IO型を利用したコードが遅くなる一つの理由がこれだと思う。

元のコード

test2 :: Int -> IO (Int,Int)
test2 x = return (x,x+1)

期待する worker-wrapper transformation

{-# INLINE test2 #-}
test2 :: Int -> IO (Int,Int)
test2 x = IO (\s -> case wtest2 x s of (# s, a, b #) -> (# s, (a,b) #))
 
wtest2 :: Int -> State# RealWorld -> (# State# RealWorld, Int, Int #)
wtest2 x s = (# s, x, x+1 #)

【2006-04-28追記】 GHC-6.4.1の compiler/cprAnalysis/CprAnalyse.lhs には以下のように書いてあった。うーむ。「enabling this would lose laziness」が何故なのか良く分からない。

The analysis here detects nested CPR information. For example, if a function returns a constructed pair, the first element of which is a constructed int, then the analysis will detect nested CPR information for the int as well. Unfortunately, the current transformations can't take advantage of the nested CPR information. They have (broken now, I think) code which will flatten out nested CPR components and rebuild them in the wrapper, but enabling this would lose laziness. It is possible to make use of the nested info: if we knew that a caller was strict in that position then we could create a specialized version of the function which flattened/reconstructed that position.

It is not known whether this optimisation would be worthwhile.

So we generate and carry round nested CPR information, but before using this info to guide the creation of workers and wrappers we map all components of a CPRInfo to NoCprInfo.

λ. Monadと思ったけどMonadじゃなかった何か

以下がMonadになってると思って頑張って証明しようとした*1けど、結局Monadになっていないことが分かってショボーン（´・ω・｀）。もし(++)が可換であればMonadになるんだけどね*2。

-- coinductive
data Automata i o = Automata [o] (i -> Automata o)

instance Monad (Automata i) where
    return x = Automata [x] (\_ -> mzero)
    (Automata as t) >>= g =
        msum [g a | a <- as] `mplus` Automata [] (\c -> t c >>= g)

instance MonadPlus (Automata i) where
    mzero = Automata [] (\_ -> mzero)
    Automata xs t `mplus` Automata ys u =
        Automata (xs++ys) (\c -> t c `mplus` u c)

λ. Domain Theoretic Models Of Polymorphism by Thierry Coquand and Carl A. Gunter

読みかけ。

cocontinuous な functor F: C→D^EP から、Grothendieck construction で圏 ΣF と射影 p:ΣF→C を定義する。CがdomainならΣFもdomainになっている。pのcoconitnuousなセクション C→ΣF とその間の自然変換からなる圏を ΠF とする。Cがdomainなら ΠF もdomainになっている。

CをD^EP自身とする。このときΣFは半順序集合にならない。ΠFは半順序「集合」にはならずクラスになるが、圏同値なdomainが存在する。このΠを使って多相型を扱う。

このモデルはuniformに振舞わないような多相的な要素を含む。 admissibleな関係に限定した場合のparametricityは……やっぱり成り立たないのかな?*1

λ. 凄い漢字

<URL:http://www.rubyist.net/~matz/20061204.html#p02> にツッコミをいれようとしたら、spamフィルタに弾かれたみたいなので、こっちに。その「うしのあゆみがおそい」はU+3E2A(「㸪」)として既に含まれているような。

λ. 第四十七回圏論勉強会

今日は圏論勉強会だった(写真)。 昨日RHG読書会で今日は圏論勉強会、二日連続はやっぱりちょっと疲れるね。

前回やりのこした6.4節の残りでは、テンパリー・リーブ圏TLに対してスターやダガーを定義して strict pivotal dagger category にして、3節で定義したDと strict pivotal dagger category として同型であることを示す。 それから、7節に入ってラムダ計算の導入。ここで考える型付け規則は線形ラムダ計算のものになっていて、次回はこれを pivotal category で解釈する模様。

KellyとLaplazaのCoherence for compact closed categoriesのPDFはElsevierにあるけど$31.50もする……