情報科学実験II資料 (4)
最適化(1)

田浦

29/10/98

η reduction (または末尾呼び出しの最適化)

簡単にできて, なおかつ非常に重要な最適化を取り上げる. これがきれいにで きるのを見て, CPSはエライと思って欲しい.

例として, 以下のような関数定義をCPS変換してみる.

(define (f x)
  (g (+ x 1)))
得られるCPS関数定義は, 以下のようなものであろう.
[f (k6 x) 
   (+ [x 1] [v9] 
      [(fixs ([k7 (r8) (appb k6 (r8))]) 
         (appb g (k7 v9)))])]
ここで, k7が, gからreturnした後の計算を実行する継続である.

しかし, 見てもわかるように, k7が実際に実行する仕事は, 受けとった 値(つまりgの返り値)を, そのままfの継続(k6)に渡してい るだけである. これはもともとのSchemeのprogramにおいて, gの返り値 がそのままfの返り値になっていることからもうなずける結果である. k7の定義を関数的に読むと(そしてML的に書くと),

fun k7 r8 = k6 r8
ということであって, まさに,
k7 = k6
である, ということをしめしいている. そこで,
k7の使用をことごとくk6の使用に置き換えれば,
k7を作らずに済ますことができ, 結果としてcontinuation recordの生 成を省くことができる. 結果として,
[f (k6 x) 
   (+ [x 1] [v9] 
     [(appb g (k6 v9))])]
のような形にすることができる.

この最適化は簡単で,

ということをすればいい. この変換をη reductionと呼ぶ. (注) この最適化はもちろんFIXHに対しても同じように行なうことができて,

この最適化は, ある関数の呼びだし結果がそのままその外側の関数の呼びだし 結果になっているあらゆる場合に適用できる. ということは,

あらゆる末尾再帰を使ったloopに対して適用できる
といことになる. 例えば,
(define (fact n p)
  (if (= n 0)
      p
      (fact (- n 1) (* p n))))
という, ``tail recursive factrial'' programは,
[fact (k10 n p) 
      (fixs ([j11 (v12) (appb k10 (v12))]) 
        (= [n 0] [] 
           [(appb j11 (p)) 
            (- [n 1] [v15] 
               [(* [p n] [v16] 
                   [(fixs ([k13 (r14) (appb j11 (r14))]) 
                      (appf fact (k13 v15 v16)))])])]))]
のようにCPS変換される(かけ算はprimitiveであると仮定する). ここで, k13factの再帰呼び出しのために作られた継続で, 当然η reductionの対象となる(これはoriginalのprogramを見ても明らか). その他に もif文の際に導入されたFIXでも同様の変換を行なうことができる. η reduction後の結果は以下のようである.
[fact (k10 n p) 
  (= [n 0] [] 
     [(appb k10 (p)) 
      (- [n 1] [v15] 
         [(* [p n] [v16] 
             [(appf fact (k10 v15 v16))])])])]
これはfactが一度呼ばれてから一度もFIXを行なわずに計算できている という意味で,
Loop並に速い末尾再帰呼びだし
ということができる.

β-contraction, β-expansion (またはinline展開)

いわゆるinline展開で, これもCPS上で簡単にできる.

(APP f ( tex2html_wrap_inline308 ))
という式(APPはAPPfでもAPPbでも良い)において, fの 定義が以下:
(FIX [(f ( tex2html_wrap_inline318 ) B)] ... (APP f ( tex2html_wrap_inline308 )))
のように見えている場合,
(FIX [(f ( tex2html_wrap_inline318 ) B)] ... (APP f ( tex2html_wrap_inline308 )))
tex2html_wrap_inline336 (FIX [(f ( tex2html_wrap_inline318 ) B)] ... tex2html_wrap_inline344 )
という変換を行えば良い(ただし, 変数の衝突は回避すること).

ここで, fが他の場所で呼ばれていない関数であれば, fの定義そのものを 消去できる.

(FIX [(f ( tex2html_wrap_inline318 ) B)] ... tex2html_wrap_inline344 )
tex2html_wrap_inline336 (... tex2html_wrap_inline344 )

この操作を, λ-calculusにおけるβ-reductionにならって, β-reductionと呼ぶ. 特に一度しか呼ばれていない関数に対する β-reductionをβ-contraction, そうでないものを β-expansionと呼ぶ.

注1:

Min-Scheme (またはMin-SchemeFix)における関数呼び出し, 例えば(f x), を除去するには, CPS変換の結果として現れる

(FIX [(k (r) ...)]
  (APPF f (k x)))
