2016/06/23

Self-callの書き換え

(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))みたいな非末尾再帰を自動的に(累積変数を導入して)末尾再帰に変えたら、なんて議論を見てちょっと思い出したのでメモっとく。

Gaucheでは、ローカル定義された関数の自己末尾呼び出しはただのジャンプになる。

gosh> (define (loop) (define (rec) (rec)) (rec))
loop
gosh> (disasm loop)
CLOSURE #<closure (loop)>
=== main_code (name=loop, code=0x139b340, size=4, const=0 stack=6):
signatureInfo: ((loop))
     0 LOCAL-ENV-JUMP(0) 0      ; (rec)
     2 RET 
     3 RET 

でも、トップレベル定義された関数への自己再帰呼び出しにはグローバル変数のルックアップが入る。 他の関数を末尾呼び出しするのと同じ。

gosh> (define (loop) (loop))
loop
gosh> (disasm loop)
CLOSURE #<closure (loop)>
=== main_code (name=loop, code=0x139b8a0, size=3, const=1 stack=3):
signatureInfo: ((loop))
     0 GREF-TAIL-CALL(0) #<identifier user#loop.13f2b40>; (loop)
     2 RET 

スタックは消費しないが、グローバル変数へのアクセスがひとつ余分に入るので、 マイクロベンチマークで多少差が出る。数値は忘れたが fibで数%くらいだったような気がする。

グローバル自己再帰を検出してローカル自己再帰に書き換えてしまうのは簡単なのだが それをやっていないのは、「ループ中にトップレベル束縛が書き換えられる」という 可能性があるからだ。これは確かCLの流儀に倣ったんだと思う。 CLではいつでも実行を中断してデバッガに落として環境を書き換えられるから。

ただ、Schemeはもうちょい静的寄りな感覚だし、R6RS風にモジュール外部からの トップレベル束縛の変更を禁止すれば(実はそういうフラグはもう実装してある)、 モジュールを読んだ時点でそのトップレベル束縛が変更され得るかどうかわかるので、 トップレベルへの自己再帰をローカル自己再帰に変えることはできる。

マイクロベンチマークで数%の速度を稼ぐのと自由度とを天秤にかけて 今は自由度を取ってるんだけど、冒頭のfactみたいにトップレベルでの 非末尾自己再帰を末尾自己再帰に書き換えるってところまでサポートするなら、 天秤を逆の方に傾けるメリットもあるかもしれない。

しかし、訓練されたSchemerは末尾呼び出しを無意識に書くから、そもそも そういう自動変換の需要は無いのではないか、という気もする。 いや、それは人間コンパイラとして馴らされてしまっただけなのかな。

Tags: Programming, Scheme, Gauche