letrec ではまる
- 今まで明示的に (funcall f)と書いていたけどカッコ悪いので内部で(f) を (funcall f) とするようにマクロ展開子を作成中。
- LLVM 関数を直接呼び出す labels/labelcall を使うとちゃんと fib 31 を実行できるが、これはホントの Scheme には無い命令なので、将来的にはなくさなくてはならない。
- そして letrec と macro-expander を使った版では fib 31 が動かない。fib 10 くらいだと動く。うーん。あきらかに何かを食いつぶして落ちている。
- 末尾再帰の最適化がうまくいっていないのか、と思ったが、よく考えたらそもそも fib は末尾再帰的じゃないのだった。
- デジャブ。
非効率さ
理由が分かった。"Our current treatment of letrec and letrec* is extremely inefficient" と書かれてあって 4.節で修正することになっている。どのくらい非効率かというと、、
;; プログラム変換 (program-conversion '(letrec ((fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))) (fib 10))) => ;; 生成された極めて非効率なコード (labels ((G48533 (code (G48532) (G48530) (let ((G48531 (vector G48532))) (if (< (vector-ref G48531 0) 2) (vector-ref G48531 0) (+ (funcall (vector-ref G48530 0) (- (vector-ref G48531 0) 1)) (funcall (vector-ref G48530 0) (- (vector-ref G48531 0) 2)))))))) (let ((G48530 (vector #f))) (vector-set! G48530 0 (closure G48533 G48530)) (tail-funcall (vector-ref G48530 0) 10)))
呼び出される度に vector で領域を確保してる。lambda の n に代入できるようにするためなので、正しいといえば正しいのだけど、この無駄は LLVM にまるなげしても取り去れない。
ああ、fib はわたしのコンパイラもどきで動く数少ないプログラムだったのに。代入できるようになって、前に進んではいるのだけど、実に悲しい。