B演習(言語処理系演習)第一回

B演習(言語処理系演習)第8回
12/5
評価器
田浦
gdbのインストール

$ su (パスワード入力)
# apt-get install gdb
すでにそろっている材料

すでにそろっている材料
• 構文木(実行すべきプログラムの文面を表した
データ構造)
• Python値の表現や構築方法
• mk_py_int(5), mk_py_float(3.3), …

最終ステージ : 評価器
• プログラムを実行  言われたPython値を作ったり，
表示したり，etc.
概要
環境の概念
 式を評価する

• 演算子，組み込み関数の実装法
文を評価する
 実行時エラーの表示

最終課題について
いずれも規定課題の正しい実行+性能測定
 選択肢

• ○ mini-Python
• △ sub-Python =
mini-Python – 辞書，リスト，タプル，文字列
• ◎ mini-Python + α
• αの例
• 性能向上
• オリジナルなmini-Pythonプログラム(大きめ)
• GC
sub-Python

サポートするデータ型が
• 整数，浮動小数点数，None, 関数(Python, native)
だけ
• おまけとして for 文もなくなる(文字列，タプル，リ
ストのどれかがないと実行できないため)
• これでも評価器の大部分を作ることにはなるが，
組み込み関数・演算子の数が激減し，各々の演
算子の動作も単純になる
期待する進め方



× まずはとにかくレジュメを熟読してから…
× まずは公開ソースを熟読してから…
○
• レジュメをまずざっと読む
• 要するに完成すべきもの(要するにPythonプログラムが実
行できれば良い)が何かを理解する
• 細かいことはさておき，動く「原理」を理解する．原理を理
解したらそれをもとにとにかく自分で作り始めてみる
• 分からなくなったとき，正しい道を進んでいるか不安に
なったときにレジュメを見る
式を評価する

py_val_t eval_expr(expr_t e, …)
評価値のデータ表現
構文木
構文木評価値のデータ表現
全体像

py_val_t eval_expr(expr_t e, …) {
switch (e->kind) {
case expr_kind_var: …
case expr_kind_literal_int: …
case expr_kind_literal_float: …
…
}
}
最も簡単な場合の例(intリテラル)

case expr_kind_literal_int:
return mk_py_int(e->u.lit_i);
構文木中にある整数
mini-Pythonのデータ表現への変換(pyvalues.c)
簡単にいかない例: 変数

case expr_kind_var:
… e->u.var … ??
構文木を見ただけではその変数の値は分か
らない
 「変数名  値に関する情報」が必要

環境
環境


変数名とその値の対応を保持しているもの
ある式の評価値はそれだけでは定まらず，環境が
あってはじめて値が決まる
• 式を「環境の下」で評価する
• 同じ変数名でも関数が違えば異なる値を保持している
• それらは「環境が違う」
• eval_exprは「環境」を引数として受け取る

変数のスコープ規則(局所変数，大域変数)などを正
確に述べる上でも役に立つ概念
Pythonの変数，スコープ規則
局所変数と大域変数
 z = 10
def f():
y = 20
def g():
z = 30
def h():
global z
z = 40

大域変数zへの代入
局所変数yへの代入
局所変数zへの代入
大域変数zへの代入
変数参照
まず局所変数を，なければ大域変数を参照
する
 z = 10
def f():
z = 5
return z
局所変数zを参照
def g():
return z

大域変数zを参照
環境による説明
プログラム全体で唯一，大域環境が作られる
 毎関数呼び出し時に，その呼び出し用の「局
所環境」が作られる
 あらゆる式・文は，局所環境，大域環境の下
で評価される(便宜上，トップレベルは局所環
境=大域環境と考える)

eval_exprのインタフェース
局所環境

大域環境
py_val_t eval_expr(expr_t e,
env_t lenv, env_t genv,
stack_trace_t bt)
スタックトレース(関数呼び出し履歴)
エラーメッセージの表示用(後述)
変数への代入, global

global x
• 局所環境で「xは大域変数である」とマーク

x=v
• 局所環境のxをvにセット
• ただし，xが大域変数であるとマークされていれば
大域環境のxをvにセット
変数の参照
局所環境を探索
 見つからなければ，またはその変数が大域
変数であるとマークされていれば大域環境を
探索
 見つかればそれが評価値
 見つからなければ実行時エラー

環境のインタフェース





env_t mk_env()
env_set(env_t env, char* key, py_val_t val)
py_val_t env_lookup(env_t env, char * key)
void env_set_global(env_t env, char * key)
int env_is_global(env_t env, char * key)
変数参照の評価(まとめ)

