10. ループと再帰 (2004/08/10)

Emacs Lispには、式や一連の式を繰り返し評価する主要な方法が2つあり、 whileループを使う方法と再帰（recursion）を使う方法である。

繰り返しはとても重要である。 たとえば、4つの文だけ先へ進むには、 1つの文のみ先へ進むだけのプログラムを書き、それを4回繰り返せばよい。 人間は繰り返し回数をまちがえたり処理を誤ったりするが、 コンピュータが飽きたり疲れたりすることはないので、 繰り返し動作が有害な結果を生むことはない。

問題を解決したりするのにとてもパワフルな再帰を使うことは可能だが (9)， ほとんどの人は while ループや同種の関数を使って Emacs Lisp 関数を書く．

10.1 while

スペシャルフォームwhileは、第1引数を評価した結果が真か偽かを検査する。 これは、Lispインタープリタがifに対して行うことに似ているが、 その検査後にインタープリタが行うことは異なる。

while式では、第1引数を評価した結果が偽ならば、 Lispインタープリタは式の残りの部分（式の本体）を飛び越し、 それらを評価しない。 しかし、値が真ならば、Lispインタープリタは式の本体を評価し、 再度、第1引数が真か偽かを検査する。 第1引数を再度評価した結果が真ならば、 Lispインタープリタは式の本体を再度評価する。

while式の雛型はつぎのとおりである。

(while 判定条件
  本体...)

while を使ったループ		Repeat so long as test returns true.
10.1.1 A while ループとリスト		A while loop that uses a list.
10.1.2 例：print-elements-of-list		Uses while, car, cdr.
10.1.3 増加カウンタによるループ		A loop with an incrementing counter.
10.1.4 減少カウンタによるループ		A loop with a decrementing counter.

while を使ったループ

評価したときにwhile式の判定条件が真を返す限り、 本体を繰り返し評価する。 飛行機が旋回（ループ）するように、Lispインタープリタが同じことを 何度も何度も繰り返すので、この処理をループと呼ぶ。 判定条件の評価結果が偽ならば、Lispインタープリタはwhile式の 残りを評価せず「ループから出る」。

明らかに、whileの第1引数の評価結果がつねに真ならば、 それに続く本体は何度も何度も...何度も...永久に評価される。 逆に、評価結果がけっして真にならなければ、本体の式はけっして評価されない。 whileループを書く工程は、続く式を評価したい回数だけ真を返し、 そのあとは偽を返すような判定条件を選ぶことである。

whileを評価した結果返される値は、判定条件の値である。 この帰結として興味深いことは、エラーなしに評価されるwhileループは、 1回繰り返そうが100回繰り返そうがまったく繰り返さなくても、 nil、つまり、偽を返すことである。 正しく評価できたwhile式は、けっして真を返さない！　 つまり、whileはつねに副作用のために評価されるのであり、 whileループの本体の式を評価した効果だけのためである。 これは意味のあることである。 ほしいのは単なる繰り返し動作ではなく、 ループの式を繰り返し評価したときの効果がほしいのである。

10.1.1 A while ループとリスト

whileループを制御する一般的な方法は、 リストに要素があるかどうかを検査することである。 要素があればループを繰り返すが、要素がなければ繰り返しを終える。 これは重要な技法なので、例示のために短い例を作ることにする。

リストに要素があるかどうかを検査する簡単な方法は、 リストを評価することである。 要素がなければ、空リストであるから空リスト()が返され、 これは偽を意味するnilの同義語である。 一方、リストに要素があれば、評価するとこれらの要素を返す。 Emacs Lispインタープリタは、nil以外の値を真と解釈するので、 要素を返すリストはwhileループの検査では真になる。

たとえば、つぎのsetq式を評価すれば、 変数empty-listにnilを設定できる。

(setq empty-list ())

setq式を評価しておけば、いつものようにシンボルの直後に カーソルを置いてC-x C-eとタイプすれば変数empty-listを 評価できる。 エコー領域にはnilと表示される。

empty-list

一方、つぎの2つの式を評価するとわかるように、 要素を持つリストを変数に設定して、その変数を評価するとリストが表示される。

(setq animals '(gazelle giraffe lion tiger))

animals

したがって、リストanimalsに要素があるかどうかを検査する whileループを書くと、ループの始めの部分はつぎのようになる。

(while animals
       ...

whileが第1引数を検査するとき、変数animalsが評価される。 これはリストを返す。 リストに要素がある限り、whileは検査結果は真であると解釈する。 しかし、リストが空になると検査結果は偽であると解釈する。

whileループが永久に廻り続けるのを防ぐには、 最終的にリストが空になるような機構を与える必要がある。 しばしば使われる技法は、while式の中の式の1つで、 リストの値にリストのCDRを設定することである。 関数cdrを評価するたびに、リストは短くなり、最終的には空リストになる。 その時点でwhileループの検査は偽を返し、 whileの引数はそれ以上評価されなくなる。

たとえば、つぎの式で、動物のリストを束縛した変数animalsに もとのリストのCDRを設定できる。

(setq animals (cdr animals))

まえの式を評価してからこの式を評価すると、 エコー領域に (giraffe lion tiger) と表示される。 この式を再度評価すると、エコー領域に(lion tiger)と表示される。 さらに評価すると(tiger)となり、 さらに評価すると空リストになりnilと表示される。

関数cdrを繰り返し使って最終的に判定条件が偽になるような whileループの雛型はつぎのようになる。

(while リストが空かどうか検査
  本体...
  リストのcdrをリストに設定)

この検査とcdrの利用は、 リスト全体を調べてリストの各要素を1行に表示する関数で使える。

10.1.2 例：print-elements-of-list

関数print-elements-of-listはリストを用いたwhileループの例である。

この関数は、複数行出力する。Emacs 21 かそれ以上のバージョンでこのマニュ アルを読んでいるなら，いつものようにInfo 上で続く式を評価できる．

もしEmacs の古いバージョンを使っているのであれば，必要な式を `*scratch*' バッファにコピーして，そこで評価する必要がある．これ は古いバージョンのEmacsではエコー領域が1行しか無いためである．

式をコピーするには、 リージョンの始めをC-SPC（set-mark-command）で マークし、カーソルをリージョンの終わりに移動してから、 M-w（copy-region-as-kill）を使ってリージョンをコピーする。 つぎに、バッファ`*scratch*'にて、 C-y（yank）とタイプすればその式を取り出せる。

バッファ`*scratch*'に式をコピーしてから、各式を順番に評価する。 最後の式(print-elements-of-list animals)は、必ず、 C-u C-x C-eとタイプして、つまり、 eval-last-sexpに引数を与えて評価すること。 これにより、評価結果は、エコー領域ではなく、 バッファ`*scratch*'に表示される （さもないと、エコー領域には、^Jgiraffe^J^Jgazelle^J^Jlion^J^Jtiger^Jnil のように表示される。 ここで、`^J'は改行のことである．)

もしEmacs 21以降を使っていれば，これらの式をInfoバッファで直接評価し， エコー領域で結果を見ることができる．

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-of-list (list)
  "Print each element of LIST on a line of its own."
  (while list
    (print (car list))
    (setq list (cdr list))))

