How implement AMB in perl?

[xiaoyafeng]

Hi gurus,

I found a very interesting artical about AMB.This is a very interesting and useful function. We can use it to solve many questions. For example:
"Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?"
scheme code is as followings:

(define (require p)
(if (not p) (amb)))

(define (distinct? items)
    (cond ((null? items) true)
          ((null? (cdr items)) true)
          ((member (car items) (cdr items)) false)
          (else (distinct? (cdr items)))))

(define (multiple-dwelling)
  (let  ((baker  (amb 1 2 3 4 5))
         (cooper (amb 1 2 3 4 5))
         (fletcher  (amb 1 2 3 4 5))
         (miller (amb 1 2 3 4 5))
         (smith  (amb 1 2 3 4 5))
      (require
       (distinct? (list baker cooper fletcher miller smith)))
(require (not (= baker 5)))
(require (not (= cooper 1)))
(require (not (= fletcher 5)))
(require (not (= fletcher 1)))
(require (> miller cooper)))
(require (not (= (abs (- smith fletch)) 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(list (list 'baker baker)
      (list 'cooper cooper)
      (list 'fletcher fletcher)
      (list 'miller miller)
      (list 'smith smith))))

I have attempt to implement amb function in perl, but failed. Compared to scheme, It seems that perl couldn't deal with continuation.

Any suggestions?

[dk]

Interesting article, thanks, I didn't know about amb before. As to your question how one would implement the function in perl, let me quote the aticle:

...we perform a depth-first search of the amb choice tree, and whenever we brush against failure, we backtrack to the most recent node of the tree that offers a further choice

In Perl, the function of the "choice tree" can be thought of as the function of the OP tree. That means, whenever amb would be called, it should investigate the caller and traverse the OP tree. The closest module I know that does similar things is Want module, which travels up the caller's OP tree. It would be really interesting to see if this approach works for amb.

Update: as to continuations, check out Coro.

[Enlil]

...we perform a depth-first search of the amb choice tree, and whenever we brush against failure, we backtrack to the most recent node of the tree that offers a further choice

That statement screams, regexes, or rather a creative use of them, akin to:

The N-queens problem using pure regexes
Pure regex Hamiltonian Circuit solution



-Enlil

[dk]

That'd be also interesting indeed, except that regexes should operate on the OP-tree, not a string. Shouldn't be a too big problem with (??{}) and friends though.

[akho]

This task can be solved with several nested greps. But if you want proper amb just for the joy of it — the following code is somewhat close.

use warnings;
use strict;
use Carp;

sub need 
{
        my $cond = shift;
        croak 'require failed' if (!$cond);
}

sub which_1
{
        my ($code, $vals) = @_;
        for my $param (@{$vals}) {
                if (my $res = eval { &{$code}($param); return 1; }) {
                        return $param;
                }
        }
        croak 'no match';
}

my @floors = (1..5);
print which_1 sub { my $p = shift; need($p == 3); }, \@floors;

The which_1 sub returns whichever element of an array (passed as a reference in a second arg) first matches all the needs in the code reference (first arg).

One can generalize this to an arbitrary number of array references using currying. I may do this later, when I have more time.

Remember — continuations can (and should) usually be replaced with closures or threads.

[blazar]

Remember — continuations can (and should) usually be replaced with closures or threads.

Not to repeat myself, but...

[ambrus]

Wait for perl6, or get a real scheme or ruby. Really. Not even Coro can give you real continuations you'd need for this.

[Joost]

I just spend a few hours messing about with Coro, googling and reading scheme documentation which got me a lot of headaches, and I'm inclined to agree. As far as I could figure out, you can't reproduce call/cc with Coro.

The fact that Coro::Cont seems to have disappeared from the Coro distribution was also kind of annoying.

I did find this interesting description of an implementation of Amb in ruby (the actual implementation is at the bottom of that page, more or less a direct port of the scheme implementation mentioned in the OP.

[jdporter]

I wonder if Quantum::Superpositions could be used to solve such problems. :-)

[Moron]

I was taught to solve this type of problem using linear programming. For Perl implementation, Math::MatrixSparse looks the most apt from that point of view.

Wikipedia has numerous entries under "amb" but they seem rather eclectic and none quite hit the spot ("Al-Aqsa Martyrs Brigades" in particular ;))

Update: the module has a Gauss-Seidel method that can perform the actual solution for the OP example.

[clscott]

I know that this is not why you posted but I couldn't resist pointing out that the Games::LogicPuzzle module was built to solve these types of puzzles.

You might want to look and see how it works in th general case.