より大きなフローグラフ言語の例

より大きなフローグラフ言語の例

トレーシングと部分評価の比較 Part4

このエントリは部分評価とトレーシングの比較シリーズの四つ目、そして最後のエントリです。
長い道のりを歩んでいます。
シリーズの最初では小さなフローグラフ言語のインタプリタとその部分評価器をお見せしました。
二つ目では同じ言語にトレーサがどのように動作するかと、部分評価とどのように関係するかについてお見せしました。
三つ目ではトレースのためのオプティマイザについて説明しました。
この最後のエントリでは、トレーシングと部分評価の二つの別々のアプローチの例を挙げ、その意味から比較と対比します。
フローチャート言語のプログラムは、これまで見てきたものはかなり小さいのですが、今回は大きなプログラムの例で示したいと思います。それは非常に単純なバイトコードセットのインタプリタです。
部分評価器がインタプリタにどのような処理を行うかを見ていきます。そして、トレーサが同様に何を行うかも見ていきます。
このシリーズで使われている全てのコードはこちらにあります: http://paste.pocoo.org/show/550282/ (トレースをプリントするよりよい方法などのいくつかの小さなプログラムを追加しています。)

バイトコードインタプリタ

フローグラフ言語でプログラムを記述することは痛みを伴いますが、今まで見てきた小さなものよりもう少し興味深い例を与えるためにまだ書かなければいけません。例は、非常に簡単なレジスタマシンのバイトコードインタプリタで、その一つであるアキュムレータは実際に全ての操作が実行されます。

この言語のオペコードは;

1. jump_if_a: アキュムレータが非ゼロの場合、ターゲットアドレスにジャンプします
   
2. mov_a_r0, mov_a_r1, mov_a_r2: アキュムレータの値をそれぞれのレジスタに移します
   
3. mov_r0_a, mov_r1_a, mov_r2_a: レジスタの値をアキュムレータに移します
   
4. add_r0_to_a, add_r1_to_a, add_r2_to_a: レジスタの値をアキュムレータに加算します
   
5. decr_a: アキュムレータの値をデクリメントします
   
6. return_a: アキュムレータの値をプリントしてプログラムを終了します
   

インタプリタは現在のプログラムカウンタの一にあるオペコードを読み、if 文までの一連の(長い)バイトコードをディスパッチし正しいオペコードを行するメインループを持ちます。
その後、次のオペコードに対しても同様の処理を行います。

擬似コードとしてのフローグラフ言語のソースコードの一部です:

bytecode_loop:
    opcode = bytecode[pc]
    pc = pc + 1
    c = opcode == 'jump_if_a'
    if c goto op_jump_if_a else goto not_jump_if_a

# select the right bytecode via a long series of if statements
not_jump_if_a:
    c = opcode == 'mov_a_r0'
    if y goto op_mov_a_r0 else goto not_mov_a_r0
not_mov_a_r0:
    c = opcode == 'mov_a_r0'
    if y goto op_mov_a_r1 else goto not_mov_a_r1
...

# bytecode implementations
op_mov_a_r0:
    r0 = a
    goto bytecode_loop

op_jump_if_a:
    c = a == 0
    target = bytecode[pc]
    pc += 1
    if c goto bytecode_loop else goto op_jump_if_a_jump

op_jump_if_a_jump:
    pc = target
    goto bytecode_loop
...

そして実際に Prolog の fact として動きます。(完全な実装は上記リンクを辿ると見つけられます):

% bytecode dispatch loop
block(bytecode_loop,
      op2(opcode, readlist, var(bytecode), var(pc),
      op2(pc, add, var(pc), const(1),
      op2(c, eq, var(opcode), const(jump_if_a),
      if(c, op_jump_if_a, not_jump_if_a))))).

% select the right bytecode via a long series of if statements
block(not_jump_if_a,
      op2(c, eq, var(opcode), const(mov_a_r0),
      if(c, op_mov_a_r0, not_mov_a_r0))).
