Common Lisp Programming

構造体

「構造体 (structor)」は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能です。Ｃ言語ユーザーにはおなじみの機能ですね。Ｃ言語の構造体はデータ型を定義するだけですが、Common Lisp の構造体はそれだけではなく、データを生成する関数 (コンストラクタ) やアクセス関数を自動的に生成します。

●構造体の定義

構造体はマクロ defstruct を使って定義します。

(defstruct 構造体名
    (スロット名 デフォルト値)
    ・・・・
    (スロット名 デフォルト値))

「スロット (slot)」とは、構造体で定義した変数のことです。他の言語、たとえばＣ言語では「メンバ変数」といいます。defstruct は構造体の定義のほかに、次の関数を生成します。

• 定義したデータを作るコンストラクタ「make-構造体名」を生成する。
• スロットの値をリードするアクセス関数「構造体名+変数名」を生成する。
• スロットへの書き込みは「setf とアクセス関数」で行うことができる。
• データをコピーする関数「copy-構造体名」を生成する。
• データ型を判定する述語「構造体名-p」を生成する。

defstruct はデータ型を定義して必要な関数を生成するだけで、実際のデータを作り出すわけではないことに注意してください。

それでは、簡単な例を示しましょう。

* (defstruct foo (a 10) (b nil) c)

FOO
* (setq z1 (make-foo))

#S(FOO :A 10 :B NIL :C NIL)
* (setq z2 (make-foo :b 20 :c 30))

#S(FOO :A 10 :B 20 :C 30)
* (setf (foo-a z1) 100)

100
* z1

#S(FOO :A 100 :B NIL :C NIL)
* (equal z2 z3)

NIL
* (equalp z2 z3)

T
* (foo-p z1)

T

SBCL の場合、構造体は #S(名前 :スロット名 値 ... ) と表示されます。また、スロット C のように、デフォルト値を省略すると NIL に初期化されます。コンストラクタでは、スロット名をキーワードとして使用することで、その初期値を設定することができます。

スロットのリード・ライトとデータ型の判定は簡単ですね。copy-foo はデータをコピーします。コピーしたデータは equal で判定すると NIL になりますが、equalp で判定すると T になります。構造体を使うと、これらの関数が自動的に生成されるのでとても便利です。

●defstruct のオプション

defstruct はいろいろなオプションを指定することができます。その中で、生成される関数の名前を変更するオプションと、ほかの構造体を取り込むオプション :include を説明します。

オプションの指定方法は、次のように行います。

(defstruct (name (option1 data1) (option2 data1) ...) ... )

それでは簡単な例を示しましょう。

* (defstruct (bar (:conc-name get-) (:constructor create-bar))
  (a 10) (b 20))

BAR
* (setq z1 (create-bar))

#S(BAR :A 10 :B 20)
* (get-b z1)

20

:include オプションを使うと、既存の構造体を取り込むことができます。

* (defstruct foo (a 10) (b 20))

FOO
* (defstruct (bar (:include foo)) (c 30))

BAR
* (setq z1 (make-foo))

#S(FOO :A 10 :B 20)
* (setq z2 (make-bar))

#S(BAR :A 10 :B 20 :C 30)
* (foo-a z1)

10
* (foo-a z2)

10
* (bar-a z2)

10

BAR は FOO を inlcude しているので、FOO の構造を取り込むことができます。したがって、FOO のスロット A, B と BAR で定義したスロット C を持っています。このとき、FOO で生成したアクセス関数は、BAR のスロット A, B にもアクセスできることに注意してください。

構造体 BAR を定義するときに、FOO で指定したデフォルト値を変更することができます。次の例を見てください。

* (defstruct (bar1 (:include foo (a 100))) (c 30))

BAR1
* (setq z1 (make-foo))

#S(FOO :A 10 :B 20)
* (setq z2 (make-bar1))

#S(BAR1 :A 100 :B 20 :C 30)

:include の後ろにスロットのデフォルト値を記述します。例のように (a 100) と設定すれば、構造体 BAR1 のスロット A は 100 に初期化されます。

