ambit

Author: Jim Wise ([email protected])
Copyright: Copyright © 2011 Jim Wise
License: 2-clause BSD-Style (see LICENSE.txt)

DESCRIPTION:

Ambit is a ruby non-deterministic programming system with backtracking and branch cut.

REQUIREMENTS:

This code will not work in JRuby or MacRuby (no callcc). It is tested (and should work fine) in Ruby 1.8.7, 1.9.3, and 2.0.0.

INSTALL:

To install:

$ gem install ambit

DEVELOPERS:

After checking out the source, run:

$ rake newb

This task will install any missing dependencies, run the tests/specs, and generate the RDoc.

SYNOPSIS:

What is Nondeterministic Programming?

Nondeterministic programming is a novel approach to problems where a program must find a working solution out of many possible choices. It greatly simplifies problems such as graph searching, or testing combinations of values, where there are many possible values to consider, often in some sort of hierarchical order, but the right combination is not known in advance.

In such a situation, it can be useful to develop a program by pretending our programming language includes knowledge of the future – and is thus able to choose the right answer off the bat, and simply programming as if this were the case.

A language with support for nondeterministic programming (such as Ruby with this gem) helps us keep up this pretense by saving the state of computation (with some limits) whenever we make an important choice. If we later determine that we did not, in fact, make the correct choice (lacking true language support for knowing the future), we can fail the current computation, which causes computation to rewind to the last choice made, and continue as if a different choice had been made.

When all possible choices have been tried, the next time computation fails, computation will be rewound to the previous choice point, and will continue with the next possible choice from there.

Imagine, for instance, that we wish to test a combination lock with a three-number combination, with each number between 1 and 10, inclusive. Instead of writing code ourself to try every possible combination, we simply proceed as if each choice was the correct one, failing if the lock fails to open. In short:

first = Ambit.choose(1..10)
second = Ambit.choose(1..10)
third = Ambit.choose(1..10)

Ambit.fail! unless open_lock(first, second, third)

# when we get here, lock is open!

As our language does not actually implement knowledge of the future, this will still try as many combinations as are needed to find the right one – but we can program as if it has chosen the right one on the first try!

How to Use This Gem

To get started, include this gem using

require 'rubygems'
require 'ambit'

This gem provides the Ambit module. This module provides several methods which implement nondeterministic programming.

Choosing and Failing

The central method of Ambit is Ambit::choose.

