述語は真 (true) か偽 (false) を返す関数です。Common Lisp の場合、偽は nil で表し、それ以外の値を真と判断します。述語の場合、条件を満たす場合はシンボル t を返します。シンボル t は真を表す代表選手なのです。
関数 equal は 2 つの引数が同じ値か調べます。簡単な例を示します。
(equal (+ 1 2 3) 6) => t
(equal (+ 2 3 4) 7) => nil
(equal 4 4.0) => nil ; 型が違うとダメ
(equal 'a 'a) => t
(equal 'a 'b) => nil
(equal '(a b c) '(a b c)) => t
(equal '(a b c) '(a b d)) => nil
関数 eq は、2 つの引数がまったく同じであるか調べます。これは、コンピュータのメモリ番地を調べます。同じシンボルであれば eq は t を返します。しかし、同じ値の数値でも eq は t を返さない場合があります。
(eq 'a 'a) => t
(eq 1d100 1d100) => nil
Lisp は数値アトムを生成する場合、同じ数値でも違うメモリ番地に実体を割り当てる場合があるからです。これはリストの場合も同様です。次の例を見てください。
(eq '(a b c) '(a b c)) => nil
あと、Common Lisp には eql と equalp が用意されています。eq, eql, equal, equalp の違いは次のようになります。
等しいと判定される範囲が eq < eql < equal < equalp と広がっていきます。
次は、数値を比較する述語をまとめて紹介しましょう。
これらの述語は、右側に書いた数式の関係を満たせば t を返し、そうでなければ nil を返します。引数は 2 つ以上与えてもかまいません。
equal は数値の型が違うと nil になりましたが、= を使うと引数の型を区別せずに数値が等しいか調べることができます。次の例を見てください。
(= 4 4) => t
(= 4 4.0) => t
(= 4 4.0 4 4.0) => t
(= 4 4.0 4.1) => nil
次は、データ型を調べる述語を紹介しましょう。
いずれの述語も引数をひとつ取り、引数が条件を満たせば t を、そうでなければ nil を返します。関数名が p で終わるのは、述語 (predicate) の頭文字に由来するそうです。atom は例外なので注意してください。
nil は偽を表すシンボルですが、空リストも表しています。それでは、listp と symbolp で nil を調べてみるとどうなるのでしょうか。
(listp nil) => t
(symbolp nil) => t
(atom nil) => t ; atom でも t を返す
(consp nil) => nil
listp の場合、nil は真を返すことに注意してください。consp を使うと nil は偽に判断されます。
Common Lisp にはデータ型を表現するために、型指定子と呼ばれるシンボルが用意されています。今まで紹介したデータと型指定子の関係を示します。
list と cons は、関数のほかにも型指定子としての役割も持っています。データ型によっては、もっと細かく分類することもできます。型指定子を使ってデータ型を調べる述語に typep があります。簡単な例を示しましょう。
(typep '(a b c) 'list) => t
(typep "abcdef" 'string) => t
(typep 100 'integer) => t
(typep 100 'float) => nil
(typep 'a 'symbol) => t
関数 type-of は引数のデータ型を型指定子で返します。次の例を見てください。
(type-of '(a b c)) => cons
(type-of "abcdef") => simple-string
(type-of 100) => integer
(type-of 1.23) => single-float
simple-string は普通の文字列を表す型指定子です。
複数の述語を組み合わせる場合はマクロ and と or を使います。
(and Ｓ式１ Ｓ式２ Ｓ式３ Ｓ式４ ..... )
(or Ｓ式１ Ｓ式２ Ｓ式３ Ｓ式４ ..... )
and は複数の述語を「〜かつ〜」で結ぶ働きをします。and は与えられた S 式を左から順番に評価します。そして、S 式の評価結果が nil であれば、残りの S 式を評価せずに nil を返します。ただし、最後まで S 式が nil に評価されなかった場合は、いちばん最後の S 式の評価結果を返します。
or は複数の述語を「〜または〜」で結ぶ働きをします。or は and と違い、S 式の評価結果が nil 以外の場合に、残りの S 式を評価せずにその評価結果を返します。すべての S 式が nil に評価された場合は nil を返します。それでは、簡単な例を示しましょう。
(defun check-number (x) (and (< 10 x) (<= x 20)))
(defun check-number-else (x) (or (>= 10 x) (> x 20)))
最初の例は、引数 x が 10 より大きくて、かつ 20 以下の場合 t を返します。次の例はその逆で、x が 10 以下、または 20 より大きい場合 t を返します。
check-number と check-number-else は逆の関係です。いちいち 2 つの関数を作らなくても結果を逆にすればいいはずです。この場合は not を使います。not は引数が nil ならば t を返し、それ以外ならば nil を返す関数です。つまり、真と偽をひっくり返す働きをします。これを否定といいます。ひらたくいえば、「〜ではない」という意味になります。次の例を見てください。
(check-number 15) => t
(not (check-number 15)) => nil
このように not を使うことで、述語の判定を逆にすることができます。
簡単な条件分岐は if を使います。if の構文を示しましょう。
(if <条件部> <then節> <else節>)
if は条件部を評価し、その結果が真ならば then 節を評価します。条件部が偽であれば else 節を評価します。else 節は省略することができます。その場合は、条件部で偽と判定されると nil を返します。これを図に示すと、次のようになります。
| 図 1 : 条件分岐 |
|---|
↓ ↓
┌─────┐No ┌─────┐No
│ 条 件 │─┐ │ 条 件 │─────┐
└─────┘ │ └─────┘ │
↓Yes │ ↓Yes ↓
┌─────┐ │ ┌─────┐ ┌─────┐
│ then節 │ │ │ then節 │ │ else節 │
└─────┘ │ └─────┘ └─────┘
│ │ │ │
├←───┘ ├←───────┘
↓ ↓
(1) (2)
|
(1) が else 節を省略した場合で、「もしも条件を満たすならば then 節を評価する」となります。(2) の場合では、「もしも条件を満たすならば then 節を評価し、そうでなければ else 節を評価する」となります。すなわち、条件によってどちらかの節が評価されることになります。簡単な使用例を示しましょう。
| List 1 : if の例 |
|---|
(defun even-or-odd (x)
(if (evenp x) ; 条件部
(print "偶数です") ; then 節
(print "奇数です"))) ; else 節
|
evenp は引数が偶数であれば t を返す述語です。逆に、奇数だと t を返す述語が oddp です。関数 even-or-odd は引数 x が奇数か偶数かを判断し、その結果を表示します。これは簡単ですので、すぐにわかると思います。
if の else 節が nil の場合には、if の代わりに when を使うことができます。逆に、if の then 節が nil の場合には unless を使うことができます。
(when test Ｓ式１ Ｓ式２ Ｓ式３ ..... )
when は最初に test を評価しその結果が nil であれば、その後ろの S 式を評価せずに nil を返します。そうでなければ、S 式を順番に評価し、最後の S 式の評価結果を返します。
unless は when とは逆の働きをします。述語が偽 (nil) に評価されたときに、引数の S 式を順番に評価します。unless は述語 not を使うと、次のように whenを使って表すことができます。
(unless test Ｓ式１ ...) ≡ (when (not test) Ｓ式１ ...)
if の場合、then 節や else 節はひとつの S 式しか受け付けませんが、when やunless では、複数の S 式を引数として受け取ることができます。
複雑な条件分岐には cond を使います。cond はちょっと奇妙な構文をもっています。
| 図 2 : cond の構造 |
|---|
(cond ( 条件部Ａ Ｓ式A1 Ｓ式A2 ... )
( 条件部Ｂ Ｓ式B1 Ｓ式B2 ... )
・・・・・
( 条件部Ｍ Ｓ式M1 Ｓ式M2 ... )
( t Ｓ式T1 Ｓ式T2 ... ))
|
cond は複数の節を引数として受け取ります。各節の先頭には条件をチェックする述語があり、条件が成立した場合、残りの S 式を評価します。条件が不成立であれば、次の節に移ります。たとえば、条件部 A が不成立であれば、次の節に移り条件部 B をチェックします。条件が成立したならば、同じ節にある S 式を順番に評価していきます。そして、いちばん最後に評価された S 式の返り値が cond の返り値となります。したがって、一度節が選択されたら、それ以降の節は評価されません。
もしも、どの条件部も不成立であれば、cond は nil を返します。ところで、上図ではいちばん最後の節で条件部が t になっていますね。t は真に評価されるので、この節は無条件に実行されることになります。つまり、条件部 A から条件部 M までのすべての条件が不成立でも、最後の節が必ず選択されるのです。cond を図に表すと次のようになります。
| 図 3 : cond の流れ図 |
|---|
↓
┌────┐Yes ┌────┐ ┌────┐
│条件部Ａ│─→│Ｓ式Ａ１│→・・・→│Ｓ式Ａ９│─→┐
└────┘ └────┘ └────┘ │
↓ No │
┌────┐Yes ┌────┐ ┌────┐ │
│条件部Ｂ│─→│Ｓ式Ｂ１│→・・・→│Ｓ式Ｂ９│─→┤
└────┘ └────┘ └────┘ │
↓ No │
・ │
↓ │
┌────┐Yes ┌────┐ ┌────┐ │
│条件部Ｍ│─→│Ｓ式Ｍ１│→・・・→│Ｓ式Ｍ９│─→┤
└────┘ └────┘ └────┘ │
↓ No │
┌────┐Yes ┌────┐ ┌────┐ │
│条件部 t│─→│Ｓ式Ｔ１│→・・・→│Ｓ式Ｔ９│─→┤
└────┘ └────┘ └────┘ │
│
↓
|
簡単な例を示しましょう。
| List 2 : cond の例 |
|---|
(defun data-type (x)
(cond
((integerp x) (print "整数です"))
((floatp x) (print "浮動小数点数です"))
((listp x) (print "リストです"))
((symbolp x) (print "シンボルです"))
((stringp x) (print "文字列です"))
(t (print "その他のデータです"))))
|
引数 x のデータ型を調べて表示します。今まで説明したデータであれば表示し、そうでなければその他のデータとして表示します。
昔の Lisp には繰り返しの関数が用意されていませんでした。ではどうやって繰り返しを実現していたかというと、再帰定義 (recursive definition) を使っていたのです。再帰定義とは、関数がその中で自分自身を呼び出すことをいいます。再帰呼び出し (recursive call) ともいいます。
Common Lisp の場合、便利な繰り返し関数が用意されているので、単純な繰り返しは再帰定義を使わなくても簡単にプログラムできます。だからといって、再帰定義が不用になったわけではなく、重要なテクニックであることに変わりはありません。
関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないか、と思われるかもしれません。M.Hiroi が最初に再帰定義を見たときは、ヘビが自分の尻尾を食べていくような奇妙な感覚に陥って、なかなか理解できませんでした。
ところが、再帰定義は特別なことではありません。ましてや Lisp の専売特許でもないのです。Ｃ言語や Perl など近代的なプログラミング言語であれば、再帰定義を使うことができるのです。 残念なことですが Lisp 以外のプログラミング言語では、再帰定義を難しいテクニックのひとつと思い込んでしまい、初心者の方は避けて通ることが多いように思います。
再帰呼び出しは、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに Lisp の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。
階乗の定義
0! = 1
x! = x * (x - 1)!
階乗の定義からわかるように、x の階乗を求めるには (x - 1) の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができるのです。
| List 3 : 再帰の例（その１） |
|---|
(defun fact (x)
(if (zerop x)
1
(* x (fact (1- x)))))
|
最後で fact 自身を再帰呼び出ししています。それでは、このプログラムの動作を説明します。次の図を見てください。
| 図 4 : 再帰呼び出し |
|---|
┌───── (fact 4) => 24 ─────┐ │ x = 4 │ │ (* 4 (fact 3)) │ │ │ │┌──── (fact 3) => 6 ────┐│ ││ x = 3 ││ ││ (* 3 (fact 2)) ││ ││ ││ ││┌─── (fact 2) => 2 ───┐││ │││ x = 2 │││ │││ (* 2 (fact 1)) │││ │││ │││ │││┌── (fact 1) => 1 ──┐│││ ││││ x = 1 ││││ ││││ (* 1 (fact 0)) ││││ ││││ ││││ ││││┌─ (fact 0) => 1 ─┐││││ │││││ x = 0 │││││ │││││ 1 │││││ ││││└──────────┘││││ │││└────────────┘│││ ││└──────────────┘││ │└────────────────┘│ └──────────────────┘ |
fact に 4 を与えて呼び出してみましょう。引数 x には 4 が代入されます。引数 x の値は (fact 4) が実行されている間だけ有効です。上図では、そのことを枠で示しています。この場合、x は 0 ではないので、else 節が実行されます。最初の枠の中を見てください。ここで x の値から 1 引いた値で自分自身を呼び出しています。
次に、2 番目の枠の中を見てください。引数 x には 3 が代入されます。関数を呼び出す場合、Lisp は引数用にメモリを割り当て、そこに実引数を書き込みます。再帰呼び出しであっても、普通の関数呼び出しには違いありません。したがって、(fact 3) を実行する場合も、引数 x に対応するメモリ領域を割り当て、そこに実引数である 3 を代入します。つまり、(fact 4) と (fact 3) の呼び出しでは、引数 x に割り当てられるメモリは異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると引数 x はひとつの領域しかないように見えますが、関数を呼び出すたびに、レキシカル変数は新しいメモリに割り当てられていくのです。したがって、(fact 4) を呼び出したときの x の値が更新されるのではありません。(fact 4) を実行しているときの x は 4 で、(fact 3) を実行しているときの x は 3 なのです。再帰呼び出しが行われるたびに、新しい x が作られると考えてください。
同様に (fact 2), (fact 1), (fact 0) と順番に呼び出していきます。(fact 0) の場合、x は 0 ですから then 節が実行されます。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
停止条件を作らなかったり、作ってもその条件を満たさないならプログラムは正常に動作しません。停止条件がなかったり条件を満たさない場合、関数呼び出しが限りなく行われるので、Lisp のシステム資源（メモリ）を食い潰し、いつかはプログラムを実行できなくなります。
(fact 0) は 1 を返します。関数を呼び出した場合、それを呼び出した関数に必ず戻ります。この場合は (fact 0) が終了したので、(fact 1) の実行に戻るのです。(fact 1) の実行は終了していないので、引数 x の値は 1 になります。図でいえば、実行が終了したら枠が壊れていくと考えてください。いちばん内側の枠が壊れて、その前に値を代入されたレキシカル変数が顔を出すのです。
(fact 0) が 1 を返してきたので、(fact 1) を計算することができます。(* 1 1) を評価して (fact 1) は 1 を返します。同様に、順番に値を計算していき、最後に (fact 4) の値を求めることができるのです。
次は、再帰定義を使ってリスト操作を行ってみましょう。リスト操作と再帰定義は相性が良いのです。まずは、リストの要素を数えるプログラムを作ります。Common Lisp には length という同等以上の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リスト nil であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト x の要素の個数を求めるには、リスト x に cdr を適用したリストの要素の個数がわかればいい、と考えるのです。それに 1 を足せば、要素の個数を求めることができます。これをプログラムすると、次のようになります。
| List 4 : リストの要素を数える |
|---|
(defun my-length (x)
(if (atom x)
0
(1+ (my-length (cdr x)))))
|
引数がアトムなら 0 を返します。そうでなければ、引数を cdr して my-length を再帰呼び出しします。リストに cdr を繰り返し適用していくと最後は空リスト nil になります。nil はアトムですから、ここで再帰呼び出しが止まって 0 を返します。そうすると、1+ によって my-length の返り値に 1 を足した値を返していきます。すなわち cdr した回数だけ 1 が足されるわけです。
次は関数 append を作ってみましょう。関数名は my-append とします。引数としてリスト x と y を渡して、それを結合したリストを返します。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト x が空リスト nil ならば、リスト y を返すだけでいいですね。次に、リスト x に要素が 1 つしかない場合を考えてみます。これは、リスト x に car を適用して要素を取り出し、それを cons でリスト y の先頭に追加すればいいでしょう。
それでは、リスト x に要素が複数ある場合を考えてください。リスト x に cdr を適用すれば空リストになりますから、この処理は再帰定義で実現することができます。つまり、リスト x とリスト y を結合するには、リスト x の cdr とリスト y を結合したリストに、リスト x の car を cons すればいいのです。これを図に示すと次のようになります。
| 図 5 : my-append の動作 |
|---|
┌────────────────────────────┐
│(my-append '(1 2) '(3 4)) │
├────────────────────────────┤
│ ( 1 2 ) │
│ ┬ ── cdr ─┐ │
│ car ↓ │
│ │ ┌──────────────────────┐│
│ │ │(my-append '(2) '(3 4)) ││
│ │ ├──────────────────────┤│
│ │ │ ( 2 ) ││
│ │ │ ┬ ─ cdr ─┐ ││
│ │ │ car ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │(my-append nil '(3 4)) => (3 4) │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ cons ←─┘ ││
│ │ │ (2 3 4) ││
│ │ └─────┼────────────────┘│
│ └──→ cons ←─┘ │
└──────┼─────────────────────┘
↓
(1 2 3 4)
|
これをプログラムすると次のようになります。
| List 5 : リストの結合 |
|---|
(defun my-append (x y)
(if (atom x)
y
(cons (car x) (my-append (cdr x) y))))
|
引数 x がアトムであればリスト y をそのまま返します。そうでなければ、リスト x に cdr を適用した値を my-append に渡して再帰呼び出しします。そして、その結果とリスト x の car を cons で接続すればいいのです。
今度は、もう少し複雑な操作を行ってみましょう。リストの要素を置き換える関数を作ってみます。Common Lisp には subst という関数が用意されていますが、再帰定義を使えば簡単に作ることができます。関数名は my-subst としました。簡単な使用例を示しましょう。
(my-subst 'a 'z '(a b a c d a)) => (z b z c d z)
(my-subst 'a 1 '(a b (a c) (d . a))) => (1 b (1 c) (d . 1))
最初の例は、シンボル a をシンボル z に置き換えます。次の例では、シンボル a を 1 に置き換えます。入れ子になったリストの中もデータを置き換えることに注意してください。プログラムは次のようになります。
| List 6 : リストの要素を置き換える |
|---|
(defun my-subst (old new tree)
(cond
((equal old tree) new)
((atom tree) tree)
(t (cons (my-subst old new (car tree))
(my-subst old new (cdr tree))))))
|
ポイントは、リストを car と cdr に分解して再帰呼び出しするところです。car と cdr で分解したリストは cons で合成できることを思い出してください。my-subst の評価値を cons で組み立てるわけです。これは、リストを操作する場合の常套手段ですので、ぜひ覚えておいてください。
あとは、再帰呼び出しの停止条件を定めるだけです。equal を使って old と等しいか判断し、そうであれば new を返します。そうでなければ atom を使って引数 tree がアトムか判断します。アトムであればこれ以上分解できませんので、tree をそのまま返します。そうでなければ car とcdr を使って分解し、my-subst を再帰呼び出しするわけです。
最後に、再帰定義の例題として有名なハノイの塔を取り上げます。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
| List 7 : ハノイの塔 |
|---|
(defun hanoi (n from to via)
(cond ((= n 1)
(format t "from ~A to ~A\n" from to))
(t
(hanoi (1- n) from via to)
(format t "from ~A to ~A\n" from to)
(hanoi (1- n) via to from))))
|
n は動かす円盤の枚数、from は移動元の棒、to は移動先の棒、via は残りの棒を示します。円盤の枚数が 1 枚の場合は簡単ですね。from にある円盤を to へ移すだけです。これが再帰の停止条件になります。format の ~A は与えられた引数を表示するための変換指定子です。この場合、最初の ~A が from の値を、次の ~A が to の値を表示します。
円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to に移します。これを format で表示します。そして、via に移した n - 1 枚の円盤を to に移します。この処理も hanoi を再帰呼び出しするだけです。これでプログラムは完成です。それでは実行してみましょう。
(hanoi 3 'A 'B 'C)
from A to B
from A to C
from B to C
from A to B
from C to A
from C to B
from A to B
nil