Module: Amb::Operator

Defined in:
lib/amb/amb_operator.rb

Overview

Use the ambiguous computation pattern as a stand-alone operator.

Instance Method Summary collapse

Instance Method Details

#amb(*choices) ⇒ Object

Recursive implementation of the amb operator, as defined by McCarty.

When choices are provided as arguments, it will save a backtracking save point for each and wait for being resumed. Resuming (starting the check/discard process) is triggered by calling amb without any arguments. It is expected you’ll attach a conditionnal stating the constraint.

Examples:


# 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 = #{x}, y = #{y}"

Parameters:

  • choices —

    a set of alternatives



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/amb/amb_operator.rb', line 44

def amb *choices
  # Fail if we have no arguments.
  backtrack if choices.empty?

  callcc do |cc|
    # cc contains the "current continuation". When called, it will make the
    # program rewind to the end of this block.
    $backtrack_points << cc

    # Return our first argument.
    return choices[0]
  end

  # We only get here if we backtrack by resuming the stored value of cc.
  # We call amb recursively with the arguments we didn't use.
  amb(*choices[1...choices.length])
end

#backtrack ⇒ Object

Rewind to our most recent backtrack point.



13
14
15
16
17
18
19
 
# File 'lib/amb/amb_operator.rb', line 13

def backtrack
  if $backtrack_points.empty?
    raise "Can't backtrack"
  else
    $backtrack_points.pop.call
  end
end

#cut ⇒ Object

Backtracking beyond a call to cut is strictly forbidden.



64
65
66
 
# File 'lib/amb/amb_operator.rb', line 64

def cut
  $backtrack_points = []
end