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

newLISP で On Lisp する...第22章(その2)

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

 “問題が正しく定義できれば、半ば解けた同然である。” と言ったのは、アメリカの教育学者John Dewey氏。
 それはさておき、前回の関数descent は、うまく動作していませんが、バックトラックはうまくいっていることが判っています。
 ただ、全ての再帰の道筋が返ってきているだけ。つまり、関数descent が再帰した分だけ n1 が cons され、返ってくる。
 問題点がわかりました。つまり、必要な分だけ再帰で戻ってきてほしいのです。それが、解決方法。
 そこで考えました、末尾再帰を使えば良いのでは!
 (defun は newlisp-utility.lsp に、=defun と =values は onnewlisp.lsp に、kids と choose-bind は 本章(その1)に定義してあります)

(defun descent (n1 n2)
  (letex (_n1 n1 _n2 n2) 
    (descent-tr '_n1 '_n2 '())))

(=defun descent-tr (n1 n2 res)
    (cond ((= n1 n2) (=values (push n2 res -1)))
          ((kids n1) (letex (_n1 n1)
                       (choose-bind n (kids '_n1)
                           (descent-tr n n2 (push '_n1 res -1)))))
          (true (fail))))

 これなら、戻ってきてほしい要素だけが、末尾再帰関数descent-tr に引数として渡されます。
 こういう時、リストの末尾に追加できるnewLISP組込push が、便利です。

> (descent 'a 'g)
(a c f g)
> (fail)
@
> (descent 'a 'd)
(a b d)
> (fail)
(a c d)
> (fail)
@
> (descent 'a 'f)
(a c f)
> (fail)
@
> 

 うまくいきました!
 ま、でも、Common Lisp や Scheme で試していたら、“うまく言った” で終わって、進歩しなかったでしょうね。newLISP を選んで正解でした(笑)。
 また、前回書き忘れましたが、前の時と違って、“On Lisp”本書のように括弧が一個なのは、今回が多値対応だからです。
 
 さて、letex で渡している変数が、n1 だけですが、全てを記述すると、

(=defun descent-tr (n1 n2 res)
    (cond ((= n1 n2) (=values (push n2 res -1)))
          ((kids n1) (letex (_n1 n1 _n2 n2 _res res)
                       (choose-bind n (kids '_n1)
                         (letex (_n n)
                           (descent-tr '_n '_n2 (push '_n1 '_res -1))))))
          (true (fail))))

 当然、このスクリプトでも動きます。
 と、いうより、こちらが本来の書き方かも(笑)。では、何故前述のスクリプトでも動くのか?
 このスクリプトで n2 は、最後まで変わりませんからね。
 ちなみに、入り口の関数descent は、

(defun descent (x y)
  (descent-tr x y ‘()))

 なら、letex は、いりません。変数 n1、n2 を 変数 x、y に変えてあるのがポイント。つまり、変数補足の問題です。
 これで、Common Lisp での実装 ならぬ newLISP による実装 が完成しました(笑)。

 カット からは、次回に。

 以上、如何でしょうか?