[plt-scheme] Re: problem with backtracking order of nested ambs

From: Sigrid (keydana at gmx.de)
Date: Tue Oct 6 08:13:20 EDT 2009

Hi Joe,

thanks for your answer! Could you perhaps detail a bit more what you
mean by reversing the nesting of the ambs, so we could see if this
would work here?

To give a more realistic example code, what I really need to do is
something like this:

(let ((list (generate-list-using-amb-for-each-item)))
    (let ((result (amb (let ((correct-list list)) (begin (check-
correct correct-list) correct-list))
                       (let ((nearly-correct-list list)) (begin (check-
nearly-correct nearly-correct-list) (make-acceptable nearly-correct-
                       (let ((still-somehow-correct-list list)) (begin
(check-still-somehow-correct still-somehow-correct-list) (make-
acceptable still-somehow-correct-list))))))

The first list, produced by  (generate-list-using-amb-for-each-item),
is totally unusable - it normally produces lots of identical items. So
I'm totally dependent on the first assert (in check-correct) to run,
and normally, when all goes well, I keep the result and that's it.
But if this assert fails, I have to make sure the program itself
doesn't fail and stop, so I have to handle it somehow. It's not even
so important what I do, the important thing is that I don't get stuck
in the blind alley of backtracking...
With one exception: The first list I can really never accept, so I
cannot just revert to that one.
(Basically I'm just using amb like in the puzzles from SICP,  choosing
whatever values with amb and then "getting it all right" with assert.
Only I have to find a workaround when the assert fails, as in my case
the puzzle needs to have some solution...)

Thanks a lot again for any further suggestions if possible :-)


On 5 Okt., 22:59, Joe Marshall <jmarsh... at alum.mit.edu> wrote:
> I believe that the backtracking order is to the most recent (dynamically) AMB.
> In your example, you could reverse the nesting of the AMBs, but I imagine
> that would be much trickier in the problem you describe.
> The propagator work that Sussman and Radul were doing was exploring how
> to get AMB to backtrack to the nearest one that could potentially satisfy
> the required dependency.  It involves a serious change to the way the compiler
> compiles the code, though.
> On Mon, Oct 5, 2009 at 12:58 PM, keyd... at gmx.de <keyd... at gmx.de> wrote:
> > Hi all,
> > I have a problem with the backtracking order of nested ambs which makes that
> > I cannot get the result I need. I've made up a dummy example:
> >  (let ((x (amb 3 5 4)))
> >   (let ((result (amb (begin (assert (even? x)) x) 77)))
> >     result))
> > I would need amb to first try all of '(3 5 4) and only after that, take 77
> > as last possible way out.
> > In practice, I want to generate a list with amb, then check if every item is
> > unique, if not, try all other possible ways to compose the list - and only
> > there's no way to get it unique,
> > decide that "ok, nearly unique is fine too", such that 2 elements may be the
> > same, so try and assert that... and so on, until I can be sure that at least
> > the program will not fail,
> > not producing any results at all.
> > I'd be glad for any hints what I'm doing wrong here...
> > Thanks a lot in advance,
> > Sigrid
> > _________________________________________________
> >  For list-related administrative tasks:
> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> --
> ~jrm
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.