日本ソフトウェア科学会第 33 回大会 (2016 年度) 講演論文集

停止性の保証による rewrite rules の改良
長田 朋久

市川 和央

千葉 滋

本研究では GHC の rewrite rules を改良し，停止性を保証した機構を Java 言語上に実装する．ホスト言語の構文機能を使用して実現された内部 DSL は実装が単純である一方，コンパイラによる直接的な最適化が困難である．
rewrite rules を用いると内部 DSL 向けの最適化処理を DSL 作者が記述できるが，各変換ルールは無制限に適用可能なため，停止しない場合がある．そこで提案手法では構文木の各節に対して変換規則ごとに一度のみの変換を適用させることで，停止性を保証し最適化処理の安全性を向上させる．

順で走査し規則を試しつつ，書き換えによって生じた1 はじめに新しい構文木には同じ書き換え規則を再適用しない．

内部 DSL は汎用プログラミング言語のライブラリ

また，提案手法を Java 言語上に実装し評価することとして作成されることが一般的である．例えば Scalaを目標とする．

[5] 言語は二項演算子のように見えるメソッドの糖衣構文が存在している．これは様々なライブラリで独2 ホスト言語の構文を使用した内部 DSL

自の演算子定義を可能とし，擬似的な言語の構成にScala [5] 等の汎用プログラミング言語では，その言寄与している．しかし，内部 DSL の意味論はコン語の構文機能のみで内部 DSL を実装することが容易

パイラの知るところではないため，最適化が期待しである．ある汎用プログラミング言語 (ホスト言語)づらい．関数型プログラミング言語の Haskell [2] で内で，さらに特定の問題領域に特化されたサブ言語は，Glasgow Haskell Compiler [4] 固有の拡張としてを内部 DSL という．内部 DSL はホスト言語の構文

rewrite rules [3] という機構が存在し，パターンマッ機能を使用し，1 つの言語に見えるようなホスト言語

チの要領で予め定義された関数の組み合わせを別の式のライブラリとして実装される．図 1 に内部 DSL のへと変換する．これを内部 DSL の作者が記述するこ

例として，Scala のリスト表現を挙げる．1 行目では，とで，コードの最適化が期待できる．Rewrite rules

1，2，3 より構成されるリストについて，全ての要の問題点として，書き換え規則適用の停止性が保証さ素に 1 を足し，その後全ての要素に 2 を掛けている．

れていないことが挙げられる．例えば引数の順序を入

この式は 2 行目と同等である．::は List クラスのメれ替える書き換え規則は無限に適用され，結果としソッドであり，引数をリストの先頭に付け加えた新たて停止しない．これを解決するため，本研究では書きなリストを返す．また，Nil は List クラスを継承した換え規則に適用順序を設け停止性を保証することをシングルトンオブジェクトである．よって，Nil から提案する．書き換え対象コードの構文木を帰りがけ::メソッドが連鎖的に呼び出され，リストが生成さA

refinement of the rewrite rules promisingtermination.
Tomohisa Osada
Kazuhiro IchikawaShigeru
Chiba, 東京大学大学院情報理工学系研究科, Dept.
of Computer Science, University of Tokyo.

れている．Scala ではメソッド呼び出しの際，呼び出し元オブジェクトと引数におけるドットと括弧を省略できる糖衣構文があるため，1 行目の簡潔な表記が可能となっている．また，_は引数を要求し，全体とし1 1::2::3::Nil map (_ + 1) map (_ * 2)
2 Nil.::(3).::(2).::(1).map(x => x + 1).map(x => x * 2)

図1

