#:g1: letrecの紹介

Posted 2014-01-15 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の16日目です。

letrecとはなにか

 letrecは、Robert Smith氏作のSchemeのletrecをCommon Lispに再現したものです。

パッケージ情報

パッケージ名letrec
Quicklisp
CLiKihttp://cliki.net/letrec
Quickdocshttp://quickdocs.org/letrec

インストール方法

(ql:quickload :letrec)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。
といってもletrecのみですが…。

 Common Lispでletrecを再現するにあたっての問題は、関数と変数が別の空間に存在していることです。これをどう取り纏めるのか、ということになりますが、letrecパッケージでは、fletを利用しています。

(letrec:letrec ((fib (lambda (n)
                       (if (< n 2)
                           n
                           (+ (fib (1- n))
                              (fib (- n 2)))))))
  (fib 10))

これが

(LET (#:G4433)
  (FLET ((FIB (&REST #:ARGS-4434)
           (APPLY #:G4433 #:ARGS-4434)))
    NIL
    (SETF #:G4433
            (LAMBDA (N)
              (IF (< N 2)
                  N
                  (+ (FIB (1- N)) (FIB (- N 2))))))
    (FIB 10)))

こんな感じに展開されます。

 私もSchemeのプログラムを移植するにあたって同じ方式でletrecを作っていましたが、やはり皆考えることは同じようです。
問題になるのは、やはり末尾呼び出しの最適化で、こんなことをすると、

(letrec:letrec ((lp (lambda (x)
                      (if (zerop x)
                          :done
                          (lp (1- x))))))
  (lp 100000))
;!! Control stack exhausted (no more space for function call frames).

スタックが溢れてしまいます。
SBCLの場合は、デバッグ情報を減らす設定にすれば最適化してくれます。

(locally 
  (declare (optimize (debug 1)))
  (letrec:letrec ((lp (lambda (x)
                        (if (zerop x)
                            :done
                            (lp (1- x))))))
    (lp 100000)))
;=> :DONE

 READMEを読むと処理系依存のものも含めて改善パッチ募集中とのことです。
私もletrecでは色々試したりしていますが、最近labelsの定義をどうにかそのまま流用できないものかと考えています。

(defun extract-letrec-vars (definitions)
  (values (mapcar #'first definitions)
          (mapcar #'second definitions)))

(sb-c:def-ir1-translator letrec ((definitions &body body) start next result) (multiple-value-bind (forms decls) (sb-int:parse-body body :doc-string-allowed nil) (multiple-value-bind (names defs) (extract-letrec-vars definitions) (let* ((placeholder-funs (mapcar (lambda (name) (sb-c::make-functional :%source-name name)) names)) (placeholder-fenv (mapcar #'cons names placeholder-funs)) (real-funs (let ((sb-c:*lexenv* (sb-c::make-lexenv :funs placeholder-fenv))) (mapcar (lambda (name def) (sb-c::ir1-convert-lambda def :source-name name)) names defs)))) (loop :for real-fun :in real-funs :and placeholder-cons :in placeholder-fenv :do (sb-c::substitute-leaf real-fun (cdr placeholder-cons)) (setf (cdr placeholder-cons) real-fun)) (sb-c::processing-decls (decls nil real-funs next result) (let ((sb-c:*lexenv* (sb-c::make-lexenv :funs (pairlis names real-funs)))) (sb-c::ir1-convert-fbindings start next result real-funs forms)))))))

(letrec ((fib (lambda (n) (if (< n 2) n (+ (fib (1- n)) (fib (- n 2))))))) (fib 30)) ;=> 832040

一見上手く動くように見えますが、変数部がlambda式固定だったりと色々と問題があります。なかなかCommon Lispでletrecは難しい。

まとめ

 今回は、letrecを紹介してみました。
letrecも一発ものという感じですが、こういうのもQuicklispに申請できるんだ、という良い例かなとも思います。

comments powered by Disqus