block(not_mov_a_r0,
      op2(c, eq, var(opcode), const(mov_a_r1),
      if(c, op_mov_a_r1, not_mov_a_r1))).
...

% bytecode implementations
block(op_jump_if_a,
      op2(c, eq, var(a), const(0),
      op2(target, readlist, var(bytecode), var(pc),
      op2(pc, add, var(pc), const(1),
      if(c, bytecode_loop, op_jump_if_a_jump))))).
block(op_jump_if_a_jump,
      op1(pc, same, var(target),
      promote(bytecode, bytecode_loop))).
block(op_mov_a_r0,
      op1(r0, same, var(a), jump(bytecode_loop))).
...

bytecode_loop ブロックはメインのディスパッチループです。
バイトコードリストからプログラムカウンタの一にあるオペコードを読み出し、
現在のオペコードを様々な既存のオペコードと比較する長い一連の if 文を持ちます。
インタプリタの完全なコードは上のリンクを辿るとあります。

インタプリタのバイトコードは実際には非常に複雑なプログラムを許可しませんが、以下のように数値を二乗するプログラムを書くことに使えます:

mov_a_r0     # r0 = a
mov_a_r1     # r1 = a
# 2:
mov_r0_a     # r0--
decr_a
mov_a_r0
mov_r2_a     # r2 += a
add_r1_to_a
mov_a_r2
mov_r0_a     # if r0!=0: goto 2
jump_if_a 2
mov_r2_a     # return r2
return_a

バイトコードインタプリタの部分的な評価

最初のエントリの部分評価器は、簡単にバイトコードインタプリタを部分評価できます。
静的な入力は、上記のように二乗の計算を行うバイトコードとプログラムカウンタの初期値です。
動的な入力はアキュムレータの内容(二乗する値)です。これは次のように行えます:

?- bytecode_square(B),
Env = [bytecode/B, pc/0],
do_pe(bytecode_loop, Env, Label),
REnv = [a/16, r0/0, r1/0, r2/0],
interp(jump(Label), REnv), listing(block).
256
:- dynamic block/2.

<lots of generated code>

部分評価器が処理した結果生成されたコードは若干読みづらいです。
以下のように様々なパスを含んでいるためです:

...
block(op_return_a1, print_and_stop(var(a))).
block(not_decr_a1, jump(op_return_a1)).
block(not_add_r2_to_a2, jump(not_decr_a1)).
block(not_add_r1_to_a2, jump(not_add_r2_to_a2)).
block(not_add_r0_to_a3, jump(not_add_r1_to_a2)).
block(not_mov_r2_a3, jump(not_add_r0_to_a3)).
block(not_mov_r1_a5, jump(not_mov_r2_a3)).
block(not_mov_r0_a5, jump(not_mov_r1_a5)).
block(not_mov_a_r27, jump(not_mov_r0_a5)).
block(not_mov_a_r18, jump(not_mov_a_r27)).
block(not_mov_a_r09, jump(not_mov_a_r18)).
block(not_jump_if_a11, jump(not_mov_a_r09)).
block(bytecode_loop12, jump(not_jump_if_a11)).
block(op_mov_r2_a2, op1(a, same, var(r2), jump(bytecode_loop12))).
...

すなわち、何もせずに別のブロックにジャンプするブロックが沢山あるということです。
散在するいくつかのブロックは実際のオペレーションを含んでいます。
手動で出力されたコードを綺麗にし、以下のようなものができあがりました。
(このクリーンアップの手順は、良い部分評価システムであれば部分評価の後に評価器自身が行うでしょう):

block(bytecode_loop1,
    op1(r0, same, var(a),
    op1(r1, same, var(a),
    op1(a, same, var(r0),
    op2(a, sub, var(a), const(1),
    op1(r0, same, var(a),
    op1(a, same, var(r2),
    op2(a, add, var(a), var(r1),
    op1(r2, same, var(a),
    op1(a, same, var(r0),
    op2(c, eq, var(a), const(0),
    if(c, bytecode_loop11, op_jump_if_a_jump1)))))))))))).

