Archive for the ‘dft-node’ Tag
newLISP で On Lisp する...第20章(その4)
(この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsp と onnewlisp.lsp に定義してあります。)
第20章 継続 も4回目。今回で終わります。
では、新しい 継続渡しマクロを使ったツリーの探索 の実装です。
(=bind、=defun、=value は onnewlisp.lsp に定義してあります)
(setq *saved* '())
(=defun dft-node (tree)
(cond ((null tree) (restart))
((atom tree) (=values tree))
(true (push (list *cont* (fn () (dft-node (cdr tree))))
*saved*)
(dft-node (first tree)))))
(=defun restart ()
(if *saved*
(let (cc (pop *saved*))
(let (*cont* (cc 0)) ((cc 1))))
(=values 'done)))
(=defun dft2 (tree)
(setq *saved* nil)
(=bind (node) (dft-node tree)
(cond ((= node 'done) (=values nil))
(true (print node)
(restart)))))
前回と違うのは、dft-node と restart のみです。dft-node で、複数の探索の例 で継続渡しを可能にするために、変数 *cont* も push し、restart で取り出しています。
単独の探索の結果は前回と同じとなります。
> (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 >
そして、複数の探索の例。*cont* で継続渡しているのはラムダ式だけなので、変数の引渡しも必要です。
> (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)) > [cmd] (=bind (tmp) (dft-node t1) (if (= tmp 'done) 'done (begin (setq node1 tmp) (=bind (node2) (dft-node t2) (list node1 node2))))) [/cmd] (a 1) > (restart) (a 2) > (time (restart) 60) 6 > (restart) (g 5) > (restart) done >
となります。変数の引き渡しとして、変数 node1 をグローバル変数にしています。継続仕様から見れば、反則技かもしれません。しかし、ダイナミック・スコープの newLISP で、継続渡しをする際の制限です。私の実力かもしれませんが(汗)。
Code-Walker と CPS変換 では、継続渡し版リスト逆転スクリプトを実装してみます。(defun と null は、newlisp-utility.lspp に定義してあります)
(defun identity (x) x)
(defun rev2 (x)
(revc x identity))
(defun revc (x k)
(if (null x)
(k '())
(letex (_k k
_1st (first x))
(revc (rest x)
(fn (w) (_k (append w (list '_1st))))))))
ここでは、letex での変数置換だけで済みます。
動作は、
> (rev2 '(a b c)) (c b a) >
この通り、継続表現は可能です。
さて、第20章 継続 のまとめです。
- newLISPでも、継続渡しを実装できます。しかし、Common Lispでの実装よりも制限が多くなります。
以上、如何でしょうか?
newLISP で On Lisp する...第20章(その3)
(この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsp と onnewlisp.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 を定義して、所望の動作をさせて見せます(笑)。
以上、如何でしょうか?