変数の有効範囲を表す用語にスコープ (scope) があります。この用語を使うと、Lisp 処理系はレキシカルスコープとダイナミックスコープの 2 つに分けることができます。伝統的な Lisp はダイナミックスコープですが、Common Lisp はレキシカルスコープを採用しています。
ちなみに、最初にレキシカルスコープを採用した Lisp 処理系が Scheme です。Emacs Lisp はダイナミックスコープですが、Common Lisp に準拠している xyzzy Lisp はレキシカルスコープです。ここではレキシカルスコープについて簡単に説明します。
それでは、レキシカル変数の規則をもう少し詳しく見てみましょう。変数 x を表示する関数 foo を定義します。
(defun foo () (print x))
(setq x 10)
(foo) => 10
foo には変数 x を定義していないので、foo を実行した場合スペシャル変数の値を探しにいきます。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 にはレキシカル変数 x を定義します。この場合、foo はどちらの値を表示するのでしょうか。実際に試してみましょう。
(defun foo1 () (let ((x 100)) (foo)))
(foo1) => 10
スペシャル変数の値を表示しました。このように、foo1 で定義したレキシカル変数 x は、foo からアクセスすることはできません。次の図を見てください。
| 図 1 : レキシカルスコープ |
|---|
┌────── Lisp system ───────┐ │ │ │ スペシャル変数 x ←────┐ │ │ │ │ │ ┌→┌─ 関数 foo ──────┐ │ │ │ │ │ ┌──────┼─┘ │ │ │ │ (print x) │ │ │ │ │ │ │ │ │ └────────────┘ │ │ │ ┌─ 関数 foo1 ─────┐ │ │ │ │ │ │ │ │ │ ┌─let : x ───┐ │ │ │ │ │ │ │ │ │ │ └─┼─┼─ (foo) │ │ │ │ │ └────────┘ │ │ │ └────────────┘ │ │ │ └────────────────────┘ |
上図では変数の有効範囲を枠で表しています。foo1 の let で定義したレキシカル変数 x は、let の枠の中でのみ有効です。枠は S 式に対応していて、この場合は (let ((x 100)) ..... ) が内側の枠になります。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠 (defun foo1 () ... ) に行き着きます。ここで変数が見つからない場合はスペシャル変数を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、スペシャル変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。これをレキシカルスコープ (lexical scope) といいます。レキシカルには文脈上いう意味があり、変数が定義されている S 式の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これをダイナミックスコープといいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在し、foo1 から呼ばれた関数ならば、どこからでもアクセスすることができます。
したがって、foo1 をダイナミックスコープの Lisp 処理系、たとえば Emacs Lisp で実行するならば、foo で表示される x の値は 100 になります。ダイナミックスコープについては、拙作のページ クロージャ をお読みください。
それでは、ラムダ式の場合はどうでしょうか。次の例を見てください。
| List 1 : リストの要素を n 倍する |
|---|
(defun times-element (n l) (mapcar #'(lambda (x) (* x n)) l)) |
ラムダ式の仮引数は x だけですから、変数 n はスペシャル変数をアクセスするように思われるかもしれません。ところが、変数 n は関数 times-element の引数 n をアクセスするのです。これを図に示すと、次のようになります。
| 図 2 : ラムダ式内の変数 |
|---|
┌────── Lisp system ──────┐ │ │ │ ┌─ times-element : n l ─┐ │ │ │ ↑ │ │ │ │ └─┐ │ │ │ │ ┌─ lambda : x ─┐│ │ │ │ │ │ ↑ ││ │ │ │ │ │ ┌──┘ ││ │ │ │ │ │ (* x n) ││ │ │ │ │ │ └───┼┘ │ │ │ │ └────────┘ │ │ │ └─────────────┘ │ │ │ └───────────────────┘ |
ポイントは、ラムダ式が関数 times-element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。ラムダ式はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義されたラムダ式は、そのとき有効なレキシカル変数にアクセスすることができるのです。
もうひとつ例題をあげましょう。指定した文字 code が先頭にある文字列を、リストから削除する関数を作ってみましょう。簡単な例を示します。
(remove-string #\a '("abc" "def" "agh" "ijk")) => ("def" "ijk")
リストに格納された文字列の中で、a から始まる文字列を削除します。この処理は、remove-if とラムダ式を使うと簡単に定義できます。
| List 2 : 先頭文字が code の文字列を削除 |
|---|
(defun remove-string (code string-list)
(remove-if
#'(lambda (x) (char= code (elt x 0)))
string-list))
|
関数 char= は文字型データどうしを比較して、等しいのであれば t を返し、そうでなければ nil を返します。ラムダ式内で remove-string の引数 code をアクセスできるので、このような定義が可能になるのです。この処理を再帰定義で書くと、次のようになります。
| List 3 : 先頭文字が code の文字列を削除（再帰版） |
|---|
(defun remove-string (code string-list)
(cond ((atom string-list) nil)
((char= code (elt (car string-list) 0))
(remove-string code (cdr string-list)))
(t (cons (car string-list)
(remove-string code (cdr string-list))))))
|
かなり複雑になりますね。ラムダ式と汎関数をうまく組み合わせると、複雑な処理でも簡単にプログラムを記述することができます。
ところで、#' は function 特殊形式の省略形で、function はシンボルに格納されている関数を取り出す働きをします。ところが、ラムダ式に function を適用すると、関数の機能を取り出すだけではなく、その時点で有効な局所変数とその値を保存したオブジェクトを返します。これをクロージャ (closure) といいます。
実をいうと、ラムダ式からほかのレキシカル変数にアクセスできるのは、このクロージャが働いているからなのです。詳しい説明は拙作のページ クロージャ をお読みくださいませ。
関数 remove-string はクロージャが絡むので、ちょっと難しかったかもしれません。Common Lisp らしくキーワード :key を使うと、もっと簡単にプログラムできます。
| List 4 : キーワード :key を使う場合 |
|---|
(defun remove-string (code string-list) (remove code string-list :key #'(lambda (x) (char x 0)))) |
文字列の先頭文字を取り出す関数をラムダ式で定義し、それを :key に設定します。あとは、remove がこのラムダ式を呼び出して、先頭文字と code を比較します。このプログラムだと、ラムダ式から code にアクセスする必要はありません。
Common Lisp では、マクロ defvar でスペシャル変数の使用を宣言することができます。
defvar symbol [initial-value [doc-string]]
defvar はシンボル symbol をスペシャル変数として宣言します。initial-value と doc-string は省略することができます。initial-value を指定すると、スペシャル変数の値は initial-value に初期化されます。
doc-string には変数の意味を説明する文字列を与えることができます。doc-string は symbol の属性リスト (xyzzy Lisp の場合は属性 lisp::variable-documentation) に格納されます。簡単な使用例を示しましょう。
(defvar *foo*) => *foo*
(defvar *foo1* 100) => *foo1*
*foo1* => 100
(defvar *foo1* 200) => *foo1*
*foo1* => 100
(defvar *foo2* 10 "テストです") => *foo2*
(symbol-plist '*foo2*)
=> (lisp::variable-documentation "テストです")
Common Lisp の場合、スペシャル変数は * で囲んで表す習慣があります。それから、スペシャル変数の値は defvar で書き換えることはできません。指定した symbol のスペシャル変数が値を持っていない場合にのみ、initial-value の値で初期化されます。ご注意ください。
また、defvar でスペシャル変数を宣言すると、その変数はダイナミックスコープで管理されます。次の例を見てください。
(defvar x 10) => x
(defun foo () (print x)) => foo
(foo) => 10 を表示
(defun foo1 () (let ((x 100)) (foo)))
=> foo1
(foo1) => 100 を表示
x => 10
defvar で変数 x をスペシャル変数として宣言します。関数 foo1 では、let で変数 x を定義しているので、x の値は 100 になります。通常のレキシカルスコープであれば、呼び出した関数 foo からこの値にアクセスすることはできません。
ところが、defvar で x をスペシャル変数として宣言すると、変数 x はダイナミックスコープで管理されるため、foo から foo1 で定義した変数 x にアクセスすることができるのです。このため、foo1 から foo を呼び出すと x の値は 100 になるのです。ダイナミックスコープの詳しい説明は、拙作のページ クロージャ をお読みください。
このように、defvar で宣言した変数はダイナミックスコープで管理されます。ただし、ダイナミックスコープには、プログラムを見ただけではどの変数にアクセスしているのかわからない、という欠点があることに注意してください。レキシカル変数とスペシャル変数は異なる名前にすることをおススメします。Common Lisp の習慣に従い、スペシャル変数は * で囲むとよいでしょう。
マクロ defconstant を使うと、スペシャル変数で定数を定義することができます。
defconstant symbol value
defconstant で定義した定数は、値を書き換えようとするとエラーになります。簡単な例を示します。
(defconstant *cc* 100) => *cc*
*cc* => 100
(setq *cc* 200) => エラー
今まで説明したリスト操作関数は、引数のリストを直接修正せずに新しいリストを生成して返しています。たとえば、append で (a b c) と (d e f) を連結する場合、最初の引数 (a b c) はそのままで、2 つのリストを連結した新しいリスト (a b c d e f) を作っています。つまり、(a b c) はコピーされているわけです。また、リストを修正する列関数 remove や substitute でも、引数のリストを修正せずに新しいリストが生成されます。
このように、リストを操作する関数の多くが新しいリストを生成して返しますが、プログラムによっては引数のリストを直接修正（破壊的修正）した方が便利な場合もあります。今回は Common Lisp に用意されているリストを破壊的に修正する関数を説明します。
さっそくプログラミング で説明したように、リストは複数のコンスセルを接続して構成されています。コンスセルにはデータを格納する CAR とコンスセルをつなぐ CDR という場所があります。Lisp にはコンスセルの CAR 部を直接書き換える関数 rplaca と、CDR 部を直接書き換える関数 rplacd が用意されています。
rplaca cell object
rplacd cell object
rplaca はコンスセル cell の CAR 部を object に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CAR 部を書き換えます。rplaca は書き換えた cell を返します。簡単な例を示しましょう。
(setq z '(a b c)) => (a b c)
(rplaca z d) => (d b c)
z => (d b c)
変数 z に (a b c) をセットします。rplaca はコンスセルの CAR 部、この場合は (a b c) の先頭セルの CAR 部を a から d に書き換えます。リストの CAR 部を直接書き換えるので、変数 z の値も (d b c) になることに注意してください。次の図を見てください。
| 図 3 : rplaca によるリストの破壊的修正 |
|---|
CAR 部を直接 d に書き換える
│
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ｄ ｂ ｃ
|
上図に示すように、変数 z はリスト (a b c) を格納しています。rplaca は変数 z が格納しているコンスセルの CAR 部を直接 d に書き換えるので、変数 z の値も (d b c) になるのです。このように、rplaca には副作用があるので使用には十分な注意が必要です。
rplacd はコンスセル cell の CDR 部を object に変更します。cell にリストが与えられた場合は、先頭のコンスセルの CDR 部を書き換えます。rplacd は書き換えた cell を返します。簡単な例を示しましょう。
(setq z '(a b c)) => (a b c)
(rplacd z 'd) => (a . d)
z => (a . d)
rplacd はコンスセルの CDR 部、この場合は (a b c) の先頭セルの CDR 部を d に書き換えます。次の図を見てください
| 図 4 : rplacd によるリストの破壊的修正 |
|---|
CDR 部を直接 d に書き換える
│
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・│ │・│・┼─→│・│／│
└┼┴┼┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
ａ ｄ ｂ ｃ
|
上図に示すように、CDR 部にはコンスセルがつながっていますが、それをシンボル d に書き換えるのですから後ろのコンスセルは切断されて、変数 z の値は (a . d) というドット対になります。rplacd にも副作用があることに注意してください。
rplaca と rplacd は初期の Lisp からある関数です。Common Lisp にも用意されていますが、実際に使うことはほとんどないでしょう。というのも、リストの破壊的修正は setf で行うことができるからです。(rplaca z 'd) は (setf (car z) 'd) または (setf (first z) 'd) と同じで、(rplacd z 'd) は (setf (cdr z) 'd) または (setf (rest z) 'd) と同じです。簡単な例を示しましょう。
(setq z '(a b c)) => (a b c)
(setf (car z) 'd) => d
z => (d b c)
(setf (cdr z) 'e) => e
z => (d . e)
このほかにも、setf は second, ... tenth, nth や列関数 elt などと組み合わせることで、リストの内容を直接書き換えることができます。次の図を見てください。
| 図 5 : setf によるリストの破壊的修正 |
|---|
(setf (first z) 'd)
│
│ (setf (second z) 'd)
│ │
│ │ (setf (third z) 'd)
↓ ↓ ↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
|
(first z) の代わりに (elt z 0) や (nth 0 z) を使うことができます。このように、書き換えるリストの位置をアクセス関数で指定するわけです。
リストを連結する関数に append がありますが、引数のリストは破壊されません。append の動作を図 (再掲) に示します。
| 図 6 : append の動作 |
|---|
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／│ ┌→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ │ └┼┴─┘ └┼┴─┘
↓ ↓ │ ↓ ↓
ａ ｂ │ ｃ ｄ
│ │ │
↓ ↓ │
┌┼┬─┐ ┌┼┬─┐ │
┌──│・│・┼─→│・│・┼─┘
│ └─┴─┘ └─┴─┘
│ 新しいセル 新しいセル
↓
append の返り値
(append '(a b) '(c d)) => (a b c d)
|
このように append は第 1 引数のリストをコピーしてから連結します。これに対し、引数のリストをコピーせずに連結する関数が nconc です。
nconc &rest lists
関数 nconc は引数のリストをつなぎあわせたリストを返します。最後を除く引数の内容が破壊されます。次の図を見てください。
| 図 7 : (nconc '(a b) '(c d)) の動作 |
|---|
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↑ ↓ ↓
ａ ｂ │ ｃ ｄ
│
CDR 部を直接書き換える
|
上図に示すように、nconc はリストの最終セルの CDR 部を直接書き換えることで、引数のリストを連結しています。簡単な例を示しましょう。
(setq x '(a b c)) => (a b c)
(setq y '(d e f)) => (d e f)
(nconc x y) => (a b c d e f)
x => (a b c d e f)
変数 x と y に格納されているリストを nconc で連結します。このとき、変数 x の値は書き換えられることに注意してください。
それでは簡単な例題として、リストを使ってキュー (queue) という基本的なデータ構造を実装してみましょう。
キューは待ち行列といわれるデータ構造です。たとえば、チケットを買う場合窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは先入れ先出し (FIFO : first-in, first-out) とも呼ばれます。
| 図 8 : キューの構造 |
|---|
先頭 最後尾
---------------------------
<= a b c d e . . . z <=
---------------------------
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
queue ─→│・│・┼─→│・│・┼─→│・│・┼・・・→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
ａ ｂ ｃ ｚ
|
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。
たとえば、データの追加に append を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると実行時間がかかるようになります。そこで、append の代わりに nconc を使うことを考えてみます。この場合、リストのコピーは回避できますが、最後尾のセルは先頭から順番にセルをたどっていかないと到達できないので、データが多くなるとやっぱり時間がかかってしまいます。
そこで、最後尾のセルを格納する変数を用意することにします。
| 図 9 : キューの構造（改良版） |
|---|
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│ａ│・┼─→│ｂ│・┼─→│ｃ│／│
└─┴─┘ └─┴─┘ └─┴─┘
↑
rear ─────────────────┘
|
上図に示すように、リストを保持する変数 front のほかに、最後尾のセルを格納する変数 rear を用意します。変数 front と rear は構造体にまとめておくといいでしょう。キューを操作するプログラムは次のようになります。
| List 5 : リストによるキューの実装 |
|---|
; キューの定義
(defstruct Queue (front nil) (rear nil))
; データを入れる
(defun enqueue (queue item)
(let ((new-cell (list item)))
(if (Queue-front queue)
; 最終セルを書き換える
(setf (cdr (Queue-rear queue)) new-cell)
; キューは空の状態
(setf (Queue-front queue) new-cell))
(setf (Queue-rear queue) new-cell)))
; データを取り出す
(defun dequeue (queue)
(if (Queue-front queue)
(prog1
(pop (Queue-front queue))
(unless (Queue-front queue)
; キューは空になった
(setf (Queue-rear queue) nil)))))
|
まず defstruct で構造体 Queue を定義します。front と rear は nil に初期化します。キューにデータがない状態（空の状態）は、front だけではなく rear の値も nil にします。ご注意ください。
キューにデータを入れる関数が enqueue です。最初に、item をセルに格納して new-cell にセットします。次に、キューにデータがある場合は、最後尾のセルの CDR 部を書き換えて new-cell を連結します。このとき、setf で (cdr (Queue-rear queue)) と指定すると、rear に格納されているセルの CDR 部を書き換えることができます。
キューにデータがない場合は front に new-cell をセットします。最後に new-cell を rear にセットして最後尾のセルを更新します。
キューからデータを取り出す関数が dequeue です。キューにデータがある場合は pop で先頭データを取り出します。prog1 により pop で取り出されたデータが dequeue の返り値となります。キューにデータがない場合は nil を返します。そして、キューが空になった場合は rear に nil をセットします。
これでプログラムは完成です。それでは実行してみましょう。
(setq *q* (make-Queue)) => #S(Queue front nil rear nil)
(dotimes (x 5) (enqueue *q* x)) ; キューにデータを追加
*q* => #S(Queue front (0 1 2 3 4) rear (4))
(dotimes (x 5) (print (dequeue *q*))) ; キューからデータを取り出す
0
1
2
3
4
nil
*q* => #S(Queue front nil rear nil) ; キューは空になる
きちんと動作していますね。ところで、キューはベクタを使っても実装することができます。詳しい説明は拙作のページ スタックとキュー をお読みくださいませ。
列を修正する関数 remove や substitute は、引数の列を修正せずに新しい列を生成します。このほかに、Common Lisp は引数の列を破壊的に修正する関数が用意されています。次の表を見てください。
| 関数名 | 機能 |
|---|---|
| nreverse sequence | 要素を逆順にした列を返す |
| replace seq1 seq2 | 列 seq1 を列 seq2 の要素に置き換える |
| delete item sequence | item と等しい要素を取り除く |
| delete-if predicate sequence | predicate が真となる要素を取り除く |
| delete-if-not predicate sequence | predicate が偽となる要素を取り除く |
| nsubstitute new old sequence | old と等しい要素を new に置き換える |
| nsubstitute-if new predicate sequence | predicate が真となる要素を new に置き換える |
| nsubstitute-if-not new predicate sequence | predicate が偽となる要素を new に置き換える |
関数 nreverse は引数を破壊します。リストを逆順にする場合、引数のコンスセルが再使用されますが、このときコンスセルの順番が元のままである保証はありません。次の例を見てください。
(setq a '(1 2 3 4 5)) => (1 2 3 4 5)
(nreverse a) => (5 4 3 2 1)
a => (1)
xyzzy Lisp で (nreverse a) を評価しても、変数 a の値は逆順になりません。このように Common Lisp の場合、(nreverse a) を評価しても変数 a の値が逆順になることは保証されていないのです。nreverse でリストを逆順にする場合は、(setq a (nreverse a)) のように返り値を変数に代入してください。
配列や文字列の場合は元の列の要素の順序を入れ替えます。次の例を見てください。
(setq b #(1 2 3 4 5)) => #(1 2 3 4 5)
(nreverse b) => #(5 4 3 2 1)
b => #(5 4 3 2 1)
(setq c "abcdefg") => "abcdefg"
(nreverse c) => "gfedcba"
c => "gfedcba"
このように、配列や文字列では変数の値も逆順になります。
関数 replace は列 seq1 を列 seq2 の要素に置き換えます。引数 seq1 は破壊的に修正されます。seq2 の要素は seq1 に格納できるようなデータ型でなければいけません。replace には、seq1 と seq2 の部分列を指定するキーワード :start1, :end1, :start2, :end2 があります。簡単な例を示しましょう。
(setq a '(1 2 3 4 5)) => (1 2 3 4 5)
(replace a '(10 20 30)) => (10 20 30 4 5)
a => (10 20 30 4 5)
(replace a '(a b c d e f)) => (a b c d e)
a => (a b c d e)
(setq b #(1 2 3 4 5)) => #(1 2 3 4 5)
(replace b '(30 40) :start1 2) => #(1 2 30 40 5)
b => #(1 2 30 40 5)
(setq c "abcdefg") => "abcdefg"
(replace c "ABCD" :start1 1 :start2 1) => "aBCDefg"
c => "aBCDefg"
関数 delete は remove とは違って引数を破壊的に修正します。簡単な例を示します。
(setq a '(1 2 3 4 5 6)) => (1 2 3 4 5 6)
(delete-if #'oddp a) => (2 4 6)
a => (2 4 6)
(delete-if #'evenp a) => nil 2002/06/01 追加
a => (2 4 6)
(setq b #(1 2 3 4 5 6)) => #(1 2 3 4 5 6)
(delete-if #'evenp b) => #(1 3 5)
b => #(1 3 5)
(setq c "abcabcabc") => "abcabcabc"
(delete #\a c) => "bcbcbc"
c => "bcbcbc"
2 番目の例を見てください。リストの要素がすべて削除される場合、delete は空リスト nil を返しますが、このとき変数 a の値は書き換えられていません。delete でリストの要素を削除する場合は、delete の返り値を変数に代入することをおススメします。
関数 nsubstitute は substitute とは違って引数を破壊的に修正します。簡単な例を示します。
(setq a '(1 2 3 4 5 6)) => (1 2 3 4 5 6)
(nsubstitute-if 0 #'evenp a) => (1 0 3 0 5 0)
a => (1 0 3 0 5 0)
(setq b #(1 2 3 4 5 6)) => #(1 2 3 4 5 6)
(nsubstitute-if 0 #'oddp b) => #(0 2 0 4 0 6)
b => #(0 2 0 4 0 6)
(setq c "abcabcabc") => "abcabcabc"
(nsubstitute #\A #\a c) => "AbcAbcAbc"
c => "AbcAbcAbc"
引数を破壊的に修正する関数を使う場合は、その副作用に十分注意してください。
リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを循環リスト (circular list) といいます。次の図を見てください。
| 図 10 : 循環リスト |
|---|
CDR 部を直接 CELL A に書き換える
└──────┐
CELL A ↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌───────────────┐
↓ │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│・│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
|
リスト (a b c) は nil で終端されています。このリストで、最後尾のセルの CDR 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。それでは、実際に循環リストを作ってみましょう。
(setq z '(a b c)) => (a b c)
(setf (cdr (cddr z)) z) => #1=(a b c . #1#)
z => #1=(a b c . #1#)
(dotimes (x 4)
(print (car z)) (setq z (cdr z)))
a
b
c
a
nil
(cddr z) で最後尾のセルを取り出して、setf で CDR 部を先頭のセルに書き換えます。xyzzy の *scratch* で評価すると、循環リストは #1=(a b c . #1#) と表示されます。循環リストに終わりはないので、最後の例のように cdr を 3 回適用すると先頭の要素 a が表示されます。
Common Lisp では、#n= により Lisp データにラベルを付けることができます。n には整数値を指定し、#n# でそのデータを参照することができます。#1=(a b c . #1#) の場合、#1= で先頭のセルにラベルがつけられ、最後尾のセルの CDR 部で先頭のセルを #1# で参照しています。これで循環リストを表すことができます。
また、#n= と #n# はプログラムで使うことができます。たとえば、(setq z '#1=(a b c . #1#)) とすれば、循環リストを生成して変数 z にセットすることができます。ほかの例も示しましょう。
(setq a '("abc" "abc")) => ("abc" "abc")
(setq b '(#1="abc" #1#)) => (#1="abc" #1#)
(eq (first a) (second a)) => nil
(eq (first b) (second b)) => t
Lisp の場合、リスト ("abc" "abc") の 2 つの文字列 "abc" は別々のデータとして生成されるのが普通です。したがって、2 つの文字列を eq で比較すると nil になります。ところが (#1="abc" #1#) とすると、最初の文字列にラベルが付けられて次の要素でその文字列を参照しているので、リストは同一の文字列データを格納することになります。よって、リストの第 1 要素と第 2 要素を eq で比較すると t になるのです。
それから、循環リストを print などで表示しようとすると、(a b c a b c a b c ... のように人が手動で中断しない限り止まらなくなります。この場合、スペシャル変数 *print-circle* の値を真にすると、print でも循環リストを表示することができます。ご注意くださいませ。
循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。
| List 6 : 循環リストのチェック |
|---|
(defun circular-list-p (l)
(let ((fast l) (slow l))
(loop
(setq fast (cddr fast)
slow (cdr slow))
(cond ((endp fast) (return))
((eq fast slow) (return t))))))
|
変数 fast が「うさぎ」で slow が「かめ」を表します。fast は cddr で、slow は cdr で進みます。fast が終端に到達すれば循環リストではありません。return で loop から脱出して nil を返します。「うさぎ」が「かめ」に追いつくと fast と slow の値は同じセルになるので、(eq fast slow) の評価結果は真になります。(return t) で loop から脱出して t を返します。
それでは実際に試してみましょう。
(circular-list-p '#1=(a b c . #1#)) => t
(circular-list-p '(a b c d)) => nil
(circular-list-p nil) => nil
正常に動作していますね。今回は簡単に繰り返しでプログラムを作りましたが、興味のある方は再帰定義でもプログラムを作ってみてください。