非決定性プログラム

SICP 4.3.2 - ロバの耳ではcallccを使わずに済ませたけれど，そろそろcallccを使えるんじゃないかと思って挑戦してみた．

…

80行もあるすごくブサイクなやつが出来た…．しかもかなり使いにくい．

関西オープンソース2005発表, 非決定性計算, KOF宴会 - Journal InTime(2005-10-29)のコードと見比べてみると，1つのchooseにつきcallccを1つしか使わなかったのが敗因らしい．

大まかな流れは理解できていると思うんだけれど，sk.call(choice.call)とfk.call(:fail)の意味が分らない．

ほとんどまるパクリのバージョン

class Amb
  class ExhaustedError < RuntimeError; end

  def initialize(c=nil)
    @fail = c
    @fail ||= proc { raise ExhaustedError, "amb tree exhausted" }
  end

  def choose(*choices)
    prev_fail = @fail
    callcc {|sk|
      choices.each {|x|
        callcc {|fk|
          @fail = proc {
            @fail = prev_fail
            fk.call()
          }
          sk.call(x)
        }
      }
      @fail.call
    }
  end

  def try_again
    @fail.call
  end

  def assert(cond)
    try_again unless cond
  end
end

def amb(&block)
  ret = []
  callcc {|c|
    a = Amb.new(c)
    ret << block.call( a)
    a.try_again
  }
  ret
end

p amb {|x|
  a = x.choose(1, 2, 3)
  b = x.choose(*%w[a b])
  [a , b]
}
#=> [[1, "a"], [1, "b"], [2, "a"], 
#    [2, "b"], [3, "a"], [3, "b"]]

お約束の

amb {|a|
  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]
}
#=> [3, 2, 4, 5, 1]