前回のあらすじ: 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