Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-04-13

LISP1.5でL-99 (P01 最後のペアを返す)

| 20:37 | LISP1.5でL-99 (P01 最後のペアを返す) - わだばLisperになる を含むブックマーク はてなブックマーク - LISP1.5でL-99 (P01 最後のペアを返す) - わだばLisperになる

今年は、LISP生誕50年であり、色々やるなら、やはりLISP1.5は外せないだろう…、ということで…。

全部大文字で書いてますが、LISP 1.5も大文字と小文字は区別せず、エミュレータに読み込ませるソースは小文字で書いても大丈夫なので、大文字にする必要はありません。

気分というか趣味の問題ですね…。

; FUNCTION   EVALQUOTE   HAS BEEN ENTERED, ARGUMENTS..
; LAST
;
; ((FOO BAR BAZ))
;
; END OF EVALQUOTE, VALUE IS ..
; (BAZ)

DEFINE((
(LAST (LAMBDA (LST) 
        (COND ((NULL (CDR LST)) LST)
              (T (LAST (CDR LST))))))
))

LAST((FOO BAR BAZ))

APL由来の関数

| 20:17 | APL由来の関数 - わだばLisperになる を含むブックマーク はてなブックマーク - APL由来の関数 - わだばLisperになる

dropで思い出しけれどLISP畑にはAPL由来の関数名は結構あるようで、自分が知ってる範囲では、iota、take、drop、reduceがある。他にもあったりするのだろうか。

でも、あまり良いネーミングとは思えない(笑)

pfcでL-99 (P02 最後2つの要素)

| 19:43 | pfcでL-99 (P02 最後2つの要素) - わだばLisperになる を含むブックマーク はてなブックマーク - pfcでL-99 (P02 最後2つの要素) - わだばLisperになる

自分は毎回混乱しているのですが、2番目の問題は、最後2つの要素を取り出す問題です。

標準でdropがあるので、それを使ってみました。

dropはSRFI-1由来だと思いますが、CLだと、LASTがdropの代わりに使えます。

