Programming with AMB

In this problem set we will be using a search evaluator written in Scheme. The file ambeval.scm contains an interpreter for AMBScheme--Scheme augmented with amb. The interpreter is a procedure-tree interpreter, that separates analysis from execution. It has the same basic structure as the one in SICP section 4.1.7, but there are major differences. The AMBScheme evaluator is explained in section 4.3.

The user interface (ha!) to the AMBScheme system is pretty crude. To initialize the evaluator use the incantation (define the-global-environment (setup-environment)). If you then type (driver-loop), you will find yourself typing at the driver loop. Please note that AMBScheme running in Scheme has no error system of its own. If you hit an error or if you interrupt your program, you will bounce back into Scheme.

The driver loop uses the prompt ;;; Amb-Eval input: instead of the ordinary Scheme prompt.

Start up the interpreter and try a few simple expressions. If you bounce out into Scheme, you should quit out of the error and re-enter the interpreter by typing (driver-loop). If you get hopelessly fouled up, you can reinitialize your global environment, but you will lose any definitions you have made.

Loading problem set 11 will get a working evaluator loaded. If you start the AMBScheme evaluator and then load up the example program, puzz.scm, using ambload, you should obtain the following behavior:

(ambload "puzz.scm")
;Value: done

(driver-loop)

;;; Amb-Eval input:
(multiple-dwelling)
;;; Starting a new problem 
;;; Amb-Eval value:
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))

;;; Amb-Eval input:
try-again
;;; There are no more values of
(multiple-dwelling)

;;; Amb-Eval input:

When doing the programming problems for code to be executed by the AMB evaluator, a good strategy is to edit the file puzz.scm, adding your new code. You can then reload the file and restart the evaluator to do your tests.

Warning: Searching can take a long time. We could have made things much faster by compiling the AMB evaluator, but we left it uncompiled to faciliate error checking. Depending on the speed of your computer, the multiple-dwelling example above could take a miniute or two to produce an answer.

Computer Exercise 1.

(Exercise 4.38 on p.419) Run the program to get the result shown above. Then, prepare a modified version that relaxes the requirement that Smith does not live on a floor adjacent to Fletcher's. Run your modified program. Is the solution still unique? If not, how many solutions are now possible?

Check the 6.001 discussion forum for computer-ex-01

Look here for information about the forum.

Computer Exercise 2a.

(Exercise 4.39 on p.419) Does the order of the restrictions affect the answer? the time to find an answer? If you think it matters, demonstrate a faster program obtained from the given one by reordering the restrictions. If you think it does not matter, argue your case.

Computer Exercise 2b.

(Exercise 4.40 on p.419) Write and demonstrate a very efficient search procedure for this problem based upon only generating those possibilities that are not already ruled out by previous filtrations. Hint: This will require a nest of let expressions.

Check the 6.001 discussion forum for computer-ex-02

Look here for information about the forum.

Computer Exercise 3.

Do Exercise 4.43 (p.420)

Check the 6.001 discussion forum for computer-ex-03

Look here for information about the forum.