Ambit::choose takes any enumerable (actually, any object which responds to #each) as an argument, and begins a nondeterministic generate-and-test process with the members of this object.

Ambit::choose immediately returns the first member of the enumerable, or calls Ambit::fail! if the enumerable is empty:

a = Ambit::choose([1, 2, 3])
puts a

prints

If, later, Ambit::fail! is called, computation is rewound until the point when Ambit::choose was last called, and the next member of the enumerable is returned from the same call to Ambit::choose:

a = Ambit::choose([1, 2, 3])
Ambit::fail! unless a.even?
puts a

prints

(and only “2”)

This means that computation now proceeds as if that had been the value returned by Ambit::choose all along.

As an alternative, Ambit::assert can be used to fail unless a condition holds. Ambit::assert will rewind to the previous invocation of Ambit::choose if and only if it’s (single) argument is false:

a = Ambit::choose([1, 2, 3])
Ambit::assert a.even?
puts a

prints

(and only “2”)

Note that this call to Ambit::fail! (or Ambit::assert) can occur any amount of time later, and works even if the function which called choose has since exited. Execution is still rewound as needed to allow the next value to be returned from the same call to Ambit::choose.

Calls to Ambit::choose can be nested to arbitrary depth – each call to Ambit::fail! will rewind to the most recent call to Ambit::choose. If that set of choices has already returned every member of its enumerable, execution is instead rewound to the previous invocation of Ambit::choose, and execution continues with the next choice from that invocation’s enumerable:

a = Ambit::choose([1, 3, 5, 7, 9, 11, 13, 15])
b = Ambit::choose([0, 5, 10, 15])
Ambit::assert a == b
puts a

prints 5 (and only “5”)

If all choices from all past calls to Ambit::choose have been exhausted (or if Ambit::fail! is called before any call to Ambit::choose), an exception of type Ambit::ChoicesExhausted is raised instead.

Side Effects

We’ve talked a lot above about “rewinding” computation to a previous choice point. Not all computations can be rewound, however – if the computation we have performed since the choice point we are rewinding to has had side effects (other than the choices made), those side effects will not themselves be rewound. While some side effects (setting of variables) could theoretically be tracked and undone, this would require very careful semantics – and other side effects could not be undone by any level of complexity added to our language. If we have printed output to the user, for instance, no amount of rewinding will make the user forget what he has seen; while we simulate the ability to see the future and to change the past, we can, in fact, do neither.

This can sometimes cause confusion. This code, for instance:

a = Ambit::choose([1, 2, 3])
puts a
Ambit::fail! unless a.even?

prints

1
2

instead of only “2” – the printing has already been done by the time we call Ambit::fail!.

Likewise, this code:

x = 1
y = Ambit::choose([1, 2, 3])
if y == 2
  puts x
else
  x = 42
end
Ambit::fail! unless a.even?

prints

, not 1, as Ambit does not rewind the setting of ‘x’ after the first return from Ambit::choose.

Such side effects can also be useful, however. This code:

i = 0
first = Ambit.choose(1..10)
i += 1
second = Ambit.choose(1..10)
i += 1
third = Ambit.choose(1..10)
i += 1
Ambit.fail! unless open_lock(first, second, third)
puts i

prints out the number of values which were chosen in total (since i remains incremented even when we rewind computation).

If we wanted to avoid this type of side effect, one option would be to use a function argument to capture this setting, as function calls (and thus the value of their arguments and local variables) are rewindable. This version, for instance:

def try_first
  i = 0
  first = Ambit::choose(1..10)
  try_second(i + 1, first)
end

def try_second i, first
  second = Ambit::choose(1..10)
  try_third(i + 1, first, second)
end

def try_third i, first, second
  third = Ambit::choose(1..10)
  Ambit.fail! unless open_lock(first, second, third)
  puts i+1
end

try_first

will always print 3 – the number of values tried in the ultimately successful series of choices, rather than the number of combinations tried over all.

Cleaning up

Ambit::clear! can be called at any time to eliminate all outstanding choices on the default Generator, ending nondeterminism (and allowing any outstanding alternate paths of execution to be garbage collected). This is most useful when a given computation is finished, so that future invocations of Ambit::fail! will not restart the now-finished computation with another choice.

Marking and Cutting

While Ambit::clear! can be used to abandon an entire set of nondeterministic computations, sometimes it is useful to abandon only one branch of a computation, while still keeping the ability to rewind to the choice which first took us down that branch.

Suppose, for instance, that we are trying to guess a word with four letters:

a = Ambit::choose('a'..'z')
b = Ambit::choose('a'..'z')
c = Ambit::choose('a'..'z')
d = Ambit::choose('a'..'z')
Ambit::assert good_word(a, b, c, d)
print a, b, c, d

This works. But what if we were able to determine, once all four letters were chosen, whether the first letter was correct? How would we proceed?

If we failed because the first letter was incorrect, we would continue trying every possible value for the second, third and fourth letters – even though none of them could be correct. We need a way to rewind to an earlier choice point.

To allow this, Ambit provides a method, Ambit::cut! which “locks in” a set of past choices, preventing them from being revisited later:

a = Ambit::choose('a'..'z')
Ambit::mark
b = Ambit::choose('a'..'z')
c = Ambit::choose('a'..'z')
d = Ambit::choose('a'..'z')
unless good_first_letter(a, b, c, d)
  Ambit::cut! 
  Ambit::fail!
end   
Ambit::assert good_word(a, b, c, d)
print a, b, c, d

When Ambit::cut! is called in the code above, all choices back to the most recent call of Ambit::mark are wiped out – the next call to Ambit::fail! will rewind to the most recent Ambit::choose invocation before the most recent call to Ambit::mark.

Ambit::cut! can also be used without Ambit::fail! to “commit” to all choices since the last call to Ambit::mark – in this case, we are saying that we know these choices are good, so if we (later) fail, we want to rewind out of the whole current branch of computation.

Finally, Ambit::unmark! can be used to remove the most recent mark (making the next Ambit::cut! operation cut back to an earlier mark (or commit to all choices if no other mark exists), and the Ambit::unmark_all! operation can be used to remove all current marks, making the next Ambit::cut! operation commit to all choices made so far.

Watching Ambit work

The class method Ambit::trace can be used to enable debug tracing of Ambit operations. Repeated calls to Ambit::trace increase the verbosity of trace output (though this has no effect in the current version), and a specific trace level (as an integer) may also be passed to Generator#trace as an optional argument.

Trace output is written to STDERR. Trace output can be disabled by specifying a trace level of 0, or by calling Ambit::untrace.

Private Generators

In addition to using methods of the Ambit module directly, another option is to allocate an Ambit::Generator object explicitly. All methods of the Ambit module are also available as methods of Ambit::Generator (and in fact, the module allocates a default Generator object to handle all calls made at the module level).

Ambit::Generator::new can be used to allocate a new Generator:

nd = Ambit::Generator::new
nd.choose('a' .. 'e')

each object allocated in this fashion has its own set of choices, and failing one will not directly affect others. Nesting choices from different Generators is a good way to make code confusing, however, and should be avoided – this capability is mainly provided to allow multi-threaded programs to safely use Ambit from more than one thread (see below).

Ambit::Generator#clear! is provided for the same reason as Ambit::clear!, but it is often clearer to use a new Ambit::Generator object for each unrelated set of nondeterministic computations.

As with other module-level operations, Ambit::trace and Ambit::untrace do not turn on or off tracing for private generators – the generator’s own Ambit::Generator#trace and Ambit::Generator#untrace must be used to enable tracing of a private generator’s operation.

Compatibility

For historical reasons, Ambit::amb and Ambit::Generator#amb are provided as aliases for Ambit::choose and Ambit::Generator#choose. Likewise, for historical reasons, calling Ambit::choose (and Ambit::Generator#choose) with no arguments is equivalent to calling Ambit::fail! (or Ambit::Generator#fail!).

For the same reason, Ambit::require and Ambit::Generator#require are provided as aliases for Ambit::assert and Ambit::Generator#assert.

These aliases allow for a more direct translation of programs written with the amb operator discussed in SICP and elsewhere.

Interaction with Threading

Given the strong modifications to flow of control which occur when a path of computation is failed, care must be taken when using nondeterministic programming in a multi-threaded program. The two main ways to do this are:

perform all nondeterministic programming from a single thread of execution

give each thread which will be using nondeterministic programming its own Ambit::Generator object. This can be done easily using thread local variables:

def nd_begin
  Thread.current[:AMB] = Ambit::Generator.new
end

def nd_choose choices
  Thread.current[:AMB].choose choices
end

def nd_fail! 
  Thread.current[:AMB].fail!
end

def nd_clear! 
  Thread.current[:AMB].clear!
end

Longer example

This solution to the N queens problem is inspired by the prolog version in The Art of Prolog by Leon Sterling and Ehud Shapiro, but is less elegant, as this is not prolog (and I am not Sterling or Shapiro).

# we want to place N queens on an NxN chess board.  Since we know no two queens
# can be in the same row, an array of N integers between 0 and N-1 will do to
# represent the placement.  Since we know no two queens can be in the same column,
# each number from 1 .. N will appear once in this array;  this means the solution
# is a permutation of 1 .. N

# Here is the complete board generator.  Next is the test if a position is safe.

def queens n, board = []
  if board.size == n
    board
  else
    c = Ambit.choose(1..n)
    Ambit.fail! unless safe board, c
    queens n, board + [c]
  end
end

# board is the first M columns of an NxN board, and is valid so far.
# piece is a proposed piece for the M+1th row of the board.
# returns true if piece is a valid placement, false otherwise

def safe board, piece
  board.each_with_index do |c, r|
    return false if c == piece  # same column
    # they're on the same diagonal if the distance in columns == the distance in rows
    rdist = board.size - r
    cdist = (piece - c).abs
    return false if rdist == cdist
  end
  true
end

The file examples/queens.rb, installed with this gem, contains a version of this with display code, and a command-line driver to print all solutions for a given N.

References

For more information on nondeterministic programming, see

Abelson, Harold and Gerald Jay Sussman, <em>Structure and Interpretation

of Computer Programs, 2nd Edition</em>, Section 4.3, MIT Press, 1996. Available online at mitpress.mit.edu/sicp/

Graham, Paul, On Lisp, Chapter 22, Prentice Hall, 1993. Available

online at www.paulgraham.com/onlisp.html

Sterling, Leon and Ehud Shapiro, The Art of Prolog, MIT Press, 1994

LICENSE:

(The BSD 2-clause License)

Copyright (c) 2011 Jim Wise
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS
BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

ambit

DESCRIPTION:

REQUIREMENTS:

INSTALL:

DEVELOPERS:

SYNOPSIS:

What is Nondeterministic Programming?

How to Use This Gem

Choosing and Failing

Side Effects

More Than One Answer

Cleaning up

Marking and Cutting

Watching Ambit work

Private Generators

Compatibility

Interaction with Threading

Longer example

References

LICENSE: