部分評価とトレーシングの比較シリーズの二つ目のエントリです。 最初のエントリでは、小さな FlowGraph 言語とそのインタプリタを作り、その言語の部分評価器を示しました。 このエントリでは、同じ言語のトレーサがどのように働くか、両方の実行がどのように関係するのかを示します。 このエントリで使われるコードはここにあります: http://paste.pocoo.org/show/543542/
トレーサのアイデア(言語の一般的な説明)は、通常の解釈を完全に行いますが、同時に実行された全ての通常のオペレーション(例: フロー制御でないオペレーションなど)のログを保持します。 これは、トレーサがブロックの開始から対応する閉じたループを実行する間続けられます。 その後、トレースが停止し、最後のオペレーションが開始へのジャンプによって置き換えられます。 トレースが終了した後、必要に応じて最適化してトレースを実行できます。
トレーサを書くために、インタプリタのルールから始めます。述語を trace にリネームし、いくつかの引数を追加しています。
従って、以下のインタプリタののルールと
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).
トレーサの以下のルールからなります。
trace(op1(ResultVar, Op, Arg, Rest), Env, op1(ResultVar, Op, Arg, T), TraceAnchor) :-
resolve(Arg, Env, RArg),
do_op(Op, RArg, Res),
write_env(Env, ResultVar, Res, NEnv),
trace(Rest, NEnv, T, TraceAnchor).
trace(op2(ResultVar, Op, Arg1, Arg2, Rest), Env, op2(ResultVar, Op, Arg1, Arg2, T), TraceAnchor) :-
resolve(Arg1, Env, RArg1),
resolve(Arg2, Env, RArg2),
do_op(Op, RArg1, RArg2, Res),
write_env(Env, ResultVar, Res, NEnv),
trace(Rest, NEnv, T, TraceAnchor).
実際に対応するインタプリタのルール本体が、どのようなトレースのルールなのかの唯一の違いはトレースの再帰呼び出しです。
trace の引数の意味は以下の通りです。
最初と二番目の引数は、インタプリタで使われるような現在実行しているオペレーションと環境です。
続く引数はトレースしているオペレーションの出力先で、上の例では実際に実行されたオペレーションになっています。
TraceAnchor はその時構築しているトレースに関する追加の情報です。
ほとんどの時間、 trace の再帰呼び出しで渡されます。
その中に何が含まれているかは後で参照します。
print_ant_stop のルール簡単に実行でき、(そのためトレースもまた) 単に停止するだけです。
trace(print_and_stop(V), Env, print_and_stop(V), _) :-
resolve(V, Env, Val),
print(Val), nl.
残りは jump と if の制御オペレーションのルールです。
トレースはジャンプを含まないように実行パスを線形化します。
ただし、最初のラベルへのジャンプに到達したとき、トレースは停止します。
従って、 jump の実装は二つのケースがあります。
trace(jump(L), Env, T, TraceAnchor) :-
(TraceAnchor = traceanchor(L, FullTrace) ->
T = loop,
write(trace), nl, write(FullTrace), nl,
do_optimize(FullTrace, OptTrace),
write(opttrace), nl, write(OptTrace), nl,
runtrace(OptTrace, Env, OptTrace)
;
block(L, Block),
trace(Block, Env, T, TraceAnchor)
).
小さな単位でこのコードを解剖してみましょう。
最初に、 TraceAnchor が何かを見ます。
TraceAnchor は traceanchor(StartLabel, FullTrace) というフォームの用語です。
StartLabel はトレースを開始したプログラムのラベルです。(ループが閉じられた時と同様に同様に終了する必要があります)
FullTrace は構築している全てのトレースを保持するアキュムレータです。
ターゲットラベル L が trace anchor にストアさているかどうかをルールのチェック開始の際に確認します。
もし含まれていれば、トレースを停止できます。
T をトレースする残りの部分は、 loop のオペレーションが割り当てられ、トレースの最初にジャンプして戻ります。
その後、プリントしてトレースを最適化します。そして、実行時に FullTrace は traceanchor の一部として使います。
ジャンプする先のラベルが StartLabel ではない場合、オペレーションを記録せずにトレースを継続します。ルールのこの部分では、再度同じようなジャンプの解釈をします。
今のところ、どのような興味深い最適化も行いません。 最適化されていないトレースを返すだけです。
do_optimize(FullTrace, FullTrace).
今足りていないオペレーションは if です。
if 文は特別な処理が必要です。トレースする制御フローの数が発散してしまうからです。
トレースは線形です。したがって分岐する可能性のあるパスの内片方しか記録できません。
実行される別のパスをトレースすることはトレースの実行時に可能です。
したがって、トレース中の真偽値と、トレースの実行中に真偽値がまだ同じ条件かどうかを確認する必要があります。
これは、この条件をチェックするガードオペレーションで済んでいます。
続くルールを実装します。
trace(if(V, L1, L2), Env, T, TraceAnchor) :-
lookup(V, Env, Val),
(Val == 0 ->
L = L2, T = guard_false(V, [], L1, NT)
;
L = L1, T = guard_true(V, [], L2, NT)
),
trace(jump(L), Env, NT, TraceAnchor).
これはインタプリタの if のルールにとても似ています。
ルールは条件が真であれば guard_true をケース中に挿入し、条件が偽であれば guard_false を挿入します。
ガードの引数は以下の通りです。
- ガードを行う変数
- 空のリスト(この理由は後々説明します)
- ガードの失敗時とトレースの残りの部分の実行を続けるために必要なラベル
トレースの開始時に便利に使える小さな述語も追加しましょう。
do_trace(L, Env) :-
block(L, StartBlock),
trace(StartBlock, Env, ProducedTrace, traceanchor(L, ProducedTrace)).
最初の実行によって、述語はラベルと環境を受け取り、受け取った環境とともにラベルを実行します。
その後、トレースを実行し、最終的にカードが失敗するとインタプリタにジャンプして戻ります。
これを、ラベル L のブロック文とコードを読むことで実行します。
そして未束縛の変数 ProducedTrace とともに trace を呼び出し、トレースとトレースを開始したラベルを含むトレースアンカーを保持し、トレース変数が生成されます。
この述語とトレースを使うと、トレースの実行がないだけで前回のブログポストは既にトレースできる力のある実装です。(実行は次のセクションでおこないます)
?- do_trace(power_rec, [res/1, x/10, y/20]). trace op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop))) opttrace op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop))) ...
計算されたトレースは:
op2(res,mul,var(res),var(x), op2(y,sub,var(y),const(1), guard_true(y,[],power_done, loop)))
実際 power_rec からのループの中身です。
if が guard_true になると、ガードが失敗した場合 power_done にジャンプします。
実際のトレースシステムには、トレーサを開始するための方法が必要になります。 例えばインタプリタの中でのプロファイリングの実行によるものや頻繁に実行されるラベルでトレーサを開始するなどです。 また、同じラベルのトレースは、通常同じ経路であればキャッシュされます。 これらの詳細はこの単純なモデルではそのままです。
実際のトレースシステムでは、トレースはマシンコードになり、 CPU で直接実行されます。 私たちの小さなモデルでは、単にこのモデルのための別のインタプリタを書き出すだけです。 このインタプリタはとても単純で、インタプリタにとても似ています。
runtrace(op1(ResultVar, Op, Arg, Rest), Env, TraceFromStart) :-
resolve(Arg, Env, RArg),
do_op(Op, RArg, Res),
write_env(Env, ResultVar, Res, NEnv),
runtrace(Rest, NEnv, TraceFromStart).
runtrace(op2(ResultVar, Op, Arg1, Arg2, Rest), Env, TraceFromStart) :-
resolve(Arg1, Env, RArg1),
resolve(Arg2, Env, RArg2),
do_op(Op, RArg1, RArg2, Res),
write_env(Env, ResultVar, Res, NEnv),
runtrace(Rest, NEnv, TraceFromStart).
これらのルールはインタプリタの op1 と op2 のルールと完全に等価です。
runtrace は、自身の再帰呼び出しで常に渡される追加の引数 TraceFromStart が必要です。
トレースの最後に到達し、ループ文が検出されると単に最初から開始します。
runtrace(loop, Env, TraceFromStart) :-
runtrace(TraceFromStart, Env, TraceFromStart).
残りの質問は、ガードが発生した時に何をするかです。 このケースでは、ガード条件をチェックする必要があります。 ガードが成功した場合、トレースの実行は続けられます。 それ以外の場合トレースは終了し、インタプリタは実行を再開します。
runtrace(guard_true(V, ResumeVars, L, Rest), Env, TraceFromStart) :-
lookup(V, Env, Val),
(Val == 0 ->
resume_interp(Env, ResumeVars, L)
;
runtrace(Rest, Env, TraceFromStart)
).
runtrace(guard_false(V, ResumeVars, L, Rest), Env, TraceFromStart) :-
lookup(V, Env, Val),
(Val == 0 ->
runtrace(Rest, Env, TraceFromStart)
;
resume_interp(Env, ResumeVars, L)
).
resume_interp(Env, [], L) :-
block(L, Block),
interp(Block, Env).
どのように実行がガードオペレーションの第三引数にエンコードされたラベルとしてインタプリタに引き渡されるのでしょうか。
ResumeVars が何なのかは、後のエントリで見ることにします。
今のところ、それは常に空のリストであると仮定します。
トレースのためのこのインタプリタを使うことで、サンプルをトレースし、実行できます。
:- do_trace(power_rec, [res/1, x/10, y/20]). trace op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop))) opttrace op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop))) 100000000000000000000
もちろんこの例はあまり面白くありません。 トレースの結果はほとんどオリジナルのコードと同じだからです。 後のエントリではより面白い例を示します。
ここでは、トレーサは実際にはインタプリタにはあまり手を加えていません。 しかし、この線形化コントロールフローに深く高度な動作はありません。 このセクションでは、より面白いことをするためにコントロールフロー言語にトレーサを許可する、重要ですが単純な拡張機能を追加します。 この拡張機能はプロモーションと呼ばれます。
プロモーションは、基本的にはプログラマがコントロールフロープログラムに追加できるヒントです。
プロモーションは変数 V と ラベル L を引数に取る promote(V, L) のようなオペレーションです。
インタプリタがこの文を実行するとき、単にラベル L にジャンプし、変数を無視します。
interp(promote(_, L), Env) :-
interp(jump(L), Env).
ただし、トレーサはいくつかの遙かに面白いことをします。
トレーサの
promote 文は V の値について知るために非常に役立つであろうヒントをトレーサに与え、残りのトレースでその値は定数として保持する必要があります。
従って、トレーサがプロモーションを検出すると、特殊な種類の guard_value と呼ばれるガードを挿入します。
trace(promote(V, L), Env, guard_value(V, Val, [], L, T), TraceAnchor) :-
lookup(V, Env, Val),
trace(jump(L), Env, T, TraceAnchor).
guard_value は興味深いオペレーションです。変数 V の現在の値 FVal をトレースの中に凍結するからです。
トレースが実行される時、ガードは変数の現在の値と凍結した値が同じかどうかをチェックします。
もし同じであれば、実行は継続されます。そうでなければトレースは終了します。
runtrace(guard_value(V, FVal, ResumeVars, L, Rest), Env, TraceFromStart) :-
lookup(V, Env, Val),
(Val == FVal ->
runtrace(Rest, Env, TraceFromStart)
;
resume_interp(Env, ResumeVars, L)
).
このオペレーションはどのように使えるのでしょうか? これは、変数 V があまり変更されないことや、これにより現在の値をトレースの中に凍結するのに役立つといったようにトレーサとコミュニケーションをとる方法です。 これによって毎回 V の値を知ることなく処理を進められます。
ここで、(少し考えられた)例を見てみましょう。
l:
c = i >= 0
if c goto b else goto l_done
l_done:
print_and_stop(var(i))
b:
promote(x, b2)
b2:
x2 = x * 2
x3 = x2 + 1
i = i - x3
goto l
プログラムの構文に落とし込みます。
block(l, op2(c, ge, var(i), const(0),
if(c, b, l_done))).
block(l_done, print_and_stop(var(i))).
block(b, promote(x, b2)).
block(b2, op2(x2, mul, var(x), const(2),
op2(x3, add, var(x2), const(1),
op2(i, sub, var(i), var(x3),
jump(l))))).
これは単純な x * 2 + 1 のカウントダウンを行うループです。
どのような x が入力されたとしても、 i >= 0 が真である期間は長くありません。
x がほとんど変更されないと仮定すると、 x * 2 + 1 が定数に畳み込みが可能なのでイテレーションごとに再実行する必要がないとプロモートする価値があります。
これは x のプロモーションによって完了します (もちろんこのループは不変のループを使ったコードに最適化され、よく動くでしょう、 x はループ中では実際に変更されないためです)。
これをトレースするには、以下のクエリを実行する必要があります。
?- do_trace(b, [i/100, x/5]). trace guard_value(x,5,[],b2,op2(x2,mul,var(x),const(2),op2(x3,add,var(x2),const(1),op2(i,sub,var(i),var(x3),op2(c,ge,var(i),const(0),guard_true(c,[],l_done,loop)))))) opttrace guard_value(x,5,[],b2,op2(x2,mul,var(x),const(2),op2(x3,add,var(x2),const(1),op2(i,sub,var(i),var(x3),op2(c,ge,var(i),const(0),guard_true(c,[],l_done,loop)))))) -10
トレースをより読みやすい方法で書くと
guard_value(x,3,[],b2, op2(x2,mul,var(x),const(2), op2(x3,add,var(x2),const(1), op2(i,sub,var(i),var(x3), op2(c,ge,var(i),const(0), guard_true(c,[],l_done, loop))))))
After the guard_value the operations performed on x could be constant-folded away, because the guard ensures that x is 5 before execution continues. To actually do the constant-folding we would need some optimization component that optimizes traces. This will be done in the next blog post.
guard_value の後で、 x へのオペレーションの実行は定数にたたみ込まれてなくなります。
x が 5 であると実行が継続される前にガードが保証するからです。
実際に定数畳み込みを実行するには、トレースを最適化するためのいくつかのコンポーネントが必要です。
これは次回のエントリで言及します。
In this section I mostly talked about how promotion is realized in the tracer, not what and how to use to use it for. Promotion is one of the most important ingredients that's responsible for the success of PyPy's tracing approach. How this works is discussed in detail in the paper "Runtime feedback in a meta-tracing JIT for efficient dynamic languages".
このセクションでは、どのようにトレーサにプロモーションを実装するかについて話し、何をどのように使うかについては触れていません。 プロモーションは一番重要な PyPy のトレーシングのアプローチの成功のために責任のある要素の一つです。 どのようにこれが動くのかは、 "Runtime feedback in a meta-tracing JIT for efficient dynamic languages" で詳しく説明されています。
このエントリでは、とても小さな最小限のトレーサと、生成されたトレースのためのインタプリタを見ました。 トレーサはオリジナルのインタプリタにとても似ていて、それはまた実行されたオペレーションを追跡して、さらにプログラムを実行します。 トレーシングの段階ではループは閉じられていて、その後トレースは最適化され、実行されます。 失敗のガードがヒットしている間トレースの実行が続きます。 ある時点で、実行は通常のインタプリタに戻ります (そしてこのシンプルな実装では通常のインタプリタに戻ったままになります) 。
オリジナルのプログラムで promote を呼ぶことでヒントの追加を可能にするトレーサの拡張もお見せしました。実行時の値をトレースに凍結して保持するフィードバックをトレーサに指示するものです。
この拡張機能は、前回のエントリで実装した部分評価器では不可能です。部分評価は厳密に実行前に終了し、変数の値がわかっていない場合は、実行時の値は見つけられない可能性が高いです。
In the next post I will show how to optimize traces before executing them and how the optimizer for traces is related to partial evaluation.
次のエントリでは、プログラムの実行前にトレースをどのように最適化するかと、どのようにトレースのオプティマイザが部分評価と関わるかについてお見せします。