(print-elements-of-list animals)

When you evaluate the three expressions in sequence, you will see this: 3つの式を順番に評価すると、つぎのように表示される。

giraffe

gazelle

lion

tiger
nil

リストの各要素が（関数printの動作により）1行に表示され、 最後に関数が返した値が表示される。 関数の最後の式はwhileループであり、whileループはつねにnil を返すので、リストの最後の要素のあとに、nilが表示される。

10.1.3 増加カウンタによるループ

終了すべきときに止まらないループは無意味である。 ループをリストで制御する以外に、ループを止める一般的な方法は、 必要回数の繰り返しを完了したら偽を返すような第1引数を書くことである。 つまり、ループにカウンタ、ループの繰り返し回数を数える式 を持たせるのである。

(< count desired-number)のように判定条件を記述すれば、 countの値が繰り返し回数desired-numberより小さければ真を返し、 countの値がdesired-numberに等しいか大きければ偽を返す。 カウンタを増加させる式は(setq count (1+ count))のような 簡単なsetqでよく、1+は引数に1を加えるEmacs Lispの 組み込み関数である （式(1+ count)は、(+ count 1)と同じ結果をもたらし、 人間にも読みやすい）。

カウンタを増加して制御するwhileループの雛型はつぎのようになる。

set-count-to-initial-value
(while (< count desired-number)         ; 判定条件
  body...
  (setq count (1+ count)))              ; 1増やす

countの初期値を設定する必要があることに注意してほしい。 普通は1に設定する。

増加カウンタの例		Counting pebbles in a triangle.
関数定義の各部分		The parts of the function definition.
関数定義をまとめる		Putting the function definition together.

増加カウンタの例

浜辺で遊んでいるときに、つぎに示すように、 最初の行には小石を1個、つぎの行には2個、そのつぎの行には3個というように、 小石で三角形を作ろうと考えたとする。

               *
              * *
             * * *
            * * * *

（約2500年前に、ピタゴラスや他の人達は、 このような問題を考察して数論の始まりを築いた。）

7行の三角形を作るには何個の小石が必要か知りたいとしよう。

明らかに、必要なことは数1から7までを加算することである。 これには2つの方法がある。 最小数1から始めて、1、2、3、4のように加算する。 あるいは、最大数から始めて、7、6、5、4のように加算する。 いずれの方法も、whileループを書く一般的な方法の例示になるので、 増やしながらの加算と減らしながらの加算の2つの例を書くことにする。 まずは、1、2、3、4と加算する例から始める。

数個の数を加算するだけならば、もっとも簡単な方法は、 それらをいっきに加算することである。 しかし、あらかじめ何個の数を加算するかわかっていなかったり、 非常に多くの数の加算にも対処したければ、 複雑な処理をいっきに行うのではなく、 単純な処理を繰り返すような加算にする必要がある。

たとえば、小石の個数をいっきに加算するかわりに、 最初は1行目の小石の個数1を2行目の個数2に加え、 これらの総和を3行目の個数3に加える。 つぎに、4行目の個数4を1行目から3行目までの総和に加えるということを繰り返す。

処理の重要な点は、繰り返しの各段階の動作は単純であることである。 この例では、各段階では、2つの数、つまり、 その行の小石の個数とそれまでの総和を加算するだけである。 最後の行をそれまでの総和に加算するまで、 2つの数の加算処理を繰り返し繰り返し実行するのである。 より複雑なループでは、各段階の動作は単純ではないかもしれないが、 すべてをいっきに行うよりは簡単である。

関数定義の各部分

以上の分析により、関数定義の骨格がわかる。 まず、小石の総数を保持する変数totalが必要である。 これは、関数が返す値である。

つぎに、関数には引数が必要である。 この引数は三角形の行数である。 これをnumber-of-rowsとしよう。

最後に、カウンタとして使う変数が必要である。 この変数をcounterと命名してもよいが、 より適したrow-numberを使おう。 カウンタが数えるのは行数であり、 プログラムではできる限りわかりやすい名前を使うべきだからである。

Lispインタープリタが関数内の式の評価を始めるときには、 totalには何も加算していないので、 totalの値は0になっているべきである。 続いて、関数では、1行目の小石の個数を総和に加算し、 2行目の小石の個数を総和に加算し、3行目の小石の個数を総和に加算し、 ということを、加算すべき行がなくなるまで行う。

totalとrow-numberのどちらも、関数の内部だけで使うので、 letでローカル変数として宣言し初期値を与える。 明らかに、totalの初期値は0である。 また、第1行から始めるので、row-numberの初期値は1である。 つまり、let文はつぎのようになる。

  (let ((total 0)
        (row-number 1))
    本体...)

内部変数を宣言しそれらに初期値を束縛したら、whileループを始められる。 判定条件の式は、row-numberがnumber-of-rowsより小さいか等しい 限りは真を返す必要がある （行の番号が三角形の行数より小さい場合に限り真を返す判定条件だと、 最後の行が総和に加算されない。 したがって、行の番号は三角形の行数より小さいか等しい必要がある）。

Lispには、第1引数が第2引数より小さいか等しいときに真を返し、 それ以外のときには偽を返す関数<=がある。 したがって、whileが判定条件として評価する式はつぎのようになる。

(<= row-number number-of-rows)