block(bytecode_loop11,
    op1(a, same, var(r2),
    print_and_stop(var(a))).

block(op_jump_if_a_jump1,
    op1(a, same, var(r0),
    op2(a, sub, var(a), const(1),
    op1(r0, same, var(a),
    op1(a, same, var(r2),
    op2(a, add, var(a), var(r1),
    op1(r2, same, var(a),
    op1(a, same, var(r0),
    op2(c, eq, var(a), const(0),
    if(c, bytecode_loop11, op_jump_if_a_jump1)))))))))).

このコードから何が見えてくるのでしょうか?
部分評価器は 最初のオペコード mov_a_r0 と mov_a_r1 に対応する bytecode_loop1 ブロックを生成し、一回のループの反復で一緒に処理されます。
そして、メインループのコピー(op_jump_if_a_jump1 ラベル)か、結果を出力して停止する bytecode_loop1 へとジャンプします。
バイトコードを処理した結果の残留コードを実行します:
アキュムレータの値を二乗し、出力します。
使われる全てのバイトコードとプログラムカウンタはなくなります。

何故部分評価器は同じように見えるメインループの二つのコピーを生成したのでしょうか?
その理由は二つ目のコピーにある追加の静的情報 target = 2 がわかったためです。
target はインタプリタのソースにあるジャンプ先を指定する変数ですが、この処理の間はとても簡単です。
この追加の静的情報は残留コードに何の影響も及ぼしませんが、同じコードが無駄に生成されます。
これは、過剰な特殊化の例です。

インタプリタをトレースする

このセクションでは、インタプリタのトレースを試みたときに何が起こるかをお見せします。
一回の反復で停止してしまうため、トレースを生成する自然な方法有用ではありません。
この問題を回避する方法に注目しました。
このセクションで説明している問題は、Tracing the meta-level: PyPy's tracing JIT compilerというペーパーのコアとなっています(ペーパー中では例より少し高度なバイトコードインタプリタを使っています)。

インタプリタのトレースするために bytecode と pc の二つの変数を常にプロモートすることは、上記のコードから bytecode_loop ブロックを置き換えるのに有用です。
それらを知らずにトレースを生成することはあまり意味がなく、面白みもありません。
これは、上記の部分評価の例で静的にそれらの変数を作ることと似ています:

block(bytecode_loop,
      promote(bytecode, bytecode_loop_promote_bytecode)).
block(bytecode_loop_promote_bytecode,
      promote(pc, bytecode_loop_promote_pc)).
block(bytecode_loop_promote_pc,
      op2(opcode, readlist, var(bytecode), var(pc),
      op2(pc, add, var(pc), const(1),
      op2(c, eq, var(opcode), const(0),
      if(c, op_jump_if_a, not_jump_if_a))))).
...

インタプリタの残りの部分は変更していません。

インタプリタのトレースするために、 単純な bytecode_loop ラベルから開始します。
インタプリタ中の bytecode_loop ラベルは一番高い頻度で飛び先として使われるためです。 (プロファイラは簡単に確立する可能性があります):

?- bytecode_square(B),
        A = 16, Env = [bytecode/B, pc/2, a/A, r0/A, r1/A, r2/0],
        do_trace(bytecode_loop, Env).
trace
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
  guard_value(pc,2,[],bytecode_loop_promote_pc)
  op2(opcode,readlist,var(bytecode),var(pc))
  op2(pc,add,var(pc),const(1))
  op2(c,eq,var(opcode),const(jump_if_a))
  guard_false(c,[],op_jump_if_a)
  op2(c,eq,var(opcode),const(mov_a_r0))
  guard_false(c,[],op_mov_a_r0)
  op2(c,eq,var(opcode),const(mov_a_r1))
  guard_false(c,[],op_mov_a_r1)
  op2(c,eq,var(opcode),const(mov_a_r2))
  guard_false(c,[],op_mov_a_r2)
  op2(c,eq,var(opcode),const(mov_r0_a))
  guard_true(c,[],not_mov_r0_a)
  op1(a,same,var(r0))
  loop

opttrace
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
  guard_value(pc,2,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]],bytecode_loop_promote_pc)
  op1(a,same,var(r0))
  op1(bytecode,same,const([mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]))
  op1(pc,same,const(3))
  op1(opcode,same,const(mov_r0_a))
  op1(c,same,const(1))
  loop

