Schemeでの効率のいいループの方法を考える

2013-12-11
#compiler #lisp

Schemeはご承知の通りループの構文がなくて、末尾再帰でループを実現する。

よく使うのはnamed letという構文で、例えば階乗の計算は

(let fact ((n 10))
  (if (= n 0)
      1
    (* n (fact (- n 1)))))

てな具合になる。簡単な実装法としては、named letはマクロによって変換されて、単純なラムダ式になる：

((lambda (fact)
   (set! fact (lambda (n)
                (if (= n 0)
                    1
                  (* n (fact (- n 1))))))
   (fact 10))
 '())

関数が自分自身を参照するためにローカル変数factへの代入が必要となっている。

しかしこの方法は（まともな処理系では最適化されるのかわからないけど、僕の参考にしている3impのスタックベースの）処理系の実装から考えるとあまりよろしくない。set!による代入を使うと、そのローカル変数はボックス化する必要があって、ヒープの確保が発生してしまう。なぜかというと、どこかから継続で使われる可能性があるので、スタック上に持っておくことができなくなるからである。しかしヒープの確保はコストがかかるのでできれば避けたい。

でヒープを使わないループの実現方法を考えたんだけど、関数に自分自身を引数に追加してしまうのはどうかと思いついた。

(let1 fact (lambda (self n)
             (if (= n 1)
                 1
               (* n (self self (- n 1)))))
  (fact fact 10))

これだとset!を使わないのでヒープの確保が発生しないので、軽くなるはず。

問題は、手書きで (fact fact n) などと書きたくないので、自動的に関数への引数を挿入する方法をどうするか。例えばmacroletのように局所的なマクロを定義できれば機械的にいけそうである。vallog: gauche に macroletを参考に、オレオレnamed-letマクロを

(define-macro (macrolet letargs . body)
  `(let-syntax
       ,(map (lambda (elm)
               (cons (car elm) `((,(with-module gauche.internal make-macro-transformer) (gensym) ,(cadr elm)))))
             letargs)
     ,@body))

(define-macro (named-let name vars . body)
  (let ((args (gensym))
        (self (gensym)))
    `(macrolet ((,name (lambda ,args `(,',self ,',self ,@,args))))
       (let1 ,self (lambda (,self ,@(map car vars))
                     ,@body)
         (,name ,@(map cadr vars))))))

のように定義してやると、

(named-let fact ((n 10))
  (if (= n 0)
      1
    (* n (fact (- n 1)))))

と素直に書けば自動的に変換できて、しかもヒープ確保なしで動く。やったね！

こういう変換をラムダリフティングというのかな。

関連記事

新着記事