Common Lisp、Scheme でループと言えば、まず do 式が思い浮かびますが、numb-lambda では敢えて do 式をサポートしていません。
Scheme は、その言語仕様で末尾再帰（ tail recursion ）の実装を必須としています。
末尾再帰、あるいは尾部再帰は再帰呼び出し（recursive call）を行ってもスタックが成長することはないのです。それは、再帰を繰り返してもスタックオーバーフローが発生しないということです。以下、本稿では末尾再帰をテイルリカージョンと呼びます。また、再帰をリカージョンと呼びます。
ところで、リカージョンを行うには関数が必要であり、それはループとは違うではないかと思われるかも知れません。Scheme では let 式にラベルを付けることができます。Schemeでは、let 式のラベルを使うことでリカージョンを実行できます。これがループを実現するのです。*1
しかし、先ずは関数を使ってリカージョンを行ってみましょう。
禁断の無限ループ
状況が許せば以下のコードを実行することでテイルリカージョンを体験することができます。ただし、共有している（とくにレンタル）サーバーでは実行しない方が無難です。理由はCPUを占有してしまうからです。自分の管理しているPCで実行するのが妥当です。読むだけで留めておいても構いません。しかし、環境が許すなら、ぜひ実行してみてください。
> (define foo
(lambda ()
(foo)))
> (foo)
ここで重要なのはスタックオーバーフローしないことです。lambda 式の本体には複数の式を書くことが出来ますが、その最後（末尾）の式で再帰をするとテイルリカージョンとなります。しかし、末尾の式であっても、リターンして演算をしなければならないものはテイルリカージョンとはなりません。
まともなループ
今度は、リターンするループを書いてみましょう。
ここで注意していただきたいことがあります。今回は関数内で副作用を多用しますが、LISP のような関数型プログラミング言語では可能なら副作用を避けるスタイルが良いプログラムとされています。まだ、データを積算する方法を学んでいないため、このようにしています。データを積算するには、例えばリストを用います。リストについては次回以降で説明します。
> (define bar
(lambda (i)
(if (>= i 1000000)
i
(begin
(display i)
(newline)
(bar (+ i 1))))))
> (bar 0)
0
1
2
3
.
.
.
1000000
>
(>= i 1000000)の式が #t となるとき、if 式は、i を返し、その後、リカージョンは起きません。もうひとつ関数を書いてみましょう。
> (define fib
(lambda (a b n)
(if (> n 0)
(let ((t (+ a b)))
(display a)
(newline)
(fib b t (- n 1))))))
> (fib 1 1 10)
1
1
2
3
5
8
13
21
34
55
>
> (define fib-revised
(lambda (n)
(define body
(lambda (a b n)
(if (> n 0)
(let ((t (+ a b)))
(display a)
(newline)
(body b t (- n 1))))))
(body 1 1 n)))
> (fib-revised 10)
1
1
2
3
5
8
13
21
34
55
>
リカージョンの停止条件が、どこだか判りますか。
ところで、シンボル body にバインドされた値（lambda 式）は、それを内包する lambda 式からは参照できますが、その外側からは見えません。
> (body 1 1 10)
net.prizo.scmlib2.sc_exception: unbound variable: body
at net.prizo.scmlib2.symbol.eval(symbol.java:53)
at net.prizo.scmlib2.environ.eval(environ.java:73)
at net.prizo.scmlib2.pair.eval(pair.java:147)
at net.prizo.scmlib2.environ.eval(environ.java:73)
at net.prizo.scmlib2.scheme.run(scheme.java:79)
at java.lang.Thread.run(Thread.java:745)
; unbound variable: body
それでは、次にラベル付き let 式の一般形を示します。
(let <シンボル> ((<シンボル> <式>)... ) <式>... )
この形式の最初の<シンボル> がラベルとなります。因みに Common Lisp の let 式にラベルは使えません。これは、（おそらく）Scheme 固有の機能です。
これを使って、
fib-revised 関数を書き換えてみます。*2
> (define fib-revised^2
(lambda (n)
(let loop ((a 1)(b 1)(i 0))
(if (< i n)
(let ((t (+ a b)))
(display a)
(newline)
(loop b t (+ i 1)))))))
> (fib-revised^2 10)
1
1
2
3
5
8
13
21
34
55
>
ところで、どんなとき、テイルリカージョンになるのでしょうか。一般に 関数を使う ときは、コール＆リターンが原則です。しかし、本来コールを書くべき所にジャンプを書くことができる場合があります。コールとジャンプの違いですが、コールは次のような動作をします。（あくまでモデルです）
- 呼び出す関数が処理を終えたとき戻るべきアドレスをスタックに積みます。
- 高級言語は一般にスタックフレームのように仮引数とローカル変数を格納する領域（環境）を作ります。
- 関数の入口となるアドレスにジャンプします。
- 適宜、環境にローカル変数を追加します。
- 関数が実行されます。
- 関数が処理を終えるとスタックフレームや環境といった領域を開放し、さらにスタックから戻るべきアドレスを取り出して、そこにジャンプ（これがリターンにあたる）します。
これに対して、テイルリカージョンでは、次のような条件のときコールの代りにジャンプだけすることが可能です。
- lambda 式の本体部分など、式の並びの最後の式になっているとき。つまり、呼び元に戻って他の式を評価する必要がないとき
- 次に呼び出す関数が現在使っているスタックフレームや環境といった領域を再利用できるとき。これは、つまり、リカージョンになっていることを意味します。
以上、ふたつの条件を満足しているときテイルリカージョンとなります。このとき、同一のスタックフレームや環境中にあるバインディングを修正した後、ジャンプするだけになります。元の関数に戻る必要がないのです。
難しい内容かも知れませんが、使い方は今後サンプルをいくつか見ていけば理解できます。そして、処理系（中間コードコンパイラ）を実装すれば完全に理解することができますので心配は無用です。
ここで、先の100万回ループを let 式を用いて書き直してみましょう。
> (let f ((i 0))
(if (>= i 1000000)
i
(begin
(display i)
(newline)
(f (+ i 1)))))
0
1
2
3
.
.
.
999999
1000000
>
> (define baz
(lambda (n)
(let e ((i n))
(if (>= i 0)
(begin
(e (- i 1))
(display i)
(newline))))))
> (baz 10)
0
1
2
3
4
5
6
7
8
9
10
> (baz 1000000)
...
ところが、
MzScheme v372 [cgc] では、なんと 1千万回でも大丈夫でした。蛇足ですが、次のように java 起動事に -Xss オプションを与え、Java VM のスタックサイズを64MBに調整して、numb-lambda を起動してみると、25万5千回までは動作しました。
java -Xss64m \
-cp ${HOME}/lib/prizo.jar net.prizo.scmlib2.scheme <<EOF 2>&1 |\
less
(define baz
(lambda (n)
(let e ((i n))
(if (>= i 0)
(begin
(e (- i 1))
(display i)
(newline))))))
(baz 255000)
EOF
筆者の環境（32bitマシン）ではハードリミットの都合上スタックサイズは64MBが限界でした。
MzSchemeではスタックの代りにヒープを消費しているようですので、かなり丈夫です。それでも、1千500万回では流石に音を上げました。*3今回は以上です。ところで、リカージョンというのは数学的帰納法によく似ていると思いませんか。帰納法でプログラムの正しさが証明できればバグは飛躍的に減少します。
次回は、いよいよリストを取り上げましょう。（予定）
--
*1 関数なしでリカージョンができると言っても、それは字面上のことです。実際 let 式は、lambda 式のシンタックス・シュガーですから関数は暗黙のうちに生成され呼び出されているのです。
*2 これでも良い......
(define fib-revised^3
(lambda (n)
(let loop ((a 1)(b 1)(i 0))
(if (< i n)
(begin
(display a)
(newline)
(loop b (+ a b) (+ i 1)))))))