amb on Ruby - 主題のない日記

先日は Scheme での非決定性プログラミングの話題を出した (http://saito.hatenablog.jp/entry/20070531/1180609793) けれども、そもそも Scheme を知らない人にはその凄さが伝わらないと思ってウェブ検索してみると Ruby でやっている例もいくつか見られるようだ。それらを参考にコードをまとめてみた。

class Amb
  def initialize() @paths = [] end
  def choose(*prob)
    if prob.empty?
      self.fail
    else
      callcc{|cc|
        @paths.push(*prob.map{|trial|proc{cc.call(trial)}})
        self.fail
      }
    end
  end
  def fail()@paths.empty? ? (throw :fail):@paths.pop.call end
  alias retry fail
  def assert(pred) self.fail if (not pred) end
  protected :fail;
end

この間のSchemeでのやりかたとは戦略が少し違うのだけれど、それは参考にしたコードから影響を受けたためだ。

実際に使ってみよう。

def xor(a,b)
  (a && (not b)) || ((not a) && b)
end

def alldiff?(ls)
  t=Hash.new;
  ls.each{|x|t[x]=true}
  return t.size == ls.size
end

amb = Amb.new;
r = Hash.new

r[:kitty]=amb.choose(1,2,3,4,5)
r[:betty]=amb.choose(1,2,3,4,5)
r[:mary]=amb.choose(1,2,3,4,5)
r[:ethel]=amb.choose(1,2,3,4,5)
r[:joan]=amb.choose(1,2,3,4,5)
amb.assert(xor(r[:kitty]==2,r[:betty]==3))
amb.assert(xor(r[:kitty]==2,r[:mary]==4))
amb.assert(xor(r[:mary]==4,r[:betty]==1))
amb.assert(xor(r[:ethel]==1,r[:joan]==2))
amb.assert(xor(r[:joan]==3,r[:ethel]==5))
amb.assert(alldiff?(r.values))
p r

実行するとこんな感じの結果が表示されただろうか？

{:mary=>4, :ethel=>5, :joan=>2, :kitty=>1, :betty=>3}

Scheme での使用例よりも Ruby で書いた方が宣言的っぽさがわかりやすいかもしれない。可能性と制約を問題文通りに書いただけであることがよくわかるだろう。

この例では全空間探索になっているが、より効率的に枝刈りするのも簡単だ。記述の順序を変えればいい。

r[:kitty]=amb.choose(1,2,3,4,5)
r[:betty]=amb.choose(1,2,3,4,5)
amb.assert(xor(r[:kitty]==2,r[:betty]==3))
r[:mary]=amb.choose(1,2,3,4,5)
amb.assert(xor(r[:mary]==4,r[:betty]==1))
amb.assert(xor(r[:kitty]==2,r[:mary]==4))
r[:ethel]=amb.choose(1,2,3,4,5)
r[:joan]=amb.choose(1,2,3,4,5)
amb.assert(xor(r[:ethel]==1,r[:joan]==2))
amb.assert(xor(r[:joan]==3,r[:ethel]==5))
amb.assert(alldiff?(r.values))
p r;

let をネストしていく Scheme よりも手軽だ。

Ruby 1.9 からは継続を廃止する予定だそうで、その理由というのは要は使用頻度の低さの割に実装の負担が大きく (処理系の) バグを発生させる原因になり易いということのようだ。たしかに非決定性プログラミングなどといったところで実際にやっているのはバックトラックであるし、問題を解くのに必須なものでもない。継続を使っているほとんどの場合では別の形に書換えることができるだろう。

だが、今回 Ruby で書いてみてわかったのは、継続は問題を解く道具というよりは機能を抽象化するための道具だということだ。オブジェクト指向中心な Ruby の理念の中で継続の重要性が低いのは納得できなくもないが、廃止予定というのはちょっと残念な気はする。

Document ID: b642d5a3e757189f3a401271e10435d2