Journal InTime

_ 関西オープンソース2005発表

発表してきた。

• スライド

ちょっと会場入りが遅れたせいもあり、進行がぐだぐだになってしまって、 申し訳なかったです。

_ 非決定性計算

今回いちばん面白かったのが、Haskell同好会のセッション。

吉田さんのプレゼンで非決定性計算の話が出て来たのだが、 Wikiでも紹介されていたようだ。

「他の言語じゃこんなことできないでしょ」という話だったが、 実はRubyConf2005のChad FowlerとJim Weirichのチュートリアルでも同じようなデモをやっていた。 それを使って書くと、

require "amb"

A = Amb.new

baker = A.choose(1, 2, 3, 4, 5)
cooper = A.choose(1, 2, 3, 4, 5)
fletcher = A.choose(1, 2, 3, 4, 5)
miller = A.choose(1, 2, 3, 4, 5)
smith = A.choose(1, 2, 3, 4, 5)

A.assert([baker, cooper, fletcher, miller, smith].uniq.length == 5)
A.assert(baker != 5)
A.assert(cooper != 1)
A.assert(fletcher != 1 && fletcher != 5)
A.assert(miller > cooper)
A.assert((smith - fletcher).abs != 1)
A.assert((fletcher - cooper).abs != 1)

p [baker, cooper, fletcher, miller, smith]

こんな感じ。 (Haskell版は全部の解が得られるけど、Ruby版は最初の解しか得られないところ がちょっと違う。)

どうやっているかというと、A.assertの呼びだしで継続を使ってバックトラック しているのだが、Rubyもなかなか面白いでしょ? ちなみに、amb.rbはこんな内容。

class Amb
  class ExhaustedError < RuntimeError; end

  def initialize
    @fail = proc { fail ExhaustedError, "amb tree exhausted" }
  end

  def choose(*choices)
    prev_fail = @fail
    callcc { |sk|
      choices.each { |choice|
        callcc { |fk|
          @fail = proc {
            @fail = prev_fail
            fk.call(:fail)
          }
          if choice.respond_to? :call
            sk.call(choice.call)
          else
            sk.call(choice)
          end
        }
      }
      @fail.call
    }
  end

  def failure
    choose
  end

  def assert(cond)
    failure unless cond
  end
end

あとで、池上くんや山下さんとちょっと話したのだが、Haskell版はlazy なのがポイントらしい。 だからRubyでは無理でしょと言われて、その時はブロック使えばいいじゃん と話したのだが、継続版だとブロックも使わずにすっきり書けますね。

元ネタはSICPらしいけど、どんな解なんだろうな。 会社に行ったら調べてみよう。

追記:

リンク元のWikiページ を見ると、継続使うのはやっぱりSchemeからの借用っぽいですね。 そらそうだよなあ。

_ KOF宴会

sheepmanさん、柳川さん、池上くんという豪華なメンバのテーブルに。 池上くんが一番よくしゃべってたような気がする。 何かたのしそうでいいなあ。

帰ってから気付いたけど、kdmsnrさんと話していたのかー。 ぜんぜんわかってなかったorz...。 須藤さんが「ブリキの人」っていうから「ブリキ」って何だろうな と思っていたのだが、blikiでしたか。 色々バカな話をしたかと思いますが、忘れてくださいm(..)m

あと、馬場さんとかとも話せなかったし、悔いの残る宴会でした。 全部須藤さんのせいだっ。