McCarthy’s Ambiguous Operator (2005)


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

# 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"

# 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]

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

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

Read More

This site uses Akismet to reduce spam. Learn how your comment data is processed.