256
B = [mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a, mov_a_r2, mov_r0_a|...],
A = 16,
Env = [bytecode/[mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a|...], pc/2, a/16, r0/16, r1/16, r2/0]

生成されたこれらのトレースはとても短いです。
bytecode と pc のプロモートとともに開始し、続いてバイトコードの 2 番目に位置する命令であるオペコード mov_r0_a を実行します。
そして pc をインクリメントし、ループの開始に戻ります。
最適化されたトレースを見ると、本質的に役に立たないことは明らかです。
それらは一回の反復でのみ実行されます。二回目の反復では pc は 3 になり、 guard_value が冒頭で失敗してしまうためです。

この問題はバイトコードディスパッチループのトレースを一回以上行うことで解決できます。
この手法はメタトレーシングと呼ばれます。
この挙動を得るために、このシンプルな例では、開始するのに十分な (かつ終了する) トレースを別のラベル op_jump_if_a_jump で行っています。
このラベルは、インタプリタが jump_if_a バイトコードを実行し、ジャンプしたときにヒットします。
実行されたバイトコードプログラム上のレベルのループでは、一つのジャンプにすぎません。
従って、このラベルからトレースすることでバイトコード上の全てのループがトレースされます。
全てのループとは、制御フロー言語のバイトコードディスパッチループに潜在的に含まれる多くの反復です。

生成結果は以下のとおりです:

?- bytecode_square(B),
        A = 16, Env = [bytecode/B, pc/11, a/A, r0/A, r1/A, r2/0, target/2],
        do_trace(op_jump_if_a_jump, Env).
trace
  op1(pc,same,var(target))
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop)
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
  guard_value(pc,2,[],bytecode_loop_promote_pc)
  op2(opcode,readlist,var(bytecode),var(pc))
  op2(pc,add,var(pc),const(1))
  op2(c,eq,var(opcode),const(jump_if_a))
  guard_false(c,[],op_jump_if_a)
  op2(c,eq,var(opcode),const(mov_a_r0))
  guard_false(c,[],op_mov_a_r0)
  op2(c,eq,var(opcode),const(mov_a_r1))
  guard_false(c,[],op_mov_a_r1)
  op2(c,eq,var(opcode),const(mov_a_r2))
  guard_false(c,[],op_mov_a_r2)
  op2(c,eq,var(opcode),const(mov_r0_a))
  guard_true(c,[],not_mov_r0_a)
  op1(a,same,var(r0))
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
  guard_value(pc,3,[],bytecode_loop_promote_pc)
  op2(opcode,readlist,var(bytecode),var(pc))
  ...
  lots of operations ommitted
  ...
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
  guard_value(pc,9,[],bytecode_loop_promote_pc)
  op2(opcode,readlist,var(bytecode),var(pc))
  op2(pc,add,var(pc),const(1))
  op2(c,eq,var(opcode),const(jump_if_a))
  guard_true(c,[],not_jump_if_a)
  op2(c,eq,var(a),const(0))
  op2(target,readlist,var(bytecode),var(pc))
  op2(pc,add,var(pc),const(1))
  guard_false(c,[],bytecode_loop)
  loop

opttrace
  op1(pc,same,var(target))
  guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop)
  guard_value(pc,2,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]],bytecode_loop_promote_pc)
  op1(a,same,var(r0))
  op2(a,sub,var(a),const(1))
  op1(r0,same,var(a))
  op1(a,same,var(r2))
  op2(a,add,var(a),var(r1))
  op1(r2,same,var(a))
  op1(a,same,var(r0))
  op2(c,eq,var(a),const(0))
  guard_false(c,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],pc/11,opcode/jump_if_a,target/2],bytecode_loop)
  op1(bytecode,same,const([mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]))
  op1(pc,same,const(11))
  op1(opcode,same,const(jump_if_a))
  op1(target,same,const(2))
  op1(c,same,const(0))
  loop

