[ANN] ambit-0.9.1 released

=3D ambit

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

Author::    Jim Wise  (mailto:[e-mail])
Copyright:: Copyright (c) 2011 Jim Wise
License::   2-clause BSD-Style (see LICENSE.txt)

=3D=3D DESCRIPTION:

This is an all-ruby implementation of choose/fail nondeterministic
programming with branch cut, as described in Chapter 22 of Paul Graham's
<em>On Lisp</em>[1], or Section 4.3 of <em>SICP</em>[2].

=3D=3D HISTORY:

=3D=3D=3D 0.9.1 / 2011-04-26

* Minor documentation improvements

=3D=3D=3D 0.9 / 2011-04-26

* First public release of ambit

=3D=3D REQUIREMENTS:

<b>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).</b>

=3D=3D INSTALL:

To install:=20

    $ gem install ambit

=3D=3D DEVELOPERS:

After checking out the source, run:

    $ rake newb

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

=3D=3D SYNOPSIS:

=3D=3D=3D 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 <em>causes computation to rewind to the last
choice made, and continue as if a different choice had been made</em>.

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 =3D Ambit.choose(1..10)
    second =3D Ambit.choose(1..10)
    third =3D 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!

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

=3D=3D=3D=3D 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 =3D Ambit::choose([1, 2, 3])
    puts a
prints
    1

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

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

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

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 =3D 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 <em>even if the function which called choose has
since exited</em>.  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 <em>most recent</em> 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 =3D Ambit::choose([1, 3, 5, 7, 9, 11, 13, 15])
    b =3D Ambit::choose([0, 5, 10, 15])
    Ambit::assert a =3D=3D 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.

=3D=3D=3D=3D 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 =3D 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 =3D 0
    first =3D Ambit.choose(1..10)
    second =3D Ambit.choose(1..10)
    third =3D Ambit.choose(1..10)
    i +=3D 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).

=3D=3D=3D=3D 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 =3D Ambit::choose([1, 3, 5, 7, 9, 11, 13, 15])
      b =3D Ambit::choose([0, 5, 10, 15])
      Ambit::assert a =3D=3D 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.

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

=3D=3D=3D=3D 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 =3D Ambit::choose('a'..'z')
    b =3D Ambit::choose('a'..'z')
    c =3D Ambit::choose('a'..'z')
    d =3D 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 tryi=
ng
every possible value for the second, third and fourth letters -- even thoug=
h 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 =3D Ambit::choose('a'..'z')
    Ambit::mark
    b =3D Ambit::choose('a'..'z')
    c =3D Ambit::choose('a'..'z')
    d =3D Ambit::choose('a'..'z')
    if !good_first_letter(a, b, c, d)
      Ambit::cut!=20
      Ambit::fail!
    end=20=20=20
    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
<em>most recent</em> call of Ambit::mark are wiped out -- the next call to
Ambit::fail! will rewind to the most recent Ambit::choose invocation
<em>before</em> 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.

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

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

=3D=3D=3D=3D 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 varia=
bles:

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

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

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

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

=3D=3D=3D Longer example

This solution to the N queens problem is inspired by the prolog version in
<em>The Art of Prolog</em> 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 tw=
o 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 s=
ame column,
    # each number from 1 .. N will appear once in this array;  this means t=
he 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 =3D []
      if board.size =3D=3D n
        board
      else
        c =3D 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 =3D=3D piece  # same column
        # they're on the same diagonal if the distance in columns =3D=3D th=
e distance in rows
        rdist =3D board.size - r
        cdist =3D (piece - c).abs
        return false if rdist =3D=3D 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.

=3D=3D=3D References

[1] Graham, Paul, <em>On Lisp</em>, Prentice Hall, 1993. Available online a=
t http://www.paulgraham.com/onlisp.html

[2] Abelson, Harold and Gerald Jay Sussman, <em>Structure and Interpretatio=
n of Computer Programs, 2nd Edition</em>, MIT Press, 1996.  Available onlin=
e at http://mitpress.mit.edu/sicp/

[3] Sterling, Leon and Ehud Shapiro, <em>The Art of Prolog</em>, MIT Press,=
 1994

=3D=3D 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 CONTRIB=
UTORS
  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.

=2D-=20
				Jim Wise
				[e-mail]