担当者が打ち込む交通費の規則
経費精算のシステムでは、担当者が設定画面に fare * 2 + 300 のような規則を打ち込みます。規則は月ごとに変わります。
変わるたびにコンパイルして、システムを再起動したくはありません。そこでシステムは、規則の構文木を持っておき、申請が来るたびに、節を1つずつ計算します。
このレッスンのゴール
メモ
構文木をそのまま実行できる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| インタプリタ | 機械語を作らずに、別のプログラムを動かすプログラム | |
| 節 | 木の中の1つの点。ノードとも言う | BinOp |
| 評価する | 節の値を求めること | |
| 葉 | 下に何もない節 | Constant(value=2) |
| 環境 | 手の届く名前と、その値の組の集まり | {'fare': 420} |
| 束縛 | 1つの名前と、その値の組 |
学生が入力するセルは、このプレビューでは空白です。
Python は自分の構文木を見せる
Python もコンパイラです。1行を動かす前に、字句解析と構文解析をして構文木にします。モジュール ast は、キーボードやパイプから読んだ1行の木を出します。--mode eval は、その行が1つの式だという意味です。
節にはそれぞれ名前があります。葉は、下に何もない節です。Run が出す木を比べましょう。
fare * 2 + 300 の木
echo "fare * 2 + 300" | python3 -m ast --mode evalここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
(fare + 300) * 2 の木
echo "(fare + 300) * 2" | python3 -m ast --mode evalここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
前に - が付いた名前の木
echo "-fare" | python3 -m ast --mode evalここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: Python が出した節
| 節 | 何か | 値の出どころ |
|---|---|---|
| Constant(value=300) | 数を持つ葉 | その数そのもの |
| Name(id='fare') | 名前を持つ葉 | 名前を探した結果 |
| BinOp(left, op, right) | 両側のある演算 | 両側を求めてから演算する |
| UnaryOp(op, operand) | 片側だけの演算 | 中身を求めてから演算する |
| Add()、Mult()、USub() | どの演算か | なし。ただの印 |
学生が入力するセルは、このプレビューでは空白です。
子を評価してから、自分を評価する
木をたどるインタプリタは、節を評価する1つの関数です。数の葉なら、その数を返します。名前の葉なら、環境から値を探します。
演算の節は、まず左の子と右の子を評価し、2つの答えで自分の計算をします。子がまた木のこともあるので、関数は自分を呼びます。デモは + と * だけを扱います。
木をたどる評価器
# 構文木を評価します。数、名前、[op, left, right] のどれか。
def evaluate(tree, env):
if type(tree) == int:
return tree
if type(tree) == str:
# 名前の値は、環境から探します。
return env[tree]
left = evaluate(tree[1], env)
right = evaluate(tree[2], env)
if tree[0] == "+":
return left + right
if tree[0] == "*":
return left * right
return None
tree = ["+", ["*", "fare", 2], 300]
print(evaluate(tree, {"fare": 420}))
# 環境を {"fare": 210} に変えて、もう一度実行しましょう。
よくある間違い
注意
インタプリタは、裏で木を機械語に直して実行している、と思いがちです。木をたどるインタプリタは、そうしません。節を訪ねながら、その場で計算し、実行のたびにそれを繰り返します。だからコンパイルしたコードより遅く、そのかわりすぐに動き始められます。
名前は環境から探す
名前を持つ葉には、どこかから値が要ります。インタプリタは環境を持ちます。手の届く名前と、その値の組の集まりです。1つの組を束縛と言います。
Python の eval は、環境を辞書で受け取ります。2つ目の辞書を渡すと、Python はそちらを先に探します。内側のスコープが外側の名前を隠すのは、このしくみです。
環境を渡して評価する
python3 -c "print(eval('fare * days', {'fare': 420, 'days': 5}))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
名前を1つ抜く
python3 -c "print(eval('fare * days', {'fare': 420}))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
先に探される内側の環境
python3 -c "print(eval('fare * days', {'fare': 420, 'days': 5}, {'days': 20}))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: fare * days の名前を探す
| Run | fare の見つかった場所 | days の見つかった場所 | 出力 |
|---|---|---|---|
| 1つ目 | 1つの辞書: 420 | 1つの辞書: 5 | 2100 |
| 2つ目 | 1つの辞書: 420 | どこにもない | NameError |
| 3つ目 | 外側の辞書: 420 | 内側の辞書: 20 | 8400 |
学生が入力するセルは、このプレビューでは空白です。
さらに挑戦: 何度も使う関数
課題の評価器に、関数を足しましょう。["fun", param, body] は関数を作り、["call", f, arg] はそれを呼びます。関数の値は、param、body、作ったときの環境の3つを持つリストにします。
呼ぶときは、作ったときの環境をコピーして、param を引数の値に束縛し、body を評価します。呼んだ側の環境でなく、作ったときの環境を使うのはなぜか、テストを1つ書いて説明しましょう。