Author:: Jim W. (mailto:[email protected])
Copyright:: Copyright © 2011 Jim W.
License:: 2-clause BSD-Style (see LICENSE.txt)
This is an all-ruby implementation of choose/fail nondeterministic
programming with branch cut, as described in Chapter 22 of Paul Graham’s
On Lisp, or Section 4.3 of SICP.
=== 0.9.1 / 2011-04-26
- Minor documentation improvements
=== 0.9 / 2011-04-26
- First public release of ambit
This code will not work in JRuby or MacRuby (no callcc). It should
in Ruby 1.9 with minor changes (callcc has moved to the ‘continuation’
$ gem install ambit
After checking out the source, run:
$ rake newb
This task will install any missing dependencies, run the tests/specs,
and generate the RDoc.
=== What is Nondeterministic Programming?
Nondeterministic programming is a novel approach to problems where a
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
of hierarchical order, but the right combination is not known in
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
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
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,
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
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
#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
If, later, Ambit::fail! is called, computation is rewound until the
point when Ambit::choose was last called, and the next member of
enumerable is returned from the same call to Ambit::choose:
a = Ambit::choose([1, 2, 3]) Ambit::fail! unless a.even? puts a
(and only “2”)
This means that computation now proceeds as if that had been the
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
(and only “2”)
Note that this call to Ambit::fail! (or Ambit::assert) can occur any
of time later, and works even if the function which called choose
since exited. Execution is still rewound as needed to allow the
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
If that set of choices has already returned every member of its
execution is instead rewound to the previous invocation of
and execution continues with the next choice from that invocation’s
a = Ambit::choose([1, 3, 5, 7, 9, 11, 13, 15]) b = Ambit::choose([0, 5, 10, 15]) Ambit::assert a == b puts a
(and only “5”)
If all choices from all past calls to Ambit::choose have been exhausted
if Ambit::fail! is called before any call to Ambit::choose), an
type Ambit::ChoicesExhausted is raised instead.
==== Side Effects
We’ve talked a lot above about “rewinding” computation to a previous
point. Not all computations can be rewound, however – if the
we have performed since the choice point we are rewinding to has had
effects (other than the choices made), those side effects will not
themselves be rewound. While some side effects (setting of variables)
theoretically be tracked and undone, this would require very careful
semantics – nd other side effects could not be undone by any level of
complexity added to our language. If we have printed output to the
for instance, no amount of rewinding will make the user forget what he
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?
instead of only “2” – the printing has already been done by the time we
Such side effects can also be useful, however. This code:
i = 0 first = Ambit.choose(1..10) second = Ambit.choose(1..10) third = Ambit.choose(1..10) i += 1 Ambit.fail! unless open_lock(first, second, third) puts i
prints out the number of combinations which were tried in total (since
remains incremented even when we rewind computation).
==== More Than One Answer
Often, more than one combination of choices is interesting to consider
may be useful, for instance, to see all combinations which do not
instead of only the first.
Since Ambit::fail! will always rewind to the previous choice point,
more possible combinations is as easy as calling Ambit::fail! in order
try the next combination – even though we have not, strictly, failed.
no more successful combinations are available, this call to Ambit::fail!
will instead raise an exception of type Ambit::ChoicesExhausted.
begin a = Ambit::choose([1, 3, 5, 7, 9, 11, 13, 15]) b = Ambit::choose([0, 5, 10, 15]) Ambit::assert a == b puts a Ambit::fail! rescue Ambit::ChoicesExhausted puts "Done." end
Note that this code, too depends on a side effect – +a+ is output each
we get a match, even though we then call Ambit::fail! to rewind
and try the next combination.
==== Cleaning up
Ambit::clear! can be called at any time to eliminate all outstanding
on the default Generator, ending nondeterminism (and allowing any
outstanding alternate paths of execution to be garbage collected). This
most useful when a given computation is finished, so that future
of Ambit::fail! will not restart the now-finished computation with
==== Marking and Cutting
While Ambit::clear! can be used to abandon an entire set of
computations, sometimes it is useful to abandon only one branch of a
computation, while still keeping the ability to rewind to the choice
first took us down that branch.
Suppose, for instance, that we are trying to guess a word with four
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
were chosen, whether the first letter was correct? How would we
If we failed because the first letter was incorrect, we would continue
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
To work around this, Ambit provides a method, Ambit::cut! which “locks
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') if !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
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
since the last call to Ambit::mark – in this case, we are saying that
know these choices are good, so if we (later) fail, we want to rewind
the whole current branch of computation.
==== Private Generators
In addition to using methods of the Ambit module directly, another
to allocate an Ambit::Generator object explicitly. All methods of the
module are also available as methods of Ambit::Generator (and in fact,
module allocates a default Generator object to handle all calls made at
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
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
but it is often clearer to use a new Ambit::Generator object for each
unrelated set of nondeterministic computations.
For historical reasons, Ambit::amb and Ambit::Generator#amb are provided
aliases for Ambit::choose and Ambit::Generator#choose. Likewise, for
historical reasons, calling Ambit::choose (and Ambit::Generator#choose)
no arguments is equivalent to calling Ambit::fail! (or
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
the amb operator discussed in SICP and elsewhere.
==== Interaction with Threading
Given the strong modifications to flow of control which occur when a
computation is failed, care must be taken when using nondeterministic
programming in a multi-threaded program. The two main ways to do this
perform all nondeterministic programming from a single thread of
give each thread which will be using nondeterministic programming its
own Ambit::Generator object. This can be done easily using thread local
Thread.current[:AMB] = Ambit::Generator.new
def nd_choose choices
=== Longer example
This solution to the N queens problem is inspired by the prolog version
The Art of Prolog by Leon Sterling and Ehud Shapiro, but is
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
# 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
The file examples/queens.rb, installed with this gem, contains a version
this with display code, and a command-line driver to print all solutions
a given N.
 Graham, Paul, On Lisp, Prentice Hall, 1993. Available
online at http://www.paulgraham.com/onlisp.html
 Abelson, Harold and Gerald Jay Sussman, Structure and
Interpretation of Computer Programs, 2nd Edition, MIT Press, 1996.
Available online at http://mitpress.mit.edu/sicp/
 Sterling, Leon and Ehud Shapiro, The Art of Prolog, MIT
(The BSD 2-clause License)
Copyright © 2011 Jim W.
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
- 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
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
“AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
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
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
POSSIBILITY OF SUCH DAMAGE.