において(注) まず, (APPF f (k x))をβ-reductionし, 結果として
(FIX [(k (r) ...)]
  (... fの本体
    (APPb k (..))))
というコードを得る. そして次に(APPb k (..))をさらに β-reductionして,
(FIX [(k (r) ...)]
  (... fの本体
    ... kの本体 ...))
を得る. そして不要になったkの定義を削除する.
  (... fの本体
    ... kの本体 ...)

β-reductionは常にやった方が良いように思えるかもしれないが, β-expansionはコードサイズの増大を招くので, むやみにやってはいけ ない. 一番簡単な戦略はβ-contractionだけをやるというものである.

注2:

β-contractionは必ずしもMin-Scheme (Min-SchemeFix)における関数呼 び出しを消すためにのみ存在するわけではない. Min-Scheme (Min-SchemeFix) のif文において作られるFIXSを消すためにも同様に使うことができる.

注3:

β-reductionを実現するにはCPS式をたどっていきなが ら, 各CPS部分式をscopeに入れている関数定義を覚えておき, 使われた場所で 必要に応じて置き換えをしていけば良い. この「定義を覚えておいて, 使用を 定義で置き換える」という構造は, 関数以外に対しても適用できる. 例えば,

(+ [3 4] [x] [ ...x... ])
の, xの使用を7で置き換えるなど (constant-folding). β-reductionを実装するのであれば, いっしょに 実装してしまうのが良い.

テスト

とにかくη-reductionがきちんと実装できているかをテストすること.

Loopなみに速い末尾再帰

(define (loop i n)
  (if (= i n)
      0
      (begin
        (display i)
        (loop (+ i 1) n))))
は,
[loop (k58 i n) 
      (= [i n] [] 
         [(appb k58 (0)) 
          (fixs ([k61 (r62) (+ [i 1] [v65] 
                               [(appf loop (k58 v65 n))])])
            (appf display (k61 i)))])]
となるべき. 注目は, loopの再帰呼出時に継続が作られずに, 最初に渡 されたk58が再利用されていること.

If文のη reduction

(define (eta-if x)
  (if (= x 0)
      (f x)
      (g x)))
η reductionを全く行なわなければ, ifのために一回, f, gそれぞれのために一回ずつ継続が生成されるが, それらは全て除去さ れ, 以下のようになる.
[eta-if (k66 x) 
  (= [x 0] [] 
     [(app f (k66 x)) 
      (app g (k66 x))])]

問題点の指摘

(define (eta-if-sugoikoto a b c d e f g h)
  (if (or (> a b) (= c d) (< e f)) g h))
ここで,
(or A B)
は,
(let ((x A)) (if x x B))
のsyntax-sugarとする. η-reductionを行ってもかなりすごいことになる.
(foo (k5 a b c d e f g h) 
  (fixs ((j8 (v9) 
           (fixs ((j10 (v11) 
                    (neq-two? (v11 #f) () 
                   ((appb k5 (g)) 
                    (appb k5 (h))))))
             (neq-two? (v9 #f) () 
               ((appb j10 (v9))
                (fixs ((j12 (v13) 
                         (neq-two? (v13 #f) () 
                           ((appb j10 (v13)) 
                            (fixs ((j16 (v17) 
                                     (neq-two? (v17 #f) () 
                                       ((appb j10 (v17)) 
                                        (appb j10 (#f)))))) 
                              (<-two (e f) () 
                                ((appb j16 (#t)) 
                                 (appb j16 (#f))))))))) 
                  (=-two (c d) () 
                    ((appb j12 (#t)) 
                     (appb j12 (#f))))))))))
     (>-two (a b) () 
       ((appb j8 (#t)) 
        (appb j8 (#f))))))
元をただせば, if文のCPS変換時に一般的にはfixを作ることが必要で, 条件部分が, (< A B)のような場合だけは特別扱いして効率的なコー ドを出すようにしたものの, 以下のようなコード:
(let ((t ...)) (if t ... ...))
にに対しては対策を施さなかったのが原因である. これを問題点だと思う人は, 対策を各自で施して欲しい(例えばβ-reductionを行うというのは一つの 手である). どのくらい一般的にやるかは好み次第というところでしょう.

課題

η-reductionは必須とし, 余力に応じて他の最適化を自分で工夫して実装 する.

締切り: 11月11日(水)

...reductionと呼ぶ.
名前はもちろんλ計算のη reduction: λx.(Mx) → Mから来ている.
...において
kが1#1-reductionで消えていないことを仮定し ている.
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999