継続による非決定計算の実装

Ruby

SICP を読んでいる今日この頃だが、Ruby でも継続が使えると知って、実際にやってみた。処理系は Windows の ActiveScriptRuby 1.8.7。最後に触ったの、いつだっけ……。そもそも今回のプログラムを書くために Ruby の文法を１日かけて復習しなければならなかった程度の知識なので、おかしいところがあるかもしれないというか、あって当然というか。しかし 1.9 でも継続は実装されているらしいと聞いたので、これはガゼン勉強せねばなるまいな、と思うのであった。

class Backtrack
  def initialize(endval = nil)
    @endval = endval
  end

  def format
    @paths = []
    callcc do |cc|
      @back_proc = lambda do
        if @paths.empty?
          cc.call @endval
        else
          @paths.pop.call
        end
      end
    end
  end

  def back
    @back_proc.call
  end

  def assert(val)
    back unless val
  end

  def choose(arr)
    callcc do |ret|
      arr.each do |choice|
        callcc do |cc|
          @paths.push cc
          ret.call choice
        end
      end
      back
    end
  end
end


この Backtrack クラスは、インスタンス内部に継続のスタックを保持する。メソッド choose は enumerable なオブジェクトを受け取り、そこから先頭要素１つを返すとともに、残りを辿るための継続をスタックにプッシュする。メソッド back が呼ばれるとスタックから継続を取り出して、それを call することでバックトラックを行う。


使用方法：
インスタンスを作る。コンストラクタ引数は、辿る継続がなくなったときに返される値。
次にバックトラックの起点にしたい場所でメソッド format を呼ぶ。たいていはトップレベルだろう。

bt = Backtrack.new :done

bt.format

Ruby における継続というのは、ローカル変数とトップレベルまでの道筋を保存しておくオブジェクトのようだ。かつて SECD マシンという種類の仮想マシンで Scheme を実装したときには、その時点でのコールスタックと変数環境とコードの残りを保存したクロージャ、という感じだった。
さて今回の場合、バックトラックは最終的に format した場所に戻ってくる。ブロックの内側とかに起点を作ると、あとで back を呼んだとき過去にタイムリープするという愉快なことになる。例えば以下のコードを実行したとすると：

x = 0

begin
  bt.format
  if 4 == x
    'return'
  else
    x += 1
    puts 'go back'
    bt.back
  end
end

"go back" と４つ表示されたのちに 'return' が返ってきて終了するが、そのあとさらに以下のようなことをすると：

x = 2

bt.back

処理が bt.format に戻り、"go back" と２度表示されたあと 'return' が返ってくる。
さて、非決定計算をするにはメソッド choose を使う：

bt = Backtrack.new :done
bt.format

[bt.choose( [1,2] ), bt.choose( [3,4] )]
#=> [1, 3]

choose は each を使ってコンテナを辿るので（ここでも継続を使っている）、引数は配列でなくてもかまわない。
バックトラックして choose に次の選択肢を選ばせるには、back を使う：

bt.back  #=> [1, 4]

辿れる選択肢がなくなったあとは（つまり @paths が空になったら）、コンストラクタに与えた引数が返ってくる：

bt.back  #=> [2, 3]
bt.back  #=> [2, 4]
bt.back  #=> :done

メソッド assert は１つの値を受け取り、それが偽のときだけ back を呼ぶ。これを使って SICP の論理パズルを解いてみよう（文章はシンプルにしてある）。


５階建てのアパートに A, B, C, D, E の５人が住んでいる。部屋のある階はみな互いに異なる。
Ａの部屋は５階ではない。
Ｂの部屋は１階ではない。
Ｃの部屋は１階でも５階でもない。
Ｄの部屋はＢよりも上の階にある。
Ｅの部屋はＣの隣の階ではない。
Ｃの部屋はＢの隣の階ではない。

def multiple_dwelling(bt)
  a = bt.choose [1, 2, 3, 4, 5]
  b = bt.choose [1, 2, 3, 4, 5]
  c = bt.choose [1, 2, 3, 4, 5]
  d = bt.choose [1, 2, 3, 4, 5]
  e = bt.choose [1, 2, 3, 4, 5]
  bt.assert( ! [a, b, c, d, e].uniq! )
  bt.assert( a != 5 )
  bt.assert( b != 1 )
  bt.assert( c != 1 && c != 5)
  bt.assert( d > b)
  bt.assert( 1 != (e - c).abs )
  bt.assert( 1 != (c - b).abs )
  [a, b, c, d, e]
end

この関数に先程の bt を渡せば、答えの配列が返ってくる。さらに back しても :done が返ってくるだけなので、答えがただ１つであると分かる。