小石の総数は、すでにわかっている総数に行の小石の個数を加算することを 繰り返して計算できる。 行の小石の個数はその行の番号に等しいので、 総数は、総数に行番号を加算すれば計算できる （より複雑な状況では、行の小石の個数は、より複雑な方法で行の番号に関係する。 そのような場合には、行の番号を適当な式で置き換える）。

(setq total (+ total row-number))

これにより、totalの新たな値は、行の小石の個数をそれまでの総数に 加えたものになる。

totalの値を設定したあと、 ループのつぎの繰り返しのための条件を確立する必要がある。 これには、カウンタとして働く変数row-numberの値を増やせばよい。 変数row-numberを増やしたあと、whileループの判定条件により、 その値がnumber-of-rowsより小さいか等しいかどうか検査する。 もしそうならば、変数row-numberの新たな値を ループのまえの段階でのtotalに加える。

Emacs Lispの組み込み関数1+は数に1を加えるので、 つぎの式で変数row-numberを増加できる。

(setq row-number (1+ row-number))

関数定義をまとめる

関数定義の各部分を作ったので、それらを1つにまとめよう。

まず、while式の内容はつぎのとおりである。

(while (<= row-number number-of-rows)   ; 判定条件
  (setq total (+ total row-number))
  (setq row-number (1+ row-number)))    ; 1増やす

let式の引数リストを加えれば、これで関数定義の本体はぼぼ完成する。 しかし、その必要性は少々微妙ではあるが、最後の要素が必要である。

つまり、while式のあとに、変数totalだけを置いた行が必要である。 さもないと、関数全体としての戻り値は、最後の式の値、 つまり、letの本体を評価した値、 つまり、whileが返す値であるが、これはつねにnilである。

一見しただけでは、これは自明ではないかもしれない。 関数全体としての最後の式は、増加する式であると思うだろう。 しかし、その式はシンボルwhileで始まるリストの最後の要素であり、 whileの本体の一部である。 さらに、whileループ全体も、letの本体の中にあるリストである。

関数の概略はつぎのとおりである。

