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

B演習(言語処理系演習)第7回
データの表現
田浦
最終段階: 評価器
構文木
“fib”
def
n
if
<
n
…
評価器
(実行器)
2
そのプログラムが起こすべき副作用
(例: print)
評価器の仕事




print 1
 “1”を表示する
print x + 3
 x + 3の「値」(= 変数xに格納されている値 + 3)を
表示する
“x + 3”と表示するのではないことに注意
一般に， print <式>
 <式>の値(式を「評価した値」という)を表示する
 評価器の重要な仕事: 「式の値の評価」
もちろん文も
def f(x):
s = 0.0
for i in range(0, x):
s = s + i
return s
 print f(x)
 式f(x)の評価
 つまり，fの中身の実行
 文(の並び)の実行
  評価器のもうひとつ重要な仕事: 文の実行

式を「評価する」とはどういうことか?

評価器内部で何を起こせば式を「評価した」と
いえるのか?
• 入力は式を表す構文木(実はこれだけでは足りな
いが後述)
• 出力はあるPythonの値(整数，リスト，辞書，etc.)
 以降ではPython値と呼ぶ

つまり大雑把に言えば，
py_val_t eval_expr(expr_t e, …)
という，「eを評価したPython値を返す」C関数
を作ることが目標
文を「評価する」とはどういうことか

文はPython値を生み出すわけではない
• continue, break
• 代入文: a = 10
• etc.

文を評価した結果
• 何らかの副作用(例: 変数の値が変わる)が実行される
• 「次の文の選択」に影響を与える(continue/break/return)

目標: 以下の関数
eval_stmt(stmt_t s, …)
返り値は「次の文の選択」に必要な情報(continueが
実行された，など)
今日の話

Python値とは何かの定義
• 大部分は復習

データ表現の決定
すべてのPython値の列挙










整数
None
浮動小数点数
Python関数 (defで定義された関数)
Native関数 (処理系内部でCで定義された関数)
文字(1文字の文字列)
文字列
タプル
リスト
辞書
sub-Python (最小限)仕様
注: Native関数
defで定義されているわけではない
 処理系内部のCの関数に対応している
 mini-Pythonプログラムからは通常の関数と
同じように呼び出せる
 なぜ必要か?

• C関数を呼び出さないと書けない機能の追加
• 組み込み関数(足し算などを含め)を作る要領
• Cとmini-Pythonの組み合わせで作るため
(次週以降)組み込み関数の作り方

例: a + b は実は複雑
• a, bがともに整数なら整数の足し算
• a, bがともに数で，どちらかが浮動小数点数なら浮動小数
点数の足し算
• a, b がともに文字列，リスト，またはともにタプルなら連結

全部処理系内部(C)で実装するのは大変で要領が
悪い
• Cでは必要最小限の単純なもののみを作る
• mini-Pythonで書けるものはmini-Pythonで
+の場合のC/Pythonの切り分け

C:
•
•
•
•
•
•

整数同士の足し算
浮動小数点同士の足し算
文字列の連結
タプルの連結
リストのappend
整数  浮動小数点の変換
mini-Pythonプログラム :
• 場合わけをしながら適切な関数を呼ぶ本体
• def add(x, y): …

処理系内部：
• a + b  add(a, b)の呼び出しに変換
評価器を作る前に決めなくてはいけな
いこと: データ表現
様々な種類のPython値(整数，リスト，辞書，
etc.)がある
 式を評価すると，結果に対応するPython値が，
評価器(それはCのプログラム)によって作ら
れる
 あらゆるPython値がCプログラム中でどう表
現されるかの「取り決め」(データ表現)が必要

Python値
(我々の頭の中に
のみある)
写像(データ表現)
Cプログラムのあるデータ
データ表現(例)

Python値の [ 1, 2, 3 ]は評価器中でどういうC
のデータとして表現されるのか?
• おそらく適当な構造体を定義し，それへのポイン
タとするのであろう
Python値の “hello”はどう評価器中でCの
データとして表現されるのか?
 Python値の5は?
 Python値の3.28は?

データ表現に当たって重要なこと

(実行時に)データの種類がきちんと区別でき
ること
• 不法な演算(例: aが整数でa[i]を実行した)を検出
する
• 同じ構文でもデータが異なれば動作が異なる(例:
a[x])
基本枠組み
構造体 py_val, それへのポインタ型 py_val_t
を定義する
 typedef struct py_val { … } py_val, *
py_val_t;
 すべてのPython値は評価器内部では
py_val_t型 (py_valへのポインタ)のCデータと
して表す

可能なpy_val抜粋

typedef struct py_val {
py_type_t type;
/* 型を示す */
union {
int i;
/* 整数 */
double f;
/* 浮動小数点数 */
py_string s;
/* 文字列 */
py_ifun i;
/* Python関数 */
py_nfun n;
/* Native関数 */
… /* タプル，リスト，辞書 (省略) */
} u;
} py_val;
例: (浮動小数点数の足し算)

py_val_t fadd(py_val_t x, py_val_t y, …) {
if (x->type != py_type_float) runtime_error(…);
if (y->type != py_type_float) runtime_error(…);
z = (py_val_t)malloc(…);
z->type = py_type_float;
z->u.f = x->u.f + y->u.f;
return z;
}
整数くらいは速くしたい
ポインタ型(py_val_t)の変数に直接整数を代
入する
 つまり(後で若干修正するが)，
 Python整数5の表現 = ((py_val_t)5)

