How implement AMB in perl?

xiaoyafeng has asked for the wisdom of the Perl Monks concerning the following question:

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))))
[download]

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?

I am trying to improve my English skills, if you see a mistake please feel free to reply or /msg me a correction

Comment on How implement AMB in perl? Download Code

Replies are listed 'Best First'.
Re: How implement AMB in perl? by dk (Chaplain) on Apr 29, 2007 at 08:37 UTC
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.	[reply] [d/l] [select]
Re^2: How implement AMB in perl? by Enlil (Parson) on Apr 29, 2007 at 09:30 UTC
...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	[reply]
Re^3: How implement AMB in perl? by dk (Chaplain) on Apr 29, 2007 at 09:40 UTC
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.	[reply] [d/l]
Re^4: How implement AMB in perl? by halley (Prior) on Apr 30, 2007 at 12:52 UTC
Re: How implement AMB in perl? by akho (Hermit) on Apr 29, 2007 at 11:36 UTC
This task can be solved with several nested `grep`s. 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;` [download] The `which_1` sub returns whichever element of an array (passed as a reference in a second arg) first matches all the `need`s 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.	[reply] [d/l] [select]
Re^2: How implement AMB in perl? by blazar (Canon) on Apr 29, 2007 at 12:42 UTC
Remember — continuations can (and should) usually be replaced with closures or threads. Not to repeat myself, but...	[reply]
Re: How implement AMB in perl? by ambrus (Abbot) on Apr 29, 2007 at 13:52 UTC
Wait for perl6, or get a real scheme or ruby. Really. Not even Coro can give you real continuations you'd need for this.	[reply]
Re^2: How implement AMB in perl? by Joost (Canon) on Apr 29, 2007 at 14:32 UTC
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. "What should it profit a man, if he should win a flame war, yet lose his cool?"	[reply]
Re: How implement AMB in perl? by jdporter (Paladin) on Apr 30, 2007 at 14:18 UTC
I wonder if Quantum::Superpositions could be used to solve such problems. :-)	[reply]
Re: How implement AMB in perl? by Moron (Curate) on May 01, 2007 at 09:13 UTC
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. __________________________________________________________________________________ ^M Free your mind!	[reply]
Re: How implement AMB in perl? by clscott (Friar) on May 02, 2007 at 00:34 UTC
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. -- Clayton	[reply]