プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(26)

またまた三連休が来ますね。
しばらく平日がないと思うだけで精神が安定するので今日はしっかり勉強できそうです。
今日も「Land of Lisp」を使って、リスト以外のデータ構造について知っていきます。

構造体

構造体は、属性を持つオブジェクトを表現するのに使われるそうです。
定義するにはdefstruct。

CL-USER> (defstruct cat
           name
           age
           sex
           weight)
CAT
CL-USER>

構造体catは、4つの属性(Lisp風に言えばスロットだそう)を持っています。
構造体を定義したので、catのインスタンスをmake-catで作れるそうです。
make-catの定義はdefstructが勝手にやってくれているらしいです。気が利きますね。

CL-USER> (defparameter *elvis*
           (make-cat :name "Elvis"
                     :age 2
                     :sex 'male
                     :weight 6.0))

*ELVIS*
CL-USER> *elvis*
#S(CAT :NAME "Elvis" :AGE 2 :SEX MALE :WEIGHT 6.0)
CL-USER> 

ふむふむ。ここから、例えばageを取り出したければ、cat-ageを呼ぶだけだそう。

CL-USER> (cat-age *elvis*)
2
CL-USER> 

構造体もやっぱり、setfで値を更新することができます。

CL-USER> (setf (cat-age *elvis*) 3)
3
CL-USER>

Lispの入力と出力の対象性を利用して、出力をそのまま利用してインスタンスを作ることもできます。