●位置によるコンストラクタ

defstruct のオプション :constructor はコンストラクタの名前だけではなく、次の書式で標準とは異なるコンストラクタを定義することができます。

(:constructor name arglist)

name はコンストラクタの名前、arglist はリストで、スロットを初期化するための引数を指定します。このとき、仮引数名がスロットと同じ名前であれば、実引数の値がスロットの初期値となります。つまり、キーワードではなく引数の位置によりスロットの初期値を指定するわけです。

簡単な例を示しましょう。

* (defstruct (foo (:constructor create-foo (a b)))
  a b)

FOO
* (create-foo 1 2)

#S(FOO :A 1 :B 2)

構造体 FOO のスロットは A, B です。コンストラクタ create-foo の引数も A, B で、スロットと同じ名前です。(create-foo 1 2) を評価すると、FOO のスロット A は 1 に B は 2 に初期化されます。この場合、デフォルトのコンストラクタ make-foo は生成されません。ご注意くださいませ。

:constructor は複数回用いることができるので、異なるコンストラクタを定義することができます。また、arglist の中ではラムダリストキーワード &key, &optional, &rest, &aux を使用することができます。

簡単な例を示しましょう。

* (defstruct (bar
  (:constructor create-bar (a b))
  (:constructor create-bar-x (x &aux (a (* x 10)) (b (* x 20)))))
  a b)

BAR
* (create-bar 1 2)

#S(BAR :A 1 :B 2)
* (create-bar-x 5)

#S(BAR :A 50 :B 100)

create-bar はスロット A, B を初期化します。create-bar-x は引数 X の値を使ってスロット A, B を初期化します。&optional (x 5) とすれば、X のデフォルト値を設定することができますし、&key (x 5) とすればキーワード :X を使って X の値を指定することができます。このように、ラムダリストキーワードを使ってスロットの初期化を柔軟に行うことができます。

●カプセル化

ところで、わざわざ構造体を使わなくてもリストで十分ではないか、と思われる方もいるでしょう。実際、リストを使って新しいデータ型を表すことも可能です。たとえば、リストの第 1 要素をデータ型名 FOO とし、第 2 要素をスロット A、第 3 要素をスロット B、第 4 要素をスロット C としましょう。コンストラクタやアクセス関数だって、わざわざ定義することもありません。

