McCarthy's Ambiguous Operator

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 .