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

(この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsponnewlisp.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での実装よりも制限が多くなります。

 以上、如何でしょうか?

広告

No comments yet

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。