1時間に1万件の申請
前のレッスンの交通費の規則は、今では1時間に1万件の申請で使われています。そのたびに木をたどるのは、遅すぎます。
そこでシステムは、木を一度だけ、小さな手順の平らなリストに直し、申請ごとにそのリストを実行します。この翻訳が、コンパイラの最後の仕事です。
このレッスンのゴール
メモ
構文木を、スタックマシンの命令に変えられる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| コード生成 | 構文木を命令に変えること | |
| スタック | 最後に入れた値が最初に出る、値の山 | |
| スタックマシン | 命令がスタックから値を取る機械 | PUSH 2 |
| バイトコード | ソフトウェアが動かす、スタックマシンの命令 | |
| 最適化 | 同じことを、より少ない仕事でするようにコードを変えること | -O2 |
| 定数畳み込み | コンパイルのときに計算を済ませること | 6 * 7 が 42 になる |
学生が入力するセルは、このプレビューでは空白です。
スタックマシンは値をスタックに置く
スタックマシンは、途中の値をスタックに置きます。PUSH 2 は2を一番上に積みます。ADD は上の2つを取り、足して、答えを積みます。
木をスタックの命令にするには、まず子の命令を作り、そのあとで節自身の命令を出します。実行すると、子がそれぞれ値をスタックに残し、節がそれを使います。
例: 2 + 3 * 4 の命令
| 命令 | 実行したあとのスタック（右が一番上） |
|---|---|
| PUSH 2 | 2 |
| PUSH 3 | 2, 3 |
| PUSH 4 | 2, 3, 4 |
| MUL | 2, 12 |
| ADD | 14 |
学生が入力するセルは、このプレビューでは空白です。
+ と * のためのコード生成器
# コード生成: 子を先に、演算をあとに。
def generate(tree, code):
if type(tree) == int:
code.append(["PUSH", tree])
return
generate(tree[1], code)
generate(tree[2], code)
if tree[0] == "+":
code.append(["ADD"])
else:
code.append(["MUL"])
code = []
generate(["+", ["*", 420, 2], 300], code)
for line in code:
print(line)
# 木を ["*", ["+", 420, 300], 2] に変えて、もう一度実行しましょう。
Python もスタックマシンを動かす
Python は、実行のたびに木をたどってはいません。木をバイトコード、つまり Python の中のスタックマシンの命令にコンパイルし、それを動かします。
モジュール dis は、ファイルのバイトコードを出します。Run で1行のファイル fare.py を書き、そのバイトコードを見ます。最初の RESUME と最後の2行は、どのファイルにも付くので気にしません。
コンパイラのフォルダに入る
cd ~/compilerここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
1行のプログラムを書く
echo "total = fare * days + 300" > fare.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
そのバイトコード
python3 -m dis fare.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: fare.py のバイトコード
| バイトコード | 私たちの命令 | すること |
|---|---|---|
| LOAD_NAME fare | LOAD fare | fare の値を積む |
| LOAD_NAME days | LOAD days | days の値を積む |
| BINARY_OP (*) | MUL | 2つ取り、積を積む |
| LOAD_CONST 300 | PUSH 300 | 数 300 を積む |
| BINARY_OP (+) | ADD | 2つ取り、和を積む |
| STORE_NAME total | まだない | 一番上を取り、total に束縛する |
学生が入力するセルは、このプレビューでは空白です。
最適化はコンパイルのときに仕事をする
gcc は本物のプロセッサの命令を作ります。スタックのほかにレジスタも使います。-O2 を付けると、最適化もします。
Run でアセンブリを2回書きます。最適化なしと、最適化ありです。そして grep -c -w で、square(7) の答えの49という数がある行を数えます。プログラムのどこにも、49とは書いてありません。
最適化なしのアセンブリ
gcc -S -O0 -o plain.s hello.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
-O2 のアセンブリ
gcc -S -O2 -o fast.s hello.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
最適化なしで49のある行
grep -c -w 49 plain.sここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
最適化ありで49のある行
grep -c -w 49 fast.sここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
Python も定数を畳み込む
echo "seconds = 60 * 60 * 24" > day.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
畳み込まれた式のバイトコード
python3 -m dis day.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
最適化とは、同じ命令を速く動かすことだ、と思いがちです。-O2 の gcc は、仕事そのものを書き換えました。square(7) を自分で計算したので、main は掛け算をしません。プログラムの出力は同じです。することが変わらない限り、最適化はどの命令を変えても構いません。
さらに挑戦: 定数を畳み込む
課題の compile_tree に、定数畳み込みを足しましょう。演算の命令を出す前に、2つの子がどちらもただの数かを調べます。そうなら計算を済ませ、PUSH を1つだけ出します。
下から順に畳み込むと、["+", ["*", 60, 60], 24] は [["PUSH", 3624]] になります。名前を含む木が一部しか畳み込めない理由と、max_depth がどう変わるかを説明しましょう。