On Lisp 22章

まずはschemeでの非決定性計算のコードを解説してから、マクロ使って実装していくという流れで、継続の時と同じ構成。schemeは継続をサポートしているのでコードが分かりやすくていい。

マクロの写経。継続マクロは前書いたヤツを使う。

(defparameter *paths* nil)
(defconstant failsym '@)

(defmacro choose (&rest choices)
  (if choices
      `(progn
     ,@(mapcar #'(lambda (c)
               `(push #'(lambda () ,c) *paths*))
           (reverse (cdr choices)))
     ,(car choices))
      '(fail)))

(defmacro choose-bind (var choices &body body)
  `(cb #'(lambda (,var) ,@body) ,choices ))

(defun cb (fn choices)
  (if choices
      (progn
    (if (cdr choices)
        (push #'(lambda () (cb fn (cdr choices)))
          *paths*))
    (funcall fn (car choices)))
      (fail)))

(defun fail ()
  (if *paths*
      (funcall (pop *paths*))
      failsym))

これを使って二つの数の和が与えられた数になるような組み合わせを見つける

(=defun two-nubers ()
  (choose-bind n1 '(0 1 2 3 4 5 6 7 8 9)
    (choose-bind n2 '(0 1 2 3 4 5 6 7 8 9)
      (=values n1 n2))))

(=defun parlor-trick (sum)
  (=bind (n1 n2) (two-nubers)
    (if (= (+ n1 n2) sum)
    `(the sum of ,n1 ,n2)
    (fail))))

実行

* (parlor-trick 5)

(THE SUM OF 0 5)
* (parlor-trick 15)

(THE SUM OF 6 9)

ちゃんと動いている。

尚、後半にカットの説明があった。要するにやらなくてもよい計算をカットする仕組みってことね。これも継続を使っている。

On Lisp
ポール グレアム,野田 開
オーム社 / ￥ 3,990 ()
通常24時間以内に発送

chooseはどのnならば引き続く計算処理が失敗しないかを、推定できるかのように機能しなければならない