Archive for 2010年7月4日|Daily archive page

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

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

 第5章 返り値としての関数 もその3です。
 今回は、Cdr 部での再帰 から。ちなみに、newLISP では、伝統的な car と cdr が無く、新しい仕様の firstrest のみとなっています。newLISP だから(笑)? newlisp-utility.lsp に、その辺りを定義してあるので、本 blog では、当たり前のように使っていますけどね。
 前置きが長くなりましたが、関数lrec は、こうなります。(defun、null、labels は newlisp-utility.lsp に定義してあります)

(define functionp (fn (x) (or (lambda? x) (primitive? x))))
(defun lrec (rec-f base-f)
  (letex (rec rec-f
          base base-f)
    (labels ((self-r (lst)
                   (if (null lst)
                       (if (functionp 'base) (base) 'base)
                       (rec (car lst)
                            (fn () (self-r (cdr lst)))))))
      self-r)))

 関数functionp が、newLISPに無いので、最初に定義しています。あとは、今まで使った手法をそのまま使えます。なんといっても、labels が使えるのが楽です(笑)。また、現在のnewLISPでは、self は組込なので、self-r に変えてあります。
 動作はというと、(numberp、oddp は newlisp-utility.lsp に定義してあります)

> ((lrec (lambda (x f) (++ (f))) 0) '(1 2 3 4))
4
> ((lrec (lambda (x f) (or (numberp x) (f)))) '(1 2 3 4))
true
> ((lrec (lambda (x f) (and (oddp x) (f))) t) '(1 5 3 7))
true
> ((lrec (lambda (x f) (list x (f))) '(5 6)) '(1 2 3 4))
(1 (2 (3 (4 (5 6)))))
> 

 そして、lrec で表現された関数は、(evenp は newlisp-utility.lsp に定義してあります)

> ((lrec (fn (x f) (cons x (f))) '()) '(1 a 2 b))
(1 a 2 b)
> (defun adjoin (x lst) (if (find x lst) lst (cons x lst)))
(lambda (x lst) 
 (if (find x lst) 
  lst 
  (cons x lst)))
> ((lrec (fn (x f) (adjoin x (f))) '()) '(1 2 3 1 3 4))
(2 1 3 4)
> ((lrec (fn (x f) (if (evenp x) x (f)))) '(1 2 3))
2
> ((lrec (fn (x f) (or (evenp x) (f)))) '(1 2 3))
true
> ((lrec (fn (x f) (or (evenp x) (f)))) '(1 5 3))
nil
> 

 こんな感じでしょうか?
 lambda は、fn と書けるの楽です。
 関数adjoin は、newLISP には、無いので途中で定義しています。
 copy-list と remove-duplicates の動作例に空リスト '() が必要なのは、newLISPでは、nil'() が別物だからです。いずれも、'() が無いと、戻りリストの最後に nil が入ります。

 そして、部分ツリーでの再帰 です。前にも言ったように、newLISP では、eq、eql、equal の区別が無いので、copy-list と copy-tree の結果の比較は無意味です。どっちみち両関数ともありませんけどね。ツリーとしてのリストとは、本書にある図とたぶん一緒です、nil が無い点を除けば。
 ですから、ツリーの葉を数える関数count-leaves
(atom は newlisp-utility.lsp に定義してあります)

(defun count-leaves (tree)
  (if (atom tree)
      1
      (+ (count-leaves (car tree))
         (or (if (cdr tree) (count-leaves (cdr tree)))
             0)))) ; orignal 1 ,but in newLISP there are no dotted pairs. 

 の動作は、

> (count-leaves '((a b (c d)) (e) f))
6
> 

 です。Common Lisp の場合と違って、アトムの数だけになります。何故って、関数count-leaves の最後の行の 10 に書き換えているからです(笑)。ここのカウントが nil の数になります。当然、newLISP では、0 でしょう、なんてね。 1 に戻せば、Common Lisp と同じ数が出ます。
 さて、関数flatten は、newlisp-utility.lsp を使えば、nconc を newLISP組込extendと置き換えるだけで、動きます。
 関数rfind-if は、

(defun rfind-if (f tree)
  (if (atom tree)
      (and ( f tree) tree)
      (or (rfind-if f (car tree))
          (if (rest tree) (rfind-if f (rest tree))))))  ; cdr -> rest at 2010/ 8/ 4 changed.

 いつものように、fn は f にして、funcall を外します。
 そして、動作は、

> (rfind-if (fint numberp oddp) '(2 (3 4) 5))
3
> 

 前回定義した fint との組み合わせも問題ありません。私の持っている“On Lisp”本書の動作例では、関数addp と記載されていますが、oddp に変えて試しています(笑)。
 次に、関数ttrav を定義します。

(defun identity (x) x)
(defun ttrav (rec-f (base-f identity))
  (letex (rec rec-f
          base base-f)
    (labels ((self-r (tree)
               (if (atom tree)
                   (if (functionp 'base) (base tree)
                       (MACRO?    'base) (eval (base tree))
                     'base)
                 (rec (self-r (car tree))
                      (if (rest tree) ; cdr -> rest at 2010/ 8/ 4 changed.
                          (self-r (rest tree)))))))
    self-r)))

 関数identity は、newLISP には、無いので、先に定義してあります。
 関数判定部分に MACRO? を追加しているのは、前回同様macro 対応です。あとは、labelsletex のおかげで、ここですら、特筆すべきことが無いですね(笑)。
 では、動作を

> ((ttrav (lambda (l r) (+ l (or r 0))) 1) '((a b (c d)) (e) f))
6
> (define nconc extend)
extend
> ((ttrav nconc mklist) '(1 2 (3 4)))
(1 2 3 4)
> ((ttrav append list) '(1 2 (3 4)))
(1 2 3 4)

 関数mklist は、第4章(その2)にあり(newlisp-utility.lspにもあります)、nconc は newLISPで同等機能の extend に変えてあります。
 そして、関数trec 。

(defun trec (rec-f (base-f identity))
  (letex (rec rec-f
          base base-f)
    (labels
      ((self-r (tree)
         (if (atom tree)
             (if (functionp 'base) (base tree)
                 (MACRO?    'base) (eval (base tree))
               'base)
             (rec tree (fn () (self-r (car tree)))
                       (fn () (if (rest tree)  ; cdr -> rest at 2010/ 8/ 4 changed.
                                  (self-r (rest tree))))))))
      self-r)))

 動作は、

> ((trec (fn (o l r) (or (l) (r))) (fn (tree) (and (oddp tree) tree))) '(2 (3 4) 5))
3
> ((trec (lambda (o l r) (extend (l) (r))) mklist) '(a b (c d (e f) g h) i))
(a b c d e f g h i)
> ((trec (lambda (o l r) (append (l) (r))) list) '(a b (c d (e f) g h) i))
(a b c d e f g h i)

 と、いうところ。抽象化が進むにつれて、実行時の表記が面倒に思えてくるのは、私だけ?

 最後に、いつ関数を作るべきか 。単純に、クロージャを返す関数から始まり、合成、再帰による展開等を使って、より抽象化されたクロージャ生成関数へと進んできました。この抽象化していくとう考え方は、Lisp に限らず、プログラミングでは重要です。後は、それをどう実装するか? Lisp は、それをクロージャを返す関数として実装できるすぐれものです。
 実行時のオーバーヘッド(関数生成にかかる時間)をどう考えるか? CPU の性能アップはメモリ帯域と共に上がりっぱなしですからね(笑)。
 この章で見てきた抽象化への道筋は、おろそかには出来ません。

 さて、第5章のまとめです。

  • newLISP でも、クロージャを返す関数は作れる。ただし、letex ( expand な部分) の使用が不可欠です。

 以上、如何でしょうか?

広告