Common Lisp Programming

リスト操作の基本

●リストの分解

最初はリストの分解から始めましょう。関数 car はリストの先頭要素を取り出し、関数 cdr はリストの先頭要素を取り除いたリストを返します。なお、参考文献 1 では car と cdr ではなく、first と rest を使うことが推奨されています。ですが、M.Hiroi は古い人間のため car と cdr を好んで使っています。

car と cdr は関数ですので、リストには引用符を付けることを忘れないでください。また、リスト以外のデータを与えるとエラーとなります。

car と cdr はリストを分解します。上図に示すように、car は先頭のセルの CAR 部に格納されたデータを返します。cdr は CDR 部に格納されたデータ (後ろに接続されているセル) を返します。つまり、先頭要素を除いたリストを返すことになります。

要素が 1 つしかないリストに cdr を適用すれば、空リスト NIL を返します。また、car も cdr も引数に NIL が与えられると NIL を返します。

* (cdr '(a))

NIL
* (car nil)

NIL
* (cdr nil)

NIL

今度は要素がリストの場合を考えてみましょう。次の例を見てください。

* (car '((a b) (c d) (e f)))

(A B)
* (cdr '((a b) (c d) (e f)))

((C D) (E F))

リストの第 1 要素は (A B) であり、A ではないことに注意してください。A を取り出したい場合は次のようになります。

* (car (car '((a b) (c d) (e f))))

A

それでは、第 2 要素を取り出す場合はどうするのでしょう。car と cdr を組み合わせれば簡単に取り出すことができます。

(car (cdr '(a b c d e f)))
     ~~~~~~~~~~~~~~~~~~~~ が評価されると a が取り除かれる。
   ||
(car '(b c d e f))  取り除いた後のリストの第 1 要素を取り出す。
=> B

このように、car と cdr を組み合わせることで、リストのどの要素にもアクセスすることができるのです。また、car と cdr を組み合わせた関数 cxxr, cxxxr, cxxxxr も用意されています。x には a か d が入ります。次の例を見てください。

(cadr '(a b c d)) ≡ (car (cdr '(a b c d))) => B
(caddr '(a b c d)) ≡ (car (cdr (cdr '(a b c d)))) => C
(cadddr '(a b c d)) ≡ (car (cdr (cdr (cdr '(a b c d))))) => D

昔の Lisp では、リストの第 2 要素や第 3 要素を取り出すために cadr や caddr がよく使われました。これらの関数は Common Lisp にも用意されていますが、第 2 要素は関数 second で、第 3 要素は関数 third で取り出した方がわかりやすいでしょう。このほかに、第 4 要素を取り出す fourth から第 10 要素を取り出す tenth まで用意されています。

●リストの合成

次は、リストの合成です。関数 cons はリストの先頭にデータを付け加えます。cons は construct の略です。

簡単な実行例を示します。

* (cons 'a nil)

(A)
* (cons 'b (cons 'a nil))

(B A)
* (cons 'c (cons 'b (cons 'a nil)))

(C B A)
* (cons 'd (cons 'c (cons 'b (cons 'a nil))))

(D C B A)

car と cdr で分解したリストは cons で合成することができます。

この関係は、リストを操作する関数を作る場合の基本です。とても重要な関係なので、覚えておいてください。

関数 list は引数を要素とする新しいリストを返します。

上図のように、list は引数を新しいリストの要素として格納します。引数がリストの場合は、それが要素となります。リスト同士をつなぐのではないことに注意してください。

簡単な実行例を示します。

* (list)

NIL
* (list 'a)

(A)
* (list 'a 'b)

(A B)
* (list '(a b) '(c d) '(e f))

((A B) (C D) (E F))

これに対し、関数 append はリスト同士を連結します。したがって、引数はリストでなければいけません。アトムを与えるとエラーになります。

append はリストを接続する場合、新しいセルを作成して引数の要素を格納します。ただし、いちばん最後の引数は新しいセルを作成しません。要素自体には何もしないことに注意してください。

簡単な実行例を示します。

* (append '(a b c) '(d e f))

(A B C D E F)
* (append '((a b) (c d)) '(e f))

((A B) (C D) E F)
* (append '((a b) (c d)) '((e f)))

((A B) (C D) (E F))         ; (A B C D E F) ではないことに注意

このように、要素がリストの場合でも、そのリストの要素を取り出すことはせずに、引数の要素を並べるだけです。

●リストの操作は非破壊的

今まで紹介した関数はシンボルの値を変更しません。次の例を見てください。

* (setq var '(a b c d e))

(A B C D E)
* (cdr var)

(B C D E)
* var

(A B C D E)

シンボル var の値は破壊されません。var の値を変更したいときは setq や setf を使います。

* (setq var (cdr var))

(B C D E)
* var

(B C D E)

以上のように、シンボル var の値は更新されます。

●ドットリスト

ここで、もう一度 cdr に戻ります。cdr は先頭の要素を取り除いたリストを返しましたが、それはセルの CDR 部を返す働きと同じです。最初に、最終セルの CDR にはリストの終わりを示すデータが格納されることを説明しました。したがって、要素がひとつしかないリストに cdr を適用すると、リストの終端を表すデータが取り出されます。もうおわかりだと思いますが、この特別なデータが NIL なのです。

今までのリストは、すべて終端に NIL がセットされています。ところが、Lisp の立場になって考えてみると、リストの終端は CDR 部に格納されるデータがセル以外であれば、そこがリストの終端であることがわかります。つまり、NIL でなくてもかまわないのです。リストの終端が NIL 以外のデータである場合、そのリストを次のように表します。

左右の括弧の中間にドット ( . ) を置き、左側に CAR 部のデータを、右側に CDR 部のデータを書きます。つまり、リスト (A) は (A . NIL) と表すことができます。このようなデータを「ドット対 (dotted pair)」と呼びます。たとえば、CAR 部がシンボル a で CDR 部がシンボル b であれば (a . b) となります。普通のリストも次のようにドット対を使って表現できます。

(A)           ≡ (A . NIL)
(A B C)       ≡ (A . (B . (C . NIL)))
((A B) (C D)) ≡ ((A . (B . NIL)) . ((C . (D . NIL)) . NIL))
((A B) C D)   ≡ ((A . (B . NIL)) . (C . (D . NIL)))

それでは、リスト (A B C) の終端を D に変えてみましょう。ドット対を使った表記法では、(A . (B . (C . D))) となりますが、これは (A B C . D) と表すことができます。

このように、NIL 以外のアトムで終端されたリストを「ドットリスト (dotted list)」と呼びます。参考文献 3 によると、カッコ ( ) の中間にドットを置いてリストを表すことを「ドット表現」といい、ドットを使わずにリストを表すことを「リスト表現」というそうです。そして、リスト表現とドット表現を混在させた表記法を「改良リスト表現」といい、多くの Lisp 処理系がこの表記法を用いています。

ドットの後ろは CDR 部にセットするデータを指定するのですから、複数のデータを書いたり省略してはいけません。次の場合はエラーになります。

( . A)       ; CAR がない
(A . )       ; CDR がない
(A . B C)    ; CDR にデータが複数ある
(A . . B)    ; ドットが複数ある
(A . B . C )

●問題

• cons と list で次に示すリストを作ってください
• xs : (a (b) ((c)) (((d))))
• ys : ((a b c) (d e f) (g h i))
• zs : ((a . b) (c . d) (e . f))
• 上記リストで各要素を取り出す S 式を作ってください

●解答

* (setq xs (list 'a (list 'b) 'c (list (list 'd)) 'e (list (list (list 'f)))))

