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.