Archive for 2010年8月月21日|Daily archive page

newLISP で On Lisp する...第20章(その3)

(この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsponnewlisp.lsp に定義してあります。)

 第20章 継続 も3回目。 継続渡しマクロを使ったツリーの探索 の前に、ちょっと解説を。
 継続渡しマクロの継続渡しは、変数*cont* を通して行われます。“On Lisp” 本書には、その解説として、クロージャの連鎖の簡単な例があります。これは Common Lisp で、下記のスクリプトと等価です。

> (funcall
    (let ((f #'identity))
      (let ((g #'(lambda (x) (funcall f (list 'a x)))))
        #'(lambda (x) (funcall g (list 'b x))))) 2)
(A (B 2))
> 

 この例は、以前、newLISP では表現できないとしていましたが、間違いです。
 下記のように記述できます。

> (define (indentify x) x)
(lambda (x) x)
> [cmd]
((letex (f 'indentify)
   (letex (g (fn (x) (f (list 'a x))))
     (fn (x) (g (list 'b x))))) 2)
[/cmd]
(a (b 2))
> 

 ポイントは、let ではなく、letex で関数を渡している点。
 newLISP でグローバル変数を使わずに継続渡しをするのに、letex で変数を置き換えることが有効です。
 言い換えれば、newLISP で継続渡しをするには、letex で変数を置き換えるか、グローバル変数を使うか、あるいは両方を使うということになります。これが、前回前振りした新たなる制限です。

 前置きが長くなりましたが、継続渡しマクロを使ったツリーの探索 の実装です。

(setq *saved* '())

(=defun dft-node (tree)
  (cond ((null tree) (restart))
        ((atom tree) (=values tree))
        (true (push (fn () (dft-node (rest tree)))
                 *saved*)
          (dft-node (first tree)))))

(=defun restart ()
  (if *saved*
      ((pop *saved*))
    (=values 'done)))


(=defun dft2 (tree)
  (setq *saved* nil)
  (=bind (node) (dft-node tree)
    (cond ((= node 'done) (=values nil))
          (true (print node)
                (restart)))))

 見た目は、“On Lisp”本書のスクリプト例と、ほぼ同等です。違うのは、Common Lisp と newLISP の違いです。
 なお、前回定義した継続渡しマクロ群(=lambda、=defun、=values、=bind、=funcall、=apply)は、onnewlisp.lsp に加えてあります。
 さて動作はというと、

> (setq t1 '(a (b (d h)) (c e (f i) g)) t2 '(1 (2 (3 6 7) 4 5)))
(1 (2 (3 6 7) 4 5))
> (dft2 t1)
abdhcefignil
> (dft2 t2)
 1236745nil

 所望の動作をしています。
 しかし、次の 複数の探索の例 となると、そうはいきません。
 では、どうするのか? それは、次回、新たに dft-node と restart を定義して、所望の動作をさせて見せます(笑)。

 以上、如何でしょうか?

広告