マクロで手軽に遅延評価 -- どうあがいても必要だったんだ!

今書いているコード、プランニング問題の探索関連なんですが、
気を付けないとすぐに爆発するので困りものです。
今日実装していて引っかかったのは次のような問題。

全体の深さNで、深さ n から一つ下るごとに枝の数がO(n)倍になる木。
つまりノードの数は O(N!) 。

昨日までのコードは小さいNで動作確認をしていたため、特に問題はなかったのですが、
いざ論文用の本番問題に手を出してみると爆発しました。

今まで使っていた手法は

• 全可能性を列挙する (関数1)
• 枝刈りする (関数2)

という流れ(どう見てもダメだろ・・・)で、しかもコード全体が結構完成していたので困りました。
明らかな問題点としてまず第一に、可能性を列挙する所でメモリがパンクします。
そのうえ、列挙するまでの時間もむちゃくちゃかかります。

普通の探索の場合、本来枝刈りはノードを展開するたびに行うものですが、
自分のコードはどちらかというと本番プランニングの前処理段階だったので、
それぐらいで爆発しないだろうとたかをくくってたわけです。
しかも、A*に代表される「ノードを展開するたびに・・・」という探索プログラムはステートフルで、関数型ではない。

さてどうしたもんでしょうか。

正格評価言語でも マクロがあれば 遅延評価は3分で実装できる

(defmacro lcons (a b)
  "cons whose cdr is lazy"
  `(cons ,a (lambda () ,b)))

(defmacro llist (a &rest args)
  "list using lcons"
  `(lcons ,a ,(when args `(llist ,@args))))

(defmacro ltree (tree)
  (if (consp tree)
      `(llist ,@(mapcar (lambda (e) `(ltree ,e)) tree))
      tree))

マクロの手にかかれば遅延評価なんてお手の物。
あ、cdrしか遅延させないのは自分のニーズがそこだけだからです。
遅延評価にthunkなんて概念ひつようなかったんや。 (もちろんそんなことはありません)

(lcons 0 1) ; --> (cons 0 (lambda () (cons 1 nil)))
(llist 0 1 2) ; --> (cons 0 (lambda () (cons 1 (lambda ...
(ltree (0
        (1 2 3)
        4
        (2
         (3 4 6)
         (7 8 9))
        5))
; --> macroexpand all
(CONS 0
      (LAMBDA ()
        (CONS
         (CONS 1 (LAMBDA () (CONS 2 (LAMBDA () (CONS 3 (LAMBDA () NIL))))))
         (LAMBDA ()
           (CONS 4
                 (LAMBDA ()
                   (CONS
                    (CONS 2
                          (LAMBDA ()
                            (CONS
                             (CONS 3
                                   (LAMBDA ()
                                     (CONS 4
                                           (LAMBDA ()
                                             (CONS 6 (LAMBDA () NIL))))))
                             (LAMBDA ()
                               (CONS
                                (CONS 7
                                      (LAMBDA ()
                                        (CONS 8
                                              (LAMBDA ()
                                                (CONS 9 (LAMBDA () NIL))))))
                                (LAMBDA () NIL))))))
                    (LAMBDA () (CONS 5 (LAMBDA () NIL))))))))))

お手軽お手軽。
なお自分のコードの方ではこれ使って捨てたりなにしたりしながら進んでいきます。
書き捨てごめん~