#:g1: fletで再帰

Posted 2021-05-23 14:49:07 GMT

こちらの記事を読んで、そういえばSchemeのプログラムをCommon Lispに移植する際などのLisp1→Lisp2変換で似たようなことが必要になるなと思ったので、自分が良く使う方法をまとめてみます。

まず、fletは少し特殊なスコープを持つ構文で、defunやlabelsと違って、同じ階層のローカル関数を呼び出すことができません。

(flet ((fib (n)
         (if (< n 2)
             n
             (+ (fib (1- n))
                (fib (- n 2))))))
  (fib 20))
>>>Error: Undefined operator fib in form (fib (1- n)).
(flet ((fib (n) n))
  (flet ((fib (n)
           (if (< n 2)
               n
               (+ (fib (1- n))
                  (fib (- n 2))))))
    (fib 20)))
→ 37

ただ、同じ階層のローカル関数がスコープにないだけなので、ローカル変数として自分自身与えれば再帰できます。

(flet ((fib (n fib)
         (if (< n 2)
             n
             (+ (funcall fib (1- n) fib)
                (funcall fib (- n 2) fib)))))
  (fib 20 #'fib))
→ 6765

Schemeのletrec等の実装方法での常套句のように変数を代入してやる方法もあります。

(let ((fib #'identity))
  (flet ((fib (n)
           (if (< n 2)
               n
               (+ (funcall fib (1- n))
                  (funcall fib (- n 2))))))
    (setq fib #'fib)
    (fib 20)))
→ 6765

この手法はCommon Lispでも古典的なようで、Spice Lisp(1980年初頭)のコンパイラでのlabelsの実装(式変形)もこんな感じみたいです。

(def-cg labels cg-labels (x &body body)
  (let ((*fenv* *fenv*))
    (do ((defs x (cdr defs))
     (new-env *fenv*)
     (let-list nil)
     (setq-list nil)
     (name (new-internal-variable) (new-internal-variable)))
    ((atom defs)
     (setq *fenv* new-env)
     ;; With new *FENV* bindings in effect, compile the functions,
     ;; then the body.
     (cg-form
      `(let ,let-list (setq ,@setq-list) (progn ,@body))
      for-value))
      (push name let-list)
      (push `#'(lambda ,@(cdar defs)) setq-list)
      (push name setq-list)
      (push (cons (caar defs) name) new-env))))

これは、

(labels ((fib (n)
           (if (< n 2)
               n
               (+ (fib (1- n))
                  (fib (- n 2))))))
  (fib 20))

のような式を、大体下記のように変形します。

(let (.fib.)
  (flet ((fib (n) (funcall .fib. n)))
    (setq .fib. #'(lambda (n)
                    (if (< n 2)
                        n
                        (+ (fib (1- n))
                           (fib (- n 2))))))
    (fib 20)))
→ 6765

Common Lispではどういう時に使うか

多分あまり使わないと思いますが、Schemeのletrec系の構文を実装する際などには、Lisp1→Lisp2の変換が必要になるので、大体似たようなものを作ることになると思います。

(letrec ((fib (lambda (n)
                (if (< n 2)
                    n
                    (+ (fib (1- n))
                       (fib (- n 2)))))))
  (fib 20))
→ 6765

■

HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus