前回のあらすじ: tail call optimizationっぽいコードを生成できた。
今回はsetqを使って再帰的なプログラムを書く。
setqは普通は次のように使う。
(setq var1 exp1) ; => value of exp1
var1 ; => value of exp1
(setq var1 exp1 ... varN expN) ; => value of expN
var1 ; => value of exp1
...
varN ; => value of expN
普通は変数と式を1つずつ書くことが多い（要出典）が、 変数と式を複数並べることもできる。 この場合は式の評価と代入が左から行われる。
(setq a 1 b a a 2) ; => 2
(list a b) ; => (2 1)
少々わかりにくいが、まずaに1が代入され、
次にbにaの値、すなわち1が代入される。
そして最後にaに2が代入される。
このように同じ変数が複数回出てきても良い。
setqを途中で抜けるような奇抜な式も書ける。
(prog () (setq x 1 y 2 x (return 3))) ; => 3
(list x y) ; => (1 2)
この場合、(return 3)が評価された時点でprogから抜けるため、
xに対する2回目の代入は起こらない。
さて、setqを途中で抜けるすべを見つけたところで、
setqだけでループを書けないだろうか。
最初に思いついたのは次のようなプログラムだ。
; It doesn't work in CLISP
(setq . #1=(var1 exp1 ... varN expN . #1#))
形の上ではexpNを評価してvarNに代入した後exp1に戻るのだが、
残念ながらこれはCLISPでも動かなかった。
どうも無限の引数というのはまずいらしい。
引数を有限にして、代わりにsetqを入れ子にすれば動く。
#1=(setq var1 exp1 ... varN expN extra-var #1#)
setqの最後の引数として式全体を入れている。
引数を偶数にするために追加の変数が必要だ。
では、これを使って実際に再帰的なプログラムを書いてみよう。 いつもおなじみの末尾再帰的な階乗だ。
(prog ((n 10) (acc 1) _)
#1=(setq
acc (if (= n 0) (return acc) (* n acc))
n (- n 1)
_ #1#))
; => 3628800
accとnに次々値が代入され、最後にreturnでprog式から抜ける。
ちなみに_に値が代入されることはない。
このreturnを使う方式では非末尾再帰的なプログラムは
（progを入れ子にしない限り）書くことができない。
それでは面白くないのでreturnを消してみる。
(let ((n 10) (acc 1) ret)
#1=(setq
acc (if (= n 0) acc (* n acc))
n (- n 1)
ret (if (< n 0) acc #1#)))
; => 3628800
#1#をifで囲むことにより、素直なプログラムになった。
returnを使う例と異なり、retには最終結果が代入される。
一般化すると次のようになる。
#1=(setq var1 exp1 ... varN expN extra-var (if cond ret #1#))
これで非末尾再帰的なプログラムも書けるのだが、
この方式、大きな分岐を書くことができない。
各部分式にifを書くことはできるが、
次の変数が現れるところでに合流してしまう。
上の階乗の例でもifが2回現れている。
これはプログラムが複雑になると辛くなってくる。
どれほど辛いかを見るために、 次は非末尾再帰的な階乗を書いてみよう。
(let ((n 10) n% ret stk)
#1=(setq
n% n
n (- n 1)
ret (when (> n% 0)
(push n% stk)
#1#)
n% (if ret (pop stk) n%)
ret (if (= n% 0) 1 (* ret n%))))
; => 3628800
これはひどい。スタックを自分で管理することで複雑になったのは仕方ないが、
whenが1回、ifが2回現れる。必要以上に複雑な感じがする。
こんなコードを手で書くのは辛い。
これをもう少し簡単にできないだろうか。
変数の代入のたびにコードが合流してしまうのが本質的な問題だ。
であれば合流させなければ良い。
ifを常にsetqの最後に置き、
その後に処理が続く場合はsetqを入れ子にすれば良い。
(setq
var1 exp1
...
varX (if cond
(setq
varN expN
...
varY (if cond
(setq ...)
...))
...))
抽象的な例ではわかりにくいと思うので具体例を書く。
; tail recursive
(let ((n 10) (acc 1) ret)
#1=(setq
ret (if (= n 0)
acc
(setq acc (* n acc)
n (- n 1)
ret #1#))))
; => 3628800
; non tail recursive
(let ((n 10) ret stk _)
#1=(setq
ret (if (= n 0)
1
(setq _ (push n stk)
n (- n 1)
ret #1#
ret (* ret (pop stk))))))
; => 3628800
（少なくても私には）読み書きしやすいコードになったが、 その反面面白さも失われた感じがする。
(let ((m 2) (n 1) ret stk _)
#1=(setq
ret (if (= m 0)
(+ n 1)
(if (= n 0)
(setq m (- m 1)
n 1
ret #1#)
(setq _ (push (- m 1) stk)
n (- n 1)
n #1#
m (pop stk)
ret #1#)))))
; => 5
アッカーマン関数もこの通り、機械的に書けるのだが、
果たしてこれはsetqを駆使したと言えるのだろうか。
もともとは単一のsetqでプログラムを書けないかという思いつきだったのだが、
CLISPで動かなかったため、setqの入れ子を許した。
一度入れ子を許したら、コードを書きやすくするために、
入れ子を使うようになってしまった。
こうなると、本来の面白さが残っているのか非常に怪しい。
コードの書きやすさと面白さを両立するのは難しい。
2021-06-19