1 {-# RULES
2"commute" forall x y. foo x y = foo y x
3#-}Scala 言語の List の例

1 {-# RULES
2 "map/map" forall f g xs.
3
map f (map g xs) = map (f.g) xs4#-}

図3

無限ループに陥る例

4 順序付き書き換え機構の提案
書き換え機構の停止性が保証できるよう，複数の書き換え規則間に適用順序を設けることを提案する．書

図2

rewrite rules による中間オブジェクトの削減

き換え規則が停止しない場合とは，以下の 2 つが挙げられる．て無名関数を構成する．これはリスト表記に特化した• ある単一の規則が無限に再適用される．

Scala の内部 DSL ということができる．

• ある規則 a が適用された後別の規則群 b, c, d, ...

しかし，ホスト言語は内部 DSL の意味論を理解し得ないため，コンパイラによる直接的な最適化は困難である．図 1 では map 関数が連続で使用されている．

map 関数は新しいリストオブジェクトを作成するため，中間オブジェクトを無駄に生成している．

が適用され，その結果再び a が適用可能となることで無限の再適用が生じる．
よって提案手法では，• ある構文木に対して特定の規則は有限回しか適用しない．

• ある規則 ai の適用された構文木にその後適用さ3 Rewrite rules の停止性れる規則は必ず ai 以降とする．

内部 DSL の最適化機構として Haskell [2] 言語にとすることで，書き換え機構の停止性を保証する．そは Glasgow Haskell Compiler [4] の拡張機能としてして，停止性が保証できるような機構の中で実用上表

rewrite rules [3] が存在する．rewrite rules では記述

現力が十分であるものを目指す．

されているパターンで関数が使用された場合，ルールに基づき式を変換する．ルールは等式で記述され，左4. 1 書き換え規則の動作

辺のパターンにマッチする式は右辺に変換される．こ図 4 に単一の書き換え規則の定義と動作の例を示の変換はマッチする式がある限り繰り返し実行される．

す．1 行目は変数定義である． a,b,c は int 型の

図 2 に rewrite rules の定義例を示す．"map/map"

変数として定義し，書き換え規則中で使用する．2 行はルール名，f，g，xs は変数であり，map はスコー目は書き換え規則の本体である．1 つの書き換え規則

プ中に存在する map 関数を指す．このルールは連続は返り値型の等しい左辺式と右辺式の対からなり，左で map 関数が使用される場合に，中間オブジェクト辺式のパターンにマッチする構文木上の式について，の発生を抑えている．右辺では f と g が関数合成さ右辺式に変換する．この規則は 3 個の int の足し算れるため，map g xs による中間オブジェクトは生における結合の優先順位を変更する．以下に書き換え成されない．

を受ける式の例を示す．

Rewrite rules の問題点として，停止性が保証されていないことが挙げられる．図 3 のように関数 foo

1 + (2 + List(3,4,5).sum())-> (1 + 2) + List(3,4,5).sum()の引数の順序を入れ替えるだけのルールは変換結果書き換え規則にある二項演算子 + はコード上に再度ルールが適用されるため，無限ループに陥る．の + と マッチ す る ．規 則 に あ る 変 数 は 任 意 のint 型 の 式 と マッチ す る ．よって ，こ の 場 合 は

1 int a,b,c;
2 a + (b + c) -> (a + b) + c

作としては， TRAVERSE はまず t の子要素全てについて再帰的に TRAVERSE を実行する．その後，i ≤ j ≤ n である任意の j について， t が書き換え
図4

書き換え規則規則 aj とマッチすれば書き換えを実行する．さらに，aj が最後の書き換え規則で無ければ，規則の順

1: traverse(Sroot ,1)
2: function traverse(t,i)
3:
4:
5:
6:

for c ← children(t) dotraverse(c,i)
for j ← i...n do
if t match with aj then7:

rewrite(t,aj )8:

if j < n thentraverse(t,j + 1)9:
図5

書き換え規則列の適用順序

序として次のものを使用して TRAVERSE を再び実行する．
書き換え規則列の適用順序を構文木で表現したものを図 6 に示す．i 番目の書き換え規則 ai は，根がP である部分木にマッチし，Q を根とした部分木に書き換えられるとする．書き換え対象のソースコードの構文木は帰りがけ順に全ての書き換え規則を試す．

P が見つかれば，根を P とする部分木を，根を Qとする部分木に書き換える．そして書き換え対象となった部分木については，その根ノードを始点としてi + 1 番目以降の書き換え規則を帰りがけ順に試す．

a = 1, b = 2, c = List(3,4,5).sum() と4. 3 書き換え機構の停止性なっている．

1 つの書き換え規則は S の各ノードに対して有限回構文木の構造が一致しない式とはマッチしない．例だけ有効である．また，ある書き換え規則 ai によっえば以下の式て書き換えられた部分木に対して使用される可能性

6 + 7 + 8のある規則は ai+1 以降であるため，書き換え規則のは + が 左 結 合 の 演 算 子 な の で ，実 際 に は順序に逆行した適用は発生しない．これにより， 生(6 + 7) + 8 である．つまり構文木としては右成された部分木に同じ書き換え規則が再度適用され側の + が式の根なので，書き換え規則の左辺とは木ることにより発生する無限ループを防ぐ．の形が異なり，マッチしない．

5 表現力の比較
4. 2 書き換え規則列の適用順序

Rewrite rules では書き換え規則の無限適用に陥る

複数の書き換え規則に順序を付け，書き換え対象と問題が表現できない一方，本研究の提案手法は不定

なるソースコードの構文木に帰りがけ順に適用して回数の再適用が必要な問題が表現できない．例えば 3

いくことで，規則の無限適用を防ぐ．

章で示したように，ある関数の引数順序を入れ替える

図 5 に書き換え規則の適用順序について，擬似コードことは rewrite rules では表現できない．提案手法でを示す． S は書き換え対象のソースコードの構文木では同じノードに同じ書き換え規則は 1 度だけ適用さあり， Sroot はその根ノードを指す． {ai }, i = 1, ..., nれるため，引数順序の入れ替えは可能である．一方，は書き換え規則列である．関数 TRAVERSE はノー提案手法では同じノードに不定回数同じ書き換え規則

ドの参照 t と試す書き換え規則の番号 i を引数に取り，を適用すべき問題が表現できない．例えば，右結合の構文木を走査しつつ書き換える．関数 CHILDREN は足し算の列をすべて左結合に直すことは難しい．図 4

引数のノードの子要素集合を返す．関数 REWRITEの規則を右結合の足し算列に適用する例を図 7 に示

はノードの参照と書き換え規則を引数にとり，そのす．太字の部分が書き換えの際の根ノードである．図

ノードを根とする部分木を書き換える．具体的な動のように構文木として根から遠い順に 3 回，書き換

図6

書き換え規則列の適用順序

1
1 + (2 + (3 + (4 + 5)))2 -> 1 + (2 + ((3 + 4) + 5))
3 -> 1 + ((2 + (3 + 4)) + 5)
4 -> (1 + (2 + (3 + 4))) + 5

図7

提案手法によって右結合の足し算列に，左結合に直11 + (2 + (3 + (4 + 5)))2 -> (1 + 2) + (3 + (4 + 5))
3 -> ((1 + 2) + 3) + (4 + 5)
4 -> (((1 + 2) + 3) + 4) + 5

図8

右結合の足し算列の理想的な書き換えす規則を適用させるえが発生しているが，結果出力される式は完全な左6 関連研究

結合の足し算列とはならない．図 8 にこの場合の理コンパイル時に最適化されたコードを生成させる想的な書き換え例を示す．各段階で構文木の根となる機構としては，MetaOCaml [7] などのマクロ関数がノードに規則を 3 回適用させると，結果は完全な左ある．マクロ関数と比べ本研究が対象とする書き換え結合の足し算列となることが分かる．これは提案手法

規則は，複数の関数配置のパターンを処理することがでは，単一の書き換え規則で表現することができなできる一方，事前の引数評価によるコード生成ができい．なお，図 4 の規則を複数並べることで，あらかない．書き換え規則では図 2 で見たように，複数のじめ予想される長さの足し算列に対して対応できる．

関数があるパターンで適用されていれば，それをよしかし，任意長の右結合の足し算列に対して対応するり効率的な式に書き換えることが可能である．しかことはできない．

しマクロ関数のように事前に一部の引数のみコンパ

イル時に評価することはできない．そのためマクロ

今後の課題としては，提案手法の停止性を厳密に証関数では可能な pow(2,3) -> 2 * 2 * 2 といっ明すること，同手法の表現力が向上するような改良をた，引数の回数だけコード断片を再帰的に展開する，加えること，Java で提案手法を実装し評価することなどの動作はできない．

が挙げられる．

C++ [6] 用の書き換え機構として CodeBoost [1] がある．CodeBoost も本研究と同様に，書き換え規則

参 考 文 献に従って書き換えを実行する．しかし特徴的な点とし[1] Bagge, O. S., Kalleberg, K. T., Haveraaen, M.,
and Visser, E.: Design of the CodeBoost transformation system for domain-specific optimisationof C++ programs, Source Code Analysis and Manipulation, 2003. Proceedings. Third IEEE International Workshop on, IEEE, 2003, pp. 65–74.
[2] Hudak, P., Hughes, J., Peyton Jones, S., andWadler, P.: A History of Haskell: Being Lazywith Class, Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III, New York, NY, USA, ACM,
2007, pp. 12–1–12–55.
[3] Jones, S. P., Tolmach, A., and Hoare, T.: Playing by the rules: rewriting as a practical optimisation technique in GHC, Haskell workshop, 2001,
pp. 203–233.
[4] Jones, S. P., Hall, C., Hammond, K., Partain, W.,and Wadler, P.: The Glasgow Haskell compiler: atechnical overview, Proc. UK Joint Framework forInformation Technology (JFIT) Technical Conference, Citeseer, 1993.
[5] Odersky, M., Spoon, L., and Venners, B.: Programming in scala, Artima Inc, 2008.
[6] Stroustrup, B.: The C++ programming language,
Pearson Education India, 1995.
[7] Taha, W.: A gentle introduction to multi-stage
programming, Domain-Specific Program Generation, Springer, 2004, pp. 30–50.て，規則に付加的な条件を設定できる．例えばz + (x * y) -> (x * y) + z,
not(is_mult_expr(z))のように z は掛け算の式ではないと条件を付けることが可能であり，表現可能な問題領域が広い．

7 まとめと今後の課題
ホスト言語のライブラリである内部 DSL はコンパイラが直接最適化することは難しい．パターンマッチによる最適化機構として GHC には rewrite rules があるが停止性が保証されていない．よって本研究では停止性が保証されるような書き換え規則の適用順序を提案した．各書き換え規則は，書き換え対象の構文木の各ノードにつき 1 度だけ適用される．また，複数の書き換え規則間には順序があり，遡った適用はされない．提案手法は rewrite rules で無限ループに陥る問題を記述可能である．しかし，あるノードに複数回同一の書き換え規則を適用させることが本質である問題に対処できない．