CL-USER> (defparameter *my-cat* #S(CAT :NAME "Elvis" :AGE 3 :SEX MALE :WEIGHT 6.0))
*MY-CAT*
CL-USER> *my-cat*
#S(CAT :NAME "Elvis" :AGE 3 :SEX MALE :WEIGHT 6.0)
CL-USER>

defstructは色々なことをやってくれる便利コマンドですね。

構造体をいつ使う?

時々オブジェクト指向の話題が盛り上がったりしますね。最近Twitterでトレンド入りしたとか。
偉そうに胡散臭い解説をしている人がいたり…この話はよくないですね。やめます。

Lispではオブジェクト指向チックなこともできるということですが、
それに頼らずとも高品質なソフトウェアは書けるというのがLisperの間では一般的考えだそうです。
まあ、とにかくオブジェクト指向スタイルで書いていない場合でも構造体は便利だと。

しかし構造体なんて使わなくてもリストで同じような表現はできるはずです。

CL-USER> (defun my-make-cat (name age sex weight)
           (list name age sex weight))
MY-MAKE-CAT
CL-USER> (defun my-cat-age (cat)
           (cadr cat))
MY-CAT-AGE
CL-USER> (defparameter *foo* (my-make-cat "neko" 1 'female 3.0))
*FOO*
CL-USER> *foo*
("neko" 1 FEMALE 3.0)
CL-USER> (my-cat-age *foo*)
1
CL-USER>

…defstructが自動でやってくれていたことを自分で書くのは面倒ですね。
面倒なだけでなく間違いが起きそうです。例えばageとweightを逆にして渡してしまうかも。
そもそも*foo*に猫の情報が格納されていることをわからないかも。
…これは変数名をテキトーにつけてしまったせいですが。
通常のリストは属性を持つリストを表現するには不向きですね。

リストでオブジェクトを表現することの大きな問題として、
オブジェクトの値は変わり得ることが更に挙げられます。
Lispのリストは、一度作ったら変わらない、というものを表現するのに向いているそうです。

データ構造の一部が途中で変化することは、コンピュータサイエンスでは特に”変更”と呼ばれるそうです。
defstructで作られる構造体の特定の特性を変更するのはとても簡単なので、
変更可能なデータと構造体は相性がよいということです。

データをジェネリックに扱う

ここまで見てきたとおりCommon Lispにはたくさんデータ型があって、
効率のいいプログラムを優雅に書くことも、データ型の多さを持て余した醜いコードを書くこともできます。

例えば、リストか配列に格納されている数を足し合わせたい時は同じ様なコードを
それぞれのデータ型に向けて書かなきゃいけないのでしょうか。
…朗報です!Common Lispにはジェネリックなコードを書くための道具が豊富にあるそうです。

シーケンス関数

引数のデータ型を気にしなくても良くなる一番簡単な方法として、
データ型のチェックを他の誰かにやってもらうことが挙げられます。
基本のライブラリには、既に様々なデータ型を受け取ってジェネリックな処理をする関数があるそう。
最もよく使われるジェネリックな関数は、シーケンス関数と呼ばれるものだそうです。

CL-USER> (length '(1 2 3 4 5))
5
CL-USER> (length "12345")
5
CL-USER> (length (make-array 5))
5
CL-USER>

長さを調べたいな、と思った時に型を気にせず一つの関数で調べられるのは便利ですね。

シーケンス関数には他にも色々あるようです。

CL-USER> (defparameter *list* '(a b c 3 e))
*LIST*
CL-USER> (defparameter *string* "abc3e")
*STRING*
CL-USER> (defparameter *array* (make-array 5))
*ARRAY*
CL-USER> (find-if #'numberp *list*)
3
CL-USER> (count 3 *list*)
1
CL-USER> (count 3 *string*)
0
CL-USER> (count #\3 *string*)
1
CL-USER> (position #\3 *string*)
3
CL-USER> (position 3 *array*)
NIL
CL-USER> (some #'numberp *list*)
T
CL-USER> (every #'numberp *list*)
NIL

テキトーに実行しました。

ジェネリックなシーケンス関数の中でもreduceという、
シーケンスの全ての要素を単一の値へと蒸留するのに使える関数が便利だそうです。
使ってみます。

CL-USER> (reduce #'+ '(1 2 3 4 5 6 7 8 9 10))
55
CL-USER>

1と2を足してその結果に3を足して…と常に中間結果とシーケンスの次の要素を+に渡しているそう。
最初の1の時は1を中間結果として扱っているらしいです。
少し複雑な関数を渡してみます。

CL-USER> (reduce (lambda (best item)
                   (if (and (evenp item) (> item best))
                       item
                       best))
                 '(7 4 6 5 2)
                 :initial-value 0)
6
CL-USER>

:initial-valueで最初の値を設定できるそうです。
つまり一番最初は引数として0と7が渡っているのですね。
そして7は奇数でないので0が返り、0と4を比較して…、て感じですね。

reduceには初期値を与えないと、見つけづらいバグが出ることがあるそうです。

CL-USER> (reduce (lambda (best item)
                   (if (and (evenp item) (> item best))
                       item
                       best))
                 '(7 4 6 5 2))
7
CL-USER>

奇っ怪なことが起きました。なんだこりゃ。

CL-USER> (reduce (lambda (best item)
                   (if (and (evenp item) (> item best))
                       (progn (print (list best item 'troot)) item)
                       (progn (print (list best item 'nilroot)) best)))
                 '(7 4 6 5 2))

(7 4 NILROOT) 
(7 6 NILROOT) 
(7 5 NILROOT) 
(7 2 NILROOT) 
7
CL-USER> 

ああ、そうか、一回も7が弾かれてくれないんですね。
偶数でもないくせにずっとbestに居座ってしまうからこうなるのか。

さて、reduceはジェネリック可能なシーケンス関数なのでリストだけでなく
配列も扱えるはずです。文字列は…関数によるか。
とにかく、最初に例として出した、要素か配列の要素を足し合わせてくれる関数です。

CL-USER> (defun sum (lst)
           (reduce #'+ lst))
SUM
CL-USER> (sum '(1 2 3 4 5))
15
CL-USER> (sum (make-array 5 :initial-contents '(1 2 3 4 5)))
15
CL-USER> (sum "tasitemiro")
; Evaluation aborted on #<TYPE-ERROR expected-type: NUMBER datum: #\t>.
CL-USER>

シーケンスの全要素に対して繰り返すもう一つの便利な関数はmapであるそう。
mapcarがリストに対してのみ使えるのに対し、mapは全てのシーケンスに使えるらしいです。
また、戻り値としてどのシーケンスの型を返すか選ぶようになっているようです。

CL-USER> (map 'list
              (lambda (x)
                (if (eq x #\s)
                    #\S
                    x))
              "this is a string.")
(#\t #\h #\i #\S #\  #\i #\S #\  #\a #\  #\S #\t #\r #\i #\n #\g #\.)
CL-USER> (map 'string
              (lambda (x)
                (if (eq x #\s)
                    #\S
                    x))
              "this is a string.")
"thiS iS a String."
CL-USER>

ほえ〜。
うん?配列は?

CL-USER> (map 'array
              (lambda (x)
                (if (eq x #\s)
                    #\S
                    x))
              "this is a string.")
; Evaluation aborted on #<SIMPLE-TYPE-ERROR expected-type:
                    (SATISFIES SB-IMPL::IS-A-VALID-SEQUENCE-TYPE-SPECIFIER-P)
                    datum: ARRAY>.
CL-USER> (length "this is a string.")
17
CL-USER> (map '(vector 17)
              (lambda (x)
                (if (eq x #\s)
                    #\S
                    x))
              "this is a string.")
; Evaluation aborted on #<SIMPLE-ERROR "bad thing to be a type specifier: ~/sb-impl:print-type-specifier/" {100403FD53}>.
CL-USER> (map '(vector * 17)
              (lambda (x)
                (if (eq x #\s)
                    #\S
                    x))
              "this is a string.")
#(#\t #\h #\i #\S #\  #\i #\S #\  #\a #\  #\S #\t #\r #\i #\n #\g #\.)
CL-USER>

…mapを使って配列で返すことはあまりないのかもしれません。
もっとちゃんとした方法もありそうですが…。

さらに重要なシーケンス関数として、subseqが挙げられています。

CL-USER> (subseq "japan" 3 5)
"an"
CL-USER>

それとsort。

CL-USER> (sort '(5 62 73 34 7 62 9 1 56) #'<)
(1 5 7 9 34 56 62 62 73)
CL-USER>

何故この2つの関数がさらに重要なのかについては特に記述ありません。
使い所がいっぱいあるのかな。

ジェネリック関数を自作する

Common Lispは動的型付け言語であるので、変数の型を調べる関数が揃っているそうです。
その様な関数(型述語)を使えばジェネリックな関数を自作することができます。
例として、数値同士とリスト同士に対して使える関数addが出てきます。

CL-USER> (defun add (a b)
           (cond ((and (numberp a) (numberp b)) (+ a b))
                 ((and (listp a) (listp b)) (append a b))))
ADD
CL-USER> (add 6 9)
15
CL-USER> (add '(6) '(9))
(6 9)
CL-USER>

引数の型を調べて、両方とも数値だったら、リストだったらと処理を分岐していますね。
条件が合わなかったら単にnilが返ってきます。

しかし多くのLisperはこのようには書かないだろうと続きます。その理由は…
・2つの型にしか対応していないからまだいいが、もっと多くの型に対応するようにしたら
 関数が膨れ上がってしまう。
・新しい型をサポートしたくなった時に改修が大変
・条件分岐がたくさんあると何をしているのか、それで正しいのか理解しづらい
コンパイラが最適化しづらく、性能が悪いかも

一つの関数が引数の型に応じて処理を切り替えられるのは便利なので、
それぞれの型に特化した複数の関数を同じ名前で定義できるdefmethodが用意されているそうです。
それで定義された関数が呼び出されると、Lispは自動的に引数を調べて、
対応する関数を呼び出してくれるということです。
これは”型によるディスパッチ”と呼ばれるとか。
というわけでadd関数を書き直します。

CL-USER> (defmethod add ((a number) (b number))
           (+ a b))
; Evaluation aborted on #<SB-INT:SIMPLE-PROGRAM-ERROR "~@<~/sb-ext:print-symbol-with-prefix/ ~
                           already names an ordinary function or a ~
                           macro.~@:>" {1004679FD3}>. ;"半端なダブルクォートのせいではてなブログが勘違いしちゃうので閉じてます
CL-USER> (makunbound 'add)
ADD
CL-USER> (defmethod add ((a number) (b number))
           (+ a b))
; Evaluation aborted on #<SB-INT:SIMPLE-PROGRAM-ERROR "~@<~/sb-ext:print-symbol-with-prefix/ ~
                           already names an ordinary function or a ~
                           macro.~@:>" {1004888B53}>. ;"半端な(以下略
CL-USER> (fmakunbound 'add)
ADD
CL-USER> (defmethod add ((a number) (b number))
           (+ a b))
#<STANDARD-METHOD COMMON-LISP-USER::ADD (NUMBER NUMBER) {1004961143}>
CL-USER> (defmethod add ((a list) (b list))
           (append a b))
#<STANDARD-METHOD COMMON-LISP-USER::ADD (LIST LIST) {1004B0D333}>
CL-USER> (add 5 9)
14
CL-USER> (add '(5) '(9))
(5 9)
CL-USER>

関数に束縛されたシンボルを開放するときにはfmakunbound。覚えました。

オブジェクト指向を知っていたら、メソッドという言葉から特定の意味を読み取るだろうとあります。
じゃあdefmethodはオブジェクト指向と関係があるのか?
ズバリ、あるそうです。
defmethodはdefstructで作った構造体に対しても使え、
そのように組み合わせることで簡単なオブジェクトシステムを作れるということで、
ここから楽しいゲーム作成の時間になります!

でも、もう長くなってしまいました。今日はここまでにします。
おやすみなさい。