C言語における整数ポインタ間の代
入
int a[10];
int * p = a; /* 普通 */
int x = a; /* 整数  ポインタ */
p = x;
/* ポインタ  ポインタ */
 合法: 警告くらいでOKが出る
 機械語レベルでの動作は，まるで特別なこと
はない(bit列を「そのまま」moveしているだけ)

もちろんこれも「合法な」Cのプログラ
ム

/* 注: 以下の構造体の定義はあくまで例 */
typedef struct py_val
{
int x;
} * py_val_t;
main()
{
py_val_t p = 10; /* 10をポインタに代入 */
}
つまり…
py_val_t (ポインタ)もint (整数)も所詮はコン
ピュータ内部では整数(32個のbit列)
 C言語がそれを表面上区別しているに過ぎな
い
 その区別を「わざと」無視することは常に可能
 整数値をpy_val_t型の記憶領域(変数や
フィールド)に格納することに驚きはない(要す
るに32bit使うといっているに過ぎない)

各データ型の表現

もちろんこのとおりにやることを強制するわけではな
い
•
•
•
•
•
•
•
•
•
•
整数
文字(1文字の文字列)
None
浮動小数点数
文字列
Python関数
Native関数
タプル
リスト
辞書
ポインタ型の32bitに必要なデー
タをすべておしこむ(ポインタで
あってポインタでない) 32bit値
即値，unboxed value
本体(構造体)が別の場所にあり，
py_val_tの値はそれへのポインタ
boxed value
32bit値
整数

mini-Pythonにおける整数iの，インタプリタ内
部での表現(py_val_t型の値)
i の整数の2進表現
※暗黙の仮定：通常のポインタ(メモリ
割り当ての結果返されるアドレス)の最
下位bitは0
1
タグbit
整数である印
なぜこれが正しく整数のタグになる
か?
もちろん保証されているわけではない
 しかしmallocで返される値はほとんどの計算
機で4または8の倍数(32 bit/64 bit)
 スタックの変数のアドレスなども同様
 心配しないでそう仮定してよい(ためしに
mallocで返された値を表示してみるとよい)

実際にmini-Pythonの「5」を表すCの
式が書けますか?


答え: ((py_val_t)((5 << 1) + 1))
Cの整数から対応するmini-Pythonの整数を作る関
数
• py_val_t mk_py_int(int i) {
return ((py_val_t)((5 << 1) + 1);
}

mini-Pythonの値から，それが表す整数をCの整数と
して取り出す関数
• int py_val_int(py_val_t v) {
int x = (int)v;
if (x & 1) return (x >> 1);
else { error(); /* これは整数ではない! */ }
}
1文字

文字c (Cではcharだが要するに整数)例えば
以下のようにする
あき
c の2進表現(8bit) 010
((py_val_t)((c << 3) + 2))
 最下位bit = 0に注意(整数と区別可能)

None
0
0110
これまでは32bitにすべてが収まって
いた

以下は収まらない
•
•
•
•
•
•
•


浮動小数点数(64bit)
文字列
Python関数
Native関数
タプル
リスト
辞書
py_val構造体の中身を定義(ソースダウンロード)
それらのデータはその構造体を確保し，そのアドレ
スで表現する
py_val抜粋

typedef struct py_val {
py_type_t type;
/* 型を示す */
union {
double f;
/* 浮動小数点数 */
py_string s;
/* 文字列 */
py_ifun i;
/* Python関数 */
py_nfun n;
/* Native関数 */
… /* タプル，リスト，辞書 (省略) */
} u;
} py_val;
浮動小数点数

つまり，
32bitポインタ
a
a番地：
type=py_type_float
u.f=32.343
文字列

typedef struct py_string
{
int n; /* 文字数 */
char * a; /* C文字列 */
} py_string, * py_string_t;
32bitポインタ
a
a番地：
type=py_type_string
u.s.n=5
u.s.a=b
b番地：
‘h’‘e’‘l’‘l’‘o’ 0
Python関数

typedef struct py_ifun {
char * name; /* defされた名前 */
str_vec_t ps; /* 引数のベクタ
(文字列のベクタ) */
stmt_vec_t b; /* 本体(文のベクタ) */
} py_ifun, * py_ifun_t;
Native関数

typedef py_val_t (*C_fun_t)(); /* C関数 */
typedef struct py_nfun
{
char * name;
/* 名前 */
int arity;
/* 引数の数 */
C_fun_t f;
/* C関数 */
} py_nfun, * py_nfun_t;
タプル，リスト，辞書

各自(資料を見ながら)工夫してみてください
• データをどう格納するか?
• それらに対する操作(a[i], a[i] = x, len(a)など)をき
ちんと実現できるか?
今週の課題
データ表現の理解
 py_values.h, incomplete_py_values.cの完成
(雛形ダウンロード可)
 各データ型に対するプリミティブな演算を関数
としてたくさんつくってみよ

• それらは後に評価器やmini-Pythonプログラムか
ら呼ばれる
• 何が必要か自分で整理してみよ

Download Report