決定論的2階パターンとプログラム変換への応用  [in Japanese] Deterministic Second-order Patterns for Program Transformation  [in Japanese]

2階パターンと2階照合を用いると高度なプログラム変換を記述することができることが知られている.しかし,2階照合はNP困難であるため効率がよい実装が望めない.われわれは,2階パターンの形を制限することで,どのような項とも得られる最汎照合子が高々1つである決定論的なパターンのクラスを定め,またこの照合を得るための効率の良いアルゴリズムを開発した.本橋では,このような決定論的2階パターンのクラスを拡張し,また線形2階パターンが決定論的であるための必要十分条件を与える.このクラスのパターンを用いて幅広いプログラム変換を記述することが可能である.

Second-order patterns and second-order matching play an important role in program transformation, but the second-order matching algorithm is known to be NP-hard and real efficient, implementation is out of Question. To resolve this problem, we introduced a class of deterministic second-order patterns, and proposed an efficient matching algorithm. In this paper, we further extend this class to cove more deterministic second-order patterns, discuss both sufficient and necessary conditions for a second-order pattern to be deterministic, and demonstrate its usefulness in program transformation.