Libraries for Vicare Scheme: amb examples ssc

1.4.2.2 Seed, square, cube

Given the seed numbers:

1 3

let’s say we want to select the one having the square among:

5 9 11

and the cube among:

13 27 31

we can imagine a search tree, amb examples ssc.

     | A |    | B |    | C |

o----- 1 -----  5 ----- 13
   |       |        |-- 27
   |       |         -- 31
   |       |
   |       |--  9 ----- 13
   |       |        |-- 27
   |       |         -- 31
   |       |
   |        -- 11 ----- 13
   |                |-- 27
   |                 -- 31
   |
    -- 3 -----  5 ----- 13
           |        |-- 27
           |         -- 31
           |
           |--  9 ----- 13
           |        |-- 27
           |         -- 31
           |
            -- 11 ----- 13
                    |-- 27
                     -- 31

Figure 1.1: Search tree for the seed, square, cube problem.

If we assign a selected seed to the variable A, a selected possible square to the variable B and a selected possible cube to the variable C, we want search for a tuple (A, B, C) satisfying the constraints: A^2 = B, A^3 = C.

To select among the seeds we use the syntax:

(amb 1 3)

to select among the possible squares we use the syntax:

(amb 5 9 11)

to select among the possible cubes we use the syntax:

(amb 13 27 31)

and the constraints can be expressed by the predicates:

(= (square A) B)
(= (cube   A) C)

the resulting program follows:

#!r6rs
(import (vicare)
  (vicare language-extensions amb))

(with-ambiguous-choices
  (let* ((A (amb 1 3))
         (B (amb 5 9 11)))
    (amb-assert (= (square A) B))
    (let ((C (amb 13 27 31)))
      (amb-assert (= (cube A) C))
      (list A B C))))
⇒ (3 9 27)

We can modify the program to show the search path:

#!r6rs
(import (vicare)
  (vicare language-extensions amb))

(define (print . args)
  (apply fprintf (current-error-port) args))

(with-ambiguous-choices
 (let ((A (amb 1 3)))
   (print "A=~a\n" A)
   (let ((B (amb 5 9 11)))
     (print "\tB=~a\n" B)
     (amb-assert (= (square A) B))
     (let ((C (amb 13 27 31)))
       (print "\t\tC=~a\n" C)
       (amb-assert (= (cube A) C))
       (list A B C)))))
⇒ (3 9 27)
-| A=1
-|         B=5
-|         B=9
-|         B=11
-| A=3
-|         B=5
-|         B=9
-|                 C=13
-|                 C=27