vallog: syntax-rules: amb

2010/05/26

非決定性というやつです。よく分からないので、写経してみました。動き気持ち悪いですね。。どうなってるんですかこれ。。
確か、On Lisp や SICP (計算機プログラムの構造と解釈)にも出てくるらしいですね。

	;; amb
	;; http://people.csail.mit.edu/jhbrown/scheme/continuationslides04.pdf

	(define amb-fail '())

	(define (initialize-amb-fail)
	(set! amb-fail
	(lambda (x)
	(error "amb tree exhusted"))))

	(define (assert pred)
	(if (not pred)
	(amb)))

	(define (fail)
	(amb))

	(define (next)
	(amb))

	(define-syntax amb
	(syntax-rules ()
	((_ argument ...)
	(let ((old-amb-fail amb-fail))
	(call/cc (lambda (return)
	(call/cc (lambda (next)
	(set! amb-fail next)
	(return argument)))
	...
	(set! amb-fail old-amb-fail)
	(amb-fail #f)))))))



	(let ((value (amb 0 1 2 3 4 5 6)))
	(assert (> value 2))
	(assert (even? value))
	value)
	; -> 4

	(define (three-dice sumto)
	(let ((die1 (amb 1 2 3 4 5 6))
	(die2 (amb 1 2 3 4 5 6))
	(die3 (amb 1 2 3 4 5 6)))
	(assert (= sumto (+ die1 die2 die3)))
	(list die1 die2 die3)))

	(initialize-amb-fail)

	(three-dice 4)
	; -> (1 1 2)
	(next)
	; -> (1 2 1)
	(next)
	; -> (2 1 1)
	(next)
	;; *** ERROR: amb tree exhusted
	;; Stack Trace:
	;; _______________________________________
	;; 0 (call/cc (lambda (return) (call/cc (lambda (next) (set! amb-fail n ...
	;; [unknown location]

view raw amb.scm hosted with ❤ by GitHub

わけわかめ。

追記