日々の流転

λ. レポート書くべし、書くべしー

λ. 借りた本

『星方遊撃隊エンジェルリンクス　激闘編』

伊吹秀明[著] 幡池裕行[イラスト]

『平成デフレ』

大谷健[著]

『日本の地価の決まり方』

西村清彦[著]

『平成不況の政治経済学』

左和隆光[著]

『統計学のはなし』

蓑谷 千鳳彦 [著]

λ. 『ベルセルク (23)』 三浦健太朗

を読んだ。

λ. ゲームプログラミング

これまで実装していない部分が思っていたよりも随分手ごわく、あと30分、あと30分とか思ってやっているやっているうちに随分遅くなってしまった。まだまだゲームの出来自体にもコードにもかなり不満はあるのだけど、気力が尽きたので12時頃になって提出。も〜ど〜でもい〜や〜。

しかし、もうバスもないし、小田急の終電にも間に合わないよ〜。ひょっとして残留しなくちゃいけないかなぁ……と思ったら、U女史が車で送ってくださることになり助かった。Uさんと二人きりで夜のドライブですよ。しかも考えてみたら七夕の夜なわけですよ。ドキドキ、バクバク……

λ. 七夕

λ. 面接

に行ってきた。

I took employment eligibility exam which consists of an English examination, a short essay and an interview. I was a bit nervous but I think I did well.

λ. 『ファウンデーションの彼方へ (上)』

を読んだ。

λ. Ruby-GNOME2のコールバック周りを少し整理

Rubyと関係ないネイティブスレッドからコールバックが呼ばれた場合にはRubyのスレッドに転送してから実行すべきなのだが、その部分がGRClosureにべったりだったので、分離してRuby-GNOME2の他のコールバックの処理でも使えるようにしてみた。

また、これまでのコードではコールバックの転送を待っているスレッドで受け取ったコールバックをそのまま実行すると、その内部で更にコールバックが発生したときにデッドロックしてしまうという問題があった。 これを回避するために、受け取ったコールバックの実行は新たに生成したスレッドで行うようにした。 ただ、これ効率悪いな。スレッドの生成が相対的に重い1.9では特に重いはず。 スレッドプールを作ってスレッドを使いまわすべきか。

また、1.9ではis_ruby_native_thread()が機能しなくなった(参考 [ruby-dev:31166])ので、コールバックの側で現在のスレッドがRubyのネイティブスレッドなのか判別できず、たとえ現在のスレッドがRubyのスレッドだとしても転送しなくてはならなくなっている。これは切ない。なんとかならないのかなぁ。

1. 現在のスレッドがRubyのネイティブスレッドで、かつGVL(Giant VM Lock)を保持しているのなら、そのまま呼び出したい。
2. 現在のスレッドがRubyのネイティブスレッドで、もしGVLを手放しているのなら、GVLを再び確保した上で、そのまま呼び出したい。

……と書いたが、[ruby-dev:31162]で落ちるので、1.9ではまだ試せていないのだった。

λ. Mutexとかめんどい

Ruby-GNOME2のコールバック周りをいじったときに、久しぶりにMutexやConditionVariableを使ったコードを書いたのだけど、面倒くさいな。 せめてMVarくらいあれば良いのにと思ってしまう。

λ. サンタクロース問題

お約束ということで、サンタクロース問題に挑戦してみた*1。

-module(santa).
-compile(export_all).

santa([_,_,_,_,_,_,_,_,_]=Reindeers, Elves) ->
   work("delivering", 3000, Reindeers), santa([], Elves);
santa(Reindeers, [_,_,_]=Elves) ->
   work("meeting", 1000, Elves), santa(Reindeers, []);
santa(Reindeers, Elves) ->
    receive {reindeer, X} -> santa([X|Reindeers], Elves)
    after 0 ->
       receive
          {reindeer, X} -> santa([X|Reindeers], Elves);
          {elf, X} -> santa(Reindeers, [X|Elves])
       end
    end.

work(What, N, XS) ->
   io:format("Santa Claus starts ~s.~n", [What]),
   random_wait(N),
   io:format("Santa Claus ends ~s.~n", [What]),
   lists:foreach(fun (X) -> X!leave end, XS).

