Let's start Scheme

2010-06-22

letのフレーム

A正規化の話だったりする。
たとえばこんなコード(変な数字が入ってるのはα変換後だから)
(define
 tarai
 (lambda
  (x.1 y.2 z.3)
  (if
   (not (< y.2 x.1))
   y.2
   (tarai
    (tarai (- x.1 1) y.2 z.3)
    (tarai (- y.2 1) z.3 x.1)
    (tarai (- z.3 1) x.1 y.2))))
こいつをA正規形にするとこうなる
(define
 tarai
 (lambda
  (x.1 y.2 z.3)
  (let
   ((#:G267 (< y.2 x.1)))
   (let
    ((#:G268 (not #:G267)))
    (if
     #:G268
     y.2
     (let
      ((#:G269 (- x.1 1)))
      (let
       ((#:G270 (tarai #:G269 y.2 z.3)))
       (let
        ((#:G271 (- y.2 1)))
        (let
         ((#:G272 (tarai #:G271 z.3 x.1)))
         (let
          ((#:G273 (- z.3 1)))
          (let
           ((#:G274 (tarai #:G273 x.1 y.2)))
           (tarai #:G270 #:G272 #:G274)))))))))))
見てのとおりコードが増大。それだけならまだいいのだが(よくないが)、問題はコードの増大に伴ってletが出現していること。
前回、継続周りで不具合が起きることを踏まえて、letが現れたらフレームを作るようにコンパイラとVMを修正したのだが、その影響で単なるたらいまわし関数がスタックオーバーフローを起こすようになった。
原因は、この大量のlet。これだけコードが増大すれば当然VMのインストラクションも増大する。どれだけ影響があるかスタックを1000から10000にして上記の関数でベンチマークをとってみた。
4秒が14秒に・・・orz

後の最適化がしやすいようにと思ってのA正規化だが、ちょっとないなぁ・・・
今のところこいつの恩恵って、変数の寿命がわかりやすいことだけだし・・・
どうしよう。

No comments:

Post a Comment