256
B = [mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a, mov_a_r2, mov_r0_a|...],
A = 16,
Env = [bytecode/[mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a|...], pc/11, a/16, r0/16, r1/16, r2/0, target/2] .

よくなったように見えます。
トレースはインタプリタで実行する、上記例で示した二乗関数のループの中の全てのバイトコードに対応します。
最適化されたコードは二つの(bytecode がまだ二乗関数のなかの一つであるかと、 pc が 2 であるかどうかをチェックする)ガードから始まります。そして、実際に計算するオペレーションのみ行います。
バイトコードディスパッチは行われず、従ってインタプリタ実行のオーバヘッドは全て取り除かれます。二つの guard_value オペレーションから離れて開始されます。

トレースの中のたくさんの割り当ては不要です。
例えば r0, r1, r2 レジスタと加算器 a 間のコピーなどです。
これらは SSA 形式を利用したより賢い最適化を用いることで簡単に解決できます。

インタプリタに関する結論

部分評価とメタトレーシングのどちらも例で用いた二乗を計算するバイトコードをインタプリタオーバヘッドのない、本質的なな計算でお見せした形式に変換する際に使われます。
素直な部分評価器はジャンプを行うだけのような沢山の追加のブロック生成しますが、後処理工程で解決可能です。
トレーサそのものは無駄に短いトレースを生成しますが、別の地点からトレースを開始する簡単なトリックを施すことでかなり良くなります。

実際のメタとレーシングシステムでは、メタトレーサはインタプリタの作者のために、どのバイトコードがバックエンドのジャンプに対応するかをマークするためのの方法が必要になります。
また、トレースをキャッシュするだけでなく自動的にトレースが開始されるように良く統合されている必要があります。
加えて、よく失敗するガード対処するしたり、失敗したガードに新しいトレースを接続する必要があります。
ただし、それらの全てはこの一連のプログエントリで発表した机上の空論に過ぎません。

高度な結論

トレーシングと部分評価の類似点に関するいくつかの高レベルな結論:トレーシングと部分評価は、自動的にインタプリタのオーバヘッドを減らすという似た問題に対処しようとしました。これらのアプローチはわずかに異なります。

トレーシングはいくつかの追加の情報をプロセスに保持するのみで、通常の評価機構にとても近いです。
しかし、トレーサの中で使われるオプティマイザは部分評価器ととても似た構造をとっています。
オプティマイザの仕事は、とても単純でオペレーションを線形リストにするのみです。制御フロー全てに対処する必要はありません。

トレーシングの検出は部分評価器の一部を利用し、 (「それらの中の評価できるものを評価するのみで、それ以外は残す」ということです)、部分評価されなかった(展開を制御する)パーツをより実用的なメカニズムによって置き換えます。
そのメカニズムは、実際のプログラムで実行される典型的な制御フローパスの選択を観測します。
同時に、トレーサの焦点はループに当たっています。
それらはプログラムの実行時間の殆どを占めているためです。

トレーシングの別の視点では、どのパスを見ているかの情報を提供する神託(実際に実行されたプログラム)によって部分評価器の制御コンポーネントを置き換えます。



ここ示したような非常に簡単なインタプリタでは既に効果が現れています。
単純な部分評価器は二つの全く同じループを生成するなどの過剰な特殊化を行います。
トレーサはそのような挙動をせず、初期化するオペコードではないループ自体のコードだけを生成します。

このシリーズでは、以上のようなものを作りました。お付き合いありがとうございます。
また、ここにこれらのPostをする前に一貫して良いフィードバックをくれた Samuele と Sven に感謝を示します。

FlowGraph 言語のトレースの最適化

原文はこちら

トレーシングと部分評価の比較 Part3