(defun 関数名 (引数リスト)
  "説明文..."
  (let (変数リスト)
    (while (判定条件)
      whileの本体... )
      ... )                     ; 最後の式をここに置く

letは、defun全体としてのリスト以外のリストの内側にはないので、 letを評価した結果がdefunが返す値となる。 しかし、whileがlet式の最後の要素だったとすると、 関数はつねにnilを返す。 これは、われわれが望むことではない！　 変数totalの値を返したいのである。 それには、letで始まるリストの最後の要素として、 そのシンボルを書けばよい。 これにより、リストのまえのものが評価されたあとに、 正しい総数が設定されてから評価される。

このことは、letで始まるリストを1行に書くとわかりやすいであろう。 変数リストとwhile式は、letで始まるリストの 第2要素と第3要素であり、totalは最後の要素であることがはっきりする。

(let (変数リスト) (while (判定条件) whileの本体... ) total) 

以上をまとめると、triangleの関数定義はつぎのとおりである。

(defun triangle (number-of-rows)    ; 増加カウンタを利用した版
  "Add up the number of pebbles in a triangle.
The first row has one pebble, the second row two pebbles,
the third row three pebbles, and so on.
The argument is NUMBER-OF-ROWS."
  (let ((total 0)
        (row-number 1))
    (while (<= row-number number-of-rows)
      (setq total (+ total row-number))
      (setq row-number (1+ row-number)))
    total))

関数を評価してtriangleをインストールすれば、試すことができる。 2つの例をあげておく。

(triangle 4)

(triangle 7)

最初の4つの数を総和したものは10であり、最初の7つを総和したものは28である。

10.1.4 減少カウンタによるループ

whileループを書く一般的な別の方法は、 カウンタが0より大きいかを調べる検査を使うことである。 カウンタが0より大きい限り、ループを繰り返す。 しかし、カウンタが0になるか0より小さくなったら、ループを止める。 このように動作させるには、カウンタを0より大きく設定しておき、 繰り返すたびにカウンタを小さくするのである。

counterの値が0より大きければ真tを返し、 counterの値が0に等しいか小さければ偽nilを返す (> counter 0)のような式を判定条件に使う。 数を減らす式は、(setq counter (1- counter))のような単純なsetq でよく、1-は引数から1を引くEmacs Lispの組み込み関数である。

減算によるwhileループの雛型はつぎのようになります。

(while (> counter 0)                    ; 判定条件
  本体...
  (setq counter (1- counter)))          ; 1減少

減少カウンタの例		More pebbles on the beach.
関数の各部分		The parts of the function definition.
関数定義をまとめる		Putting the function definition together.

減少カウンタの例

減少カウンタによるループの例として、カウンタを0まで減少させるように 関数triangleを書き換える。

これは、この関数の前版の逆である。 つまり、3行の三角形を作るために必要な小石の個数は、 3行目の小石の個数3をそのまえの個数2に加え、2つの行の総数を そのまえの個数1に加えて計算する。

同様に、7行の三角形の小石の個数は、 7行目の小石の個数7をまえの行の個数6に加え、2つの行の総数を それらのまえの行の個数5に加え、と繰り返して計算する。 まえの例と同様に、各加算では2つの数、すでに加算した行の総数と、 加算すべき行の小石の個数を扱う。 2つの数を加える処理を、加えるべき小石がなくなるまで繰り返す。

始めの小石の個数はわかっている。 最後の行の小石の個数は、その行の番号に等しい。 7行の三角形の場合、最後の行の小石の個数は7である。 同様に、1つまえの行の小石の個数もわかっていて、行の番号より1つ小さい。

関数の各部分

3つの変数が必要である。 三角形の行の数、行の小石の個数、求めたい小石の総数である。 これらの変数をそれぞれ、number-of-rows、 number-of-pebbles-in-row、totalとしよう。

totalとnumber-of-pebbles-in-rowのいずれも関数の内側だけで 使うので、これらはletで宣言する。 totalの初期値は、当然、0である。 しかし、もっとも長い行から加算を始めるので、 number-of-pebbles-in-rowの初期値は、 三角形の行数に等しい必要がある。

つまり、let式の始めの部分はつぎのようになる。

(let ((total 0)
      (number-of-pebbles-in-row number-of-rows))
  本体...)

小石の総数は、行の小石の個数をすでにわかっている総数に加算すればよく、 つぎの式を繰り返し評価すればよい。

(setq total (+ total number-of-pebbles-in-row))

number-of-pebbles-in-rowをtotalに加算したあと、 ループのつぎの繰り返しでは、まえの行を総和に加算するので、 number-of-pebbles-in-rowを1減らす必要がある。

まえの行の小石の個数は、今の行の小石の個数より1小さいので、 Emacs Lispの組み込み関数1-を使って、まえの行の小石の個数を計算できる。 これはつぎの式になる。

(setq number-of-pebbles-in-row
      (1- number-of-pebbles-in-row))

whileループは行の小石がなくなったら繰り返しを止める。 したがって、whileループの判定条件は単純である。

(while (> number-of-pebbles-in-row 0)

関数定義をまとめる

機能する関数定義を作成するためにこれらの式をまとめることができる．しか し，調べてみると，ローカル変数の1つは不要であることが分かる!

関数定義は以下のようになる．

;;; 最初の減算版
(defun triangle (number-of-rows)
  "Add up the number of pebbles in a triangle."
  (let ((total 0)
        (number-of-pebbles-in-row number-of-rows))
    (while (> number-of-pebbles-in-row 0)
      (setq total (+ total number-of-pebbles-in-row))
      (setq number-of-pebbles-in-row
            (1- number-of-pebbles-in-row)))
    total))

この関数は正しく動作する。

しかし，number-of-pebbles-in-row は必要ではない．

関数triangleを評価するとき、 シンボルnumber-of-rowsには数が束縛され、それが初期値になる。 その数を変更しても関数の外側の変数の値に影響することはなく、 ローカル変数であるかのように関数の本体でその数を変更できる。 これはLispのとても有用な特徴である。 つまり、関数内部では、number-of-pebbles-in-rowのかわりに 変数number-of-rowsを使えるのである。

簡素に書き直した、この関数の第2版を示す。

(defun triangle (number)                ; 第2版
  "Return sum of numbers 1 through NUMBER inclusive."
  (let ((total 0))
    (while (> number 0)
      (setq total (+ total number))
      (setq number (1- number)))
    total))

まとめると、正しく書かれたwhileループは3つの部分から成る。

1. 必要回数だけループを繰り返したら偽を返す判定条件。

2. 繰り返し評価したあとに望みの値を返す式。

3. 必要回数だけループを繰り返したら判定条件が偽を返すように、 判定条件で使う値を変更する式。

10.2 dolist と dotimes (2004/08/08)

while に加えて，dolist と dotimes もループを実現 できます．時々，while ループと等価なものをより素早く書くことが できる．これらは両方とも Lisp マクロである．(See 節 `Macros' in

dolist は CDR でリストを辿っていく while ループのよ うに機能する．dolist は自動的にループが実行されるたびにリストの CDR を取ることで，リストを短くし，そのリストの CAR を最初の 引数に割り当てる．

dotimes は規定の回数だけループする．

dolist マクロ
dotimes マクロ

dolist マクロ

例えば，リストを"1番目" "2番目" "3番目" が "3番目" "2番目" "1番目" に なるように反転したいとする．

実際には，以下のように関数 reverse を使うだろう．

(setq animals '(gazelle giraffe lion tiger))

(reverse animals)

以下に while ループを使ってリストを反転させる例を示す．

(setq animals '(gazelle giraffe lion tiger))

(defun reverse-list-with-while (list)
  "Using while, reverse the order of LIST."
  (let (value)  ; make sure list starts empty
    (while list
      (setq value (cons (car list) value))
      (setq list (cdr list)))
    value))

(reverse-list-with-while animals)

そして，dolist マクロを使うと下記のようになる．

(setq animals '(gazelle giraffe lion tiger))

(defun reverse-list-with-dolist (list)
  "Using dolist, reverse the order of LIST."
  (let (value)  ; make sure list starts empty
    (dolist (element list value)
      (setq value (cons element value)))))

(reverse-list-with-dolist animals)

Info では各式の閉じ括弧の後にカーソルを起き，C-x C-e を入力する． この例では，以下のような結果がエコー領域に表示される．

(tiger lion giraffe gazelle)

この例では，存在している関数 reverse を使うのが明らかに最もいい． while ループはちょうど最初の例のようなものである (see 節 A while Loop and a List)．while は最初にリストが要素を持つかどうかを確認する．もしあれば，リストの最初 の要素を既存のリスト(最初の実行では nil)に追加することで新しい リストを作成する．2番目の要素は最初の要素の前に追加される．そして，3番 目の要素は2番目の要素の前に追加され，リストは反転される．

while を使った式では (setq list (cdr list)) でリスト を短くし，結果として while ループは停止する．さらに， ループの繰り返しのたびに新しく短いリストを作ることで cons 式に 新しい要素を渡していく．

dolist 式は while 式とほとんど同じである．異なっているの は while 式を使って書くところを dolist マクロを使ってい ることだ．

whileループのように dolist はループする．違いは ループするたびに自動的に -- 自分でリストの CDR を取ることで-- リ ストを短くしていくことだ．そして，短くなったリストの CAR が自動的 に最初の引数となる．

この例では各短リストの CAR はシンボル `element' を使って参照 できる．リスト自体は `list' で参照し，結果は `value' に保存 される．dolist 式の残りは本体である．

dolist はリストを短くし，その CAR を element に設定 してから，本体を評価する．そして，ループを繰り返す．結果は value で返される．

dotimes マクロ

dotimes マクロは dolist と似ている．異なるのは， dotimes が規定回数だけループする．

dotimes の最初の引数は0，1，2のような数字であり，ループが進むに つれて増えていく．そして，3番目の引数の値が返される．また，2番目の引数にはマ クロを何回繰り返すかを設定する必要がある．

例えば，以下のコードでは number を0から始まる数字を代入するが，3 は含めず，3つの数から成るリストを構成する．(最初の数は0である．2番目は 1，3番目は2となる．最初の数を0から始めるので全部で3つの数となる)．

(let (value)      ; otherwise a value is a void variable
  (dotimes (number 3 value)
    (setq value (cons number value))))

=> (2 1 0)

dotimes は value を返す．だから，dotimes を number 回繰り返し，リストかアトムにして結果を返すように使う．

以下に三角形状に小石を積み上げていった時の数を計算するために dotimes を使った defun の例を示す．

(defun triangle-using-dotimes (number-of-rows)
  "Using dotimes, add up the number of pebbles in a triangle."
(let ((total 0))  ; otherwise a total is a void variable
  (dotimes (number number-of-rows total)
    (setq total (+ total (1+ number))))))

(triangle-using-dotimes 4)

10.3 再　帰 (2004/08/10)

再帰関数では Lisp インタープリタに自分自身を少し異なる引数で実行するよ うなコードを含む．実行されるコードは名前が同じであるので同じである．し かし，例え同じ名前であっても，同じスレッドで実行されるわけではない．専 門的に言うと異なる"インスタンス"である．

結局，プログラムが正確に書かれていれば，"わずかに異なる引数"が最初の引 数とは十分に異なっていれば，結果として最後のインスタンスが停止することになる．

10.3.1 ロボットの構築: 隠喩の拡張 (2004/08/08)		Same model, different serial number ...
10.3.2 The Parts of a Recursive Definition		Walk until you stop ...
10.3.4 リストについての再帰 (2004/08/09)		Using a list as the test whether to recurse.
10.3.5 カウンタの代用としての再帰 (2004/08/09)
10.3.6 condを用いた再帰の例 (2004/08/09)
10.3.7 再帰関数の典型例 (2004/08/09)		Often used templates.
10.3.8 待機なしでの再帰 (2004/08/10)		Don't store up work ...
10.3.9 待機なしの解決 (2004/08/09)

10.3.1 ロボットの構築: 隠喩の拡張 (2004/08/08)

実行されているプログラムを仕事を行うロボットとして考えることは時に役に 立つ．仕事をする時，再帰関数は助けてもらうために2台目のロボットを呼ぶ． 2台目のロボットはすべての点で1台目と同じである．2台目のロボットは1台目 のロボットを助け，1台目とは異なった引数を受け取る．

再帰関数では，2台目のロボットが3台目を呼ぶかもしれない．そして，3台目 が4台目を呼ぶかもしれない．それぞれは異なった存在であるが，すべて複製 なのだ．

それぞれのロボットはわざうかに異なる指示(引数はあるロボットと次のロボッ トでは異なる)を受けている．最後のロボットはいつやめるべきかを知ってい なければならない．

このプログラムがロボットであるという隠喩を拡張しよう．

関数定義はロボットの設計図である．関数定義をインストールする，つまり， スペシャルフォーム defun を評価すると，ロボットを製造するための 必要な機器を設置したことになる．工場では組み立てラインを立ち上げる必要 がある．同じ名前を持つロボットは同じ設計図で製造される．だから，言って みれば同じ"モデル"であるが"製造番号"は異なるロボットがあるようなものだ．

しばしば再帰関数は"自分自身を呼び出す"と述べている．この意味は，再帰関 数の指示で Lisp インタープリタに引数は異なるが，同じ名前を持ち，同じ仕 事を行う関数を実行させることである．

重要なのは，あるインスタンスと次のものとでは引数が異なるという点である． もしそうでなければ，同じ作業を延々と繰り返すことになり，プロセスが停止 しない．

10.3.2 The Parts of a Recursive Definition

10.3.3 再帰関数の定義 (2004/08/09)

典型的な再帰的関数には、3つの部分から成る条件式が含まれる。

1. 関数を再度呼び出すかどうかを決定する判定条件。 これを再帰条件（do-again-test）と呼ぶ。

2. 関数名。名前が呼ばれると，関数の新しいインスタンス(新しいロボット)が呼 ばれ，何をすべきかを伝えられる．

3. 関数が呼ばれるたびに違う値を返すような式であり，ここでは 次段式 を呼び出す．結果として，新しい関数のインス タンスに渡る引数は前のインスタンスの引数とは異なる．これにより，条件式， 再帰条件を引き起こし，繰り返しを規定数繰り返して偽になっているか を確認する．

再帰的関数は、他の種類の関数よりもとても簡単である。 もちろん、これを使い始めたばかりの人には、 理解できないほど不可思議に単純に見える。 自転車に乗るのと同じように、再帰的関数定義を読むには、 最初は難しくてもしだいに簡単に思えるようになるコツが必要である。

一般的な再帰にはいくつかのパターンがある．以下にとても単純な例を示す．

(defun 再帰関数名 (引数リスト)
  "説明文..."
  (if 再帰条件
    本体...
    (再帰関数名
         次段式)))

再帰関数を評価するたびに，新しいインスタンスが作成され，何をするべきか が伝えられる．引数が何をすべきかをインスタンスに伝える．

引数には次段式の値が束縛される．それぞれのインスタンスは次段式の異なる 値で実行される．

次段式の値は再帰条件で使われる．

次段式の返す値は関数の新しいインスタンスへ渡され，続けるか停止するかを 判断するために評価(あるいは演算)される． 関数をそれ以上繰り返さない場合には、再帰条件が偽になるように次段式を作る。

再帰条件が偽になると繰り返しを停止するので、 再帰条件を停止条件（stop condition）と呼ぶこともある。

10.3.4 リストについての再帰 (2004/08/09)

動物のリストの各要素を表示するwhileループの例を 再帰的に書くことができる。 変数animalsにリストを設定する式も含めて、そのコードを示す。

Emacs 20 かそれ以前のものを使っているのであれば，この例を `*scratch*' バッファにコピーして各式をそこで評価しなければなりま せん．結果がバッファに表示されるように、C-u C-x C-eを使って 式(print-elements-recursively animals)を評価すること。 さもないと、Lispインタープリタは結果をエコー領域の1行に押し込めて表示する。

また、関数print-elements-recursivelyの注釈のまえの 最後の閉じ括弧の直後にカーソルを置くこと。 さもないと、Lispインタープリタは注釈を評価しようとする。

Emacs 21以降を使っているのであれば，Info 上で直接評価できる．

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (if list                              ; 再帰条件
      (progn
        (print (car list))              ; 本体
        (print-elements-recursively     ; 再帰呼び出し
         (cdr list)))))                 ; 次段式

(print-elements-recursively animals)

関数print-elements-recursivelyは、まず、リストの先頭要素、 つまり、リストのCARを表示する。 続いて、リストが空でなければ、関数は自分自身を呼び出すが、 その引数には、リスト全体ではなく、リストの2番目以降の要素、 つまり、リストのCDRを渡す。

これを評価すると、受け取った引数（もとのリストの2番目以降の要素）の先頭要素を 表示する。 続いて、if式を評価し、真ならば、リストのCDR、 つまり、（2回目なので）もとのリストのCDRのCDRを 引数として自身を呼び出す。

関数が自身を呼び出すごとに、もとのリストを短くしたものを引数に渡す。 最終的に、空リストで自身を呼び出す。 関数printは空リストをnilと表示する。 つぎに、条件式ではlistの値を調べる。 listの値はnilなので、if式の判定条件は偽になり、 真の場合の動作は評価されない。 そして、関数全体としてはnilを返す。 そのため、この関数を評価するとnilが2つ表示されるのである。

バッファ`*scratch*'で(print-elements-recursively animals)を 評価するとつぎのようになる。

giraffe

gazelle

lion

tiger
nil

10.3.5 カウンタの代用としての再帰 (2004/08/09)

前節で説明した関数triangleを再帰で書くこともできる。 つぎのようになる。

(defun triangle-recursively (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
  (if (= number 1)                    ; 再帰条件
      1                               ; 真の場合の動作
    (+ number                         ; 偽の場合の動作
       (triangle-recursively          ; 再帰呼び出し
        (1- number)))))               ; 次段式

(triangle-recursively 7)

これを評価して関数をインストールすれば、 (triangle-recursively 7)を評価して試すことができる （注釈のまえの関数定義の最後の括弧の直後にカーソルを置くこと）。関数は 28を返す．

この関数の動作を理解するために、 引数として、1、2、3、4をこの関数に渡すとどうなるかを考えよう。

引数が1か2の時 (2004/08/09)
引数が3か4の時 (2004/08/09)

引数が1か2の時 (2004/08/09)

まず、引数が1の場合はどうなるだろうか？

関数には、説明文字列に続けてif式がある。 これはnumberの値が1に等しいかどうかを調べる。 等しければ、Emacsはif式の真の場合の動作を評価し、 関数の値として数1を返す （1行の三角形には1個の小石がある）。

では、引数の値が2の場合を考えよう。 この場合は、Emacsはif式の偽の場合の動作を評価する。

偽の場合の動作は、加算、triangle-recursivelyの再帰呼び出し、 減算動作から成り、つぎのとおりである。

(+ number (triangle-recursively (1- number)))

Emacsがこの式を評価するとき、もっとも内側の式が最初に評価され、 つぎに、それ以外の部分が評価される。 詳しくはつぎのような手順になる。

手順1　もっとも内側の式を評価する。

もっとも内側の式は(1- number)であり、 Emacsはnumberの値を2から1へ減らす。

手順2　関数triangle-recursivelyを評価する。

関数の中にそれ自身があるかどうかは関係ない。 Emacsは手順1の結果を引数として使って、 関数triangle-recursivelyを呼び出す。

この場合、Emacsは引数1でtriangle-recursivelyを評価する。 つまり、triangle-recursivelyを評価すると1が返される。

手順3　numberの値を評価する。

変数numberは、+で始まるリストの2番目の要素であり、 その値は2である。

手順4　+式の評価。

+式は2つの引数、 numberの評価結果（手順3）と、triangle-recursivelyの評価結果 （手順2）を受け取る。

加算の結果は、2足す1で、数3が返される。 これは正しい値である。 2行の三角形には3個の小石がある。

引数が3か4の時 (2004/08/09)

引数が3の場合 (2004/08/09)

引数3でtriangle-recursivelyが呼ばれた場合を考えよう。

手順1　再帰条件の評価。

最初にif式が評価される。 これは再帰条件であり偽を返すから、if式の偽の場合の動作が評価される （この例では、再帰条件が偽の場合に自身を呼び出すのであり、 真の場合には呼ばない）。

手順2　偽の場合の動作のもっとも内側の式を評価する。

偽の場合の動作のもっとも内側の式が評価され、3から2に減る。 これは次段式である。

手順3　関数triangle-recursivelyを評価する。

関数triangle-recursivelyに数2が渡される。

Emacsが、引数2でtriangle-recursivelyを評価するとどうなるかは すでに知っている。 上で述べたような動作順序のあとで、値3が返される。 ここでもそのようになる。

手順4　加算の評価。

3が加算の引数として渡され、関数呼び出しの結果の数3に加算される。

関数全体として返す値は、6になる。

これで、引数3でtriangle-recursivelyを呼ぶとどうなるかがわかった。 引数4で呼んだ場合にどうなるかも明らかであろう。

再帰呼び出しにおいて、

(triangle-recursively (1- 4))

の評価結果は、つぎの式の評価結果であり、

(triangle-recursively 3)

これは6であり、この値が3行目で4に加えられる。

関数全体として返す値は10である。

Each time triangle-recursively is evaluated, it evaluates a version of itself--a different instance of itself--with a smaller argument, until the argument is small enough so that it does not evaluate itself. triangle-recursivelyを評価するたびに、引数が小さくなりすぎて評 価できなくなるまで，自分自身を(自分自身の異なるインスタンスを)より小さ な引数で，評価する．

この再帰関数に特有な設計には操作が引き伸ばされる必要がある．

(triangle-recursively 7) が答えを計算するまえに， (triangle-recursively 6) を呼ばないといけない． (triangle-recursively 6) の前には (triangle-recursively 5) をといったように呼ばないといけない．つまり， (triangle-recursively 7) は (triangle-recursively 6) が 計算するまで待たないといけない．(triangle-recursively 6) は (triangle-recursively 5) が完了するまで待つ．

もしtriangle-recursively のインスタンスのそれぞれが異なるロボッ トだとすると，最初のロボットは2番目が仕事を完了するまで待たないといけ ないし，2番目は3番目を待たないといけない．

この猶予に関しては Recursion without Deferments にて検討することになる．

10.3.6 condを用いた再帰の例 (2004/08/09)

triangle-recursivelyの上の版は、 スペシャルフォームifを用いて書いた。 別のcondと呼ばれるスペシャルフォームを使っても書ける。 スペシャルフォームcondの名前は、 単語`conditional'の略である。

スペシャルフォームcondは、Emacs Lispのソースでは、 ifほど多用されないが、ここで説明するに十分なほど使われる。

cond式の雛型はつぎのとおりである。

(cond
 本体...)

本体は、一連のリストである。

より詳しく書くと、雛型はつぎのとおりである。

(cond
 (first-true-or-false-test 最初の帰結動作)
  (2番目の判定条件 2番目の帰結動作)
  (3番目の判定条件 3番目の帰結動作)
  ...)

Lispインタープリタがcond式を評価するとき、 condの本体の一連の式の最初の式の最初の要素 （CAR、つまり、判定条件）を評価する。

判定条件がnilを返すと、式の残り、つまり、帰結動作は飛び越され、 つぎの式の判定条件を評価する。 判定条件がnil以外の値を返す式がみつかると、 その式の帰結動作を評価する。 帰結動作は、複数個の式でよい。 帰結動作が複数個の式の場合、それらの式は順番に評価され、 最後のものの値が返される。 式に動作がない場合には、判定条件の値が返される。

真となる判定条件がない場合には、cond式はnilを返す。

condを用いて書くと、関数triangleはつぎのようになる。

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

この例では、condは、数が0より小さいか等しい場合には0を返し、 数が1の場合には1を返し、 数が1より大きい場合には、(+ number (triangle-using-cond (1- number)))を 評価する。

10.3.7 再帰関数の典型例 (2004/08/09)

ここでは3つの一般的な再帰の例を紹介する．これらはリストを必要とする． 再帰自体にはリストは必要ではないが，Lisp はリストを処理するように設計 されている．だから，リストは再帰でも重要になる．

再帰のパターン: every (2004/08/10)
再帰のパターン: accumulate (2004/08/10)
再帰のパターン: keep (2004/08/10)

再帰のパターン: every (2004/08/10)

再帰のパターン every では，ある操作がリストにあるすべての要素で 実行される．

基本的なパターンは

• もしリストが空なら，nilを返す．
• そうでなければ，リストの先頭 (リストの CAR) で実行
  • リストの残り (CDR)で再帰を行う
  • そして，任意で，実行した結果を cons を使って要素を連結する

例をあげる．

(defun square-each (numbers-list)
  "Square each of a NUMBERS LIST, recursively."
  (if (not numbers-list)                ; 再帰条件
      nil
    (cons
     (* (car numbers-list) (car numbers-list))
     (square-each (cdr numbers-list))))) ; 次段式

(square-each '(1 2 3))
    => (1 4 9)

numbers-list が空であれば，何もしない．しかし，内容があれば，再 帰的に呼ぶことで，最初の数の2乗を持つようなリストを作成する．

(この例はパターンのままである．もし，数のリストが空であれば nil を返す．実際には，数のリストが空で無い時にのみ実行するような条件式を書 くだろう．)

関数 print-elements-recursively (see 節 Recursion with a List) はパターン every の別の例である．ただし，consを使って，個々の出力 を行っていることが異なっている．

print-elements-recursively は以下である．

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (if list                              ; 再帰条件
      (progn
        (print (car list))              ; 本体
        (print-elements-recursively     ; 再帰呼び出し
         (cdr list)))))                 ; 次段式

(print-elements-recursively animals)

print-elements-recursively の概略は以下のようになる．

• リストが空であれば，何もしない
• しかし，リストに少なくとも1個要素があれば
  • リストの先頭 (リストの CAR) に処理する
  • そして，リストの残り (CDR) に再帰呼び出しを行う

再帰のパターン: accumulate (2004/08/10)

他の再帰パターンは accumulate パターンと呼ばれる．再帰パターン accumulate では，リストのすべての要素で実行され，他の要素で実行 された結果に積み重ねていく．

これは cons が使われないで，他の連結方法を使うことを除けば， cons を使って "すべての" パターンを連結するのに非常に似ている．

概略は以下のようになる．

• リストが空であれば，0か他の定数を返す
• そうでなければ，リストの先頭 (リストの CAR) に処理する
  • そして，+ か他の連結関数を使って， 処理された要素を連結する
  • リストの残り (CDR) に再帰呼び出しを行う

例をあげよう

(defun add-elements (numbers-list)
  "Add the elements of NUMBERS-LIST together."
  (if (not numbers-list)
      0
    (+ (car numbers-list) (add-elements (cdr numbers-list)))))

(add-elements '(1 2 3 4))
    => 10

See 節 Making a List of Files にある例もこのパターンであ る．

再帰のパターン: keep (2004/08/10)

3番目の再帰パターンは keep パターンと呼ばれる．再帰パターン keep では，各リストが確認され，基準に合う要素の結果だけが結果と して得られる．

これもまた，"every"パターンととてもよく似ている．異なるのは，基準に合 わないと無視される点だ．

このパターンは3つの部分を持つ．

• もしリストが空であれば，nil を返す．
• もしそうでなければ，リストの先頭 (リストの CAR) を確認し， 基準に合えば
  • 要素を処理し，cons を使って連結する
  • リストの残り (CDR) を再帰呼び出しで処理する．
• そうでなく，リストの先頭 (リストの CAR) が基準に合わなければ
  • その要素を無視する．
  • そして，リストの残り (CDR) を再帰呼び出しで処理する．

これは cond を使った例である．

(defun keep-three-letter-words (word-list)
  "Keep three letter words in WORD-LIST."
  (cond
   ;; 最初に，再帰条件: 停止条件
   ((not word-list) nil)

   ;; 2番目に，再帰条件: 実行すべき時
   ((eq 3 (length (symbol-name (car word-list))))
    ;; combine acted-on element with recursive call on shorter list
    (cons (car word-list) (keep-three-letter-words (cdr word-list))))

   ;; 3番目に 再帰条件: 無視すべき要素の時
   ;;   次段式で短くなったリストで再帰呼び出し
   (t  (keep-three-letter-words (cdr word-list)))))

(keep-three-letter-words '(one two three four five six))
    => (one two six)

停止すべき時の確認として nil を使う必要がないのはもちろんのこと である．そして，もちろん，これらのパターンを組み合わせることもできる．

10.3.8 待機なしでの再帰 (2004/08/10)

関数 triangle-recursively を実行した時に何が起こるのかをまた考 えてみよう．見てみると，途中の計算はすべての計算が実行されるまで，延期 されるのが分かるだろう．

以下は関数定義である．

(defun triangle-recursively (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
  (if (= number 1)                    ; 再帰条件
      1                               ; 真の場合の動作
    (+ number                         ; 偽の場合の動作
       (triangle-recursively          ; 再帰呼び出し
        (1- number)))))               ; 次段式

この関数を引数 7 で実行した時には何が起こるだろうか？

関数 triangle-recursively の最初のインスタンスは数 7 に2番目の triangle-recursively のインスタンス (引数は6)による結果を追加する． つまり，最初の計算は

(+ 7 (triangle-recursively 6)

となる．

triangle-recursively の最初のインスタンス (小さなロボットとし て考えたいかもしれない) は仕事を完了できない． (triangle-recursively 6) の計算のために，2番目のインスタンス(つ まり，2台目のロボット)に計算処理をまかせなければいけない．2番目のもの は最初の1つ目とは完全に異なる．専門的には"異なったインスタンス化"であ る．別の言い方をすると，異なるロボットである．このロボットは最初のもの と同じモデルであり，再帰的に数を計算する．しかし，異なった製造番号を持っ ている．

そして，(triangle-recursively 6) は何を返すのだろうか？この関数 は，数 6に引数 5 で triangle-recursively を評価した値を追加する． ロボットの隠喩を使えば，他のロボットに助けを頼むのだ．

今，全体は以下のようになる．

(+ 7 6 (triangle-recursively 5)

さて，次に何が起こるだろうか？

(+ 7 6 5 (triangle-recursively 4)

最後の時を除くと，triangle-recursively が呼ばれるたびに，プログ ラムの他のインスタンス(他のロボット)を作り，計算をしてくれるように頼む．

結果として，全体では以下のような式ができ，実行される

(+ 7 6 5 4 3 2 1)

この関数では，最初の計算は2番目が実行されるまで待ち，2番目は3番目が実行されるまで待 ちといった設計になっている．各関数が処理を待っているため，コンピュータ は何が待っているかを記憶しておかなければならない．このことは，例のよう に数段階の処理であれば問題にはならない．しかし，多くの段階からなるよう なプログラムでは問題になる可能性がある．

10.3.9 待機なしの解決 (2004/08/09)

待機させるような処理の問題を解決するには処理を待機させないように書くこ とである(10)．このためには，異なった パターンで書く必要がある．多くの場合，"初期化" 関数と "援助" (ヘルパー)関数と いう2つの関数を書く必要がある．

"初期化"関数は仕事を開始させ，"援助"関数が実際の処理を行う．

以下に数を加算する2つの関数定義をあげる．これらはとても単純だが，理解 しにくい．

(defun triangle-initialization (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
This is the `initialization' component of a two function
duo that uses recursion."
  (triangle-recursive-helper 0 0 number))

(defun triangle-recursive-helper (sum counter number)
  "Return SUM, using COUNTER, through NUMBER inclusive.
This is the `helper' component of a two function duo
that uses recursion."
  (if (> counter number)
      sum
    (triangle-recursive-helper (+ sum counter)  ; sum
                               (1+ counter)     ; counter
                               number)))        ; number

両方の関数を評価することでインストールし，以下の2の列で triangle-initialization を呼んでみよ．

(triangle-initialization 2)
    => 3

"初期化"関数は"援助"関数の最初のインスタンスを 0，0，ある数(3角形の列 の数)という3つの引数で呼ぶ．

"援助" 関数に渡される最初の2つの引数は初期値である．これらの値は triangle-recursive-helper が新しいインスタンスを呼ぶたびに変更 される (11)

1列しかない3角形の時，何が起こるか見てみよう(この3角形には1個しか小石 がない)

triangle-initialization は引数を 0 0 1 で援助関数を 呼ぶ．援助関数では (> counter number) という条件式を実行する．

(> 0 1)

そして，結果が偽であると分かり，if 文の中にある偽の時に実行され る処理を実行する．

    (triangle-recursive-helper
     (+ sum counter)  ; plus と counter を足す => sum
     (1+ counter)     ; counter に1を足す => counter
     number)          ; number はそのままにする

以下のように計算するだろう．

(triangle-recursive-helper (+ 0 0)  ; sum
                           (1+ 0)   ; counter
                           1)       ; number
以下になる

(triangle-recursive-helper 0 1 1)

また，(> counter number) が偽であり，そして，また Lisp インター プリタは新しい引数で新しいインスタンスを作成し， triangle-recursive-helper を評価するだろう．

この新しいインスタンスは以下のようになるだろう

    (triangle-recursive-helper
     (+ sum counter)  ; plus と counter を足す => sum
     (1+ counter)     ; counter に1を足す => counter
     number)          ; number はそのままにする

以下になる

(triangle-recursive-helper 1 2 1)

この場合，(> counter number) が真になる! だから，このインスタン スは期待通り，合計値である 1 を返す．

今度は triangle-initialization に引数 2を渡して，2列の3角形にい くつの小石があるか試してみよう．

この場合，(triangle-recursive-helper 0 0 2) を呼び出す．

各段階で，各インスタンスは以下のようになるだろう．

                          sum counter number
(triangle-recursive-helper 0    1       2)

(triangle-recursive-helper 1    2       2)

(triangle-recursive-helper 3    3       2)

最後のインスタンスが呼ばれると，(> counter number) は真になるか ら，最後のインスタンスは sum の値である 3 を返すだろう．

このパターンはコンピュータのリソースを多く使うような関数を書く時に役立 つ．

10.4 ループの演習問題

• triangleに似た関数で、各行には行の番号の2乗の値があるような関数を 書いてみよ。 whileを使うこと。

• triangleに似た関数で、加算のかわりに乗算を使う関数を書いてみよ。

• これらの2つの関数を再帰的に書き直してみよ。 これらの関数をcondを使うように直してみよ。

• 段落内の各`@dfn'に対するインデックスをその段落の始めに作るような Texinfoモード用の関数を書いてみよ （Texinfoファイルでは、`@dfn'は定義に印を付ける。 詳しくは、以下を参照のこと． @xref{Indicating, , Indicating Definitions, texinfo}.) 節 `Indicating' in
  Texinfo Manual
  .)