Ambit-0.9.1 released

dubstep · April 26, 2011, 11:24pm

= ambit

https://github.com/jimwise/ruby/tree/master/ambit

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

== DESCRIPTION:

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[1], or Section 4.3 of SICP[2].

== HISTORY:

=== 0.9.1 / 2011-04-26

Minor documentation improvements

=== 0.9 / 2011-04-26

First public release of ambit

== REQUIREMENTS:

This code will not work in JRuby or MacRuby (no callcc). It should
work
in Ruby 1.9 with minor changes (callcc has moved to the ‘continuation’
stdlib).

== 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
1

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
2
(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
2
(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 – nd 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!.

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
+i+
remains incremented even when we rewind computation).

==== More Than One Answer

Often, more than one combination of choices is interesting to consider
– it
may be useful, for instance, to see all combinations which do not
fail,
instead of only the first.

Since Ambit::fail! will always rewind to the previous choice point,
getting
more possible combinations is as easy as calling Ambit::fail! in order
to
try the next combination – even though we have not, strictly, failed.
When
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

prints
5
15
Done.

Note that this code, too depends on a side effect – +a+ is output each
time
we get a match, even though we then call Ambit::fail! to rewind
computation
and try the next combination.

==== 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 work around 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')
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
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.

==== 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.

==== 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[3], 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

[1] Graham, Paul, On Lisp, Prentice Hall, 1993. Available
online at On Lisp

[2] 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/

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

== LICENSE:

(The BSD 2-clause License)

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

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
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-0.9.1 released

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

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