(last '(1 2 3 4) 2) => (3 4)

(last2 [1 2 3 4])
;=> [3 4]

(def (last2 lst)
  (drop (- (length lst) 2) lst))

(def (last2 lst)
  (if (>= 2 (length lst))
      lst
      (last2 (cdr lst))))

CLで学ぶ「プログラミングGauche」 (6)

| 18:13 | CLで学ぶ「プログラミングGauche」 (6) - わだばLisperになる を含むブックマーク はてなブックマーク - CLで学ぶ「プログラミングGauche」 (6) - わだばLisperになる

今回は6章「リスト」です。

6.1 リストの二つの顔

ここはCL/Scheme共通だと思います。

6.2 リストの基本操作

()のcar、cdr適用は動作が違っているのは、CL/Schemeでの違いでも割と有名な事項だと思います。

CLでは、伝統に則って空リストにcarとcdrを適用すると、()が返ります。

色々深遠な理由があるとも言われているようですが、LISP 1.5では、このような動作ではなく、PDP-1 LISPからかと思っていましたが、(cdr () )は、()のプロパティが返るのでnilが返って来ている訳ではありませんでした。そうなると、PDP-6 LISP以降だと思うのですが、いまいちはっきりしません。まあ、誰も拘ってないと思いますが(笑)

()にcarや、cdrを適用してもエラーにならないというのは、便利なところもありますが、

(defun foo (lst)
  (when (atom (car lst))
    (car lst)))

のように書くと、

(foo ())
;=> nil
(foo '(()))
;=> nil

では、区別がつかないし、エラーにもならないしで気付かないバグを入れていることが自分は多いです。ということで

(defun *car (lst)
  (when (null lst)
    (warn "()にcarを適用しました。"))
  (car lst))

のようなものを作って使ってみたりもしますが、いまいちです。

ちなみに、TAOでは、デフォルトの挙動を大域変数で変更できてエラーにすることも、nilを返すこともできたようです。

  • null?、pair?

CLでは、null、pair?はそれぞれnullと、conspになります。

最後に、-pが付くか、-?が付くかはSchemeと伝統的LISPの習慣の違いかと思いますが、atomと、nullには、-pが付かないので一貫性がなかったりします。これは、LISP 1.5からそうなので、50年来の伝統というほかないんでしょう。処理系によっては、atompや、nullpもあったりするようです。

空リストかを判定する関数としては、nullの他に、endpがあります。endpは、リスト以外を与えるとエラーになります。

6.3 リストの操作

  • fold => reduce

ここでは、foldがでてきます。CLには、foldという名前の関数はありませんが、同じような機能としてreduceがあります。

;; fold
(fold <手続き> <初期値> <リスト> ... <リストN>)

;; reduce / CL
(reduce <手続き> <リスト> :initial-value <初期値>)

reduceでは、初期値をキーワードで与えることと、複数のリストを与えることができないというところが違っています。

また、このセクションででてくる+inf.0、-inf.0のようなものはCLにはありません。

most-negative-〜定数があるので、それが近いといえば近いのかもしれませんが、どうなのでしょう。

  • 内部define => flet、labels

恐らく、Schemeでは、名前空間が一つで変数/関数の名前の衝突を避ける必要があるのでローカル関数は多用される傾向があるんじゃないかと思います。

CLでは空間が別々で変数と関数の名前は衝突せず、割と大らかに大域で定義してしまうことが多いように思います。

個人的には、関数内関数は個別にデバッグするのが面倒に感じるので、大域で定義することが多いです。まあ、デバッグが済んでから合体すれば良いのですが…。

また、CLでは、さらにパッケージを分割することもできるので、名前空間の汚染に関してはそれほど気にする必要はないのかもしれません。

「いちいちfuncallを付けなくてはいけない面倒臭ささ」と「名前の衝突回避のノウハウを頭の片隅に常駐させて置く負担」はトレードオフな気もします。

そして、CLでは、defunの中でdefunを使うような書き方は普通されず、

(defun max-number (lst)
  (defun pick-greater (a b)
    (if (> a b) a b))
  (reduce #'pick-greater lst
          :initial-value most-negative-long-float))

(defun max-number (lst)
  (flet ((pick-greater (a b)
           (if (> a b) a b)))
    (reduce #'pick-greater lst
            :initial-value most-negative-long-float)))

下の例のように、fletや、再帰する場合、labelsを使ってローカル関数を定義します。

内部defunは以前のSBCLでは警告が出たと思ったのですが、今回改めて試してみると警告はでなくなっているようです。

他の処理系でも警告は出ないのですが、これは書法としてOKなのでしょうか…。

6.4 foldの定義

リストの操作を学習する上で、foldの定義をしてみるというのは教材として良いアイディアではないかと思いました。

ここで#?=を使用したデバッグプリントがでてきますが、CLにはないので、適当に以前作ったものを、また載せてみます。

(defmacro debug-print (obj &optional name (output t))
  `(let ((name (if ,name ,name 0)))
     (format ,output "~&#?=[~A]:~A~%#-~4T~A~%" name ',obj ,obj)
     ,obj))

(defun gauche-debug-print (stream char arg)
  (declare (ignore char))
  (if (char= #\= (peek-char t stream))
      (read-char stream))
  `(debug-print ,(read stream t nil t) ,arg t))

(set-dispatch-macro-character #\# #\? #'Gauche-debug-print)

;; #?=を仕込む
(defun fold (proc init lst)
  (if (null lst)
      init
      (fold proc
            #111?=(funcall proc (car lst) init)
            #555?=(cdr lst))))

;; 使ってみる
(fold #'+ 0 '(1 2 3 4 5))
;>>>
;#?=[111]:(FUNCALL PROC (CAR LST) INIT)
;#-  1
;#?=[555]:(CDR LST)
;#-  (2 3 4 5)
;#?=[111]:(FUNCALL PROC (CAR LST) INIT)
;#-  3
;#?=[555]:(CDR LST)
;#-  (3 4 5)
;#?=[111]:(FUNCALL PROC (CAR LST) INIT)
;#-  6
;#?=[555]:(CDR LST)
;#-  (4 5)
;#?=[111]:(FUNCALL PROC (CAR LST) INIT)
;#-  10
;#?=[555]:(CDR LST)
;#-  (5)
;#?=[111]:(FUNCALL PROC (CAR LST) INIT)
;#-  15
;#?=[555]:(CDR LST)
;#-  NIL

Gaucheのようにソースファイルの行を表示することは、難しかったのですが、ディスパッチマクロ文字は、10進数の引数が取れるので番号付けで代用してみています。

しかし、CLには、普通にtraceがあるので、

(trace fold)

で、

  0: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 0 (1 2 3 4 5))
    1: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 1 (2 3 4 5))
      2: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 3 (3 4 5))
        3: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 6 (4 5))
          4: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 10 (5))
            5: (FOLD #<FUNCTION (SB-C::&OPTIONAL-DISPATCH +) {10007DEFC9}> 15
                     NIL)
            5: FOLD returned 15
          4: FOLD returned 15
        3: FOLD returned 15
      2: FOLD returned 15
    1: FOLD returned 15
  0: FOLD returned 15

のように表示することもできるので、普通はこっちを使えば良いかなと思います。

6.5 簡単なリスト処理

ここでは、CLの関数で言えば、last、copy-list、copy-tree/練習問題、append、reverse、find-ifを自作することによってリスト処理を学びます。

deep-copy-listは、CLの標準関数でいうと、copy-treeになるかと思います。

一応、課題を書いてみました。

(defun deep-copy-list (lst)
  (if (consp lst)
      (cons (deep-copy-list (car lst))
            (deep-copy-list (cdr lst)))
      lst))
  • char-alphabetic? => alpha-char-p

char-alphabetic?は、CL標準では、alpha-char-pとして存在しています。

  • find => find-if

ここでのfindは、CLでは、find-ifです。

また、condの説明がでてきますが、Schemeのようにelseがキーワードになってはいません。

慣例的にtを書きますが、CLでは、nil以外は全部真なので、'Tでも'elseでも:elseでもOKです。

また、RSR6風の括弧の使い方ですが、CLにはこのようなものはないので欲しい場合は、自作することになると思います。

(defun open-bracket-macro-char (stream macro-char)
  (declare (ignore macro-char))
  (read-delimited-list #\] stream t))
(set-macro-character #\[ #'open-bracket-macro-char)
(set-macro-character #\] (get-macro-character #\)))

;; 使用例
(defun my-find-if (pred lst)
  (cond [(null lst) nil]
        [(funcall pred (car lst)) (car lst)]
        [:else (my-find-if pred (cdr lst))]))

6.6 2種類の再帰

末尾再帰とそれ以外の再帰についてのセクションです。

Schemeでは末尾再帰が最適化されるというところは、Schemeのプログラミング書法にはかなり大きく影響していると思います。

CLでは、最適化することを義務付けてはいないので、処理系によってするものもあればしないものもあるといった感じです。

ということで、末尾再帰が必ず最適化されることを期待して書くということは推奨されていないようで普通にループで書くことが多いようです。

イレギュラーなところでは、

(defun len (lst)
  (prog ((lst lst) (n 0))
    =>  (return (if (null lst)
                    n
                    (progn (setq lst (cdr lst) n (1+ n))
                           (go =>))))

のように書けば、関数呼び出し気分なgotoを書けるので、もの好きな方にはお勧めしたいです(笑)

このブログでも、末尾再帰の最適化機構付きのtail-recursive-defunというマクロを古いMacLISPのコードからみつけて動作を考えてみたことがありましたが、マクロのレベルで構文を解析して、末尾再帰的記述をループに書き換えるというのはどの程度有効なのでしょう。

どうしても、変数の代入と束縛というところが違ってきてしまう気はしますが…。

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20080413