fletとlabels

common lisp lisp

CommonLispのfletとlabels的なものを(あらかじめ使えるものはlambdaしかない状況で)自分で実装する必要が出てきたので、その際のメモ。
なお、以下では煩雑になるためfuncall呼び出しの記述を省略している(実際にはScheme処理系で動作確認を行っていた)。

let

flet、labelsの前にまずはlambdaを使ったletの実現方法を考える。

;; 以下のように変換可能
(let ((a 10)
      (b 20)
      (c 30))
  (list a b c))
   ↓
((lambda (a b c)
   (list a b c))
 10 20 30))
; => (10 20 30)

flet

上のようにしてletが使えると仮定した場合、fletと同じ機能を実現するのは簡単。

;; 単に変数に(lambda ...)を束縛すれば良い
(let ((hello (lambda (x)
               (list 'hello x))))
  (hello 'world))
; => (HELLO WORLD)

labels

これがlabels(ローカル関数の再帰呼び出しが可能)になると少し難しくなる。
以下、fletと同様の方法で試した場合。

;; フィボナッチ数を計算
(let ((fib (lambda (n)
             (if (< n 2)
                 n
               ;; fibの再帰呼び出し
               (+ (fib (- n 2)) (fib (- n 1)))))))
  (fib 10))
; => ERROR: 再帰呼び出し部分でfib関数が見つからないと云われる

fib変数に束縛したlambdaの本体のコンテキストからは、fib変数が見つからないため、エラーとなる。
再帰呼び出しに使用するfib関数を明示的に引数を渡すようにすれば、問題は解決する。

(let ((fib (lambda (n fib) ; 第二引数に常にfib関数を渡すようにする
             (if (< n 2)
                 n
               (+ (fib (- n 2) fib) (fib (- n 1) fib))))))
  (fib 10 fib))
; => 55

ただ、上の方法の引数の形が変わってしまうのが難点。
若干複雑にはなるが、以下のようにクロージャを使って再帰関数を持ち回すようにすれば、引数及び本体の形はほぼ変わらないので、マクロなどで生成するのは楽になる(ように思う)。

(let ((fib-rec (lambda (fib-rec) ; 再帰関数を引数に渡す　
                 (lambda (n)
                   (let ((fib (fib-rec fib-rec))) ; 再帰関数の情報を埋め込んだfib関数を返す
                     (if (< n 2)
                         n
                       (+ (fib (- n 2)) (fib (- n 1)))))))))
  (let ((fib (fib-rec fib-rec))) ; 再帰関数の情報を埋め込んだfib関数を返す
    (fib 10)))
; => 55

これでローカル関数の再帰呼び出しはできるようになったのでは、マクロを使ってシンタックスを整えれば、labelsが実現できることになる。

  • -

以前に、何でCommonLispにはfletとlabelsの二つがあるのか、とかOcamlでletとlet recが分かれているか、とか少し疑問に思ったことがあったように思うけど、少し理由が分かった気がする。