Schemeのお勉強その6 スコープについて(後編)

再帰と関数内関数

　理由は良く知りませんが、Lisp/Scheme では繰り返し処理には再帰が好まれます。どんなループも再帰に変換できる、ということを昔C言語で試行錯誤したことがありますが、どんな内容だったかは覚えていません。（このテーマはまた後日）。
　再帰といえばおなじみ階乗計算。

;; 階乗計算
(define (fact n)
    (if (= 1 n) 1
        (* n (fact (- n 1)))))

　前回の「型チェック付きadd関数」に習って、安全な fact 関数を作ってみましょう。

;; 安全な階乗計算
(define (fact n)
  ;; 関数内でローカルなループ（再帰）関数を定義
  (define (loop n)
    (if (= 1 n) 1
        (* n (loop (- n 1)))))
  ;; fact関数の処理実行部
  (cond
   ((not(number? n)) 0)
   ((< n 0) 0)
   (else (loop n))))

　前回の add は関数内関数を定義する意義が薄い「例題のためのコード」でしたが、この fact の場合それなりの意義があります。最初に書いた fact 関数内で型チェックを行うと、再帰呼び出しのたびに型チェックが行われることになります。チェックは最初の一回だけで十分ですから、チェックとループを分離するこちらの方法のほうがコスト的に有利です。

再帰と lambda

　では、lambda を使って書いてみましょう。……と途中まで書いて手が止まります。無名関数じゃ再帰がかけない。自分自身を呼び出すには自分自身をあらわす名前が必要です。しかし、define で名前を付けたらそれは普通に関数定義するのと一緒。そこで let を使ってレキシカル変数を lambda 式で作られるクロージャに束縛してみましょう。
　擬似コードだとこうです。最終的には let の前に引数チェックが入りますが問題をシンプルにするために、ここでは省略します。

;; let を使った fact (擬似コード)
(define (fact n)
  (let ((loop (lambda(n)
　　　　　　　　　( #|名前loopで自己再帰を行う処理|#))))
    (loop n)))

　実際にはこうなります

;; let を使った fact
(define (fact n)
  (let ((loop (lambda(n)
		(if (= 1 n) 1
		    (* n (loop (- n 1))))))) ;[1]
    (loop n)))

　ところが、このコードは実行時に [1] の行でエラーになります。

(fact 10) ;=> ERROR: unbound variable: loop

　let の初期化リストの初期値は、let の外側のスコープに属しています。したがって、lambda からはレキシカル変数 loop は見えないんですね。確かに理屈は合います。
　ところで let とはスコープの扱いが異なる let* というスペシャルフォームがありました。let* は同じ機能を let でも実現できます。

;; let* の機能を let で実現

(let* ((x 1)(y x))
  (list x y))       ;=> (1 1)

(let ((x 1))
  (let ((y x))
    (list x y)))    ;=> (1 1)

　上の式は２つとも等価です。let* は、ネストしたレキシカル変数定義をフラットにかけるようにしたものです。ちなみに let の初期化リストで複数のレキシカル変数を導入すると、変数の初期化の順序は保証がありません。しかし let* では左側から初期化が行われることが保証されています。上のコード比較を見れば自明でしょう。
　では、let* を使えば、lambda で再帰が出来るでしょうか？ダメなようです。let* は前で定義されたレキシカル変数(x)を、後ろの定義(y)で参照するためのフォームです。しかしここでやろうとしているのはレキシカル変数の名前を、そのレキシカル変数自身の初期値(S式)の中で参照したいという若干無茶な要求だったのです。

letrec

　実はその無茶を通すフォームが Scheme には用意されています。letrec というスペシャルフォームです。

;; letrec を使った最小のコード
(letrec ((f (lambda() f)))
    (eq? f (f)))            ;=> #t

　レキシカル変数 f は lambda式の評価値、クロージャに束縛されます。クロージャは単純に変数 f の値を返しているだけです。変数定義後に行っているのは、eq? による比較で、 f 自身と f の評価値（返り値）を比較しています。eq? は二つのオブジェクトが同じインスタンスであるかどうかを調べる述語ですから、letrec式の値が #t であるということは、f は自分自身を返している、つまりクロージャが自分自身に束縛されたレキシカル変数 f を参照できていることになります。
　letrec の機能を示せる最小のコードを追求したらこのようになったんですが、それで分かったことは letrec が意味を持つのは再帰クロージャでレキシカル変数を束縛する時と言えそうです。let-recurse を略して letrec ですね。
　ちなみに、ここで書いた最小コードのような説明はあまり見かけません。letrecの解説ではなぜか整数の奇遇判定 odd, even を相互再帰で書く例をあげるのがセオリーのようです。たぶんそれは、自己再帰を行うクロージャには letrec よりも便利な書き方が用意されているからではないかと思います。
　letrec のまとめとして、安全なfact を letrec を使って書いてみましょう。

;; 安全な階乗計算 (letrec版)
(define (fact n)
  (cond
   ((not(number? n)) 0)
   ((< n 1) 0)
   (else (letrec ((loop (lambda(n)
			  (if (= 1 n) 1
			      (* n (loop (- n 1)))))))  ; クロージャ loop の定義
	   (loop n)))))                                   ; クロージャ loop の評価

名前付き let

　letrec より便利な自己再帰記述方法とは、名前付き let という let式のバリエーションです。

;; 安全な階乗計算 (名前付きlet版)
(define (fact n)
  (cond
   ((not(number? n)) 0)
   ((< n 1) 0)
   (else (let loop ((n n))
	   (if (= 1 n) 1
	       (* n (loop (- n 1))))))))

　letrec とは異なり、レキシカル変数導入部分は普通の let と同じです。仮引数を導入し実引数で初期化を行っているだけです。普通の let と違うのは、let とレキシカル変数導入部の間に識別名 loop を挿入しているところです。その識別名を使って再帰処理を記述しています。
　letrec はクロージャに名前をつけるだけなので、あとでそのクロージャを評価する必要がありました。それに比べ名前付きletはダイレクトに再帰処理が式の中に書かれているので改めて評価をする手間も減っています。
　しかしなんでこのようなことが可能なんでしょうか？そういう仕様といえばそれまでですが、想像すると let 式は内部で暗黙のうちにクロージャを作って評価しているのではないでしょうか？であれば、式ブロック（=クロージャ）に名前をつけたり再帰させたりということができそうな気がします。
　識別名 loop が単なるラベルで goto ジャンプしているだけだと、再帰におけるスタック管理など実装が無駄に複雑になりそうですし。