(A (B) C ((D)) E (((F))))
* (setq ys (list (list 'a 'b 'c) (list 'd 'e 'f) (list 'g 'h 'i)))

((A B C) (D E F) (G H I))
* (setq zs (list (cons 'a 'b) (cons 'c 'd) (cons 'e 'f)))

((A . B) (C . D) (E . F))
* (car xs)

A
* (caadr xs)

B
* (caddr xs)

C
* (caar (fourth xs))

D
* (fifth xs)

E
* (caaar (sixth xs))

F
* (first (first ys))

A
* (second (second ys))

E
* (third (third ys))

I
* (caar zs)

A
* (cdar zs)

B
* (caadr zs)

C
* (cdadr zs)

D
* (caaddr zs)

E
* (cdaddr zs)

F

数と算術演算

Common Lisp では、いくつかの種類の数が定義されています。大きく分けると整数 (integer)、分数 (ratio)、浮動小数点数 (floating-point number)、複素数 (complex number) という 4 種類の数があります。

●整数

Common Lisp の場合、整数の大きさには制限がありません。5000! や 10000! でも求めることができます。ただし、処理系の内部では整数を fixnum と bignum (多倍長整数) に分けています。その処理系で効率良く整数を表せる範囲が fixnum で、それ以外の整数が bignum となります。fixnum の範囲は処理系に依存しますが、その値は変数 most-negative-fixnum と most-positive-fixnum に格納されています。

* most-negative-fixnum

-4611686018427387904
* most-positive-fixnum

4611686018427387903

このように、sbcl の fixnum は 63 bit で表されています。

整数は通常 10 進表記ですが、それ以外の基数でも書くことができます。

#nnrddddd または #nnRddddd

nn が基数 (2 - 32) を表します。よく使われる基数には省略形が用意されています。

• 2 進表記
  #b の後ろに 0 と 1 の数値を記述
• 8 進表記
  #o の後ろに 0 から 7 までの数値を記述
• 16 進表記
  #x の後ろに 0 から f までの数値を記述

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

#4r1230123 => 6939
#b10101010 => 170
#o1234567  => 342391
#o-127     => -87
#xabcdef   => 11259375

●分数

Common Lisp は分数を扱うことができます。分数は 2 つの整数を / で区切って表します。簡単な例を示します。

1/2, 2/3, 4/3, 11/13, -51/100, 30517578125/32768

また、4/6 や 3/12 のような入力もできますが、この場合は約分されることになります。とくに、4/2 のような割り切れる分数は、ただちに整数に変換されます。次の例を見てください。

4/6  => 2/3
3/12 => 1/4
10/5 => 2    ; 整数に変換される

●浮動小数点数

Common Lisp は浮動小数点数を扱うことができます。浮動小数点数は一種類だけではなく、処理系によって複数の種類を持つことができますが、その精度と大きさは処理系に依存します。Common Lisp で推奨されている浮動小数点数の種類を表 1 に示します。

浮動小数点の表記法は次のようになります。

[+|-] 数字 小数点 数字 指数マーカ [+|-] 数字

 0.1234                   ; single-float
 0.1234d0                 ; double-float
 1.2345e10                ; single-float
-9.876542999999999d-100   ; double-float

各精度の上限値と下限値は次の定数に格納されています。

most-positive-xxxx             ; 正の無限大に最も近い値
least-positive-xxxx            ; 0 に最も近い正の値
least-positive-normalized-xxxx ; 同上 (正規化)
least-negative-xxxx            ; 0 に最も近い負の値
least-negative-normalized-xxxx ; 同上 (正規化)
most-segative-xxxx             ; 負の無限大に最も近い値
                               ; xxxx は データ型名を表す

SBCL での most-positive-xxxx の値を示します。

* most-positive-short-float

3.4028235e38
* most-positive-single-float

3.4028235e38
* most-positive-double-float

1.7976931348623157d308
* most-positive-long-float

1.7976931348623157d308

Common Lisp の仕様では、これら 4 つの形式をすべてサポートしなければならないわけではなく、処理系によっては 4 つより少なくてもかまいません。SBCL の場合、short-float と single-float が同じ形式、double-float と long-float が同じ形式になります。ようするに、Ｃ/Ｃ++ の float (単精度浮動小数点型) に相当するのが short-float, single-float で、double (倍精度浮動小数点型) に相当するのが double-float, long-float になります。

なお、指数マーカには e, E を使うことができます。この場合、浮動小数点数は変数 *read-default-float-format* に格納されている形式に変換されます。また、指数マーカを省略した場合も同様です。デフォルトは single-float です。

●複素数

Common Lisp は複素数を扱うことができます。複素数は #C の後ろに実部と虚部のリストを付けて表します。簡単な例を示しましょう。

#C(5 -3)
#C(1.2 2.4)
#C(1/2 2/3)
#C(0.5 2/3) => #C(0.5 0.6666667)

実部と虚部の指定には、整数、浮動小数点数、分数を使うことができます。もし、実部と虚部が異なる種類（型）の数ならば、同じ種類の数になるよう変換されます。

●四則演算

ここでは簡単な四則演算を説明します。

+ は足し算を、* は掛け算を、- は引き算を行います。これらの関数は引数をいくつでも取ることができます。数以外のデータを引数に与えるとエラーになります。引数の型が異なる場合は強制的に型変換が行われます。簡単な例を示しましょう。

(+)           => 0
(+ 1)         => 1
(+ 1 2 3)     => 6
(+ 1 2 3 1/2) => 13/2
(+ 1 2 3 4.5) => 10.5

(*)           => 1
(* 1)         => 1
(* 1 2 3)     => 6
(* 1 2 3 1/4) => 3/2
(* 1 2 3 4.5) => 27.0

(- 1)         => -1
(- 10 5 4)    => 1
(- 10 5/2)    => 15/2
(- 10 4.5)    => 5.5
(-)           => エラー  ; 引数が足りない

関数 1+ は引数に 1 を加え、関数 1- は引数から 1 を引きます。

(1+ 2)   => 3
(1+ 2.5) => 3.5
(1- 2)   => 1
(1- 2.5) => 1.5

incf と decf は次の S 式と同じ働きをします。

(incf a)   ≡ (setf a (1+ a))
(incf a n) ≡ (setf a (+ a n))
(decf a)   ≡ (setf a (1- a))
(decf a n) ≡ (setf a (- a n))

incf は第 2 引数が省略されると、第 1 引数のシンボルに格納されている数値に 1 を加えます。第 2 引数が与えられると、その値を加えます。incf は足し算した結果を返します。decf は incf とは逆に引き算を行います。

関数 / は割り算を行います。整数同士の割り算で割り切れない場合は分数になります。引数が 0 の場合はエラーになります。

(/ 2)     => 1/2    ; 引数の逆数を求める
(/ 8 4 2) => 1      ; 約分されて整数になる
(/)       => エラー

●数の変換

整数や分数を浮動小数点数に変換するには関数 float を使います。

float number [other]

float は number を other と同じ形式の浮動小数点数に変換します。other は浮動小数点数でなければならず、省略すると single-float に変換されます。

(float 1/3)     => 0.3333333
(float 1/3 1d0) => 0.3333333333333333d0
(float 3)       => 3.0
(float 3 1d0)   => 3.0d0

逆に、分数や浮動小数点数を整数に変換するには、次に示す関数を使います。

• floor num1 [num2]
  i ≦ num1 ＜ i + 1 を満たす整数 i を求める。
• ceiling num1 [num2]
  i - 1 ＜ num1 ≦ i を満たす整数 i を求める。
• truncate num1 [num2]
  小数点以下を切り捨てる。
• round num1 [num2]
  近い方の整数に丸める。ちょうど 0.5 の場合には偶数方向に丸める。

引数 num2 が与えられた場合は (/ num1 num2) を評価し、その結果を整数に変換します。

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

* (floor 2.5)

2
0.5
* (floor -2.5)

-3
0.5
* (floor 5 2)

2
1

これらの関数は 2 つの値を返します。これを「多値 (multiple values)」といいます。最初の値は今までの関数と同じように受け取ることができます。2 番目の値を受け取る方法は、多値の使い方と一緒にあとで詳しく説明します。

2 番目の値は、引数 (数値) が 1 つの場合は "数値 - 求めた整数" です。引数が 2 つ (数値と除数) の場合は "数値 - 求めた整数 * 除数"、つまり剰余になります。

●剰余と累乗

剰余は関数 mod と rem で求めることができます。

mod number divisor
rem number divisor

mod は (floor number divisor) を実行し、その 2 番目の値を返します。rem は (truncate number divisor) を実行し、その 2 番目の値を返します。

簡単な例を示しましょう

* (mod 5 2)

1
* (rem 5 2)

1
* (floor 5 2)

2
1
* (truncate 5 2)

2
1
* (mod -5 2)

1
* (rem -5 2)

-1
* (floor -5 2)

-3
1
* (truncate -5 2)

-2
-1

関数 expt は累乗を計算します。

expt x y

(expt x y) は x^y を返します。x が整数または分数で y が整数ならば、正確な値 (整数または分数) が返されます。そうでなければ浮動小数点数による近似値が返されます。

(expt 2 32)     => 4294967296
(expt 2 64)     => 18446744073709551616
(expt 1/2 16)   => 1/65536
(expt 1/2 32)   => 1/4294967296
(expt 0.5d0 32) => 2.3283064365386963d-10
(expt 2 0.5d0)  => 1.4142135623730951d0

●その他

関数 gcd はすべての引数の最大公約数を返します。関数 lcm はその引数の最小公倍数を返します。どちらの関数も引数は整数でなければいけません。

(gcd 91 49)     => 7
(gcd 63 42 35)  => 7
(lcm 14 35)     => 70
(lcm 1 2 3 4 5) => 60

関数 exp x は e^x を求めます。e は自然対数の底です。関数 log x [b] は log_b x を求めます。b を省略すると e になります。関数 sqrt x は√x を求めます。

* (exp 1d0)

2.718281828459045d0
* (log 10d0)

2.302585092994046d0
* (log 10d0 10)

1.0d0
* (log 10d0 2)

3.3219280948873626d0
* (sqrt 2d0)

1.4142135623730951d0

このほかにも、Common Lisp にはたくさんの数学関数が用意されています。興味のある方は調べてみてください。

●問題

次に示す数式を Lisp で計算してください。

1. \( 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 \)
2. \( \dfrac{n(n + 1)}{2} \)
   変数 n に適当な正整数をセットすること
3. \( \dfrac{-b\pm\sqrt{b^2-4ac}}{2a} \)
   変数 a, b. c には適当な値をセットすること
4. \(d = \dfrac{1 + \sqrt 5}{2}, e = \dfrac{1 - \sqrt 5}{2} \)
5. \( \dfrac{d^{n+1} - e^{n+1}}{\sqrt 5} \)
   変数 n には適当な正整数をセットすること
6. \( 1 + 2 + 2^2 + 2^3 + \cdots + 2^{80} = 2^{81} - 1\)
7. \(7^{654321}\) の末尾の数字

●解答

* (+ 1 2 3 -4 5 6 78 9)    ; -4 は (- 4) としてもよい

100
* (+ (+ (+ (+ (- (+ (+ 1 2) 3) 4) 5) 6) 78) 9)

100
* (setq n 10)

10
* (/ (* n (+ n 1)) 2)

55
* (setq n 100)

100
* (/ (* n (+ n 1)) 2)

5050
* (setq a 2 b -4 c -6)

-6
* (/ (+ (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))

3.0
* (/ (- (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))

-1.0
* (setq a 1 b 0 c 1)

1
* (/ (+ (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))

#C(0.0 1.0)
* (/ (- (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))

#C(0.0 -1.0)
* (setq d (/ (+ 1 (sqrt 5)) 2))

1.618034
* (setq e (/ (- 1 (sqrt 5)) 2))

-0.618034
* (setq n 10)

10
* (/ (- (expt d (1+ n)) (expt e (1+ n))) (sqrt 5))

89.00001
* (setq n 20)

20
* (/ (- (expt d (1+ n)) (expt e (1+ n))) (sqrt 5))

10946.002
* (setq d (/ (+ 1 (sqrt 5d0)) 2))

1.618033988749895d0
* (setq e (/ (- 1 (sqrt 5d0)) 2))

-0.6180339887498949d0
* (setq n 10)

10
* (/ (- (expt d (1+ n)) (expt e (1+ n))) (sqrt 5))

88.99999869328373d0
* (setq n 20)

20
* (/ (- (expt d (1+ n)) (expt e (1+ n))) (sqrt 5))

10945.999839288585d0
* (1- (expt 2 81))

2417851639229258349412351
* (mod (expt 7 654321) 10)

7