srand() -> {X,Y,Z}=erlang:now(), random:seed(X,Y,Z).

random_wait(N) ->
    receive
    after random:uniform(N) -> true
    end.

loop(Santa, Kind, Name) ->
    random_wait(2000),
    io:format("~s comes.~n", [Name]), Santa!{Kind, self()},
    receive
       leave ->
          random_wait(1000), io:format("~s leaves.~n", [Name]),
          loop(Santa, Kind, Name)
    end.

start() ->
    Santa = spawn_link(fun () -> srand(), santa([], []) end),
    [ spawn_link(fun () -> srand(),
         loop(Santa, K, S ++ erlang:integer_to_list(X, 10)) end)
     || {S,K,N} <- [{"Elf", elf, 10}, {"Reindeer", reindeer, 9}]
      , X <- lists:seq(1,N) ].

タイムアウト節を持つreceiveを使うことで、指定した時間だけ待ったり、優先順位付きの受信をしたりといったことが出来るのが少し面白かった。 それから、プロセスのリンクやモニタのような機能は、他の言語の並行処理でも結構欲しくなることがあるので、これが組み込みであるのはいいなぁ。

λ. “Types are calling convensions” by Max Bolingbroke and Simon Peyton Jones

Types are Calling Conventions | Lambda the Ultimate より。 積読中だったんだけど、Chatonの haskell-ja > Archives > 2009/07/06 で出てきたので読んでみた。

Haskell の関数はカリー化されているとはいえ、実際に実行時に一引数渡して関数を返してまた一引数渡して……なんてやっていたら遅くて仕方がないので、実際には引数を出来るだけまとめて渡している。 一方で、複数の値を返すときにはタプルで返すように書くけれど、実際にタプルをヒープ上に確保してなんてやっていたら遅くて仕方がないので、これも出来る限り複数の値を直接返すようにしている*1。 それに出来るだけ非ボックス化して渡したり、他にも色々あるのだけど、こうした呼び出し規約の最適化をGHCは非常にアドホックな形で行っている。

これはあまりよろしくないので、これらの呼び出し規約の違いを型で自然に表現出来るような中間言語 Strict Core を導入し、そうした最適化を安全かつシステマティックに出来るようにしようという話。

Strict Core は名前が示すように正格な言語で、また関数が多引数・多出力になっている。 Strict Core では、評価済みのIntとBoolを一度に受け取って、評価済みのIntを二つ返すような関数の型は 〈Int, Bool〉→〈Int, Int〉 になるし、引数を一つずつ受けとるような関数の場合には 〈Int〉→〈〈Bool〉 → 〈Int, Int〉〉 といった感じの型になる。また、サンクは{Int, Bool}のような型になる*2。 以下では表記をわかりやすくするため、引数・返り値が一つの場合には山括弧は省略することにする。

そうすると、例えば以下のように呼び出し規約を型で書き分けることが出来る。 ただし、丸括弧で囲まれているのはヒープ上に確保されたタプルを表す単一の値の型。

• f1 : Int → Bool → (Int, Bool)
• f2 : 〈Int, Bool〉 → (Int, Bool)
• f3 : 〈(Int, Bool)〉 → 〈Int, Bool〉
• f4 : 〈{Int}, Bool〉 → (Int, Bool)

それで、Haskell(のサブセット言語)を Strict Core に変換して、その上で各種の最適化を行うのだけど、型として違いがわかると確かにわかりやすい。

示されている最適化は基本的に現在のGHCでも(アドホックながら)実装されているものなのだけど、6.2の Use-site arity raising だけは現在のGHCでは行っていない。 これは例えば zipWith : 〈{a} → {b} → c, List a, List b〉 → List c という関数の worker-wrapper 変換で、〈〈{a}, {b}〉→c, List a, List b〉 → List c という型の worker と、関数引数のarityの変換するようなwrapperへと変換するもの。 これは従来の動的なarityの検査*3の代替になりうる。

関連

• Making a fast curry: push/enter vs. eval/apply for higher-order languages - ヒビルテ(2004-11-16)