#はじめに
人間が思考の対象とする情報は、再帰的データ構造を伴っていることが多い、というよりは
再帰的な構造を伴った情報こそ人間の扱う情報である、と言っても過言ではないかも
しれません。 再帰的なデータ構造に寄り添った制御構造がLispやPrologの再帰関数や再帰
述語と言ってもいいでしょう。 そう言った制御構造を、私は敢えて繰り返しに圧し潰す
ことを幾度か試みて来ました。 そこには、スタックに積むオーバヘッドを節約したいとか、
スタックオーバフローを起こしづらいコードを書きたいとか言う意図が込められていました。
然し私の真の主張は再帰的制御構造を理解するのに、それを繰り返しに書き下すことは
大いなる助けになるのではないかというところにありました。
この記事は、そんな考えの元に私が、プログラミングを学ぶごく初期段階に於いて試みた
「"ハノイの塔"を繰り返しに圧し潰す」（当時はPascalで書いていました）試みを、
ISLispで再現したものです。 Lispを学び始めたばかりの頃の私にとってはこの試みは
困難を極めたものですが、同時に実りの多いものでもありました。
私は以前「Lispアドヴェントカレンダー2016」の最終日に「逆転ポインタ法による
ガーベジコレクションの実装とスタック無し再帰」という記事を投稿しました。
この記事はそれに於いて出題した「ハノイの塔をスタック無し再帰で書く」例題への
解答例でもあります。 なおこの記事に於いて私は、完全なるスタック無しで書く
ことは断念して、帰り先の決定にのみスタックを用いる決断をしたことを書き添えて
おきます。 完全なるスタック無しを示してみろ、とおっしゃる方は、先程のQiitaの
記事を参照してみてください。
尚、この記事の真の狙いについては、末尾のほうに記述があります。
#ハノイの塔について
さて、諸兄をバカにしているわけではありませんが、用語を統一するためにハノイの塔の
問題をここに再掲してみます。
n枚の、中央に穴の開いた円盤群があります。 1番目が一番小さく、一番大きなn番目に
行くに従って大きくなってゆきます。 円盤を通すべき棒が立った3つの置き場所
A、B、Cがあります。 Aにある円盤群を、全部Cに移さなくてはなりません。
但し、小さな円盤の上に大きな円盤を置くことは途中経過であっても許されません。
また、複数の円盤を同時に手に持つことも許されません。 なお、Bを円盤の
仮置き場として使うことは許されています。
この条件で円盤群を移動させる手順を示しなさい。
というもので確認して頂けると思います。 BとCは、置き換っている場合が
あるので注意して下さい。
#実際のコード
##再帰バージョン
このコードをいきなり非再帰で書くことには、意外に辛いものがありますので
（私にはそうです）まずは普通に再帰で書いてみます。 結果は、リストで
得られるように書いてみました。
(defun hanoi1(x y z n)
(cond ((<= n 1) (list 'MOVE 'DISC '1 'FROM x 'TO y))
(t (list (hanoi1 x z y (- n 1))
(list 'MOVE 'DISC n 'FROM x 'TO y)
(hanoi1 z y x (- n 1))
) ) ) )
(defun hanoi(n) (hanoi1 'A 'C 'B n))
という具合です。このコードは、OKI ISLisp ver 0.80 で検証しました。
これをいちいち説明することはそれこそLisper諸兄を侮辱することになるのでやめます。
補助関数hanoi1に於いてA,C,Bがx,y,zに置き換わることと、私のうっかりミスから
CとBの役割が置き換わってしまったことに注意してください。
hanoiに円盤の数nを与えると解が得られるようになっています。
##ｎをスタックに積まない
このコードを、順次非再帰に書き直してゆくこととします。
まず、ネスティングレベルが上がるときに、nの値は1だけデクリメントされます。
逆に下がるときにはインクリメントされて元に戻ります。
これに着目すると、nをスタックに積む必要がなくなります。
(defun prog23(f1 f2 f3) f2)
(defun hanoi2(x y z)
(cond ((<= n 1) (list 'MOVE 'DISC '1 'FROM x 'TO y))
(t (prog23
(setf n (- n 1))
(list
(hanoi2 x z y)
(list 'MOVE 'DISC (+ n 1) 'FROM x 'TO y)
(hanoi2 z y x)
)
(setf n (+ n 1))
) ) ) )
(defun hanoi3(x y z n0)
(setf n n0)
(hanoi2 x y z)
)
(defun hanoi4(n) (hanoi3 'A 'C 'B n))
hanoi4にnを与えると解が得られます。 ここでprog23があまりにも技巧的でご都合
主義的な存在なので書いていて頭が痛いです。 第1～第3引数をこの順で評価（実行）
して第2を持って帰るという関数です。
ここで利用しているのは再帰から戻ってきたときにnをインクリメントすれば復元
できるという事実です。 通常の再帰に於いては、値をスタックに積まない限り復元
できません。 そのことが、再帰が強力な手段であることの傍証になっています。
スタックに積まないと環境を復元できないようなコードを用いているからこそ強力な
プログラミングが現実のものとなっていることは普段諸兄が経験されている通りです。
##ｘ，ｙ，ｚをスタックに積まない
さて、x,y,zをスタックに積む必要がなくなれば、スタックに積むべきものはシステムが
勝手に積んでくれる（制御の流れの情報である）戻り先に関するものだけとなります。
そこで、x,y,zの動きに着目してみれば、最初のrecursionに於いてはyとzが入れ
替わっているだけです。 考えを単純にするために、戻ってきたら再びyとzを入れ
替えて元に戻しておくものとします。 次のrecursionに於いては、こんどはxとzが
入れ替わっています。 戻ってきたら、やはり単純ににするためにxとzを入れ替えて
おくことにします。 これによりx,y,zをスタックに積む必要がなくなります。
これをコードにすると、次の様になります。
(defglobal n nil)
(defglobal w nil)
(defglobal x nil)
(defglobal y nil)
(defglobal z nil)
(defmacro swap(p q) `(progn (setf w ,p)(setf ,p ,q)(setf ,q w)))
(defun prog23(f1 f2 f3) f2)
(defun hanoi5()
(cond ((<= n 1) (list 'MOVE 'DISC '1 'FROM x 'TO y))
(t (prog23
(setf n (- n 1))
(list
(prog23 (swap y z)(hanoi5)(swap z y))
(list 'MOVE 'DISC (+ n 1) 'FROM x 'TO y)
(prog23 (swap z x)(hanoi5)(swap x z))
)
(setf n (+ n 1))
) ) ) )
(defun hanoi6(x0 y0 z0 n0)
(setf x x0)(setf y y0)(setf z z0)(setf n n0)
(hanoi5)
)
(defun hanoi7(n)(hanoi6 'A 'C 'B n))
不必要に長いコードですが、hanoi7にnを与えると、解が得られます。
ここで、スタックに積まなくて済むようになった値を保持しておくためにグローバル
変数が使われています。 wは直後に出てくるswapの動作に必要なものです。
swapはやはり技巧的かつご都合主義的なもので、pとqを入れ替えるマクロです。
マクロをLispの最も強力な武器とする向きがありますが、私は関数evalが存在する
こととそれが再帰的に利用できることこそがLispの真骨頂だと考えており、この考えには
与しません。 swapの定義に於いて出現するprognは、第1引数～第n引数をこの順で
評価（実行）して第nをもって値とする技巧的な関数で（Lisp1.5に於いて導入された
ものだそうですが）ISLispに於いて標準で装備されています。 ここでは、その値は
利用されることなく、ただ引数を順に実行するためだけに利用されています。
prog23については先程と同様です。
（Lisp1.5に於いてprognはfexpr関数というもので定義可能でしたが、現代のLispに
於いてはマクロとして定義可能ですので、興味のある方は小手試しとしてどうぞ）
yとz、zとxの入れ替えを（引数を記述する順番ではなく）実際に明示的に行うことに
より、スタックに積むことなしに、環境の設定と復元を実現しています。
nの値の操作に関して前述したとおり、今回の技巧がうまくゆくのは単なる偶然に
よるものです。
再帰を利用する一般のプログラムに於いては、システムがどんどんスタックに積んで
ゆくことで環境の設定復元が行われるために問題解決がより単純に実現可能となります
実はこのことに注意喚起することこそ、この記事の真の狙いだったのです！
##完全な非再帰のために
さて、このコードに於いてはまだスタックに積まれるべきものが残っています。
前述した通り、recursionからの帰り先を決定するための情報です。 このままでは
スタック無しではありません。 非常に汚らしいコードになることさえ覚悟すれば、
それを明示的に行って完全なるスタック無しを実現することはそれほど困難なこと
ではありません。 ですがその様なコードを書くことは、Lispの精神に反すると思って、
あえて掲載を断念します。
例えば帰り先（それはnilかtだけで決定される）をつむ一次元配列を用意するだけで
実現が可能です。 （Basicでのプログラミングに慣れている方はその実際のコードが
すぐに思いつくかも知れません） ちょっとした小手試しとして、チャレンジして
みるのも悪くないかもしれません。
#最後に
最後に、この記事に於いては右括弧に妙なインデントが掛かっています。 どこでどう
インデントが掛かっているかよく見てください。 これはLisp入門の著者中西正和先生が
専ら用いられた方法で、括弧の対応関係を示してくれない原始的なテキストエディタに
於いて特に有効な方法です。 紙だけでコードを示すときにも意外に有効な
方法ですので、取り入れてみることをお勧めします。
最後まで読んで頂いてありがとうございました。
#おまけ
昔のヨーロッパに於いては、今日のグレゴリオ暦ではなく、教会暦と言うものが
使われていました。 それでは、１日の始まりは日没時とされています。 日没と
ともに（日付の改まった新しい日の）夜が始まる、とされているのです。
ですから今日の暦で言う12月24日の夜は、教会暦では12月25日の夜、という位置づけに
なるのです。24日をクリスマスイブと呼ぶのは、それがクリスマスの日の夜つまり
イブニングに当たるからなのですね。