Tuesday, September 12, 2006

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))))

Related link from Roti

No comments: