http://morepypy.blogspot.com/2012/01/comparing-partial-evaluation-and.html の訳
私の博士論文の一部として、私は今 PyPy のメタトレーシングアプローチと従来の言語処理系からの情報のみ利用する(JIT)コンパイラの様々なアイデアとの関連について考えています。 これらの線に沿って一番研究されたアイデアの一つは 部分評価 です。 部分評価は、基本的にコンパイラに付属するという PyPy と同じゴールを持っています。 インタプリタを書き、コンパイラをコストなしに手に入れるということです。 ゴールにたどり着く方法は、若干違います。 この一連のブログポストでは、PyPy のメタトレーシングと部分評価の類似点と相違点を探してみようと思います。
「部分評価」が何なのかと「メタトレーシング」が何なのかの明確な理解のために両者の「実行モデル」を示します。 その後、小さな命令型言語を定義し、その言語のための部分評価器とトレーサーがどのようなものなのかを示します。 全てのコードは Prolog で実装されるでしょう。(パターンマッチングが使える関数型言語でも構いませんが、私が知る中では Prolog がベストです。バックトレーシングは使いませんので、単に関数型プログラムとして読めます。) このポストでは、言語とその言語の部分評価器の定義から始めます。 このブログのポストに書かれた全てのコードはここにあります: http://paste.pocoo.org/show/541004/
言語は概念的には PyPy の Flow Graph に近いものです。しかし、少し制限があります。 関数呼び出しを持たず、ラベルづけされた、一連の実行する命令の後に条件付き、もしくは条件なしのジャンプが付随するブロックから構成されます。 全ての操作は、いくつかの演算をいくつかの引数に適用し、計算された値を変数に代入します。
x の y 乗を計算する単純なプログラムはこのようなものです。
power:
res = 1
if y goto power_rec else goto power_done
power_rec:
res = res * x
y = y - 1
if y goto power_rec else goto power_done
power_done:
print_and_stop(res)
Prolog のデータ構造で同じプログラムを表します。以下のような Prolog のコードです。
block(power, op1(res, same, const(1),
if(y, power_rec, power_done))).
block(power_rec, op2(res, mul, var(res), var(x),
op2(y, sub, var(y), const(1),
if(y, power_rec, power_done)))).
block(power_done, print_and_stop(var(res))).
ブロックのそれぞれのルールは、最初にブロックのラベルを示し、コードが続きます。これで一つのブロックを宣言します。
コードは op1 か op2 文が連なり、ジャンプ、 if もしくは print_and_stop によって終了します。
op1 は一つの引数を受ける op1(res_variable, operation_name, argument, next_statement) のような命令です。
引数は var(name) 形式の変数か const(value) 形式の定数が使えます。
この FlowGraph 言語を実行するには、最初にいくつかの補助機能を必要とします。 最初のいくつかの補助機能は、インタプリタがプログラムで発生する、変数名の実行中の値とのマッピングに使うためのデータ構造で、実行環境を扱うことに関係します。 Python では辞書型がこの目的で使われます。しかし、 Prolog では キーと値のペアのリストを使ってエミュレートしなければいけません。(かなり効率は悪いですが、必要十分です)
lookup(X, [], _) :- throw(key_not_found(X)). lookup(Key, [Key/Value | _], Value) :- !. lookup(Key, [_ | Rest], Value) :- lookup(Key, Rest, Value). write_env([], X, V, [X/V]). write_env([Key/_ | Rest], Key, Value, [Key/Value | Rest]) :- !. write_env([Pair | Rest], Key, Value, [Pair | NewRest]) :- write_env(Rest, Key, Value, NewRest). remove_env([], _, []). remove_env([Key/_ | Rest], Key, Rest) :- !. remove_env([Pair | Rest], Key, [Pair | NewRest]) :- remove_env(Rest, Key, NewRest). resolve(const(X), _, X). resolve(var(X), Env, Y) :- lookup(X, Env, Y).
これらの関数の実装は重要ではありません。 lookup 関数は環境のリストからキーを見つけ、 write_env 関数は新しいキーと値のペアを環境に追加し、 remove_env 関数はキーを削除します。 resolve 関数は、定数か変数のいずれかを引数として取り、値を返す為に使います。 もし定数であればその値が返され、変数であれば環境からルックアップします。 注意として、 lookup と resolve の最後の引数は、実際には戻り値で、このような方法は Prolog ではよくあるアプローチです。
これまでのところ、基本演算のプログラム上の意味が定義されていません。 そのため、基本演算とともに do_op 関数を定義します。
do_op(same, X, X). do_op(mul, X, Y, Z) :- Z is X * Y. do_op(add, X, Y, Z) :- Z is X + Y. do_op(sub, X, Y, Z) :- Z is X - Y. do_op(eq, X, Y, Z) :- X == Y -> Z = 1; Z = 0. do_op(ge, X, Y, Z) :- X >= Y -> Z = 1; Z = 0. do_op(readlist, L, I, X) :- nth0(I, L, X). do_op(Op, _, _, _) :- throw(missing_op(Op)).
重要なことなのでもう一度言います。最後の引数は出力先の変数です。
単純な操作を実行する準備が整いました。なので、 interp という述語を定義します。 これは、最初の引数が実行環境、二つ目の引数が実行する操作を表します。 例では、一つか二つの引数をと共に基本演算を実行しています。
interp(op1(ResultVar, Op, Arg, Rest), Env) :-
resolve(Arg, Env, RArg),
do_op(Op, RArg, Res),
write_env(Env, ResultVar, Res, NEnv),
interp(Rest, NEnv).
interp(op2(ResultVar, Op, Arg1, Arg2, Rest), Env) :-
resolve(Arg1, Env, RArg1),
resolve(Arg2, Env, RArg2),
do_op(Op, RArg1, RArg2, Res),
write_env(Env, ResultVar, Res, NEnv),
interp(Rest, NEnv).
最初に、引数を値として解決します。その後、演算が実行され、結果が環境に書き戻されます。 そして interp がプログラムの残りの部分とともに呼び出されます。 同様に、条件なしジャンプと print_end_stop も簡単です。
interp(jump(L), Env) :-
block(L, Block),
interp(Block, Env).
interp(print_and_stop(Arg), Env) :-
resolve(Arg, Env, Val),
print(Val), nl.
条件なしジャンプの中では、単にターゲットのブロックを取得し、その実行を継続します。 print_and_stop の実行は、引数を解決し、値をプリントし、終了します。
条件付きジャンプだけはは少し難しいです。
interp(if(V, L1, L2), Env) :-
lookup(V, Env, Val),
(Val == 0 ->
block(L2, Block)
;
block(L1, Block)
),
interp(Block, Env).
最初に変数を環境からルックアップし、変数の値がゼロであれば二つ目のブロックの実行を継続します。そうでなければ最初のブロックを継続します。
このインタプリタは、上記のサンプルを Prolog のコンソールでこのように実行できます。
$ swipl -s cfglang.pl ?- block(power, Block), interp(Block, [x/10, y/10]). 10000000000
それでは、この単純な FlowGraph 言語のための部分評価器がどのようなものか見てみましょう。 部分評価は特殊化とも呼ばれ、プログラム操作のテクニックです。 部分評価は入力のプログラムを受け取り、(うまくいけば)シンプルで高速な出力プログラムに変換します。 これは、入力プログラム中のいくつかの変数を定数であると仮定します。 定数にのみ作用する全ての演算は、畳み込まれます。 それ以外の全ての演算は、出力プログラムでもそのままにする必要があります。(残留プログラムと呼ばれます) 従って、部分評価器は、単にいくつかの演算を実行できないだけで、殆どインタプリタのような結果をもたらします。 また、出力は単なる値ではなく、最適化できなかった残りの演算のリストです。
部分評価器は通常の環境では使えません。全ての変数の値が知られているインタプリタとは異なるためです。 そのために、部分的な環境の下では分かっている変数のみを保存します。 これらの部分的な環境のために、いくつかの新しい補助関数が必要です。
plookup(Key, [], var(Key)). plookup(Key, [Key/Value | _], const(Value)) :- !. plookup(Key, [_ | Rest], Value) :- plookup(Key, Rest, Value). presolve(const(X), _, const(X)). presolve(var(V), PEnv, X) :- plookup(V, PEnv, X).
plookup 関数は変数と部分環境を受け取り、変数が部分環境内で見つかった場合は const(Value) を、見つからなかった場合は ``var(Key) を返します。
同様に presolve は lookup の代わりに plookup を使う以外は resolve と同じ関数です。
これらの補助関数を使うことで部分評価器を書き始められます。 下記の二つのルールは定数の畳み込みのための主な最適化で使います。 部分評価器のアイデアは、定数引数のみを含む操作を見てください。それらは定数の畳み込み操作を行い、それ以外はそうではありません。
pe(op1(ResultVar, Op, Arg, Rest), PEnv, NewOp) :-
presolve(Arg, PEnv, RArg),
(RArg = const(C) ->
do_op(Op, C, Res),
write_env(PEnv, ResultVar, Res, NEnv),
RestResidual = NewOp
;
remove_env(PEnv, ResultVar, NEnv),
NewOp = op1(ResultVar, Op, RArg, RestResidual)
),
pe(Rest, NEnv, RestResidual).
pe(op2(ResultVar, Op, Arg1, Arg2, Rest), PEnv, NewOp) :-
presolve(Arg1, PEnv, RArg1),
presolve(Arg2, PEnv, RArg2),
(RArg1 = const(C1), RArg2 = const(C2) ->
do_op(Op, C1, C2, Res),
write_env(PEnv, ResultVar, Res, NEnv),
RestResidual = NewOp
;
remove_env(PEnv, ResultVar, NEnv),
NewOp = op2(ResultVar, Op, RArg1, RArg2, RestResidual)
),
pe(Rest, NEnv, RestResidual).
pe という述語は、部分環境を受け取り、現在の演算と行われる可能性のある新しい演算を返します。 単純な演算の部分評価のために、これらの引数は部分環境からルックアップされます。 もし全てのの引数が定数であれば、演算は実行できるので、新しい演算は生成されません。 それ以外の場合は今見ているものと同じように動作する新しい残留演算を生成する必要があります。 また、結果の変数は部分環境から削除する必要があります。不明な値によって上書きされるためです。
潜在的に生成された残留演算は NewOp の出力引数として保存されます。
再帰呼び出しの出力の引数は、新しく生成された残留演算の最後の引数で、再帰的な呼び出しによって埋められます。
これは Prolog では典型的なアプローチですが、 Prolog に馴染みない人には奇妙に見えるかもしれません。
注意として、これらのルールの最初のケースでは、解釈のようなことのみを行います。 二つ目のケースでは、実際にはなにもしておらず、残留演算を生成しているだけです。 この通常の評価と部分評価の間の関連は、とても典型的なものです。
条件なしジャンプと print_and_stop はとても簡単です。
pe(jump(L), PEnv, jump(LR)) :-
do_pe(L, PEnv, LR).
pe(print_and_stop(Arg), Env, print_and_stop(RArg)) :-
presolve(Arg, Env, RArg).
部分評価のために、条件なしジャンプは再度ジャンプを生成します。 既存のジャンプターゲットのラベルは、残留コードを生成するために、ラベル L 渡とされた部分環境を伴って部分評価器にで評価することで計算されます。 print_and_stop は単に print_and_stop を返すだけです。 do_pe のコードをすぐに見てみましょう。
条件付きジャンプはより興味深いです。
pe(if(V, L1, L2), PEnv, NewOp) :-
plookup(V, PEnv, Val),
(Val = const(C) ->
(C = 0 ->
L = L2
;
L = L1
),
do_pe(L, PEnv, LR),
NewOp = jump(LR)
;
do_pe(L1, PEnv, L1R),
do_pe(L2, PEnv, L2R),
NewOp = if(V, L1R, L2R)
).
最初に、条件変数の値を参照します。 もしそれが定数であれば、よりよいコードを生成できます。静的に一つのパスにしか到達できないことが分かるためです。 従って、そのパスのへのコードを生成し、条件なしのジャンプを出力します。 もし条件変数が部分評価時にわからなければ、どちらのパスに対しても部分評価を適用し、残留コードして条件付きジャンプを生成します。
部分評価器がインタプリタよりも多く作業を行う可能性がある原因のルールは一つで、 if の後でしばしば両方のパスを探索しなければいけないということです。
最悪のケースでは、このプロセスは終了しません。なので、実際の部分評価器では、どのように終了するかを確認しなければいけません
それを行うための多くのアルゴリズムがありますが、ここではこの問題を無視します。
今 do_pe という述語がなにをしているかを理解することが必要です。 一番重要なタスクは、以前に部分評価されたかどうかをメモ化するコードによって、同じ作業を二回しないことを確認することです。 そのために部分環境のラベルから残留コードのラベルへのマッピングを保持します。
do_pe(L, PEnv, LR) :-
(code_cache(L, PEnv, LR) ->
true
;
gensym(L, LR),
assert(code_cache(L, PEnv, LR)),
block(L, Code),
pe(Code, PEnv, Residual),
assert(block(LR, Residual))
).
もしラベル L が既に部分環境 PEnv の中で部分評価されていることをコードキャッシュが示すのであれば、以前生成した残留コードのラベル LPrevious が返ります。 それ以外は gensym によって新しいラベルが生成され、コードキャッシュは新しいラベルを割り当てて通知し、ブロックは部分評価され、残留コードがデータベースに追加されます。
部分評価について知るための用語集: この部分評価器は polyvariant online 部分評価器です。 "Polyvariant" の意味するところは、全てのラベル、いくつかの特殊化したバージョンのブロックを生成できるということです。 "Online" の意味は、部分評価器を走らせる前の事前処理がないということです。
このコードで、部分評価の古典的な例を見られます。(恐らく部分評価における "Hello, world" のようなものです) 冪乗関数について部分評価器に尋ね、指数 y が定数(例えば 5)や、ベースの x が不明であるということです。
?- do_pe(power, [y/5], LR). LR = power1. To find out which code was produced, we can use listing: ?- listing(code_cache) code_cache(power, [y/5], power1). code_cache(power_rec, [y/5, res/1], power_rec1). code_cache(power_rec, [y/4], power_rec2). code_cache(power_rec, [y/3], power_rec3). code_cache(power_rec, [y/2], power_rec4). code_cache(power_rec, [y/1], power_rec5). code_cache(power_done, [y/0], power_done1). ?- listing(block) .... the block definition of the user program .... block(power_done1, print_and_stop(var(res))). block(power_rec5, op2(res, mul, var(res), var(x), jump(power_done1))). block(power_rec4, op2(res, mul, var(res), var(x), jump(power_rec5))). block(power_rec3, op2(res, mul, var(res), var(x), jump(power_rec4))). block(power_rec2, op2(res, mul, var(res), var(x), jump(power_rec3))). block(power_rec1, op2(res, mul, const(1), var(x), jump(power_rec2))). block(power1, jump(power_rec1)).
code_cache は、部分環境の下でどのオリジナルラベルがどの残留ラベルに対応するかを教えてくれます。
従って、y が 5 であるという想定のもとで power1 が power のコードに含まれます。
リストのブロックを見ると、 power1 というラベルは x を全く使用せずに、単純に 5 回 x を掛けるコード対応します。
オリジナルのプログラムではループであったものは、完全に展開されてループ変数の y は消えてしまいました。
うまくいけばこれはオリジナルのプログラムよりも速くなります。
このブログのポストで見たものは、 Prolog で作られたシンプルな Flow Graph 言語のインタプリタと、その部分評価器です。 部分評価器は、本質的にはインタプリタのあらゆるルールを複製します。 もし全ての処理中の引数が全て分かっているならば、それはインタプリタのように振る舞います。そうでなければ単純に残留コードに演算をコピーするだけです。
部分評価は様々なアプリケションに利用できますが、最もよく引用されて適用されるるものの一つはインタプリタです。 インタプリタが走らせるプログラムは部分評価器によって定数とみなされます。 したがって、特殊化されたバージョンのインタプリタは入力するプログラムを全く使用せずに生成されます。 残留コードは入力プログラムのコンパイルされたバージョンであるとみなせます。
このシリーズの次のブログポストでは、同じ FlowGraph 言語の単純なトレーサを書いてみます。