これは部分評価とトレーシングを比較するシリーズの三つ目のエントリです。最初のエントリでは、小さ FlowGraph 言語をインタプリタとともに紹介し、FlowGraph 言語の部分評価器をお見せしました。二つ目のエントリでは、トレーサが同じ言語にどのように働くかと、部分評価とトレーサの二つの実行がどのように関係するのかをお見せしまし、プロモーションの機能をトレーサに追加しました。
このエントリでは、トレーサによって生成されたトレースをどのように最適化するかをお見せし、部分評価のオプティマイザの構造とトレーサのオプティマイザの構造を比較します。
このエントリで使われているソースコードはここにあります: http://paste.pocoo.org/show/547304/

トレースの最適化

前回のエントリで、どのようにスペシャルモードでの制御フローグラフプログラムの実行によるガードとともに線形化したトレースを生成するかを見ました。トレースはいつも loop 文で終わり、開始地点にジャンプします。トレーサはインタプリタが実行したオペレーションのログを取るだけなので、出力されるトレースには余計なオペレーションが含まれてしまいます。一方で、トレースはプロモーションといくつかの決定を通して、最適化に利用できるいくつかの実行時の値も含みます。以下の例は、前回のエントリのサンプルのプロモーションによって生成されたトレースです。

op2(c,ge,var(i),const(0),
guard_true(c,[],l_done,
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),
loop))))))

guard_value(x, 5, ...) の操作の後、 x が 5 であるとわかります。ただし 5 ではない場合、実行はインタプリタにフォールバックされます。従って、 ガードの後の x に対するオペレーションは、定数に畳み込めます。定数畳み込みの並べ替えを行うために追加の最適化のステップが必要です。どの変数が定数として扱えるかと、どの値が部分環境で使われているかの情報を利用しながら最適化のステップはトレースに沿って動作します。オプティマイザは定数引数のみを持つオペレーションを取り除き、それ以外をトレースに残します。このプロセスは部分評価に実際に非常に似ていて、いくつかの分かっている変数は定数になり、定数引数のみのオペレーションは最適化によって取り去られ、残りはそのままです。
最適化を行うためのコードを以下に示します。

