継続でバックトラックを Ruby で

年度末になると忙しくなる人種に巻き込まれてしまい、RubyPerl を使って遊ぶのは数週間ぶりのことです。中断していた作業をチェックアウトして眺めていたのですが、どうも気分が乗らないので、リハビリを兼ねて LispUser.net : 継続でバックトラックscheme のバックトラックの例題を Ruby に直訳してみました。
if 文の条件式を満たす x、y、z の組み合わせを探す問題です。探索範囲は 0 から 100 の整数。それぞれの値で条件が成り立つかどうかをチェックし、成り立たないときは、fail 関数を呼ぶことでバックトラックを生じさせて、次の数値のチェックを続けます。

require 'trial'

def solve
  x = Trial.in_range(0, 100)
  y = Trial.in_range(0, 100)
  z = Trial.in_range(0, 100)
  if x * x == 2 * y + z + 500
    [x, y, z]
  else
    Trial.fail
  end
end

p solve #=> [23, 0, 29]

試行の仕組みは Trial モジュールへ閉じ込めておくことにしました。

module Trial
  @@fail = lambda { raise "no solution" }
  
  class <<self
    def fail
      @@fail.call
    end
    
    def in_range(i, f)
      callcc {|k| step_by_step(i, f, k) }
    end
    
    private
    
    def step_by_step(i, f, cont)
      if i > f
        @@fail.call
      else
        last_one = @@fail
        @@fail = lambda {
          @@fail = last_one
          step_by_step(i + 1, f, cont)
        }
        cont.call(i)
      end
    end
  end
end

再試行時に実行するプロシージャを挿げ替えていくのが技で、うまいやりかたです。Ruby の現在の継続のコールはスタックコピーの書き戻しジャンプなので、実行速度がいまいちですが、solve 関数の可読性は捨てがたいですね。同じバックトラックするにしても、素直にループを回す方が速いはずでしょうけど。なお、ここでは、クラス変数をプロシージャへ束縛しておくことにしましたが、Trial モジュール・オブジェクトのインスタンス変数の方が良かったかもしれないと動かした後で気が付いたのですが……まあいいか。