1 (define (ambeval exp env succeed fail)
2   ((analyze exp) env succeed fail))
3 (define (analyze exp)
4   (cond ((self-evaluating? exp) 
5          (analyze-self-evaluating exp))
6         ((quoted? exp) (analyze-quoted exp))
7         ((variable? exp) (analyze-variable exp))
8         ((assignment? exp) (analyze-assignment exp))
9 	((permanent-assignment? exp) 
10 	 (analyze-permanent-assignment exp))
11         ((definition? exp) (analyze-definition exp))
12         ((if? exp) (analyze-if exp))
13 	((and? exp) (analyze (and->if exp)))
14 	((or? exp) (analyze (or->if exp)))
15 	((not? exp) (analyze (not->if exp)))
16 	((xor? exp) (analyze (xor->or-and-not exp)))
17         ((lambda? exp) (analyze-lambda exp))
18 	((let? exp) (analyze (let->combination exp)))
19 	((let*? exp) (analyze (let*->nested-lets exp)))
20 	((named-let? exp) (analyze (named-let->combination exp)))
21 	((letrec? exp) (analyze (letrec->let exp)))
22 	((do? exp) (analyze (do->combination exp)))
23         ((begin? exp) (analyze-sequence (begin-actions exp)))
24         ((cond? exp) (analyze (cond->if exp)))
25 	((amb? exp) (analyze-amb exp))
26 	((ramb? exp) (analyze (ramb->amb exp)))
27 	((require? exp) (analyze-require exp))
28 	((if-fail? exp) (analyze-if-fail exp))
29 ;;	((if-fail? exp) (analyze (if-fail->amb exp)))
30         ((application? exp) (analyze-application exp))
31         (else
32          (error "Unknown expression type -- ANALYZE" exp))))
33 
34 
35 ;; analyzing procedures
36 (define (analyze-self-evaluating exp)
37   (lambda (env succeed fail)
38     (succeed exp fail)))
39 (define (analyze-quoted exp)
40   (let ((qval (text-of-quotation exp)))
41     (lambda (env succeed fail)
42       (succeed qval fail))))
43 (define (analyze-variable exp)
44   (lambda (env succeed fail)
45     (succeed (lookup-variable-value exp env)
46              fail)))
47 (define (analyze-lambda exp)
48   (let ((vars (lambda-parameters exp))
49         (bproc (analyze-sequence (scan-out-defines (lambda-body exp)))))
50 ;;	(bproc (analyze-sequence (lambda-body exp))))
51     (lambda (env succeed fail)
52       (succeed (make-procedure vars bproc env)
53                fail))))
54 (define (analyze-if exp)
55   (let ((pproc (analyze (if-predicate exp)))
56         (cproc (analyze (if-consequent exp)))
57         (aproc (analyze (if-alternative exp))))
58     (lambda (env succeed fail)
59       (pproc env
60              ;; success continuation for evaluating the predicate
61              ;; to obtain pred-value
62              (lambda (pred-value fail2)
63                (if (true? pred-value)
64                    (cproc env succeed fail2)
65                    (aproc env succeed fail2)))
66              ;; failure continuation for evaluating the predicate
67              fail))))
68 (define (analyze-if-fail exp)
69   (let ((dproc (analyze (if-fail-default exp)))
70 	(aproc (analyze (if-fail-alternative exp))))
71     (lambda (env succeed fail)
72       (dproc env
73 	     succeed
74 	     (lambda ()
75 	       (aproc env succeed fail))))))
76 (define (analyze-sequence exps)
77   (define (sequentially a b)
78     (lambda (env succeed fail)
79       (a env
80          ;; success continuation for calling a
81          (lambda (a-value fail2)
82            (b env succeed fail2))
83          ;; failure continuation for calling a
84          fail)))
85   (define (loop first-proc rest-procs)
86     (if (null? rest-procs)
87         first-proc
88         (loop (sequentially first-proc (car rest-procs))
89               (cdr rest-procs))))
90   (let ((procs (map analyze exps)))
91     (if (null? procs)
92         (error "Empty sequence -- ANALYZE"))
93     (loop (car procs) (cdr procs))))
94 (define (analyze-definition exp)
95   (let ((var (definition-variable exp))
96         (vproc (analyze (definition-value exp))))
97     (lambda (env succeed fail)
98       (vproc env                        
99              (lambda (val fail2)
100                (define-variable! var val env)
101                (succeed 'ok fail2))
102              fail))))
103 (define (analyze-assignment exp)
104   (let ((var (assignment-variable exp))
105         (vproc (analyze (assignment-value exp))))
106     (lambda (env succeed fail)
107       (vproc env
108              (lambda (val fail2)        ; *1*
109                (let ((old-value
110                       (lookup-variable-value var env))) 
111                  (set-variable-value! var val env)
112                  (succeed 'ok
113                           (lambda ()    ; *2*
114                             (set-variable-value! var
115                                                  old-value
116                                                  env)
117                             (fail2)))))
118              fail))))
119 (define (analyze-permanent-assignment exp)
120   (let ((var (permanent-assignment-variable exp))
121 	(vproc (analyze (permanent-assignment-value exp))))
122     (lambda (env succeed fail)
123       (vproc 
124        env
125        (lambda (val val-fail)
126 	   (set-variable-value! var val env)
127 	   (succeed 'ok val-fail))
128        fail))))
129 
130 (define (analyze-application exp)
131   (let ((fproc (analyze (operator exp)))
132         (aprocs (map analyze (operands exp))))
133     (lambda (env succeed fail)
134       (fproc env
135              (lambda (proc fail2)
136                (get-args aprocs
137                          env
138                          (lambda (args fail3)
139                            (execute-application
140                             proc args succeed fail3))
141                          fail2))
142              fail))))
143 (define (get-args aprocs env succeed fail)
144   (if (null? aprocs)
145       (succeed '() fail)
146       ((car aprocs) env
147                     ;; success continuation for this aproc
148                     (lambda (arg fail2)
149                       (get-args (cdr aprocs)
150                                 env
151                                 ;; success continuation for recursive
152                                 ;; call to get-args
153                                 (lambda (args fail3)
154                                   (succeed (cons arg args)
155                                            fail3))
156                                 fail2))
157                     fail)))
158 
159 (define (analyze-amb exp)
160   (let ((cprocs (map analyze (amb-choices exp))))
161     (lambda (env succeed fail)
162       (define (try-next choices)
163         (if (null? choices)
164             (fail)
165             ((car choices) env
166                            succeed
167                            (lambda ()
168                              (try-next (cdr choices))))))
169       (try-next cprocs))))
170 (define (analyze-require exp)
171   (let ((pproc (analyze (require-predicate exp))))
172     (lambda (env succeed fail)
173       (pproc env
174              (lambda (pred-value fail2)
175                (if (false? pred-value)
176                    (fail2)
177                    (succeed 'ok fail2)))
178              fail))))
179 
180 (define (tagged-list? exp tag)
181   (if (pair? exp)
182       (eq? (car exp) tag)
183       false))
184 
185 ;; amb/ramb/require
186 (define (amb? exp) (tagged-list? exp 'amb))
187 (define (amb-choices exp) (cdr exp))
188 (define (make-amb choices)
189   (cons 'amb choices))
190 
191 (define (ramb? exp)
192   (tagged-list? exp 'ramb))
193 (define (ramb->amb exp)
194   (make-amb (shuffle (amb-choices exp))))
195 
196 (define (shuffle items)
197   (if (null? items)
198       '()
199       (let ((first (list-ref items (random (length items)))))
200       (cons first 
201 	    (shuffle (remove (lambda (i) (eq? first i))
202 			     items))))))
203 (define (require? exp) (tagged-list? exp 'require))
204 (define (require-predicate exp) (cadr exp))
205 
206 
207 
208 ;; self-evaluating/variable/quoted
209 (define (self-evaluating? exp)
210   (cond ((number? exp) true)
211         ((string? exp) true)
212         (else false)))
213 (define (variable? exp) (symbol? exp))
214 (define (quoted? exp)
215   (tagged-list? exp 'quote))
216 (define (text-of-quotation exp) (cadr exp))
217 
218 ;; assignment/permanent-assignment/definition
219 (define (assignment? exp)
220   (tagged-list? exp 'set!))
221 (define (assignment-variable exp) (cadr exp))
222 (define (assignment-value exp) (caddr exp))
223 (define (make-assignment var val)
224   (list 'set! var val))
225 (define (permanent-assignment? exp)
226   (tagged-list? exp 'permanent-set!))
227 (define permanent-assignment-variable assignment-variable)
228 (define permanent-assignment-value assignment-value)
229 (define (definition? exp)
230   (tagged-list? exp 'define))
231 (define (definition-variable exp)
232   (if (symbol? (cadr exp))
233       (cadr exp)
234       (caadr exp)))
235 (define (definition-value exp)
236   (if (symbol? (cadr exp))
237       (caddr exp)
238       (make-lambda (cdadr exp)   ; formal parameters
239                    (cddr exp)))) ; body
240 (define (make-definition var val)
241   `(define ,var ,val))
242 
243 ;; if/and/or/not/xor/if-fail
244 (define (if? exp) (tagged-list? exp 'if))
245 (define (if-predicate exp) (cadr exp))
246 (define (if-consequent exp) (caddr exp))
247 (define (if-alternative exp)
248   (if (not (null? (cdddr exp)))
249       (cadddr exp)
250       'false))
251 (define (make-if predicate consequent alternative)
252   (list 'if predicate consequent alternative))
253 
254 (define (and? exp)
255   (tagged-list? exp 'and))
256 (define (and-clauses exp)
257   (cdr exp))
258 (define (or? exp)
259   (tagged-list? exp 'or))
260 (define (or-clauses exp)
261   (cdr exp))
262 (define (and->if exp)
263   (define (expand-clauses clauses)
264     (cond ((null? clauses) 'true)
265 	  ((null? (cdr clauses)) (car clauses))
266 	  (else (make-if (car clauses)
267 			 (expand-clauses (cdr clauses))
268 			 'false))))
269   (expand-clauses (and-clauses exp)))
270 (define (or->if exp)
271   (define (expand-clauses clauses)
272     (if (null? clauses)
273 	'false
274         (make-if (car clauses)
275 		 (car clauses)
276 		 (expand-clauses (cdr clauses)))))
277   (expand-clauses (or-clauses exp)))
278 (define (not? exp)
279   (tagged-list? exp 'not))
280 (define (not->if exp)
281   `(if ,(cadr exp) false true))
282 (define (xor? exp)
283   (tagged-list? exp 'xor))
284 (define (xor->or-and-not exp)
285   (let ((pred-1 (cadr exp))
286 	(pred-2 (caddr exp)))
287     `(or (and ,pred-1 (not ,pred-2))
288 	 (and (not ,pred-1) ,pred-2))))
289 ;; (define (if-fail->amb exp)
290 ;;   (make-amb (list (if-fail-default exp)
291 ;; 		  (if-fail-alternative exp))))
292 (define (if-fail? exp)
293   (tagged-list? exp 'if-fail))
294 (define (if-fail-default exp)
295   (cadr exp))
296 (define (if-fail-alternative exp)
297   (caddr exp))
298 
299 ;; lambda/let/let*/letrec
300 (define (lambda? exp) (tagged-list? exp 'lambda))
301 (define (lambda-parameters exp) (cadr exp))
302 (define (lambda-body exp) (cddr exp))
303 (define (make-lambda parameters body)
304   (cons 'lambda (cons parameters body)))
305 
306 (define (make-let vars vals body)
307   (cons 'let
308 	(cons (map list vars vals)
309 	      body)))
310 (define (let? exp)
311   (and (tagged-list? exp 'let)
312        (not (symbol? (cadr exp)))))
313 (define (let-vars exp)
314   (map car (cadr exp)))
315 (define (let-vals exp)
316   (map cadr (cadr exp)))
317 (define (let-body exp)
318   (cddr exp))
319 (define (let->combination exp)
320   (make-application (make-lambda (let-vars exp) (let-body exp))
321 		    (let-vals exp)))
322 (define (named-let? exp)
323   (and (tagged-list? exp 'let)
324 v       (symbol? (cadr exp))))
325 (define (named-let-name exp)
326   (cadr exp))
327 (define (named-let-vars exp)
328   (map car (caddr exp)))
329 (define (named-let-vals exp)
330   (map cadr (caddr exp)))
331 (define (named-let-body exp)
332   (cdddr exp))
333 (define (named-let->combination exp)
334   (sequence->exp
335    (list (make-definition (named-let-name exp)
336 			  (make-lambda (named-let-vars exp)
337 				       (named-let-body exp)))
338 	 (make-application (named-let-name exp)
339 			   (named-let-vals exp)))))
340 (define (make-named-let name vars vals body)
341   (cons 'let 
342 	(cons name
343 	      (cons (map list vars vals)
344 		    body))))
345 
346 (define (letrec? exp)
347   (tagged-list? exp 'letrec))
348 
349 (define (letrec-vars exp)
350   (map car (cadr exp)))
351 (define (letrec-vals exp)
352   (map cadr (cadr exp)))
353 (define (letrec-body exp)
354   (cddr exp))
355 (define (letrec->let exp)
356   (let* ((vars (letrec-vars exp))
357 	 (unassigneds (map (lambda (var) ''*unassigned*)
358 			   vars))
359 	 (vals (letrec-vals exp))
360 	 (assignments (map (lambda (var val)
361 			     (make-assignment var val))
362 			   vars
363 			   vals))
364 	 (body (letrec-body exp)))
365   (make-let vars 
366 	    unassigneds
367 	    (append assignments body))))
368 
369 (define (make-application op args)
370   (cons op args))
371 
372 (define (let*? exp)
373   (tagged-list? exp 'let*))
374 (define let*-vars let-vars)
375 (define let*-vals let-vals)
376 (define let*-body let-body)
377 (define (let*->nested-lets exp)
378   (define (expand-lets vars vals)
379     (if (null? (cdr vars))
380 	(make-let (list (car vars)) 
381 		  (list (car vals))
382 		  (let*-body exp))
383 	(make-let (list (car vars))
384 		  (list (car vals))
385 		  (list (expand-lets (cdr vars) (cdr vals))))))
386   (let ((vars (let*-vars exp))
387 	(vals (let*-vals exp)))
388     (if (null? vars)
389 	(sequence->exp (let*-body exp))
390 	(expand-lets vars vals))))
391 
392 ;; do loop
393 (define (do? exp)
394   (tagged-list? exp 'do))
395 (define (do-vars exp)
396   (map car (cadr exp)))
397 (define (do-inits exp)
398   (map cadr (cadr exp)))
399 (define (do-steps exp)
400   (map (lambda (var-init-step)
401 	 (if (null? (cddr var-init-step))
402 	     (car var-init-step)
403 	     (caddr var-init-step)))
404        (cadr exp)))
405 (define (do-test exp)
406   (caaddr exp))
407 (define (do-expressions exp)
408   (if (null? (cdaddr exp))
409       (caddr exp)
410       (cdaddr exp)))
411 (define (do-commands exp)
412   (cdddr exp))
413 (define (do->combination exp)
414   (make-named-let
415    'do-iter
416    (do-vars exp)
417    (do-inits exp)
418    (list
419     (make-if
420      (do-test exp)
421      (sequence->exp (do-expressions exp))
422      (sequence->exp
423       (append (do-commands exp)
424 	      (list (make-application
425 		     'do-iter
426 		     (do-steps exp)))))))))
427 
428 
429 ;; begin/sequence
430 (define (begin? exp) (tagged-list? exp 'begin))
431 (define (begin-actions exp) (cdr exp))
432 (define (last-exp? seq) (null? (cdr seq)))
433 (define (first-exp seq) (car seq))
434 (define (rest-exps seq) (cdr seq))
435 (define (sequence->exp seq)
436   (cond ((null? seq) seq)
437         ((last-exp? seq) (first-exp seq))
438         (else (make-begin seq))))
439 (define (make-begin seq) (cons 'begin seq))
440 
441 ;; application
442 (define (application? exp) (pair? exp))
443 (define (operator exp) (car exp))
444 (define (operands exp) (cdr exp))
445 (define (no-operands? ops) (null? ops))
446 (define (first-operand ops) (car ops))
447 (define (rest-operands ops) (cdr ops))
448 
449 ;; cond
450 (define (cond? exp) (tagged-list? exp 'cond))
451 (define (cond-clauses exp) (cdr exp))
452 (define (cond-else-clause? clause)
453   (eq? (cond-predicate clause) 'else))
454 (define (cond-predicate clause) (car clause))
455 (define (cond-actions clause) (cdr clause))
456 (define (cond-extended-clause? clause)
457   (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
458 (define (cond-extended-proc clause)
459   (caddr clause))
460 (define (cond->if exp)
461   (expand-clauses (cond-clauses exp)))
462 (define (expand-clauses clauses)
463   (if (null? clauses)
464       'false                          ; no else clause
465       (let ((first (car clauses))
466             (rest (cdr clauses)))
467         (if (cond-else-clause? first)
468             (if (null? rest)
469                 (sequence->exp (cond-actions first))
470                 (error "ELSE clause isn't last -- COND->IF"
471                        clauses))
472 	    (if (cond-extended-clause? first)
473 		(make-if (cond-predicate first)
474 			 (make-application
475 			  (cond-extended-proc first)
476 			  (list (cond-predicate first)))
477 			 (expand-clauses rest))
478 		(make-if (cond-predicate first)
479 			 (sequence->exp (cond-actions first))
480 			 (expand-clauses rest)))))))
481 (define (true? x)
482   (not (eq? x false)))
483 (define (false? x)
484   (eq? x false))
485 
486 ;; procedure
487 (define (make-procedure parameters body env)
488   (list 'procedure parameters body env))
489 (define (scan-out-defines body)
490   (let* ((definitions (filter definition? body))
491 	 (vars (map definition-variable definitions))
492 	 (unassigneds (map (lambda (var) ''*unassigned*) 
493 			   vars))
494 	 (vals (map definition-value definitions))
495 	 (assignments 
496 	  (map (lambda (var val)
497 		 (make-assignment var val))
498 	       vars vals))
499 	 (exps (remove definition? body)))
500     (if (null? definitions)
501 	body
502 	(list
503 	 (make-let vars
504 		   unassigneds
505 		   (append assignments exps))))))
506 (define (compound-procedure? p)
507   (tagged-list? p 'procedure))
508 (define (procedure-parameters p) (cadr p))
509 (define (procedure-body p) (caddr p))
510 (define (procedure-environment p) (cadddr p))
511 
512 ;; environment
513 (define (enclosing-environment env) (cdr env))
514 (define (first-frame env) (car env))
515 (define the-empty-environment '())
516 (define (make-frame variables values)
517   (cons variables values))
518 (define (frame-variables frame) (car frame))
519 (define (frame-values frame) (cdr frame))
520 (define (add-binding-to-frame! var val frame)
521   (set-car! frame (cons var (car frame)))
522   (set-cdr! frame (cons val (cdr frame))))
523 (define (extend-environment vars vals base-env)
524   (if (= (length vars) (length vals))
525       (cons (make-frame vars vals) base-env)
526       (if (< (length vars) (length vals))
527           (error "Too many arguments supplied" vars vals)
528           (error "Too few arguments supplied" vars vals))))
529 (define (lookup-variable-value var env)
530   (define (env-loop env)
531     (define (scan vars vals)
532       (cond ((null? vars)
533              (env-loop (enclosing-environment env)))
534             ((eq? var (car vars))
535 ;;	     (let ((val (car vals)))
536 ;;	       (if (eq? val '*unassigned*)
537 ;;		   (error "Var not yet defined -- LOOKUP-VARIABLE-VALUE" var)
538 ;;		   val)))
539 	     (car vals))
540             (else (scan (cdr vars) (cdr vals)))))
541     (if (eq? env the-empty-environment)
542         (error "Unbound variable" var)
543         (let ((frame (first-frame env)))
544           (scan (frame-variables frame)
545                 (frame-values frame)))))
546   (env-loop env))
547 (define (set-variable-value! var val env)
548   (define (env-loop env)
549     (define (scan vars vals)
550       (cond ((null? vars)
551              (env-loop (enclosing-environment env)))
552             ((eq? var (car vars))
553              (set-car! vals val))
554             (else (scan (cdr vars) (cdr vals)))))
555     (if (eq? env the-empty-environment)
556         (error "Unbound variable -- SET!" var)
557         (let ((frame (first-frame env)))
558           (scan (frame-variables frame)
559                 (frame-values frame)))))
560   (env-loop env))
561 (define (define-variable! var val env)
562   (let ((frame (first-frame env)))
563     (define (scan vars vals)
564       (cond ((null? vars)
565              (add-binding-to-frame! var val frame))
566             ((eq? var (car vars))
567              (set-car! vals val))
568             (else (scan (cdr vars) (cdr vals)))))
569     (scan (frame-variables frame)
570           (frame-values frame))))
571 
572 ;; (define (remove-binding-from-frame! var frame)
573 ;;   (define (scan vars vals)
574 ;;     (cond ((null? (cdr vars))
575 ;; 	   (error "Binding not found -- REMOVE-BINDING-FROM-FRAME!" var))
576 ;; 	  ((eq? var (cadr vars))
577 ;; 	   (set-cdr! vars (cddr vars))
578 ;; 	   (set-cdr! vals (cddr vals)))
579 ;; 	  (else (scan (cdr vars) (cdr vals)))))
580 ;;   (let ((vars (frame-variables frame))
581 ;; 	(vals (frame-values frame)))
582 ;;     (if (eq? var (car vars))
583 ;; 	(begin (set-car! frame (cdr vars))
584 ;; 	       (set-cdr! frame (cdr vals)))
585 ;; 	(scan vars vals))))
586 
587 ;; primitives
588 (define (primitive-procedure? proc)
589   (tagged-list? proc 'primitive))
590 (define (primitive-implementation proc) (cadr proc))
591 (define primitive-procedures
592   (list (list 'car car)
593         (list 'cdr cdr)
594 	(list 'caar caar)
595 	(list 'cadr cadr)
596 	(list 'cddr cddr)
597 	(list 'caddr caddr)
598 	(list 'cdddr cdddr)
599         (list 'cons cons)
600 	(list 'list list)
601         (list 'null? null?)
602 	(list 'pair? pair?)
603 	(list '* *)
604 	(list '/ /)
605 	(list '+ +)
606 	(list '- -)
607 	(list '= =)
608 	(list '< <)
609 	(list '> >)
610 	(list '<= <=)
611 	(list '>= >=)
612 	(list 'abs abs)
613 	(list 'remainder remainder)
614 	(list 'even? even?)
615 	(list 'eq? eq?)
616 	(list 'equal? equal?)
617 	(list 'member member)
618 	(list 'memq memq)
619 	(list 'display display)
620 	(list 'error error)))
621 (define (primitive-procedure-names)
622   (map car
623        primitive-procedures))
624 (define (primitive-procedure-objects)
625   (map (lambda (proc) (list 'primitive (cadr proc)))
626        primitive-procedures))
627 (define (apply-primitive-procedure proc args)
628   (apply
629    (primitive-implementation proc) args))
630 
631 ;; execute application
632 
633 (define (execute-application proc args succeed fail)
634   (cond ((primitive-procedure? proc)
635          (succeed (apply-primitive-procedure proc args)
636                   fail))
637         ((compound-procedure? proc)
638          ((procedure-body proc)
639           (extend-environment (procedure-parameters proc)
640                               args
641                               (procedure-environment proc))
642           succeed
643           fail))
644         (else
645          (error
646           "Unknown procedure type -- EXECUTE-APPLICATION"
647           proc))))
648 
649 
650 ;; driver-loop
651 (define (prompt-for-input string)
652   (newline) (newline) (display string) (newline))
653 (define (announce-output string)
654   (newline) (display string) (newline))
655 (define (user-print object)
656   (if (compound-procedure? object)
657       (display (list 'compound-procedure
658                      (procedure-parameters object)
659                      (procedure-body object)
660                      '<procedure-env>))
661       (display object)))
662 (define (setup-environment)
663   (let ((initial-env
664          (extend-environment (primitive-procedure-names)
665                              (primitive-procedure-objects)
666                              the-empty-environment)))
667     (define-variable! 'true true initial-env)
668     (define-variable! 'false false initial-env)
669     initial-env))
670 (define the-global-environment (setup-environment))
671 
672 (define input-prompt ";;; Amb-Eval input:")
673 (define output-prompt ";;; Amb-Eval value:")
674 (define (driver-loop)
675   (define (internal-loop try-again)
676     (prompt-for-input input-prompt)
677     (let ((input (read)))
678       (if (eq? input 'try-again)
679           (try-again)
680           (begin
681             (newline)
682             (display ";;; Starting a new problem ")
683             (ambeval input
684                      the-global-environment
685                      ;; ambeval success
686                      (lambda (val next-alternative)
687                        (announce-output output-prompt)
688                        (user-print val)
689                        (internal-loop next-alternative))
690                      ;; ambeval failure
691                      (lambda ()
692                        (announce-output
693                         ";;; There are no more values of")
694                        (user-print input)
695                        (driver-loop)))))))
696   (internal-loop
697    (lambda ()
698      (newline)
699      (display ";;; There is no current problem")
700      (driver-loop))))
701 
702 
703 ;; auxiliary
704 (define (test-case actual expected)
705   (newline)
706   (display "Actual:   ")
707   (display actual)
708   (newline)
709   (display "Expected: ")
710   (display expected)
711   (newline))
712 (define try-again
713   (lambda ()
714     "No current problem"))
715 (define (geval exp) ;; eval globally
716   (if (eq? exp 'try-again)
717       (try-again)
718       (ambeval exp 
719 	       the-global-environment
720 	       (lambda (val next-alternative)
721 		 (set! try-again next-alternative)
722 		 val)
723 	       (lambda ()
724 		 (set! try-again
725 		       (lambda ()
726 			 "No current problem"))
727 		 "No alternatives"))))
728 (define (test-eval exp expected)
729   (test-case (geval exp) expected))
730 (define (print-eval exp)
731   (user-print (geval exp)))
732 
733 ;; test-suite
734 
735 ;; procedure definitions
736 
737 (geval
738  '(define (append x y)
739     (if (null? x)
740 	y
741 	(cons (car x) (append (cdr x) y)))))
742 (geval
743  '(define (list-ref items n)
744     (if (= n 0)
745 	(car items)
746 	(list-ref (cdr items) (- n 1)))))
747 (geval
748  '(define (fold-left f init seq) 
749     (if (null? seq) 
750 	init 
751 	(fold-left f 
752 		   (f init (car seq)) 
753 		   (cdr seq)))))
754 (geval
755  '(define (enumerate-interval low high)
756     (if (> low high)
757 	'()
758 	(cons low (enumerate-interval (+ low 1) high)))))
759 (geval 
760  '(define (assoc key records)
761     (cond ((null? records) false)
762 	  ((equal? key (caar records)) (car records))
763 	  (else (assoc key (cdr records))))))
764 
765 (geval
766  '(define (map proc list)
767     (if (null? list)
768 	'()
769 	(cons (proc (car list))
770 	      (map proc (cdr list))))))
771 (geval
772  '(define (map-2 proc l1 l2)
773     (if (null? l1)
774 	'()
775 	(cons (proc (car l1) (car l2))
776 	      (map-2 proc (cdr l1) (cdr l2))))))
777 
778 (geval 
779  '(define (accumulate op initial sequence)
780     (if (null? sequence)
781 	initial
782 	(op (car sequence)
783 	    (accumulate op initial (cdr sequence))))))
784 
785 ;; ;; ;; all special forms
786 ;; (test-eval '(begin 5 6) 6)
787 ;; (test-eval '10 10)
788 ;; (geval '(define x 3))
789 ;; (test-eval 'x 3)
790 ;; (test-eval '(set! x -25) 'ok)
791 ;; (test-eval 'x -25)
792 ;; (geval '(define z (lambda (x y) (+ x (* x y)))))
793 ;; (test-eval '(z 3 4) 15)
794 ;; (test-eval '(cond ((= x -2) 'x=-2)
795 ;; 		  ((= x -25) 'x=-25)
796 ;; 		  (else 'failed))
797 ;; 	   'x=-25)
798 ;; (test-eval '(if true false true) false)
799 
800 ;; (test-eval 
801 ;;  '(let ((x 4) (y 7))
802 ;;     (+ x y (* x y)))
803 ;;  (+ 4 7 (* 4 7)))
804 
805 
806 ;; ;; and/or
807 ;; (geval '(define x (+ 3 8)))
808 ;; (test-eval '(and 0 true x) 11)
809 ;; (test-eval '(and 0 true x false) false)
810 ;; (test-eval '(and 0 true x (set! x -2) false) false)
811 ;; (test-eval 'x -2)
812 ;; (test-eval '(and 0 true x false (set! x -5)) false)
813 ;; (test-eval 'x -2)
814 ;; (test-eval '(or false (set! x 25)) 'ok)
815 ;; (test-eval 'x 25)
816 ;; (test-eval '(or (set! x 2) (set! x 4)) 'ok)
817 ;; (test-eval 'x 2)
818 ;; (test-eval '(or false (set! x 25) true false) 'ok)
819 ;; (test-eval 'x 25)
820 ;; (test-eval '(or ((lambda (x) x) 5)) 5)
821 ;; (test-eval '(or (begin (set! x (+ x 1)) x)) 26) ;; this fails because or->if repeats the same clause twice
822 ;; (newline)
823 ;; (display "Failure expected")
824 ;; (newline)
825 
826 ;; ;; cond
827 
828 ;; (test-eval 
829 ;;  '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
830 ;; 	(else false))
831 ;;  2)
832 
833 ;; (test-eval
834 ;;  '(cond ((= 3 4) 'not-true)
835 ;; 	((= (* 2 4) 3) 'also-false)
836 ;; 	((map (lambda (x)
837 ;; 		(* x (+ x 1)))
838 ;; 	      '(2 4 1 9))
839 ;; 	 =>
840 ;; 	 (lambda (x)
841 ;; 	   (accumulate + 0 x)))
842 ;; 	(else 'never-reach))
843 ;;  118)
844 ;; ;; '(6 20 2 90)
845 
846 
847 ;; ;; procedure definition and application
848 ;; (geval
849 ;;  '(define (factorial n)
850 ;;     (if (= n 0)
851 ;; 	1
852 ;; 	(* n (factorial (- n 1))))))
853 ;; (test-eval '(factorial 5) 120)
854 
855 ;; ;; map
856 
857 ;; (test-eval
858 ;;  '(map (lambda (x)
859 ;; 	 (* x (+ x 1)))
860 ;;        '(2 1 4 2 8 3))
861 ;;  '(6 2 20 6 72 12))
862 ;; ;; accumulate
863 
864 ;; (test-eval
865 ;;  '(accumulate + 0 '(1 2 3 4 5))
866 ;;  15)
867 
868 ;; ;; make-let
869 ;; (test-eval 
870 ;;  (make-let '(x y) '(3 5) '((+ x y)))
871 ;;  8)
872 ;; (test-eval 
873 ;;  '(let ()
874 ;;     5)
875 ;;  5)
876 ;; (test-eval
877 ;;  '(let ((x 3))
878 ;;     x)
879 ;;  3)
880 ;; (test-eval
881 ;;  '(let ((x 3)
882 ;; 	(y 5))
883 ;;     (+ x y))
884 ;;  8)
885 ;; (test-eval 
886 ;;  '(let ((x 3)
887 ;; 	(y 2))
888 ;;     (+ (let ((x (+ y 2))
889 ;; 	     (y x))
890 ;; 	 (* x y))
891 ;;        x y))
892 ;;  (+ (* 4 3) 3 2))
893 ;; (test-eval
894 ;;  '(let ((x 6)
895 ;; 	(y (let ((x 2))
896 ;; 	     (+ x 3)))
897 ;; 	(z (let ((a (* 3 2)))
898 ;; 	     (+ a 3))))
899 ;;     (+ x y z))
900 ;;  (+ 6 5 9))
901     
902 
903 ;; ;; let*
904 
905 ;; (test-eval
906 ;;  '(let* ((x 3)
907 ;; 	 (y (+ x 2))
908 ;; 	 (z (+ x y 5)))
909 ;;     (* x z))
910 ;;  39)
911 
912 ;; (test-eval
913 ;;  '(let* ()
914 ;;     5)
915 ;;  5)
916 ;; (test-eval
917 ;;  '(let* ((x 3))
918 ;;     (let* ((y 5))
919 ;;       (+ x y)))
920 ;;  8)
921 
922 ;; (test-eval 
923 ;;  '(let* ((x 3)
924 ;; 	 (y (+ x 1)))
925 ;;     (+ (let* ((x (+ y 2))
926 ;; 	      (y x))
927 ;; 	 (* x y))
928 ;;        x y))
929 ;;  (+ (* 6 6) 3 4))
930 ;; (test-eval
931 ;;  '(let* ((x 6)
932 ;; 	 (y (let* ((x 2)
933 ;; 		   (a (let* ((x (* 3 x)))
934 ;; 			(+ x 2))))       
935 ;; 	      (+ x a)))                  
936 ;; 	 (z (+ x y)))                    
937 ;;     (+ x y z))
938 ;;  32)
939 
940 ;; ;; named-let
941 
942 ;; (test-eval
943 ;;  '(let eight ()
944 ;;     5
945 ;;     7
946 ;;     8)
947 ;;  8)
948 ;; (test-eval
949 ;;  '(let loop ((count 0))
950 ;;     (if (= 100 count)
951 ;; 	count
952 ;; 	(loop (+ count 1))))
953 ;;  100)
954 ;; (geval
955 ;;  '(define (prime? x)
956 ;;     (let prime-iter ((i 2))
957 ;;       (cond ((> (* i i) x) true)
958 ;; 	    ((= (remainder x i) 0) false)
959 ;; 	    (else (prime-iter (+ i 1)))))))
960 ;; (test-eval
961 ;;  '(let primes ((x 2)
962 ;; 	       (n 20))
963 ;;     (cond ((= n 0) '())
964 ;; 	  ((prime? x) 
965 ;; 	   (cons x
966 ;; 		 (primes (+ x 1) (- n 1))))
967 ;; 	  (else (primes (+ x 1) n))))
968 ;;  '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
969 
970 ;; (geval
971 ;;  '(define (fib n)
972 ;;     (let fib-iter ((a 1)
973 ;; 		   (b 0)
974 ;; 		   (count n))
975 ;;       (if (= count 0)
976 ;; 	  b
977 ;; 	  (fib-iter (+ a b) a (- count 1))))))
978 ;; (test-eval '(fib 19) 4181)
979 
980 ;; ;; do-loop	  
981 ;; (test-eval
982 ;;  '(let ((y 0))
983 ;;     (do ((x 0 (+ x 1)))
984 ;; 	((= x 5) y)
985 ;;       (set! y (+ y 1))))
986 ;;  5)
987 ;; (test-eval
988 ;;  '(do ()
989 ;;       (true))
990 ;;  true)
991 ;; (test-eval
992 ;;  '(do ()
993 ;;       (true 5))
994 ;;  5)
995 ;; (test-eval
996 ;;  '(let ((y 0))
997 ;;     (do ()
998 ;; 	((= y 5) y)
999 ;;       (set! y (+ y 1))))
1000 ;;  5)
1001 
1002 ;; (test-eval
1003 ;;  '(do ((y '(1 2 3 4)))
1004 ;;       ((null? y))
1005 ;;     (set! y (cdr y)))
1006 ;;  true)
1007 ;; (test-eval
1008 ;;  '(let ((y 0))
1009 ;;     (do ((x 0 (+ x 1)))
1010 ;; 	((= x 5) y)
1011 ;;       (set! y (+ y 1))))
1012 ;;  5)
1013 ;; (test-eval
1014 ;;  '(let ((x '(1 3 5 7 9)))
1015 ;;     (do ((x x (cdr x))
1016 ;; 	 (sum 0 (+ sum (car x))))
1017 ;; 	((null? x) sum)))
1018 ;;  25)
1019 ;; (test-eval 
1020 ;;  '(let ((z '()))
1021 ;;     (do ((x '(1 2 3 4) (cdr x))
1022 ;; 	 (y '(1 2 3 4 5 6 7 8) (cddr y)))
1023 ;; 	((null? x) y x z)
1024 ;;       (set! z (cons (car x) z))))
1025 ;;  '(4 3 2 1))
1026 
1027 
1028 
1029 ;; ;; make-unbound!
1030 ;; ;; broken now due to scan-out-defines
1031 
1032 ;; ;; (test-eval
1033 ;; ;;  '(let ((x 3))
1034 ;; ;;     (let ((x 5))
1035 ;; ;;       (make-unbound! x)
1036 ;; ;;       (* x x)))
1037 ;; ;;  9)
1038 
1039 ;; ;; (test-eval
1040 ;; ;;  '(let ((x 3))
1041 ;; ;;     (let ((x 5))
1042 ;; ;;       (define y x)
1043 ;; ;;       (make-unbound! x)
1044 ;; ;;       (* y x)))
1045 ;; ;;  15)
1046 
1047 ;; ;; (test-eval
1048 ;; ;;  '(let ((y -1) (x 3))
1049 ;; ;;     (let ((y 0.5) (x 5))
1050 ;; ;;       (define a x)
1051 ;; ;;       (define b y)
1052 ;; ;;       (make-unbound! x)
1053 ;; ;;       (make-unbound! y)
1054 ;; ;;       (* a b x y)))
1055 ;; ;;  (* 5 3 -1 0.5))
1056 
1057 ;; ;; (test-eval
1058 ;; ;;  '(let ((x 3) (y 4))
1059 ;; ;;     (let ((x 5))
1060 ;; ;;       (make-unbound! x)
1061 ;; ;;       (+ x 4)))
1062 ;; ;;  7)
1063 
1064 ;; ;; (test-eval 
1065 ;; ;;  '(let ((a 1) (b 2) (c 3) (d 4))
1066 ;; ;;     (make-unbound! b)
1067 ;; ;;     (+ a c d))
1068 ;; ;;  (+ 1 3 4))
1069 
1070 ;; ;; (test-eval
1071 ;; ;;  '(let ((x 4) (y 5))
1072 ;; ;;     (let ((a 1) (b 2) (c 3))
1073 ;; ;;       (let ((x (+ a b)) (y (+ c a)))
1074 ;; ;; 	(make-unbound! x)
1075 ;; ;; 	(let ((a x) (b (+ x y)))
1076 ;; ;; 	  (define z b)
1077 ;; ;; 	  (make-unbound! b)
1078 ;; ;; 	  (* (+ a z)
1079 ;; ;; 	     (+ a b y))))))
1080 ;; ;;  (* (+ 4 8)
1081 ;; ;;     (+ 4 2 4)))
1082  
1083 ;; ;; x 3 -- y 4
1084 ;; ;; x 4 -- y 4
1085 ;; ;; a 4 -- b 4
1086 ;; ;; a 4 -- b 2
1087 
1088 ;; ;; scan-out-defines
1089 
1090 ;; (geval
1091 ;;  '(define (f x)
1092 ;;     (define (even? n)
1093 ;;       (if (= n 0)
1094 ;; 	  true
1095 ;; 	  (odd? (- n 1))))
1096 ;;     (define (odd? n)
1097 ;;       (if (= n 0)
1098 ;; 	  false
1099 ;; 	  (even? (- n 1))))
1100 ;;     (even? x)))
1101 ;; (test-eval '(f 5) false)
1102 ;; (test-eval '(f 10) true)
1103 
1104 ;; ;; (geval
1105 ;; ;;  '(let ((x 5))
1106 ;; ;;     (define y x)
1107 ;; ;;     (define x 3)
1108 ;; ;;     (+ x y)))
1109 ;; ;; signal an error because x is undefined if variables are scanned out
1110 
1111 ;; ;; letrec
1112 
1113 ;; (geval
1114 ;;  '(define (f x)
1115 ;;     (letrec ((even?
1116 ;; 	      (lambda (n)
1117 ;; 		(if (= n 0)
1118 ;; 		    true
1119 ;; 		    (odd? (- n 1)))))
1120 ;; 	     (odd?
1121 ;; 	      (lambda (n)
1122 ;; 		(if (= n 0)
1123 ;; 		    false
1124 ;; 		    (even? (- n 1))))))
1125 ;;       (even? x))))
1126 ;; (test-eval '(f 11) false)
1127 ;; (test-eval '(f 16) true)
1128 
1129 ;; (test-eval 
1130 ;;  '(letrec ((fact
1131 ;; 	    (lambda (n)
1132 ;; 	      (if (= n 1)
1133 ;; 		  1
1134 ;; 		  (* n (fact (- n 1)))))))
1135 ;;     (fact 10))
1136 ;;  3628800)
1137 
1138 ;; amb
1139 ;; (geval '(define (require p) (if (not p) (amb))))
1140 
1141 ;; (test-eval '(amb 1 2 3) 1)
1142 ;; (test-eval 'try-again 2)
1143 ;; (test-eval 'try-again 3)
1144 ;; (test-eval 'try-again "No alternatives")
1145 ;; (test-eval 'try-again "No current problem")
1146 ;; (test-eval 'try-again "No current problem")
1147 ;; (test-eval '(amb (amb 1 2) (amb 'a 'b))
1148 ;; 	   1)
1149 ;; (test-eval 'try-again 2)
1150 ;; (test-eval 'try-again 'a)
1151 ;; (test-eval 'try-again 'b)
1152 ;; (test-eval 'try-again "No alternatives")
1153 ;; (test-eval '(require false) "No alternatives")
1154 ;; (test-eval '(require true) false)
1155 
1156 	   
1157 (geval
1158  '(define (an-integer-between low high)
1159     (require (<= low high))
1160     (amb low (an-integer-between (+ low 1) high))))
1161 
1162 (geval 
1163  '(define (a-pythagorean-triple-between low high)
1164     (let ((i (an-integer-between low high)))
1165       (let ((j (an-integer-between i high)))
1166 	(let ((k (an-integer-between j high)))
1167 	  (require (= (+ (* i i) (* j j)) (* k k)))
1168 	  (list i j k))))))
1169 
1170 ;; (test-eval
1171 ;;  '(a-pythagorean-triple-between 1 20)
1172 ;;  '(3 4 5))
1173 ;; (test-eval 'try-again '(5 12 13))
1174 ;; (test-eval 'try-again '(6 8 10))
1175 ;; (test-eval 'try-again '(8 15 17))
1176 ;; (test-eval 'try-again '(9 12 15))
1177 
1178 (geval
1179  '(define (an-integer-starting-from low)
1180     (amb low (an-integer-starting-from (+ low 1)))))
1181 
1182 (geval
1183  '(define (pythagorean-triples-starting-from low)
1184     (let* ((k (an-integer-starting-from low))
1185 	   (i (an-integer-between low k))
1186 	   (j (an-integer-between i k)))
1187       (require (= (+ (* i i) (* j j)) (* k k)))
1188       (list i j k))))
1189 
1190 ;; (test-eval '(pythagorean-triples-starting-from 1)
1191 ;; 	   '(3 4 5))
1192 ;; (test-eval 'try-again '(6 8 10))
1193 ;; (test-eval 'try-again '(5 12 13))
1194 ;; (test-eval 'try-again '(9 12 15))
1195 ;; (test-eval 'try-again '(8 15 17))
1196 
1197 (geval
1198  '(define (next-triplet trp)
1199     (let ((i (car trp))
1200 	  (j (cadr trp))
1201 	  (k (caddr trp)))
1202       (cond ((= i j k) (list 1 1 (+ k 1)))
1203 	    ((= j k) (list (+ i 1) (+ i 1) k))
1204 	    (else (list i (+ j 1) k))))))
1205 (geval
1206  '(define (triplet-starting-from trp)
1207     (amb trp (triplet-starting-from (next-triplet trp)))))
1208 (geval
1209  '(define (pythagorean-triples-starting-from low)
1210     (let* ((triplet (triplet-starting-from (list low low low)))
1211 	   (i (car triplet))
1212 	   (j (cadr triplet))
1213 	   (k (caddr triplet)))
1214       (require (= (+ (* i i) (* j j)) (* k k)))
1215       (list i j k))))
1216 (geval
1217  '(define (distinct? items)
1218     (cond ((null? items) true)
1219 	  ((null? (cdr items)) true)
1220 	  ((member (car items) (cdr items)) false)
1221 	  (else (distinct? (cdr items))))))
1222 
1223 (geval
1224  '(define (an-element-of items)
1225     (require (not (null? items)))
1226     (amb (car items) (an-element-of (cdr items)))))
1227 
1228 (geval 
1229  '(define count 0))
1230 (test-eval
1231  '(let ((x (an-element-of '(a b c)))
1232 	(y (an-element-of '(a b c))))
1233     (permanent-set! count (+ count 1))
1234     (require (not (eq? x y)))
1235     (list x y count))
1236  '(a b 2))
1237 (test-eval 'try-again '(a c 3))
1238 
1239 (test-eval
1240  '(if-fail (let ((x (an-element-of '(1 3 5))))
1241 	     (require (even? x))
1242 	     x)
1243 	   'all-odd)
1244  'all-odd)
1245 (test-eval 'try-again "No alternatives")
1246 
1247 (test-eval
1248  '(if-fail (let ((x (an-element-of '(1 3 5 8))))
1249 	     (require (even? x))
1250 	     x)
1251 	   'all-odd)
1252  8)
1253 (test-eval 'try-again "all-odd")
1254 (test-eval 'try-again "No alternatives")
1255 
1256 ;; Exercise 4.53.  With permanent-set! as described in exercise 4.51 and if-fail as in exercise 4.52, what will be the result of evaluating
1257 
1258 (geval
1259  '(define (prime? n)
1260     (= n (smallest-divisor n))))
1261 (geval
1262  '(define (smallest-divisor n)
1263     (find-divisor n 2)))
1264 (geval
1265  '(define (square x) (* x x)))
1266 (geval 
1267  '(define (find-divisor n test-divisor)
1268     (cond ((> (square test-divisor) n) n)
1269 	  ((divides? test-divisor n) test-divisor)
1270 	  (else (find-divisor n (+ test-divisor 1))))))
1271 (geval
1272  '(define (divides? a b)
1273     (= (remainder b a) 0)))
1274 
1275 
1276 (geval
1277  '(define (prime-sum-pair list1 list2)
1278     (let ((a (an-element-of list1))
1279 	  (b (an-element-of list2)))
1280       (require (prime? (+ a b)))
1281       (list a b))))
1282 
1283 (test-eval
1284  '(let ((pairs '()))
1285     (if-fail 
1286      (let ((p (prime-sum-pair '(1 3 5 8)
1287 			      '(20 35 110))))
1288        (permanent-set! pairs (cons p pairs))
1289        (amb))
1290      pairs))
1291  '((8 35) (3 110) (3 20)))
1292  
1293 ;;  Exercise 4.54.  If we had not realized that require could be implemented as an ordinary procedure that uses amb, to be defined by the user as part of a nondeterministic program, we would have had to implement it as a special form. This would require syntax procedures
1294 
1295 ;; (define (require? exp) (tagged-list? exp 'require))
1296 ;; (define (require-predicate exp) (cadr exp))
1297 
1298 ;; and a new clause in the dispatch in analyze
1299 
1300 ;; ((require? exp) (analyze-require exp))
1301 
1302 ;; as well the procedure analyze-require that handles require expressions. Complete the following definition of analyze-require.
1303 
1304 ;; (define (analyze-require exp)
1305 ;;   (let ((pproc (analyze (require-predicate exp))))
1306 ;;     (lambda (env succeed fail)
1307 ;;       (pproc env
1308 ;;              (lambda (pred-value fail2)
1309 ;;                (if <??>
1310 ;;                    <??>
1311 ;;                    (succeed 'ok fail2)))
1312 ;;              fail))))
1313