optimize(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),
        NewOp = RestResidual
    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op1(ResultVar, Op, RArg, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

optimize(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),
        NewOp = RestResidual
    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op2(ResultVar, Op, RArg1, RArg2, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

部分評価と同じですね!部分評価器からのヘルパ関数 presolve と部分環境 PEnv の再利用をしています。オペレーションの引数が部分環境の中で定数だと分かっている時、オペレーションは最適化の際に実行され、トレースから取り除かれます。そうでなければオペレーションは出力のトレースに残ります。結果の変数(部分評価器内にあるもの) は部分環境から取り除くために必要です。不明な結果によって上書きされるためです。
トレースの中でガードで対処する必要があります。

optimize(guard_true(V, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C) ->
        NewOp = RestResidual
    ;
        NewOp = guard_true(V, PEnv, L, RestResidual)
    ),
    optimize(Rest, PEnv, RestResidual).

optimize(guard_false(V, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C) ->
        NewOp = RestResidual,
        NEnv = PEnv
    ;
        write_env(PEnv, V, 0, NEnv),
        NewOp = guard_false(V, PEnv, L, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

ガードされた変数が実際は定数だとわかったとき、ガードを取り除けます。
注意としては、定数のガードが失敗したときは可能ではありません。 (??)
トレーサは実際の値で実行している間のオペレーションを記録します。
従って、値のガードが成功するにはオプティマイザが定数を検出する必要があります。
guard_false は guard_true と若干違います。guard_false の後は引数が実際に 0 だとわかりますが、 guard_true の後は値がゼロではないことのみ知り、正確な値はわかりません。
別の点に注目してください。カードによる最適化で、これまでのところ常に空リストだったガードオペレーションの二つ目の引数が部分環境 PEnv に置換されます。この置換がなぜ必要なのかを掘り下げて論じます。
変数の関係に関する本当に詳細な情報を提供することを除き、 guard_value の最適化はとても似ています。

optimize(guard_value(V, C, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C1) ->
        NewOp = RestResidual,
        NEnv = PEnv
    ;
        write_env(PEnv, V, C, NEnv),
        NewOp = guard_value(V, C, PEnv, L, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

このオペレーションは、オプティマイザが後のオペレーションで定数畳み込みのために利用する定数変数を得る主な方法です。以下が部分評価との主な違いです。

• オプティマイザは開始時にいくつかの変数の値を知っています。
  
• トレースの最適化時、最初はどの変数の値もわかりません。
  
• いくつかの変数についての情報は、ガードの実行後後にのみ得られます。
  

今はループ文で何が起こるのかの情報が不足しています。原則として、再度ループ文に入るとそれになる。(それって何? トレース状態?)
ただし、ループ文でいくつかの追加のオペレーションが出力のために必要です。出力とは、最適化して取り去ったオペレーションとそれによって定数として割り当てられる変数の結果の値です。それが意味するところは、関係する可能性のある変数がいくつかの古い値を持っている可能性があるということです。ループの次のイテレーションは、明らかに間違っているこの古い値で続けます。従って、ループ文以前にいくつか割り当てた部分環境のエントリごとに一つ出力する必要があります。

optimize(loop, PEnv, T) :-
    generate_assignments(PEnv, T).

generate_assignments([], loop).
generate_assignments([Var/Val | Tail], op1(Var, same, const(Val), T)) :-
    generate_assignments(Tail, T).

どのように割り当ての生成が働くかの例としては、以下の例を見てください。部分環境が [x/5, y/10] であるときに、続く割り当てが生成されます。

?- generate_assignments([x/5, y/10], Out).
Out = op1(x, same, const(5), op1(y, same, const(10), loop)).

それらがオプティマイザのコードの全てです。一方、基本的な構造は、部分評価器とよく似ていて、複雑な部分もあまりありません。部分評価器を作るのが難しいものは、制御フローステートメントへの対処と、同じブロックが同じ定数を使って部分評価されたときはコードが再利用可能かどうかの確認と対処の両方必要です。ここでは、全ての複雑なものは置いておきます。トレーサは既に全ての制御フローを削除してガードに置換していて、一回のループオペレーションが終わっています。従って、オプティマイザは単純に 1 パスのオペレーションを実行でき、いくつかを削除します。(ループ文へのいくつかの追加のケアも行います)
この機能を使うと、前回のエントリのプロモーションの例からトレースの最適化を行えます。

?- optimize(
    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)))))),
    [],
    LoopOut).
LoopOut = guard_value(x, 3, [], b2, op2(i, sub, var(i), const(7), op2(c, ge, var(i), const(0), guard_true(c, [x/3, x2/6, x3/7], l_done, op1(x, same, const(3), op1(x2, same, const(6), op1(x3, same, const(7), loop)))))))

より読みやすく、最適化したバージョンは以下です:

guard_value(x, 3, [], b2,
op2(i, sub, var(i), const(7),
op2(c, ge, var(i), const(0),
guard_true(c, [x/3, x2/6, x3/7], l_done,
op1(x, same, const(3),
op1(x2, same, const(6),
op1(x3, same, const(7),
loop)))))))

意図したとおり、 guard_value の後の x へのオペレーションは全て削除されます。ただし、いくつか追加された割り当て (x, x2, x3) が最終的に生成されています。この追加の変数は余分なものに見えますが、オプティマイザにはそれを簡単に認識するための十分な情報がありません。この挙動は修正できますが、より複雑にするというコストをかける必要があります。(実際のシステムでは静的単一代入形式 (static single assignment/SSA) にトレースを変換することがこの問題への解となっています)

インタプリタの再開

