newLISP で On Lisp する．．．第２０章（その４）

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

　第２０章 継続 も４回目。今回で終わります。

　では、新しい 継続渡しマクロを使ったツリーの探索 の実装です。
（=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)
> 

　この通り、継続表現は可能です。

　さて、第２０章 継続 のまとめです。

• newLISPでも、継続渡しを実装できます。しかし、Common Lispでの実装よりも制限が多くなります。

　以上、如何でしょうか？

newLISP で On Lisp する．．．第２０章（その３）

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

　第２０章 継続 も３回目。 継続渡しマクロを使ったツリーの探索 の前に、ちょっと解説を。
　継続渡しマクロの継続渡しは、変数*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 を定義して、所望の動作をさせて見せます（笑）。

　以上、如何でしょうか？