Common Lisp には簡単で便利な繰り返し機能がいくつか用意されています。まず最初に、指定した回数だけ処理を繰り返す dotimes から説明しましょう。
dotimes はマクロで、構文は次のようになります。
(dotimes (var limit result) Ｓ式 ...)
dotimes は limit で指定した回数だけ、与えられた S 式を繰り返し評価します。dotimes は最初に limit を評価します。このとき、その評価結果は 0 以上の整数値でなければいけません。評価結果を n とすると、0 から n - 1 までの整数が順番に変数 var に代入され、そのあとの S 式を評価します。
var はレキシカル変数として扱われ、dotimes が評価されている間だけ有効です。最後に result が評価され、その値が dotimes の返り値となります。result が省略された場合は NIL を返します。次の例を見てください。
* (dotimes (x 5) (print x)) 0 1 2 3 4 NIL
この処理はレキシカル変数 X の値を print で表示するだけですが、繰り返すたびに X の値が 1 つずつ増えていくことがわかります。最後の NIL は dotimes の返り値です。これを図に表すと次のようになります。
↓
┌─────┐
│ x ← 0 │
└─────┘
├←────┐
↓ │
No ┌─────┐ │
┌───│ x < 10 │ │
│ └─────┘ │
│ ↓Yes │
│ ┌─────┐ │
│ │(print x) │ │
│ └─────┘ │
│ ↓ │
│ ┌─────┐ │
│ │x ← x + 1│ │
│ └─────┘ │
│ └─────┘
└──────┐
↓
図 : dotimes の処理
それでは簡単な例を見てみましょう。階乗の計算を dotimes でプログラムします。
リスト : dotimes の使用例
(defun fact (x)
(let ((result 1))
(dotimes (n x result)
(setq result (* result (1+ n))))))
let で変数 RESULT を定義し、その値を 1 に初期化します。次に、dotimes で 1 から X まで RESULT と乗算することで階乗を計算します。ただし、dotimes は 0 から始まるので、1+ で N の値に 1 を加えていることに注意してください。関数 * を評価しただけでは RESULT の値は変わらないので、setq を使って乗算の結果を RESULT に代入します。
もちろん、FizzBuzz 問題も dotimes で簡単に解くことができます。
* (dotimes (x 100) (format t "~A " (fizzbuzz (1+ x)))) 1 2 FIZZ 4 BUZZ FIZZ 7 8 FIZZ BUZZ 11 FIZZ 13 14 FIZZBUZZ 16 17 FIZZ 19 BUZZ FIZZ 22 23 FIZZ BUZZ 26 FIZZ 28 29 FIZZBUZZ 31 32 FIZZ 34 BUZZ FIZZ 37 38 FIZZ BUZZ 41 FIZZ 43 44 FIZZBUZZ 46 47 FIZZ 49 BUZZ FIZZ 52 53 FIZZ BUZZ 56 FIZZ 58 59 FIZZBUZZ 61 62 FIZZ 64 BUZZ FIZZ 67 68 FIZZ BUZZ 71 FIZZ 73 74 FIZZBUZZ 76 77 FIZZ 79 BUZZ FIZZ 82 83 FIZZ BUZZ 86 FIZZ 88 89 FIZZBUZZ 91 92 FIZZ 94 BUZZ FIZZ 97 98 FIZZ BUZZ NIL
format の ~A は S 式を印字する変換指定子です。
次は dolist を説明しましょう。dolist もマクロで、構文も dotimes とたいへんよく似ています。
(dolist (var init-form result) Ｓ式 ... )
dolist は名前が示すように、リストに関係があります。最初に init-form を評価します。このとき、評価結果はリストでなければいけません。リスト以外の場合はエラーとなります。dolist は、このリストの要素を順番に変数 var に代入して S 式を評価します。リストの要素がなくなったら result を評価し、その値が dolist の返り値になります。次の例を見てください。
(dolist (x '(0 1 2 3 4)) (print x)) 0 1 2 3 4 NIL
この処理はレキシカル変数 X の値を print で表示するだけですが、繰り返しのたびにリストの要素が X に代入されていることがわかります。最後の NIL は dolist の返り値です。これを図に表すと次のようになります。
↓
├←────┐
No ┌─────┐ │
┌───│要素がある│ │
│ └─────┘ │
│ ↓Yes │
│ ┌───────┐ │
│ │ x ← 次の要素│ │
│ └───────┘ │
│ ↓ │
│ ┌─────┐ │
│ │(print x) │ │
│ └─────┘ │
│ └─────┘
└──────┐
↓
図 : dolist の処理
dolist の簡単な例として、リスト YS の中から X と等しい要素を数える関数 my-count x ys を作りましょう。Common Lisp には関数 count があるので、名前を my-count としました。
リスト : X と等しい要素の個数を求める
(defun my-count (x ys)
(let ((c 0))
(dolist (y ys c)
(if (eql x y) (incf c)))))
最初に変数 C を 0 で初期化しておきます。dolist はリスト YS の要素を順番に取り出して変数 Y にセットします。あとは述語 eql で X と Y が等しいかチェックして、そうであれば incf で C の値を + 1 します。これで X と等しい要素の個数を数えることができます。
それでは実際に試してみましょう。
* (my-count 'a '(a a b a b c a b c d)) 4 * (my-count 'b '(a a b a b c a b c d)) 3 * (my-count 'c '(a a b a b c a b c d)) 2 * (my-count 'd '(a a b a b c a b c d)) 1 * (my-count 'e '(a a b a b c a b c d)) 0
次は loop を説明しましょう。loop はマクロですが、単純なループと拡張されたループ機能の二種類があります。Common Lisp で loop マクロというと、後者の拡張版のほうが有名ですが、ここでは単純版のほうを説明します。拡張版は高機能なので、回を改めて説明する予定です。
loop は最も単純な繰り返しです。与えられた S 式をずっと繰り返し評価します。ようするに「無限ループ」になります。したがって、繰り返しを止めるなんらかの方法が必要です。これには return を使います。
return はマクロで、引数をひとつ与えることができます。繰り返しの中で return が評価されると、繰り返しはそこで中断されます。そして、与えられた引数を評価し、その評価結果が繰り返しの返り値となります。引数が省略された場合は NIL が返り値となります。次の図に示すように、return は条件分岐と組み合わせて使います。
↓
├←─────┐
┌──────if───────┐ │
│ Yes ┌─────┐│ │
│ ┌───│ 条件部 ││ │
│ │ └─────┘│ │
│ ↓ ↓No │ │
│┌─────┐┌─────┐│ │
││ return ││ else節 ││ │
│└─────┘└─────┘│ │
│ ↓ │ │
└───┼──────────┘ │
│ ↓ │
│ ┌─────┐ │
│ │ Ｓ 式 │ │
│ └─────┘ │
│ └──────┘
└──────┐
↓
loop より脱出
図 : loop による繰り返しの処理
ほかのプログラミング言語、たとえばＣ言語や Python では、return は関数の返り値を返すために使用されます。ところが、Lisp の場合はループから抜け出すために return を使います。Ｃ言語や Python を使ったことがある方は、この違いに注意してください。
それでは、loop と return を使って階乗の計算を定義してみましょう。
リスト : loop と return の例
(defun fact (x)
(let ((result 1) (i 2))
(loop
(if (> i x) (return result)) ; loop から脱出
(setq result (* result i)
i (1+ i)))))
変数 I が X より大きくなったら、return でループから脱出します。このとき、return の引数 RESULT が評価されて、階乗の計算結果が loop の返り値となり、それが関数 fact の返り値となります。ところで、setq は複数の変数の値を更新することができます。たとえば、(setq a 1 b 2) は (setq a 1) と (setq b 2) を順番に実行したことと同じになります。
return は今まで紹介した dotimes と dolist、次に説明する do からも脱出することができます。いずれの場合も return の評価結果が繰り返しの返り値となります。
最後に、より柔軟性のある繰り返しを提供する do を説明します。do の構文は少々複雑です。
(do ((var [init-form [step-form]]) ...) (end-test [result]) Ｓ式 ... )
変数 var はレキシカル変数として扱われます。do の処理を図に表すと次のようになります。
↓
┌────────┐
│var ← init-form│
└────────┘
┌──────→┤
│ ↓
│ ┌────────┐ 真 ┌────────┐
│ │ end-test を評価│─→│resultを評価する│
│ └────────┘ └────────┘
│ ↓偽
│ ┌───────┐
│ │Ｓ式を評価する│
│ └───────┘
│ ↓
│ ┌────────┐
│ │var ← step-form│
│ └────────┘
└───────┘
図 : do の処理
do はＣ言語や Perl の for 文とよく似ています (実際は FORTRAN の do ループの影響を受けたと思われます)。ただし、Ｃ言語や Perl では、end-test が真の間は繰り返しを続けるのですが、Lisp の do は end-test が真になると繰り返しを終了します。繰り返しを続ける条件が逆になっているので注意して下さい。
それでは簡単な使用例を示しましょう。
リスト : do の使用例
(defun fact (x)
(do ((n 2 (1+ n)) (result 1)) ; 変数の定義
((< x n) result) ; end-test と result
(setq result (* result n)))) ; 繰り返す S 式
do を使って階乗を計算します。N と RESULT がレキシカル変数です。変数 N は 2 に初期化されます。そして、繰り返すたびに step-form の (1+ n) が評価され、N の値がひとつ増加します。RESULT は 1 に初期化されますが、step-form は省略されています。(< x n) が終了条件で、result の評価結果が do の返り値になります。
それでは簡単な例題として、配列に格納されているデータの平均値を求めてみましょう。次のリストを見てください。
リスト : 平均値を求める
(defvar *height*
'(148.7 149.5 133.7 157.9 154.2 147.8 154.6 159.1 148.2 153.1
138.2 138.7 143.5 153.2 150.2 157.3 145.1 157.2 152.3 148.3
152.0 146.0 151.5 139.4 158.8 147.6 144.0 145.8 155.4 155.5
153.6 138.5 147.1 149.6 160.9 148.9 157.5 155.1 138.9 153.0
153.9 150.9 144.4 160.3 153.4 163.0 150.9 153.3 146.6 153.3
152.3 153.3 142.8 149.0 149.4 156.5 141.7 146.2 151.0 156.5
150.8 141.0 149.0 163.2 144.1 147.1 167.9 155.3 142.9 148.7
164.8 154.1 150.4 154.2 161.4 155.0 146.8 154.2 152.7 149.7
151.5 154.5 156.8 150.3 143.2 149.5 145.6 140.4 136.5 146.9
158.9 144.4 148.1 155.5 152.4 153.3 142.3 155.3 153.1 152.3))
(defun mean (xs)
(let ((s 0) (c 0))
(dolist (x xs (/ s c))
(incf s x)
(incf c))))
リスト *height* には生徒 100 人の身長が格納されています。defvar は初期値を指定することができます。ただし、値をセットできるのは変数が未束縛 (unbound) のときだけです。defvar で値を書き換えることはできません。ご注意くださいませ。
平均値を求めるには、これらのデータの合計値 [*1] を求めて、それを人数で割り算すればいいですね。プログラムは簡単です。変数 S にデータの合計値を、変数 C に人数を求めます。S と C は 0 に初期化しておきます。あとは dolist で XS の要素を順番に取り出して S に加算し、C の値を +1 していきます。最後に S / C を計算すれば平均値を求めることができます。
それでは実行してみましょう。
* (mean *height*) 150.627
次は数値積分で円周率 \(\pi\) を求めてみましょう。区間 [a, b] の定積分 \(\int_{a}^{b} f(x) \, dx\) を数値的に求めるには、区間を細分して小区間の面積を求めて足し上げます。小区間の面積を求める一番簡単な方法は長方形で近似することです。この場合、3 つの方法が考えられます。
1 は左端の値 f(a) を、2 は右端の値 f(b) を、3 は中間点の値 f((a + b) / 2) を使って長方形の面積を計算します。この中で 3 番目の方法が一番精度が高く、これを「中点則」といいます。このほかに、台形で近似する「台形則」や、2 次近似で精度を上げる「シンプソン則」という方法があります。
それでは実際に、中点則でπの値を求めてみましょう。\(\pi\) は次の式で求めることができます。
プログラムは次のようになります。
リスト : 数値積分で円周率を求める
(defun midpoint (n)
(let ((w (/ 1d0 n)) (s 0d0))
(dotimes (i n (* s w))
(let ((x (* (+ i 0.5d0) w)))
(incf s (/ 4d0 (+ 1d0 (* x x))))))))
関数 midpoint の引数 N が分割数です。最初に小区間の幅を求めて変数 W にセットします。面積は変数 S にセットします。次の dotimes で区間 [0, 1] を N 個に分割して面積を求めます。
最初に x 座標を計算します。中間点を求めるため、変数 I を 0 から始めて、x 座標を次の式で求めます。
x = (i + 0.5) * w
たとえば、変数 I が 0 の場合は 0.5 になるので、変数 X は区間 [0 * w, 1 * w] の中間点になります。あとは、4 / (1 + x * x) を計算して S に加算します。最後に S に W を掛け算して全体の面積を求めます。
実行結果を示します。
* (midpoint 10000) 3.141592654423134d0
最後に素数を求めるプログラムを作ってみましょう。いちばん簡単な方法は、奇数 3, 5, 7, 9, ... をそれまでに見つかった素数で割ってみることです。見つかった素数はリストに格納しておけばいいでしょう。プログラムは次のようになります。
リスト : 素数を求める
;;; 素数のチェック
(defun primep (n ps)
(dolist (m ps t)
(if (zerop (mod n m)) (return))))
;;; 素数のリストを返す
(defun prime (n)
(do ((ps '(2)) (m 3 (+ m 2)))
((< n m) ps)
(if (primep m ps)
(setq ps (append ps (list m))))))
素数を判定する述語 primep は簡単です。引数 PS は素数のリストです。ここから素数を順番に取り出して、割り切れるか調べればいいわけです。この処理には dolist を使えばいいですね。(mod n m) が 0 であれば割り切れたので、N は素数ではありません。return でループを脱出して NIL を返します。dolist が最後まで終了すれば N は素数です。dolist で T を返します。
素数のリストを返す関数 prime も簡単です。素数のリストを格納する変数 PS は (2) に初期化します。あとは、M が素数か primep でチェックし、素数であれば PS の最後尾に追加します。リストの先頭にデータを追加することは簡単ですが、最後尾に追加するのはちょっと面倒です。list で M をリストに格納し、それを append で PS と結合します。最後に do が終了したら PS を返します。
それでは実行してみましょう。
* (prime 100) (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
100 以下の素数は全部で 25 個あります。
ところで、この方法には無駄があります。N が素数か判別するため、N より小さい素数で割り切れるか調べていますが、実は √N より小さい素数を調べるだけでいいのです。さっそくプログラムを改造しましょう。次のリストを見てください。
リスト : 素数を求める (改良版)
;;; 素数のチェック
(defun fast-primep (n ps)
(dolist (m ps t)
(cond
((zerop (mod n m)) (return))
((< n (* m m)) (return t)))))
;;; 素数のリストを返す
(defun fast-prime (n)
(do ((ps '(2)) (m 3 (+ m 2)))
((< n m) ps)
(if (fast-primep m ps)
(setq ps (append ps (list m))))))
述語 fast-primep で PS から取り出した素数 M の 2 乗が N より大きくなったならば、N は素数であることがわかります。M > √N のかわりに M * M > N をチェックしています。この場合は return で dolist を脱出して T を返します。
それでは、どの程度の差がつくのか、実際に試してみましょう。
* (time (length (prime 100000))) Evaluation took: 1.755 seconds of real time 1.718750 seconds of total run time (1.687500 user, 0.031250 system) [ Run times consist of 0.062 seconds GC time, and 1.657 seconds non-GC time. ] 97.95% CPU 4,213,680,424 processor cycles 736,134,112 bytes consed 9592 * (time (length (fast-prime 100000))) Evaluation took: 0.326 seconds of real time 0.328125 seconds of total run time (0.296875 user, 0.031250 system) [ Run times consist of 0.063 seconds GC time, and 0.266 seconds non-GC time. ] 100.61% CPU 781,667,100 processor cycles 736,149,520 bytes consed 9592 実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz
結果は、最初のプログラムが 1.755 秒、改良版が 0.326 秒でした。ただし、append を使ってリストを連結しているので、その部分でもかなりの無駄があります。リスト以外のデータ構造、たとえば「配列 (array)」を使うと、もっと速くなると思います。
次の関数を繰り返しを使って定義してください。
リスト : 九九表
(defun ninety-nine ()
(format t " | 1 2 3 4 5 6 7 8 9~%")
(format t "---+---------------------------~%")
(dotimes (i 9)
(format t "~2D | " (1+ i))
(dotimes (j 9)
(format t "~2D " (* (1+ i) (1+ j))))
(terpri)))
九九表は二重の dotimes で簡単に作ることができます。変数 I, J の値は 0 から 8 までなので、1+ で値を 1 つ増やしていることに注意してください。format の書式 ~2D の 2 はフィールド幅を指定します。~nD は表示する整数が n 桁未満の場合、上位の桁には空白文字が埋められます。
* (ninety-nine) | 1 2 3 4 5 6 7 8 9 ---+--------------------------- 1 | 1 2 3 4 5 6 7 8 9 2 | 2 4 6 8 10 12 14 16 18 3 | 3 6 9 12 15 18 21 24 27 4 | 4 8 12 16 20 24 28 32 36 5 | 5 10 15 20 25 30 35 40 45 6 | 6 12 18 24 30 36 42 48 54 7 | 7 14 21 28 35 42 49 56 63 8 | 8 16 24 32 40 48 56 64 72 9 | 9 18 27 36 45 54 63 72 81 NIL
リスト : リストの探索
(defun my-find (x ys)
(dolist (y ys)
(if (eql x y) (return y))))
Common Lisp には関数 find が用意されているので、関数名は my-find としました。なお、find はリストだけではなく、ベクタ (vector, 1 次元配列のこと) と文字列にも使うことができます。プログラムは簡単で、dolist でリストから要素を取り出し、(eql x y) が真ならば return で要素 Y を返します。見つからない場合は、dolist が終了して NIL を返します。
* (my-find 'a '(a b c d e)) A * (my-find 'c '(a b c d e)) C * (my-find 'e '(a b c d e)) E * (my-find 'f '(a b c d e)) NIL
リスト : 整数値の乗算
(defun product (s e)
(do ((n s (1+ n)) (a 1))
((> n e) a)
(setq a (* a n))))
関数 product は簡単です。変数 A に乗算した結果を求めます。変数 N を S に初期化して、do ループで +1 していきます。N が E よりも大きくなったならば、ループを終了して A を返します。
* (product 1 10) 3628800 * (product 11 20) 670442572800
リスト : リスト XS はリスト YS よりも長いか？
(defun longerp (xs ys)
(do ((xs1 xs (cdr xs1))
(ys1 ys (cdr ys1)))
((or (null xs1) (null ys1)) xs1)))
関数 longerp も簡単です。変数 XS1, YS1 を XS, YS に初期化します。あとは do ループで XS1 と YS1 に cdr を適用し、どちらかが空リストになったら、ループを終了して XS1 を返します。
* (longerp '(a b c) '(a b)) (C) * (longerp '(a b c) '(a b c)) NIL * (longerp '(a b c) '(a b c d)) NIL
今回は組み合わせの数を求める関数 comb を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。
１ 0Ｃ0
／ ＼ ／ ＼
１ １ 1Ｃ0 1Ｃ1
／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ２ １ 2Ｃ0 2Ｃ1 2Ｃ2
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ３ ３ １ 3Ｃ0 3Ｃ1 3Ｃ2 3Ｃ3
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ４ ６ ４ １ 4Ｃ0 4Ｃ1 4Ｃ2 4Ｃ3 4Ｃ4
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\) に対応しています。
きれいな三角形にはなりませんが、簡単なプログラムを示します。
リスト : パスカルの三角形
(defun comb (n r)
(if (or (= n r) (zerop r))
1
(/ (* (comb n (1- r)) (1+ (- n r))) r)))
(defun pascal (n)
(dotimes (i n)
(dotimes (j (1+ i))
(format t "~3D " (comb i j)))
(terpri)))
dotimes で二重ループを構成します。terpri は標準出力へ改行を出力します。実行結果は次のようになります。
* (pascal 10) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 NIL
きれいな三角形を出力するプログラムは、皆さんにお任せいたします。また、関数 comb を使わないでパスカルの三角形を出力するプログラムを作ってみるのも面白いでしょう。
繰り返しではありませんが、S 式を順番に実行する関数を紹介しましょう。
progn は与えられた S 式を順番に実行し、いちばん最後に評価した値を返します。簡単な例を示しましょう。
* (progn (print 1) (print 2) (print 3)) 1 2 3 3
progn は defun, cond, let, do などで、複数の S 式を評価する場合と同じです。このため、progn を単独で使うことはほとんどありませんが、if と組み合わせて使う場合があります。次の例を見てください。
(if <条件節>
(progn Ｓ式Ａ Ｓ式Ｂ ... ) ; then 節
(progn Ｓ式ａ Ｓ式ｂ ... )) ; else 節
if の then 節や else 節は複数の S 式を受け付けません。このような場合、progn を使えば複数の S 式を評価することができます。もっとも、このような場合は cond を使ったほうがよいのかもしれません。
prog1 は最初に評価した S 式の値が返り値となります。prog2 は 2 番目に評価した S 式の値が返り値となります。簡単な例を示しましょう。
* (prog1 (print 1) (print 2) (print 3)) 1 2 3 1 * (prog2 (print 1) (print 2) (print 3)) 1 2 3 2
prog1 や prog2 は、変数の値を取り出しておいてから、変数の値を更新する処理などで役に立ちます。簡単な例題として、「スタック (stack)」というデータ構造を操作する関数を作ってみましょう。
最初にスタックについて説明します。スタックの例として、バネ付きのトレイを取り上げます。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH (3) PUSH (4) POP (5) POP
A B B A
図 : スタックの動作例
初めはトレイが入っていない空の状態です。ここにトレイを上から入れると、重さによってバネを圧縮し、次のトレイを追加できるようになります。もうひとつトレイを乗せると、さらにバネを圧縮し次のトレイを追加できるようになります。バネが限界まで圧縮されると、トレイは追加できません。トレイを取り出す場合は、上にあるトレイから取り出していきます。ひとつ取り出すと、その分バネが伸びて下にあるトレイが上に出てくるので、次のトレイを取り出すことができます。
このトレイをデータと考えてください。データ A をスタックに追加し(2)、次にデータ B を追加します(3)。データを取り出す場合、後から入れたデータ B が先に取り出され(4)、その次にデータ A が取り出されて、スタックが空になります(5)。このように、スタックは後から入れたデータが先に取り出されるので、「後入れ先出し (Last-In First-Out : LIFO)」と呼ばれます。スタックにデータを追加する操作を「プッシュ (PUSH)」といい、スタックからデータを取り出す操作を「ポップ (POP)」といいます。
スタックはリストを使うと簡単に実現することができます。たとえば、スペシャル変数 *STACK* にスタックを保持することにします。プッシュはリストの先頭にデータを追加していくことで実現できます。これは cons を使えば簡単ですね。データをプッシュする push-stack は、次のようになります。
リスト : プッシュ (defvar *stack*) (defun push-stack (data) (setq *stack* (cons data *stack*)))
それでは、実際に試してみましょう。
* (setq *stack* nil) NIL * (push-stack 10) (10) * (push-stack 20) (20 10)
最初スタックにはデータがありませんから、*STACK* は NIL で初期化しておきます。push-stack を実行するたびに、スタック *STACK* にデータが追加されていきます。
次は、データをポップする pop-stack を作ります。ポップはリストの先頭にあるデータを取り出す操作です。データを取り出すには car を使えばいいですね。取り出したデータは *STACK* から削除します。これには cdr を使えばいいでしょう。
ポイントは、car でデータを取り出したあとで *STACK* を更新し、取り出したデータを関数の返り値とするところです。このとき、prog1 がとても役に立つのです。次のリストを見てください。
リスト : ポップ
(defun pop-stack ()
(prog1 (car *stack*)
(setq *stack* (cdr *stack*))))
最初に car を使ってデータを読み、cdr で残りの要素を変数 *STACK* にセットします。これで先頭の要素を取り除くことができました。prog1 を使っているので、car で読み出したデータを返すことができるのです。progn では cdr の値を返してしまうので、取り出したデータを返すことができません。それでは、実際に試してみましょう。
* (pop-stack) 20 * *stack* (10) * (pop-stack) 10 * *stack* NIL
確かにスタック *STACK* からデータが削除され、そのデータが関数の返り値になっています。
スタックを操作する関数 push-stack と pop-stack を作りましたが、Common Lisp にはスタックを操作するマクロ push と pop が用意されています。
push item place pop place
push は変数 place に格納されているリストの先頭に item を追加し、その結果を返します。place の内容は書き換えられることに注意してください。つまり、push は次の S 式と同じ働きをするわけです。
(push item place) ≡ (setq place (cons item place))
pop は変数 place に格納されているリストの先頭要素を返します。そして、先頭要素を取り除いたリストを place にセットします。
簡単な使用例を示しましょう。
* (defvar z '(a b c d)) Z * (push 'x z) (X A B C D) * z (X A B C D) * (pop z) X * z (A B C D) * (pop z) A * z (B C D)
スタックの動作は単純ですが、とても役に立つ重要なデータ構造です。ぜひ覚えておいてください。
次に示す関数を定義してください。
逆ポーランド記法 (RPN : Reverse Polish Notation) は演算子を後ろに置く書き方で、数式が 1 + 2 であれば 1 2 + のように書きます。逆ポーランド記法の利点は、計算する順番に演算子が現れるため、カッコが不要になることです。たとえば、1 と 2 の和と 3 と 4 の和との積という数式を表してみましょう。
(1 + 2) * (3 + 4) => 1 2 + 3 4 + *
逆ポーランド記法は、日本語の読み方とまったく同じです。1 2 + で 1 と 2 の和を求め、3 4 + で 3 と 4 を求め、最後に 2 つの結果を掛け算して答えが求まります。
簡単な実行例を示します。
* (rpn '(1 2 + 3 4 + *)) 21 * (rpn '(1 2 + 3 4 - *)) -3 * (rpn '(1 2 + 3 4 + 5 6 + * *)) 231 * (rpn '(1 2 + 3 4 + 5 6 + * /)) 3/77 * (rpn '(1 2 + 3 4 + * 5 6 + /)) 21/11
逆ポーランド記法の数式はスタックを使うと簡単に計算することができます。アルゴリズムは次のようになります。
1. 数値はスタックに追加する。 2. 演算子であればスタックから 2 つ数値を取り出し、演算結果をスタックに追加する。 3. 最後にスタックに残った値が答えになる。
たったこれだけの規則で数式を計算することができます。
リスト : リストの生成
(defun my-make-list (n x)
(do ((m n (1- m))
(xs nil))
((zerop m) xs)
(push x xs)))
* (my-make-list 10 'a) (A A A A A A A A A A) * (my-make-list 10 0) (0 0 0 0 0 0 0 0 0 0)
Common Lisp には関数 make-list が用意されているので、名前を my-make-list としました。なお、make-list は要素の指定をキーワード引数 :initial-element で行います。
make-list size :initial-element item
* (make-list 8 :initial-element 'a) (A A A A A A A A) * (make-list 8 :initial-element '10) (10 10 10 10 10 10 10 10) * (make-list 8) (NIL NIL NIL NIL NIL NIL NIL NIL)
キーワード引数はあとで説明します。
リスト : リストの反転
(defun my-reverse (xs)
(let ((ys nil))
(dolist (x xs ys) (push x ys))))
* (my-reverse '(a b c d e)) (E D C B A)
変数 YS を NIL に初期化します。あとは dolist でリスト XS の要素を順番に取り出し、それを push で YS に追加していくだけです。これで XS の先頭要素が YS の末尾に、XS の末尾要素が YS の先頭になります。
リスト : リストを反転して結合する (defun my-revappend (xs ys) (dolist (x xs ys) (push x ys)))
* (my-revappend '(a b c) '(1 2 3)) (C B A 1 2 3)
Common Lisp には関数 revappend が用意されているので、名前を my-revappend としました。プログラムは my-reverse とほとんど同じで、引数の YS にリスト XS の要素をプッシュしていくだけです。
パスカルの三角形は、両側がすべて 1 で内側の数はその左上と右上の和になっています。したがって、n 段の三角形を作る場合、一段前の値を記憶しておいて隣同士の要素を足し算すればいいわけです。一段前の値をリストに格納すると、プログラムは次のようになります。
リスト : パスカルの三角形
(defun pascal-sub (xs)
(do ((ys (cons 0 xs) (cdr ys))
(zs nil))
((null ys) zs)
(if (null (cdr ys))
(push 1 zs)
(push (+ (first ys) (second ys)) zs))))
(defun pascal1 (n)
(do ((xs nil)
(m n (1- m)))
((zerop m))
(setq xs (pascal-sub xs))
(print xs)))
関数 pascal-sub は、リストの隣同士の要素を足した値をリストに格納して返します。引数 XS の先頭に 0 を追加してから処理を行うことに注意してください。パスカルの三角形は左右対称なので、足し算した値をリスト ZS にプッシュすれば OK です。リスト YS の要素が 1 つになったら 1 を ZS にプッシュします。あとは pascal1 で pascal-sub を n 回呼び出すだけです。
* (pascal1 10) (1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1) (1 6 15 20 15 6 1) (1 7 21 35 35 21 7 1) (1 8 28 56 70 56 28 8 1) (1 9 36 84 126 126 84 36 9 1) NIL
リスト : 逆ポーランド記法の計算
(defun rpn (xs)
(let ((zs nil))
(dolist (x xs (if (and (consp zs) (null (cdr zs))) ; (singlep zs) を使ってもよい
(car zs)
"invalid expression"))
(if (numberp x)
(push x zs)
(let ((b (pop zs)) (a (pop zs)))
(if (or (null b) (null a))
(return "stack underflow"))
(case
x
(+ (push (+ a b) zs))
(- (push (- a b) zs))
(* (push (* a b) zs))
(/ (push (/ a b) zs))
(t (return "invalid operation"))))))))
関数 rpn の引数 XS が数式を表すリストです。局所変数 ZS がスタックを表します。XS の要素は dolist で順番に取り出して変数 X にセットします。dolist が終了したらスタックトップの値を返します。このとき、スタックが空または複数の値が格納されている場合はエラーメッセージを返します。
次に、X が数値の場合はそれをスタックに追加します。そうでなければ、X は演算子を表すシンボルです。この場合、最低でも 2 つの値がスタックになければいけません。0 個または 1 個しかない場合は return でエラーメッセージを返します。あとは演算子を case で場合分けして、計算結果をスタックに追加します。このとき、先頭の要素 b が第 2 引数、2 番目の要素 a が第 1 引数になることに注意してください。