なぜ上記のコードは最適化できないガードのために部分環境を追加する必要があるのでしょうか? 理由は、なぜループの前に割り当てを追加しなければならないのか、ということに関連します。問題は、オプティマイザが変数の値を知るとき、オプティマイザが変数への割り当てを取り除くことにあります。それが意味することは、実行中の最適化されたトレースからインタプリタへのスイッチバックを行うときに環境の中のいくつかの変数が更新されず、インタプリタの実行が不適切に行われてしまいます。
上記の例で、これを変数 x2 と x3 に適用します。二つ目のガードが失敗したとき、最適化された場合はそれらは代入されません。従って、ガードは変数とその値(常に定数です)をリストします。
スイッチバックするとき、インタプリタ側の対応する変数に対する割り当てを作らなければいけません。従って、前回のエントリのコードに以下のように resume_interp 関数を適用する必要があります。

write_resumevars([], Env, Env).
write_resumevars([Key / Value | Rest], Env, NEnv) :-
    write_env(Env, Key, Value, Env1),
    write_resumevars(Rest, Env1, NEnv).

resume_interp(Env, ResumeVars, L) :-
    write_resumevars(ResumeVars, Env, NEnv),
    block(L, Block),
    interp(Block, NEnv).

再開時に、 ResumeVars (元の部分環境) は単に元の通常環境に追加され、インタプリタに戻ります。ガードの失敗時にトレースの実行を終了し、インタプリタの実行を再開するために必要な、ガードにアタッチされたデータは、多くの場合非常に複雑なトレースシステムの一部です。ほとんどのガードが失敗しないうちはデータは大きくなる可能性があります。従って、ほとんどの実際のシステムではアタッチされるデータの困難な圧縮を試みたりその後のガードとのデータの共有を試みたりしています。

まとめ

このエントリでは、部分環境の変数を適用してトレースを最適化方法とその原理について説明しました。

• 定数引数のみを持つ全てのオペレーションを実行し、それ以外を残すこと
  
• 制御フローを含まないため、トレースの最適化はとても単純であること
  
• 制御フローに関する全ての疑問はトレーシングコンポーネントによって予め解決しているということ
  

次の、そしてシリーズ最後のエントリでは、小さなバイトコードインタプリタを最適化できるトレーシングと部分評価のより大きな例をお見せします。

FlowGraph 言語のための単純なトレーサ

原文はこちら

Part2 トレーシングと部分評価の比較

部分評価とトレーシングの比較シリーズの二つ目のエントリです。最初のエントリでは、小さな 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))))))

guard_value の後で、 x へのオペレーションの実行は定数にたたみ込まれてなくなります。x が 5 であると実行が継続される前にガードが保証するからです。実際に定数畳み込みを実行するには、トレースを最適化するためのいくつかのコンポーネントが必要です。これは次回のエントリで言及します。

このセクションでは、どのようにトレーサにプロモーションを実装するかについて話し、何をどのように使うかについては触れていません。プロモーションは一番重要な PyPy のトレーシングのアプローチの成功のために責任のある要素の一つです。どのようにこれが動くのかは、"Runtime feedback in a meta-tracing JIT for efficient dynamic languages"で詳しく説明されています。

結論

このエントリでは、とても小さな最小限のトレーサと、生成されたトレースのためのインタプリタを見ました。トレーサはオリジナルのインタプリタにとても似ていて、それはまた実行されたオペレーションを追跡して、さらにプログラムを実行します。トレーシングの段階ではループは閉じられていて、その後トレースは最適化され、実行されます。失敗のガードがヒットしている間トレースの実行が続きます。ある時点で、実行は通常のインタプリタに戻ります (そしてこのシンプルな実装では通常のインタプリタに戻ったままになります) 。

オリジナルのプログラムで promote を呼ぶことでヒントの追加を可能にするトレーサの拡張もお見せしました。実行時の値をトレースに凍結して保持するフィードバックをトレーサに指示するものです。この拡張機能は、前回のエントリで実装した部分評価器では不可能です。部分評価は厳密に実行前に終了し、変数の値がわかっていない場合は、実行時の値は見つけられない可能性が高いです。

次のエントリでは、プログラムの実行前にトレースをどのように最適化するかと、どのようにトレースのオプティマイザが部分評価と関わるかについてお見せします。