* (setq z (list 'foo 10 20 30))

(FOO 10 20 30)
* (second z)

10
* (setf (second z) 100)

100
* z

(FOO 100 20 30)

簡単にプログラムできるように思えますが、この方法には大きな弱点があるのです。ひとつは、データにアクセスするときに、要素の位置とデータの対応をプログラマが把握していないといけません。スロット C はリストの何番目だったかな、A, B, C の 3 番目か、いや先頭にデータ型のシンボルが入るから 4 番目か、などと考えながらプログラムするのではストレスがたまってしまいますね。

もうひとつは、データ構造を変更するときです。たとえば、スロット A が不用になったので、リストから削除することにしました。すると、スロット B, C の位置がひとつずつ前へずれるので、アクセスしている個所をすべて修正しなければいけません。データへのアクセスは単なるリスト操作関数にすぎないので、その関数が目的のデータを操作しているのか、それとも、それ以外のデータを操作しているのかを区別しながら、すべてのプログラムを修正しなければいけません。この修正作業は、プログラムの規模が大きくなればなるほど困難なものになります。

ようするに、データに直接アクセスするから、このような問題を引き起こすのです。そこで、次のようなアクセス関数を定義してみましょう。

(defun get-a (data)
  (second data))
(defun put-a (data value)
  (setf (second data) value))

(defun get-b (data)
  (third data))
(defun put-b (data value)
  (setf (third data) value))

(defun get-c (data)
  (fourth data))
(defun put-c (data value)
  (setf (fourth data) value))

アクセス関数の仕様さえわかっていれば、スロット A がリストの 2 番目の要素に対応するといった、データ構造の詳細を把握する必要はありませんね。それから、関数名によってスロットの値をリードしていることが明確になります。また、スロット A を削除する場合、関数 get-a を検索すれば、修正個所を簡単に見つけることができます。スロット B, C にしても、関数 get-b, put-b を (second data) に、get-c, put-c を (third data) に修正するだけで、ほかのプログラムを見直す必要はまったくありません。

このように、データ構造に直接アクセスせず、アクセス関数を経由してデータの読み書きを行うことを、「データ抽象」とか「カプセル化」といいます。わざわざアクセス関数を用意するのは面倒なようですが、そのことによりデータ構造の細かいところを気にしなくてもいいわけです。それだけプログラムも読みやすくなり、修正にも強いプログラムを作ることができます。

Ｃ言語の構造体はデータ構造を定義するだけです。したがって、カプセル化を行うにしても、アクセス関数はプログラマが用意しなければいけません。ところが、Common Lisp の場合は、defstruct を使用するだけでアクセス関数も自動的に用意されるため、カプセル化を簡単に行うことができるのです。これが Common Lisp で構造体を使うメリットです。

このデータ抽象を進めていくと「オブジェクト指向」へとつながります。ここでオブジェクト指向の話はしませんが、興味のある方は拙作のページ お気楽 CLOS プログラミング入門 をお読みください。

●リストによるキューの実装

それでは簡単な例題として、リストを使って「キュー (queue)」という基本的なデータ構造を実装してみましょう。キューは「待ち行列」といわれるデータ構造です。たとえば、チケットを買う場合窓口に長い列ができますが、それと同じだと考えてください。

チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。

キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。

たとえば、データの追加に append を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると実行時間がかかるようになります。そこで、append の代わりに nconc を使うことを考えてみます。この場合、リストのコピーは回避できますが、最後尾のセルは先頭から順番にセルをたどっていかないと到達できないので、データが多くなるとやっぱり時間がかかってしまいます。

そこで、最後尾のセルを格納する変数を用意することにします。

上図に示すように、リストを保持する変数 FRONT のほかに、最後尾のセルを格納する変数 REAR を用意します。変数 FRONT と REAR は構造体にまとめておくといいでしょう。キューを操作するプログラムは次のようになります。

リスト : リストによるキューの実装

;;; キューの定義
(defstruct queue (front nil) (rear nil))

;;; キューは空か？
(defun emptyp (q)
  (null (queue-front q)))

;;; データの挿入
(defun enqueue (q item)
  (let ((new-cell (list item)))
    (if (emptyp q)
        ;; キューは空の状態
        (setf (queue-front q) new-cell)
      ;; 最終セルを書き換える
      (setf (cdr (queue-rear q)) new-cell))
    (setf (queue-rear q) new-cell)))

;;; データを取得
(defun dequeue (q)
  (unless (emptyp q)
    (prog1
        (pop (queue-front q))
      (when (emptyp q)
        ;; キューは空になった
        (setf (queue-rear q) nil)))))

最初に defstruct で構造体 QUEUE を定義します。FRONT と REAR は NIL に初期化します。関数 emptyp はキュー Q が空ならば T を返し、そうでなければ NIL を返します。キューが空の場合は FRONT だけではなく REAR の値も NIL にしますが、データの有無は FRONT の値をチェックするだけで十分です。

キューにデータを挿入する関数が enqueue です。最初に、引数 ITEM をセルに格納して変数 NEW-CELL にセットします。次に、キューが空の場合は FRONT に NEW-CELL をセットします。キューが空でなければ、最後尾のセルの CDR 部を書き換えて NEW-CELL を連結します。このとき、setf で (cdr (Queue-rear queue)) と指定すると、REAR に格納されているセルの CDR 部を書き換えることができます。最後に NEW-CELL を REAR にセットして最後尾のセルを更新します。

キューからデータを取得する関数が dequeue です。キューにデータがある場合は pop で先頭データを取り出します。prog1 により pop で取り出されたデータが dequeue の返り値となります。キューが空の場合は NIL を返します。そして、キューが空になった場合は REAR に NIL をセットします。

これでプログラムは完成です。それでは実行してみましょう。

* (setq que (make-queue))

#S(QUEUE :FRONT NIL :REAR NIL)
* (dotimes (x 5) (enqueue que x))

NIL
* que

#S(QUEUE :FRONT (0 1 2 3 4) :REAR (4))
* (loop (if (emptyp que) (return)) (print (dequeue que)))

0
1
2
3
4
NIL
* que

#S(QUEUE :FRONT NIL :REAR NIL)

きちんと動作していますね。

●循環リストによるキューの実装

次は循環リストを使ってキューを実装してみましょう。循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。

               図 : 循環リストによるキューの構造

循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、rear が参照する最後尾のセルの CDR 部は空リストではありません。CDR 部が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように rear が参照するセルの CDR 部は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように空リストとします。

●プログラムの作成

それではプログラムを作りましょう。次のリストを見てください。

リスト : 循環リストによるキューの実装

(setq *print-circle* t)

;;; キューの定義
(defstruct queue (rear nil))

;;; キューは空か？
(defun emptyp (q)
  (null (queue-rear q)))

;;; データの挿入
(defun enqueue (q item)
  (let ((new-cell (list item)))
    (if (emptyp q)
        (setf (cdr new-cell) new-cell)
      (setf (cdr new-cell) (cdr (queue-rear q))
            (cdr (queue-rear q)) new-cell))
    (setf (queue-rear q) new-cell)))

;;; データの取得
(defun dequeue (q)
  (unless (emptyp q)
    (let ((front (cdr (queue-rear q))))
      (if (eq front (queue-rear q))
          (setf (queue-rear q) nil)
        (setf (cdr (queue-rear q)) (cdr front)))
      (car front))))

最初に defstruct で構造体 QUEUE を定義します。REAR は NIL に初期化します。関数 emptyp はキュー Q が空ならば T を返し、そうでなければ NIL を返します。これは REAR が NIL かチェックするだけです。関数 enqueue は、最初に ITEM をリストに格納して変数 NEW-CELL にセットします。キューが空の場合、NEW-CELL の CDR 部を自分自身に書き換えてから、最後で REAR にセットします。

キューにデータがある場合は、REAR の後ろに NEW-CELL を連結します。まず、NEW-CELL の CDR 部を (cdr (queue-rear q)) に書き換えます。これで NEW-CELL の後ろに先頭のセルが接続されます。それから、REAR の CDR 部を NEW-CELL に書き換えます。これで、REAR と先頭のセルの間に NEW-CELL を挿入することができます。最後に NEW-CELL を REAR にセットします。

次に関数 dequeue を定義します。キューにデータがある場合、先頭のセル (cdr (queue-rear q)) を変数 FRONT にセットします。FRONT と REAR が eq で等しい場合、最後のデータを取り出してキューは空になります。この場合、REAR に空リストをセットします。そうでなければ、REAR の CDR 部を (cdr front) に書き換えて、FRONT のセルを循環リストから外します。最後に FRONT の要素 (car front) を返します。

●実行例

これでプログラムは完成です。それでは実行してみましょう。

* (setq que (make-queue))

#S(QUEUE :REAR NIL)
* (dotimes (x 5) (enqueue que x))

NIL
* que

#S(QUEUE :REAR #1=(4 0 1 2 3 . #1#))
* (loop (if (emptyp que) (return)) (print (dequeue que)))

0
1
2
3
4
NIL
* que

#S(QUEUE :REAR NIL)

正常に動作していますね。

●ベクタによるキューの実装

ところで、キューは配列を使っても簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

                    図 : キューの動作

まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値をインクリメントします。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。

次に、データを取り出す場合、front の示すデータを取り出してから front の値をインクリメントします。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。

rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実現する場合は、リングバッファとするのがふつうです。

●プログラムの作成

Common Lisp の場合、リングバッファを操作する関数は用意されていないので、実際に作ってみることにしましょう。最初に、基本的な操作関数を説明します。

• create-queue n
  大きさが n のキューを作る。
• enqueue q item
  キュー q にデータ item を追加する。成功は T を失敗は NIL を返す。
• dequeu q
  キュー q からデータを取り出す。失敗は NIL を返す。
• front q
  キュー q の先頭データを返す。このとき、データはキューから削除されない。
• emptyp q
  キュー q が空の場合は T を、そうでなければ NIL を返す。
• fullp q
  キュー q が満杯の場合は T を、そうでなければ NIL を返す。
• clear q
  キュー q を空にする。

述語 emptyp と fullp は Lisp らしく最後に p を付けてみました。 次に、キューを表す構造体を定義します。

●キューの定義

リスト : キュー (リングバッファ) の定義

(defstruct (queue
            (:constructor create-queue (size &aux (buffer (make-array size)))))
  (front 0) (rear 0) (count 0) size buffer)

スロット COUNT はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。スロット SIZE はベクタの大きさを、スロット BUFFER にはベクタをセットします。create-queue の引数が SIZE にセットされ、その大きさでベクタが生成されます。

●データの挿入

次はデータを追加する関数 enqueue を作ります。

リスト : データの挿入

(defun enqueue (q item)
  (unless (fullp q)
    (setf (aref (queue-buffer q) (queue-rear q)) item)
    (incf (queue-count q))
    (incf (queue-rear q))
    (if (= (queue-rear q) (queue-size q))
        (setf (queue-rear q) 0))
    t))

まず、(fullp q) でキューが満杯かチェックします。空きがある場合、REAR の位置に ITEM を格納し、COUNT と REAR の値を更新します。そして、REAR の値がベクタの範囲を超えたならば 0 に戻します。

●データの取得

次は、キューからデータを取得する関数 dequeue を作ります。

リスト : データの取得

(defun dequeue (q)
  (unless (emptyp q)
    (prog1
        (aref (queue-buffer q) (queue-front q))
      (decf (queue-count q))
      (incf (queue-front q))
      (if (= (queue-front q) (queue-size q))
          (setf (queue-front q) 0)))))

まず (emptyp q) でキューが空かチェックします。空でなければ、aref で FRONT の位置にあるデータを取り出します。prog1 を使っているので、aref で取り出したデータが dequeue の返り値になることに注意してください。あとは、COUNT と FRONT の値を更新し、FRONT の値がベクタの範囲を超えたら 0 に戻します。

●その他の操作関数

あとの関数 front, emptyp, fullp, clear は簡単なので説明は省略します。リストをお読みください。

リスト : キューの操作関数

;;; キューが空か
(defun emptyp (q) (zerop (queue-count q)))

;;; キューが満杯か
(defun fullp (q)
  (= (queue-count q) (queue-size q)))

;;; 先頭データの参照
(defun front (q)
  (unless (emptyp q)
    (aref (queue-buffer q) (queue-front q))))

;;; キューを空にする
(defun clear (q)
  (setf (queue-rear  q) 0
        (queue-front q) 0
        (queue-count q) 0))

●使用例

これでプログラムは完成です。それでは、簡単な使用例を示しましょう。

* (setq que (create-queue 8))

#S(QUEUE :FRONT 0 :REAR 0 :COUNT 0 :SIZE 8 :BUFFER #(0 0 0 0 0 0 0 0))
* (dotimes (x 8) (enqueue que x))

NIL
* que

#S(QUEUE :FRONT 0 :REAR 0 :COUNT 8 :SIZE 8 :BUFFER #(0 1 2 3 4 5 6 7))
* (enqueue que 100)

NIL
* (loop (if (emptyp que) (return)) (print (dequeue que)))

0
1
2
3
4
5
6
7
NIL
* que

#S(QUEUE :FRONT 0 :REAR 0 :COUNT 0 :SIZE 8 :BUFFER #(0 1 2 3 4 5 6 7))

create-queue でキューを作成して変数 QUE にセットします。dotimes でキューにデータを 8 個セットします。これでキューは満杯になるので、これ以上データを追加することはできません。次に、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかりますね。これでキューは空の状態になります。