Loading article…
コンピュータサイエンスにおいて、A 正規形(略称ANF、管理正規形またはアトミック正規形と拡張されることもある)は、関数型プログラミング言語コンパイラにおけるプログラムの中間表現です。ANF では、関数への引数はすべて自明なもの (定数または変数) でなければなりません。つまり、各引数の評価は直ちに停止する必要があります。
ANF は、継続渡しスタイル(CPS)のよりシンプルな代替手段として、1992 年にSabry とFelleisenによって導入されました[1]。中間表現として CPS を使用する利点としては、CPS のプログラムではソース言語よりも最適化が簡単に実行できること、またコンパイラがCPS のプログラムのマシン コードを生成するのが簡単であることが挙げられます。Flanagan ら[2]は、コンパイラが ANF を使用して 1 つのソース レベルの変換で同じ利点を実現する方法を示しました。対照的に、現実的なコンパイラでは、CPS 変換には通常、CPS 項を簡略化するなどの追加のフェーズが含まれます。
文法
定数とlet式を含む純粋なλ計算を考えてみましょう。ANF制約は次のように適用されます。
- 関数適用のオペランドとして値（変数、定数、λ項）のみを許可し、
- 非自明な式 (関数適用など) の結果を、let でバインドされた変数にすぐに取り込むことを要求します。
次のBNF文法は、ANF の制約を実装するために λ 式の構文を変更する方法を示しています。
コンパイラや研究で使用される ANF のバリアントでは、レコード、タプル、複数引数関数、プリミティブ操作、条件式も許可されることがよくあります。
例
表現:
f(g(x)、h(y)) の式は、
ANFでは次のように記述されます:
v0 = g(x) とすると
v1 = h(y) とすると
関数v0,v1
この関数呼び出しによって生成されるアセンブリの種類を想像すると、次のようになります。
;; v0 = g(x) とします xをargs[0]に移動する gに電話する 結果をtemp[0]に移動する ;; v1 = h(y) とします yをargs[0]に移動する 電話する 結果をtemp[1]に移動する ;; f(v0, v1) temp[0]をargs[0]に移動する temp[1]をargs[1]に移動する fに電話する
ANF と関数のコンパイルされた形式の間にはすぐに類似点が見られます。この特性は、ANF がコンパイラーの最適化に適した中間表現となる理由の 1 つです。
参照
参考文献
- ^ Sabry, Amr; Felleisen, Matthias. 「継続渡しスタイルのプログラムについての推論」。1992 ACM LISP および関数型プログラミング会議の議事録、LFP'92 。米国カリフォルニア州サンフランシスコ。CiteSeerX 10.1.1.22.7509。Sabry92 。
- ^ Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.; Felleisen, Matthias。「継続によるコンパイルの本質」(PDF)。ACM SIGPLAN 1993 Conf. on Programming Language Design and Implementation、PLDI'93 会議議事録。アルバカーキ、ニューメキシコ州、米国。Flanagan93。2012年 11 月 16 日閲覧。