amb

amb หรือ Angelic Operator เป็น operator ที่มีเฉพาะใน
language ที่ support continuations เท่านั้น
(scheme, ruby, ...)
Angelic Operator มีชื่อเรียกอีกชื่อคือ "McCarthy's Ambiguous Operator
(John McCarthy คือคนที่สร้าง Lisp ขึ้นมา)

ลองดูความพิสดารของมันกัน
(โจทย์จาก ruby quiz #70)

begin
  a = amb 0,1,2,3,4
  b = amb 0,1,2,3,4
  c = amb 0,1,2,3,4

  amb unless a < b
  amb unless a + b == c
  puts "a = #{a}, b = #{b}, c = #{c}"
  amb
rescue
  puts "no more solution."
end

ผลลัพท์ที่ได้ จะมีหน้าตาแบบนี้

irb(main):063:0> 
a = 0, b = 1, c = 1
a = 0, b = 2, c = 2
a = 0, b = 3, c = 3
a = 0, b = 4, c = 4
a = 1, b = 2, c = 3
a = 1, b = 3, c = 4
no more solution.
nil

โดยในตอนแรกที่เราสั่ง

a = amb 0,1,2,3,4

a จะมีค่าเป็น 0
ส่วน b และ c ก็จะเริ่มต้นที่ 0 เช่นเดียวกัน
จากนั้นเมื่อถึงบรรทัดที่

amb unless a < b

ณ จุดที่ evaluate นี้ a กับ b มีค่า เท่ากับ 0
ดังนั้นมันจะเกิดการเรียกใช้ amb แบบไม่มี parameter
ซึ่งจะทำให้เกิดการ backtrack ย้อนกลับไปให้เลือกค่า a, b ใหม่
จนได้ค่า a = 0, b = 1 มา จึงจะผ่านบรรทัดนี้ไปได้

key สำคัญก็คือการ backtrack ซึ่งเขา implement โดยใช้ contiunation
ตัวอย่างการ implement amb โดย Jim Weirich
มีหน้าตาแบบนี้

class Amb

  class ExhaustedError < RuntimeError; end

  def initialize
    @fail = proc { fail ExhaustedError, "amb tree exhausted" }
  end

  def choose(*choices)
    prev_fail = @fail
    callcc { |sk|
      choices.each { |choice|
        callcc { |fk|
          @fail = proc {
            @fail = prev_fail
            fk.call(:fail)
          }
          if choice.respond_to? :call
            sk.call(choice.call)
          else
            sk.call(choice)
          end
        }
      }
      @fail.call
    }
  end
  
  def failure
    choose
  end
  
  def assert(cond)
    failure unless cond
  end
end

เห็นแล้วตาลาย เพราะเขา port มาจากตัวอย่างใน Teach Yourself Scheme in Fixnum Days โดยตรง
มันมีกลิ่นของ funtional language เยอะไปหน่อย

แต่ลองดูตัวอย่างที่ Eric Kidd implement ไว้อีกแบบ
อันนี้มีกลิ่น imperative language เยอะหน่อย ทำให้ดูเข้าใจง่ายขึ้น

# A list of places we can "rewind" to
# if we encounter amb with no
# arguments.
$backtrack_points = []

# Rewind to our most recent backtrack
# point.
def backtrack
  if $backtrack_points.empty?
    raise "Can't backtrack"
  else
    $backtrack_points.pop.call
  end
end

# Recursive implementation of the
# amb operator.
def amb *choices
  # Fail if we have no arguments.
  backtrack if choices.empty?
  callcc {|cc|
    # cc contains the "current
    # continuation".  When called,
    # it will make the program
    # rewind to the end of this block.
    $backtrack_points.push cc

    # Return our first argument.
    return choices[0]
  }

  # We only get here if we backtrack
  # using the stored value of cc,
  # above.  We call amb recursively
  # with the arguments we didn't use.
  amb *choices[1...choices.length]
end

# Backtracking beyond a call to cut
# is strictly forbidden.
def cut
  $backtrack_points = []
end

ดูง่ายกว่ากันเยอะเลย

ลอง implement โจทย์เดียวกันนี้ใน scheme บ้าง
(สบายหน่อย ตรง scheme มี library amb มาให้อยู่แล้ว)
หน้าตาโปรแกรมออกมาแบบนี้

(require (lib "extra.ss" "swindle"))

(define assert
  (lambda (pred)
    (if (not pred) (amb))))

(define solve
  (lambda ()
    (let ((a (amb 0 1 2 3 4))
          (b (amb 0 1 2 3 4))
          (c (amb 0 1 2 3 4)))
      (assert (< a b))
      (assert (equal? (+ a b) c))
      
      (printf "a=~a, b=~a, c=~a\n" a b c)
      (amb))))