McCarthy's Ambiguous Operator

Posted by Eric Tue, 11 Oct 2005 00:00:00 GMT

Back in 1961, John McCarthy (the inventor of LISP) described an interesting mathematical operator called amb. Essentially, amb hates to be called with no arguments, and can look into the future to keep that from happening. Here's how it might look in Ruby.

# amb will (appear to) choose values
# for x and y that prevent future
# trouble.
x = amb 1, 2, 3
y = amb 4, 5, 6

# Ooops! If x*y isn't 8, amb would
# get angry.  You wouldn't like
# amb when it's angry.
amb if x*y != 8

# Sure enough, x is 2 and y is 4.
puts x, y

Of course, amb can't actually see the future. However, it can rewind into the past whenever it sees trouble, and try a different coice.

So, how could we implement this function? As it turns out, we need continuations. Here's a basic implementation in Ruby.

# 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

If you'd like a fun, non-technical overview of continuations, see the explanation at RubyGarden.

Tags , , ,

Comments

  1. Dan Piponi said 134 days later:

    I have an implementation of “amb” that can be used in C here. Thanks for giving a name to this operator for me – I never knew what to call it.

  2. Ben said 463 days later:

    Thats really interesting. It means that you could write a constraint DSL in Ruby or any other language which implements continuations. I thought constraint engines were hard…

    Cheers Ben

  3. Ben said 463 days later:

    Wow, I just implemented the send+more=money solver with amb:

    
# define variables
m = 1
n = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)
o = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)
r = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)
s = amb(2, 3, 4, 5, 6, 7, 8, 9)
y = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)
e = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)
d = amb(0, 2, 3, 4, 5, 6, 7, 8, 9)

# reduce the problem space
amb unless(d+e  y || d+e  y+10)
amb unless(s+m+1 >= 10)

	
      
	
    1. The actual problem
send = s1000  e100  n10 + d
more = m1000  o100  n10 + e
money = m10000  o1000  n100  e10  y
amb unless(send+more == money)
      2. 
	
    


	
      
	
    1. p “m=#{m}, n=#{n},  o=#{o}, r=#{r}, s=#{s}, y=#{y}, e=#{e}, d=#{d},”
      2. 
	
    


	
      
	
    1. Make sure all variables are different
a = [m, n, o, r, s, y, e, d]
t = Array.new(10, 0)
a.each { |v| amb unless (t[v]+=1)<2 }
      2. 
	
    


	
      
	
    1. stop
cut
      2. 
	
    


p “Final solution: m=#{m}, n=#{n},  o=#{o}, r=#{r}, s=#{s}, y=#{y}, e=#{e}, d=#{d},”

    Amb is pretty cool! Ben

  4. Eric Kidd said 467 days later:

    Wow! That’s very cool.

    If you’re into constraint languages, you might also enjoy Oz, which can do heavily-optimized searches of constraint problems.

    The big advantage of Oz: Before choosing which path to investigate, it tries to infer as much information as possible (aka “propagation”). And then it makes very intelligent guesses about exactly which “guess” to make next (aka “distribution”).

    Since a backtracking search takes O(2^N) time (yikes!), it’s worth doing a lot of work before actually branching.

    And the most popular implementation of Oz can actually spread the search over an entire cluster of computers!

  5. Christian Theil Have said 605 days later:

    “Since a backtracking search takes O(2^N) time (yikes!), it’s worth doing a lot of work before actually branching.”

    This really depends on the nature of the problem. If you are only going to backtrack a little, it might not be worth spend cycles on forward-checking or ensuring arc consistency. Propagation can also be quite costly.

    But sure, in most cases, amb is not a very efficient way solving constraint problems..