再帰的なプログラムというのがあります。プログラムを書き始めたばかりの頃、そういうものがあるとは全く知らなかったときに再帰的なプログラムに出会ったときの衝撃は大きかったです。大学では情報処理の授業でFORTRANを習いましたが、今はどうか知りませんが少なくとも当時、仕様上再帰コールはできなかったはずです。再帰的なプログラムとは、FORTRANではないですが、次のようなもの。
架空の言語です。でもプログラミングを少しでもやっている人なら意味は分かるでしょう。例で説明します。 f(4) を計算しましょう。それには 4 * f(3) を計算しなければなりません。つまり4をかけ算する相手を計算するために、そこで再び自分自身をコールしなければなりません。 4 * f(3) の f(3) の部分を計算するために関数がコールされるのです。コールされた関数内部では 3 * f(2) を返すために、f(2) を求めなればなりません。また関数がコールされ、2 * f(1) が返されようとしますが、f(1) を求めるためにさらに関数をコールします。これは関数の定義のｘ == 1 のケースなので、return 1 で1が返されます。ここから逆に辿って、f(2) = 2 * f(1) = 2 が返り、f(3) = 3 * f(2) = 3 * 2 = 6 が返り、f(4) = 4 * f(3) = 4 * 6 = 24 が返ります。要するにこれはｘ！を計算するプログラムです。
多分当時のBASICも再帰コールはできませんでした。そういうわけで、初めて出会ったときには何かいけないことをしているような気がしたものです。不思議でした。上の関数ではｘという変数が使われています。f(4)をコールするとｘ＝4と代入されますが、これを計算するためにf(3)を求めなければならないのでした。そこでf(3)をコールすると、ｘ＝3と代入されます。ここで、「さっきｘに入れた4は上書きされて消えてしまったはず。大丈夫なのか？」と思ったのです。関数は1回しか定義されていません。関数f(x)の本体はひとつだけです。だからその内部にある変数ｘもひとつです。……実はここが誤りだったのですが、当時はそんなことは分かりません。
からくりを明かしてしまうと、変数は関数がコールされるたびに新しく用意される、ということです。メモリのどこに新しい変数を用意したのか、混乱しないように管理しなければなりませんが、原理はそういうことです。こうして再帰コール可能な関数が使えるようになるのです。再帰コールについては関係する話を書いています。併せてご覧ください。
高校生のときカシオのポケットコンピュータFX-702Pでプログラミングを始め、以来趣味でやってきました。Cの解説書などで「関数がコールされるとそこで使われる変数が使う領域がスタックに確保される」みたいな説明を読みましたが、自分で言語そのものを作った経験がないと分かった気がしません。具体的に自分でいじってみないとなかなかイメージできないのだと思います。
こんな感じで、言語を作ってみる、というのも面白いものです。日頃お世話になっている言語がいったいどのようにコンピュータをコントロールしているのか、身にしみて分かります。やはりコンピュータ、凄い機械です。どれだけ勉強できるのか。面白さ、コストパフォーマンス、どこをとっても凄いです……。
