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

2013-12-11
blog

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)))))

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

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