[plt-scheme] how to test for optional requirements in nondeterministic programming

From: Thomas Chust (chust at web.de)
Date: Tue Jan 20 09:44:26 EST 2009

Sigrid Keydana wrote:
> [...]
> like in the SICP "puzzles", I am using amb to choose people from a list
> and then verify that requirements are fulfilled with an assert method.
> Now, in addition to the requirements, I also want to make the result
> satisfy some "optional" requirements or "nice-to-have"s if possible, but
> in contrast to the "hard requirements" the program may not fail if this
> doesn't work out.
> [...]


this sounds as if you could solve your problem simply by nesting the
dynamic scope of amb backtracking contexts. Here is a stupid example
that wraps the results satisfying all hard preconditions in pairs whose
car is #t iff the soft preconditions are met and whose cdr contains the
result itself:

  #lang scheme
   (planet murphy/amb:1:1/amb))

  (define (solutions)
     (let ([i (let ([i (for/amb ([i (in-range 0 10)])
                ;; Check hard preconditions
                (amb-assert (odd? i))
                (amb-assert (> i 1))
       (cons (amb
                ;; Check soft preconditions
                (amb-assert (> i 5))
                (amb-assert (< i 9))

[The for/amb syntax is just a shorthand from my implementation of the
amb operator. In this particular example it could be replaced with (amb
0 1 ... 9)]


Posted on the users mailing list.