Section4-3 > R5RS
To get the most out of Section4-3, you would need a working non-deterministic Scheme. One way to get it is pursued in the section 4.3.3 of SICP - the authors extend the meta-circular evaluator to support backtracking. Another solution, which uses macros and call/cc, Gerald Jay Sussman's favorite (1975, p. 3) 1], is presented here. Besides being useful to check the exercises, it is a simple use example of these features. |
RU |
amb is implemented as a simple macro, and not a procedure, as it needs to be lazy in its arguments. The magic happens thanks to a stack of continuations amb-stack. try-again simply pops a continuation off the stack and yields control to it. The core procedure, amb+ accepts two computation branches, a and b, pushes a continuation with b onto the stack, and does a. Therefore, when a fails with try-again, control is yielded to b. |
RU |
The solution seeks to be R5RS compatible. It has been tested on PLT Scheme and GUILE. |
RU |
For GUILE, use (use-syntax (ice-9 syncase)) at the top of the file (turns on macro support). |
Для GUILE, добавьте (use-syntax (ice-9 syncase)) в начало файла: |
(define-syntax amb
(syntax-rules ()
((amb) (try-again))
((amb x) x)
((amb x . xs)
(amb+ (lambda () x)
(lambda () (amb . xs))))))
(define (require p)
(if (not p) (amb)))
(define (try-again)
(if (null? amb-stack)
(error "amb search tree exhausted")
(let ((r (car amb-stack)))
(set! amb-stack (cdr amb-stack))
(r))))
(define (amb-reset)
(set! amb-stack '()))
(define amb-stack '())
(define (amb+ a b)
(define s '())
(set! s amb-stack)
(call/cc
(lambda (r)
(call/cc
(lambda (c)
(set! amb-stack
(cons c amb-stack))
(r (a))))
(set! amb-stack s)
(b))))
(define call/cc call-with-current-continuation)
Examples of use from the book: |
RU |
(define (py-triples low high)
(let ((i (int low high)))
(let ((j (int i high)))
(let ((k (int j high)))
(require (= (+ (* i i) (* j j)) (* k k)))
(list i j k)))))
(define (int low high)
(require (>= high low))
(amb low (int (+ 1 low) high)))
Testing: |
RU |
> (py-triples 1 10) (3 4 5) > (try-again) (6 8 10) > (try-again) ERROR: amb search tree exhausted