py_val_t env_lookup_var(
env_t lenv, env_t genv,
char * key, …)
{
py_val_t v = env_lookup(lenv, key);
if (v != py_val_not_found
&& v != py_val_global)
return v;
v = env_lookup(genv, key);
if (v != py_val_not_found)
return v;
else エラー;
}
その他のケース
expr_kind_display_tuple:
/* [ a, b, c,...] */
要素部を評価してデータを作る関数を呼ぶ
(mk_py_tuple, /*
etc.)
 expr_kind_display_list:
[ a, b, c,...] */
sub-Pythonでは不要
 expr_kind_display_dict:
/* { a : x, b : y } */
 expr_kind_paren:
/* ( e ) */
カッコ内の式を評価する
 expr_kind_operator:
/* e + e, etc. */
ほとんどの場合関数呼び出しの一種とみなせる(後述)
 expr_kind_subscript:
/* e[e] */
 expr_kind_attref:
/* e.f */
単独で現れたらエラー(後述)
 case expr_kind_call:
/* e(e:e,..) */

関数呼び出し式の評価

E0 (E1, …, En)の評価 (後でひとつだけ例外説
明)
• E0を評価  py_val_t : f
• E1, …, En を評価  py_val_vec_t : A
• 場合1: f が native関数の場合対応するC関数
を呼び出す
• 場合2: f が Python関数の場合後述
• 場合3: どちらでもない場合エラー
Python関数の呼び出し
新しい環境を作る(e’ = mk_env())
 その環境に「パラメータ名 : 渡された引数」を
登録する(env_set(e’, …))
 その新しい局所環境の下で関数の本体(文の
列)を評価する(eval_stmt_vec(…, e’, …)

E0がattref式の場合の例外
例: L.append(x)
 mini-Python固有の約束:

• L.append(x) = append(L, x)
• L.appendは構文としては，expr_kind_attrefという
種類の式として構文解析されるが，関数呼び出し
の関数の位置以外に現れることを許さない
• 関数呼び出しを評価する際にこの場合を特別扱
いする(レジュメ4.6節)
演算子，添え字式，などを関数呼び
出しとみなす

例: E0 + E1
•
•
•
•
実際評価の方法は似ている
E0 を評価  v0
E1 を評価  v1
v0 + v1を計算する(それほど簡単ではない)
そこでこれを add(E0 , E1)という関数呼び出し
だとみなして評価する
 addはどこかに(native関数，Python関数とし
て)定義する

文の評価
py_val_t eval_stmt(stmt_t s,
env_t lenv, env_t genv,
stack_trace_t bt)
 返り値の意味

•
•
•
•
py_val_continue  continueで実行が終了した
py_val_break  breakで実行が終了した
Pythonデータの表現  returnで実行が終了した
py_val_next それ以外で(普通に)実行が終了し
た
文の種類













stmt_kind_expression
stmt_kind_assignment
stmt_kind_pass
stmt_kind_return
stmt_kind_break:
stmt_kind_continue:
stmt_kind_del:
stmt_kind_print:
stmt_kind_global:
stmt_kind_if:
stmt_kind_while:
stmt_kind_for:
stmt_kind_fundef:
自明な3つ

pass, break, continue
• py_val_next, py_val_break, py_val_continueを返
すだけ
次に簡単な2つ

expression
• 式をeval_exprを用いて評価する
• py_val_nextを返す

return E
• Eをeval_exprを用いて評価する
• それを返す
「関数呼び出しとみなせる」文たち
print E
 del E0[E1]
 E0[E1] = E

環境を書き換える文(1)

global x
• 局所環境でxが大域変数であるとマーク
(env_set_global)

x=E
• Eを評価  v
• 局所環境でxをvにセット
• ただし，局所環境でxが大域変数であるとマークさ
れていれば(env_is_global)大域環境でxをvにセッ
ト
環境を書き換える文(2)
def f(x, y, …):
S
 Python関数(mk_py_ifun)を作って，環境に登
録

• 変数fへの代入と同じ効果
制御構造

if, while, for
エラーメッセージの表示
エラー発生ソース位置
 簡単なエラーメッセージ
 スタックトレース

スタックトレースのインタフェース


stack_trace_t mk_stack_trace()
void stack_trace_push(stack_trace_t
bt, char* name, src_pos_t call_site)
• btに，「nameとい関数がソース位置call_siteで呼ばれた」と記録(push)

void stack_trace_pop(stack_trace_t bt,
char* name, src_pos_t call_site)
• btから頂上のエントリをひとつ除去(pop)する．それは，「nameとい関数がソー
ス位置call_siteで呼ばれた」というエントリでなくてはならない

void print_stack_trace(stack_trace_t
bt)
まとめ:作る部品の全体像
各種演
算子，
組み込
み関数
環境(env_t)
native関数群
eval_expr
関数呼び出し
スタックトレース
実行時エラー表示
式文
eval_stmt
Pythonで書かれた組み込
み関数，演算子，添え字
式，del, printに対応した関
数群
del, print,
E[E] = E
まとめ:概念として重要だったもの

環境
• これがないと変数を含む式・文は評価できない

Python関数呼び出しの評価方法
• 新しい局所環境が作られる
• 引数のあたいが局所環境に登録されて渡される

様々な種類の式・文が「関数呼び出しの一種」とみ
なせる(要領よく実装)
• 演算子，添え字，添え字に代入，del, print

文を評価した結果の返り値
• py_val_continue, break, next

Download Report