非決定計算

OnLisp曰く、プログラムに超自然的な力、すなわち未来を見通す力を与える方法。またある人いわく、天使の演算子(angel operator)。

でも結局は、裏では全数探索をするのだけれども、プログラマにそれを意図させないだけなんだけどね。
たとえば、[1,2,3,4,5]というリストから和が5になる組み合わせを探したいとする。
すると普通はこう書く。

for x in [1,2,3,4,5]
  for y in [1,2,3,4,5]
    if x + y == 5 then
      puts x,y
    end
  end
end

でも非決定計算を用いると次のように書ける。

x = amb.choice 1,2,3,4,5
y = amb.choice 1,2,3,4,5
 
unless x + y == 5
  amb.fail
else
  puts x,y
end

すると、あたか??