前回のあらすじ: 再帰的な式を使えば再帰的なプログラムが書けた。
今回は再帰的な関数を「関数を定義せず」書き直す。 まずは末尾再帰的な階乗を考えてみる。
(defun fact-tail (n acc)
(if (= n 0)
acc
(fact-tail (- n 1) (* n acc))))
(fact-tail 10 1) ; => 3628800
これを再帰的な式で表現しようとすると以下のようになる。
(let ((n 10) (acc 1))
#1=(... #1# ...))
まずfact-tailの呼び出しをletに書き換える。
それから関数の本体を#1=でラベル付けして、
再帰を#1#によって実現する。完成形はこちら。
(let ((n 10) (acc 1))
#1=(if (= n 0)
acc
(let ((n (- n 1)) (acc (* n acc)))
#1#))) ; => 3628800?
再帰する際に変数を書き換えるためletを使っているのに注意。
このプログラム、例によってCLISPでは動くが、SBCLでは動かない。
SBCLで動かすためには例によってlet-evalのお世話になる。
(defun let-eval (binds exp)
(eval `(let ,binds ,exp)))
(let-eval
'((n 10) (acc 1))
#1='(if (= n 0)
acc
(let-eval
`((n ,(- n 1)) (acc ,(* n acc)))
#1#))) ; => 3628800
letがlet-evalになり、各所にクォートが付いただけでほぼ同じだ。
これで（少なくても表面上は）関数を定義せずに等価なプログラムが書けた。
次は末尾再帰的でない階乗を考える。
(defun fact (n)
(if (= n 0)
1
(* (fact (- n 1)) n)))
これを再帰的な式に変換すると次のようになる。
(let ((n 10))
#1=(if (= n 0)
1
(* (let ((n (- n 1))) #1#)
n))) ; => 3628800?
*の引数としてletが現れて少々見づらいが、それ以外は同じだ。
SBCLで動かそうとすると次のようになる。
(let-eval
'((n 10))
#1='(if (= n 0)
1
(* (let-eval `((n ,(- n 1))) #1#)
n))) ; => 3628800
これも特に見どころはないだろう。
次はもう少し複雑な関数としてアッカーマン関数を考える。
(defun ack (m n)
(if (= m 0)
(+ n 1)
(if (= n 0)
(ack (- m 1) 1)
(ack (- m 1) (ack m (- n 1))))))
(ack 2 1) ; => 5
ackの引数としてackを使っているのが特徴だ。
これを再帰的な式に変換すると次のようになる。
(let ((m 2) (n 1))
#1=(if (= m 0)
(+ n 1)
(if (= n 0)
(let ((m (- m 1)) (n 1)) #1#)
(let ((m (- m 1))
(n (let ((m m) (n (- n 1))) #1#)))
#1#)))) ; => 5?
letの数がやたらと増えたが、注目すべきは一番最後のletだ。
これはletの内側で使われている。
#1#に直接引数を渡すようなことはできないため、
ackの内側のackはこのようにletを仲介する必要がある。
SBCLで動かすためには、やはりlet-evalを使う。
(let-eval
'((m 2) (n 1))
#1='(if (= m 0)
(+ n 1)
(if (= n 0)
(let-eval `((m ,(- m 1)) (n 1)) #1#)
(let-eval
`((m ,(- m 1))
(n ,(let-eval `((m ,m) (n ,(- n 1))) #1#)))
#1#)))) ; => 5
機械的に変換できるため特に見どころはない。
次は相互再帰的な関数を考える。
(defun even? (n)
(if (= n 0)
t
(odd? (- n 1))))
(defun odd? (n)
(if (= n 0)
nil
(even? (- n 1))))
(even? 6) ; => T
(odd? 6) ; => NIL
これを同様に変換すると次のようになる。
(let ((n 6))
#1=(if (= n 0)
t
(let ((n (- n 1)))
(if (= n 0)
nil
(let ((n (- n 1))) #1#))))) ; => T?
これでCLISPでは動くのだが、少々問題がある。
これはeven?を呼び出すための式であり、
odd?を呼び出そうとすると式を作り直さなければならない。
odd?の本体を#2=でラベル付けしても、そのままではeven?が呼ばれてしまう。
これを回避するには、全体をクォートしてから#n#でラベルを参照すれば良い。
(let ((even-odd
'#1=(if (= n 0)
t
(let ((n (- n 1)))
#2=(if (= n 0)
nil
(let ((n (- n 1))) #1#))))))
(print (let ((n 6)) #1#)) ; T
(print (let ((n 6)) #2#)) ; NIL
'done) ; => DONE?
letでeven-oddを定義しているが、実のところこれには意味がない。
クォートした式の値を捨てれれば何でも良い。
これにより、#2#でodd?を呼ぶことができるようになった。
SBCLで動かす方法はこれまでと同じだ。
(let ((even-odd
#1='(if (= n 0)
t
(let-eval
`((n ,(- n 1)))
#2='(if (= n 0)
nil
(let-eval `((n ,(- n 1))) #1#))))))
(declare (ignore even-odd))
(print (let-eval '((n 6)) #1#)) ; T
(print (let-eval '((n 6)) #2#)) ; NIL
'done) ; => DONE
even-oddを使わないとSBCLが大激怒するのでdeclareを付け加えた。
自画自賛だが、思いつきで作ったlet-evalという抽象化はなかなかうまく動く。
この目的以外で使いみちがあるのかは分からないが。
ここまでできるようになれば、かなりの関数を再帰的な式に変換できるだろう。 もちろん高階関数やクロージャなどは実現できないが、そこは諦めてもらいたい。
さて、最初に『今回は再帰的な関数を「関数を定義せず」書き直す』と書いたが、
これは本当だろうか。defunやflet、lambdaが現れないという点では
関数を定義していないと言えるが、letはある意味では関数定義だ。
再帰的な式で表現された階乗をもう一度見てみよう。
(let ((n 10))
#1=(if (= n 0)
1
(* (let ((n (- n 1))) #1#)
n))) ; => 3628800?
この式にはletが2回現れるが、これらはlambdaに書き換えることができる。
((lambda (n)
#1=(if (= n 0)
1
(* ((lambda (n) #1#) (- n 1))
n)))
10)
この式を見て「関数を定義していない」というのは少々無理があるだろう。
これまでに出てきた式は実のところ、非再帰的な無名関数を次々呼んでいたのだ。
前回のfletの例と同じだ。
ところでこの式、SBCLは無論、CLISPでも動かない。
lambdaを使うと最適化をしようと色気を出してしまうのだろうか。
これを動かすためにはapply-evalという新しい関数を用意する。
(defun apply-eval (fn &rest args)
(eval `(apply ,fn ',args)))
(apply-eval
'(lambda (n)
#1=(if (= n 0)
1
(* (apply-eval '(lambda (n) #1#) (- n 1))
n)))
10) ; => 3628800
より一層、関数を呼び出している感じが強くなった気がする。
実のところ関数は消えておらず、消えたのは関数の名前だけだったというオチだ。
これまで#1=(... #1# ...)という形の式が何度も現れたが、
これらはすべて自由変数を含んでいた。
例えば階乗の例で#1=で参照される式は変数nを含んでいたが、
このnは#1=の中では自由変数だ。
#1#を単独で評価することはできず、外側にletやlambdaを書くことで
初めて評価できるようになる。
自由変数を含んでいなければ（副作用がない限り）常に同じ結果になるため、
再帰的なプログラムを書くためには自由変数は必須だろう。
自由変数を束縛するためには（字面上はともかく本質的には）
関数が必須であるため、関数から逃れることはできない。
グローバル変数とsetqを使って関数から逃れる手法については
読者の演習問題とする。
2021-05-28