Edited at

Python3.x系でprint命令文を追加する話.

More than 1 year has passed since last update.

※この記事はEEICの「大規模ソフトウェアを手探る」という実験の成果レポートを兼ねてます

※この記事はその実験の前半に試みた内容の話で,後半の内容は「Pythonにプライベート変数を実装しようと試みた話。」です


背景

EEICにある「大規模ソフトウェアを手探る」という授業でPythonを手探ることにした.手頃な目標としてPython3.x系でprint命令文を追加しようということになった.実際に手探ったのは,Python-3.5.2なので,以後Python3.5.2と書く.


Python3.5.2でprint命令文を追加するとは

python3.5.2では,python2.x系にあったprint命令文がなくprint()関数になっている.python3.5.2でprint()関数とprint命令文が両方使えるように拡張した.

つまり,

print "HOGE"

print("HOGE")

が両方Python3.xで動くようにした.


とりあえずどこを変えれば動くの?

1: /src/Python-3.5.2/Grammar/Grammarのsmall_stmtが書かれた行を書き換え


Grammar

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |

import_stmt | global_stmt | exec_stmt | assert_stmt | print_stmt)

直後の行に以下を追加


Grammar

print_stmt: 'print ' arglist


2: /src/Python-3.5.2/Python/ast.cに以下の関数を追加


ast.c

static stmt_ty

ast_for_print_stmt(struct compiling *c, const node *n)
{
node *dummy;
node *dummy_child;
expr_ty print_func;
expr_ty e;

/*create a dummy node to access the print function*/
dummy = (node *)malloc(sizeof(node));
dummy_child = (node *)malloc(sizeof(node));
dummy->n_type = 324;
dummy->n_str = NULL;
dummy->n_lineno = n->n_lineno;
dummy->n_col_offset = n->n_col_offset;
dummy->n_nchildren = 1;

dummy_child->n_type = 1;
dummy_child->n_str = "print";
dummy_child->n_lineno = n->n_lineno;
dummy_child->n_col_offset = n->n_col_offset;
dummy_child->n_nchildren = 0;
dummy_child->n_child = NULL;

dummy->n_child = dummy_child;

/* calculate the stmt_type for the print function*/
print_func = ast_for_atom(c, dummy);

e = ast_for_call(c, CHILD(n, 1), print_func);
if (!e) {
fprintf(stderr,"ERROR_AT_PRINTX_STMT\n");
return NULL;
}
return Expr(e, LINENO(n), n->n_col_offset, c->c_arena);
}


また,同じファイル(ast.c内)の,ast_for_stmt内に,以下を追加(コメントの下の2行)


ast.c/ast_for_stmt

static stmt_ty

ast_for_stmt(struct compiling *c, const node *n)
if (TYPE(n) == small_stmt) {
n = CHILD(n, 0);
/* small_stmt: expr_stmt | del_stmt | pass_stmt | flow_stmt
| import_stmt | global_stmt | nonlocal_stmt | assert_stmt
| import_stmt | global_stmt | nonlocal_stmt | assert_stmt|print_stmt
*/

switch (TYPE(n)) {
case expr_stmt:
return ast_for_nonlocal_stmt(c, n);
case assert_stmt:
return ast_for_assert_stmt(c, n);
//ここから下の部分を追加
case print_stmt:
return ast_for_printx_stmt(c, n);


3: src/Python-3.5.2/Parser/tokenizer.c の,tok_get関数内に以下を記述


tokenizer.c/tok_get

/* async/await parsing block. */

if (tok->cur - tok->start == 5) {
/* Current token length is 5. */
//ここから追加
//すごく都合のいいことにprintもtoken名が5だぞ???
if(memcmp(tok->start, "print", 5) == 0) {
//printだった。
struct tok_state ahead_tok;
char *ahead_tok_start = NULL, *ahead_tok_end = NULL;
int ahead_tok_kind;
memcpy(&ahead_tok, tok, sizeof(ahead_tok));
ahead_tok_kind = tok_get(&ahead_tok, &ahead_tok_start,
&ahead_tok_end);

if (ahead_tok_kind == LPAR) {
//do-nothing
}else {
*p_end += 1;
return NAME;
}
}


とりあえずこれで動きます!!!(make-> make installしてね)

勿論これだけではなぜこのようにソースを変更したのかわからないので解説をします.


解説

まずはソースをいじった時に何を参考にしたか示し,その後Pythonのソースの解釈〜実行の流れを概説し,最終的になぜそのソースを弄るにいたったかを説明する.


ソースを手探る時のテクニック


1:公式ドキュメントを読む (Python Developer's Guide)

自分で何もわからない状態から適当にデバッガを起動して手探るのは,真っ暗な洞窟を明かりを付けずに探索するようなもの.ドキュメントを読まないと謎が謎を呼んで意味のない部分を編集してしまったり無駄を成す.またソースを読むだけではよく分からない概要を把握でき理解が深まる.

 今回の場合,特に23,24節がGrammarの変更とコンパイラの動作についての解説なので参考になる(というか自分はそこしか読んでいない).


2:その他の参考になるサイトを読む

とりあえずこれまでの「大規模ソフトウェアを手探る」でPythonを扱った記事を参考にした.

CPythonに後置インクリメントを加えてみた

Pythonを改造してみた


3:予備知識として文脈自由文法や,抽象構文木について知っておく.

知るとソースが何をやろうとしているのかが理解しやすくなり手探るのが大変に楽になった.

 計算理論の基礎 1.オートマトンと言語に文脈自由文法については詳しく書かれている.

 抽象構文木ははっきりとは理解していない.とりあえずwikipediaに書いている.

また,一番はじめの部分は再帰下降構文解析なのでwikipeidaを見ておくといいかもしれない(と書いている今思った).


Pythonのソースの解釈の流れ

ソースは下図のように加工されてゆく.

sourceflow.png

CFL,AST,CFGなどとよく分からない略語が続いていると思う.それらのうち,特にprint命令文を作る際に弄る必要があったCFLとASTについて説明する.


Conxtext Free Language(文脈自由言語)

文脈自由言語とは,前後の文脈に依存しないで文法が決定するような言語のことである.そのような言語はステートメントの遷移の組み合わせで生成の仕方を書くことが出来る.

例えば,足し算と掛け算をする言語を解釈する場合,と,,という3つの状態と,数字の代表としてaという文字を設定しておくと以下のような遷移条件が作れる.

ScreenShot 2016-11-29 7.39.03.png

この遷移条件を用いると,例えば"a + a × a"という文章は,以下のような木として解釈される.

ScreenShot 2016-11-29 7.44.50.png

Pythonのソースコードは,まず最初にこのCFLの構文木として解釈される.ソースコードにおける状態の定義と,状態遷移の定義はGrammar/Grammarに書いてある.だから一番はじめに弄るべきなのがGrammar/Grammarなのだ.


Abstract Syntax Tree(抽象構文木)

CFLの構文木にはプログラムの実行には関係ない状態遷移がたくさんついている.また,ソースコードの実行には"("(左括弧)などのいらない要素がついていることもある.そこでそれらのプログラムの実行に関係ない部分を取り除いた木が抽象構文木である.

 例えば,CFLの時にも考えた"a + a × a"を抽象構文木にすると,下図のようになる.

ScreenShot 2016-11-29 8.16.49.png

枝の部分に演算子等が付き,葉の部分にそれらの引数となる定数や変数が付くということが分かる.

PythonにおいてCFLからASTを作る作業を担うのがast.cにある関数群である.

どのようにCFLからASTを作るのかというと,CFLにおける状態を演算子の状態と引数に当たる部分の状態に分けて,引数に当たる部分を状態の列から引っ張って(足し算掛け算の例でやってみると,<EXPR>→<TERM>→<FACTOR>→aという状態の列からaを引っ張ってくる,という感じ)間の部分を無くすようにして作っている.


字句解析について

CFLを作るにあたって,入力文字列をどのように切り分けるかが問題になる.例えば「len = 100」のような文字列が入った時に,1文字づつではなく"len","=","100"のように複数文字を一つのトークン(構文解析をする最小要素のこと,それ以上切り分けられない意味の塊)として扱いたい.そのために,ソースからCFLを作る前にトークンを作成する前処理(字句解析)が必要になる.

Pythonで字句解析を担うのがtokenizer.cである.

これで弄った部分が担っていることの紹介が終わったので,ここからは各ソースの詳説をする.


Pythonの弄ったソースの詳説〜printx命令文の作成編

実際に弄ったソースを紹介する.まずはGrammar/Grammar,次にtokenizer.c,最後にast.cを説明する.


Grammar/Grammar

こいつがCFLの状態と,状態遷移を定義している.このソース自体は正規言語で,Parserによって解釈される.Grammar/GrammarによってPython/graminit.cが生成され,graminit.cにCFLの作製法が書かれている.

Grammar/Grammarを読んでみると,

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |

import_stmt | global_stmt | exec_stmt | assert_stmt )


と書いてあり,small_stmtが大体(if,for,whileなど以外)の命令文等の状態を認識していることが分かる.そこで,「print "HOGE"」などを認識する状態を作成し,small_stmtから遷移するようにすればうまくいくかもしれないとあたりを付けた.

 変更するとこうなる


Grammar/Grammar

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |

import_stmt | global_stmt | exec_stmt | assert_stmt | print_stmt)
print_stmt: 'print' arglist

arglistは,関数等の引数となるリストを表す状態である.これでprint命令文を認識できるようになったので,makeをして確認しようとすると...makeが通らなくなる.

何故かというと,print関数が認識できなくなったからである.

PythonはPython自身でも書かれているのだが,そのソースコードの中にprint()関数が使われている.'print'という状態があった時点でこれ以降は引数として認識されるので,既存のprint()関数は,'print'と,引数(タプル)として認識されてしまう.そのせいでprint()関数とは認識されず,かつprint_stmtをASTに解釈する部分は書いてないのでコンパイルできなくなったのだと思われる.(詳しく調べてはいない.そもそもmakeが通らないので調べるのが難しい)

そこで初めは'print'ではなくて,'printx'を認識するようにした.


Grammar/Grammar

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |

import_stmt | global_stmt | exec_stmt | assert_stmt | printx_stmt)
printx_stmt: 'printx' arglist

これだとprint()関数に悪影響を与えないのでmakeをすることが出来た.この状態では,printx "HOGE"のような文章を認識することができるが,認識して出来たCFLからどのようにASTを作るのかの記述がないのでASTの部分でエラーが発生する.そこで,ast.cを弄る必要がある.


ast.c

ast.cには,基本的に各CFLの状態につき一つの関数があり,それぞれが処理をしつつ子供にもっているCFLの状態に対応する関数を呼び出して終わるという作りになっている.ということは,printx_stmtに対応する関数を作成し,そこでprintの関数呼び出しと同じASTを作成するようにすればprint命令文が動くということになる.

Grammarでは,printx_stmtはsmall_stmtから遷移するようになっていた.そこで,small_stmtがどの関数で処理されるのかを調べると,at_for_stmtであることが分かる.


ast_for_stmt

static stmt_ty

ast_for_stmt(struct compiling *c, const node *n)
{
if (TYPE(n) == stmt) {
assert(NCH(n) == 1);
n = CHILD(n, 0);
}
if (TYPE(n) == simple_stmt) {
assert(num_stmts(n) == 1);
n = CHILD(n, 0);
}
if (TYPE(n) == small_stmt) {
n = CHILD(n, 0);
/* small_stmt: expr_stmt | del_stmt | pass_stmt | flow_stmt
| import_stmt | global_stmt | nonlocal_stmt | assert_stmt|print_stmt
*/

switch (TYPE(n)) {
case expr_stmt:
return ast_for_expr_stmt(c, n);
case del_stmt:
return ast_for_del_stmt(c, n);
case pass_stmt:
return Pass(LINENO(n), n->n_col_offset, c->c_arena);
case flow_stmt:
return ast_for_flow_stmt(c, n);
case import_stmt:
return ast_for_import_stmt(c, n);
case global_stmt:
return ast_for_global_stmt(c, n);
case nonlocal_stmt:
return ast_for_nonlocal_stmt(c, n);
case assert_stmt:
return ast_for_assert_stmt(c, n);

compilingというのが作成途中のASTで,nodeがCFLである.CHILD(n,0)は,nの0番目の子供を返すマクロである.よって,このswitch文で,printx_stmtに対応する関数を作れば良いことが分かる.


ast_for_stmt

    if (TYPE(n) == small_stmt) {

n = CHILD(n, 0);
/* small_stmt: expr_stmt | del_stmt | pass_stmt | flow_stmt
| import_stmt | global_stmt | nonlocal_stmt | assert_stmt|print_stmt
*/

switch (TYPE(n)) {
/*
...
*/

case print_stmt:
return ast_for_printx_stmt(c, n);

次に,ast_for_printx_stmt関数では,print()関数の時と同じASTを作るようにCFLを加工しなければいけない.そこで,自分でASTを作るのは難しいので,ダミーとなるCFLを勝手に作成し,それをprint()関数の時と同じようにast関数で処理したものを返すようにしようということになった.

ast_for_printx_stmt関数はこうなっている.


ast_for_printx_stmt

static stmt_ty

ast_for_print_stmt(struct compiling *c, const node *n)
{
node *dummy;
node *dummy_child;
expr_ty print_func;
expr_ty e;

/*create a dummy node to access the print function*/
dummy = (node *)malloc(sizeof(node));
dummy_child = (node *)malloc(sizeof(node));
dummy->n_type = 324;
dummy->n_str = NULL;
dummy->n_lineno = n->n_lineno;
dummy->n_col_offset = n->n_col_offset;
dummy->n_nchildren = 1;

dummy_child->n_type = 1;
dummy_child->n_str = "print";
dummy_child->n_lineno = n->n_lineno;
dummy_child->n_col_offset = n->n_col_offset;
dummy_child->n_nchildren = 0;
dummy_child->n_child = NULL;

dummy->n_child = dummy_child;

/* calculate the stmt_type for the print function*/
print_func = ast_for_atom(c, dummy);

e = ast_for_call(c, CHILD(n, 1), print_func);
if (!e) {
fprintf(stderr,"ERROR_AT_PRINTX_STMT\n");
return NULL;
}
return Expr(e, LINENO(n), n->n_col_offset, c->c_arena);
}


初めから見ていく.

     node *dummy;

node *dummy_child;
expr_ty print_func;
expr_ty e;

ここでダミーとなるnodeとexpr_tyを宣言している.expr_tyとは,ASTのうちPythonで式として評価される要素の構造体のポインタである.

/*create a dummy node to access the print function*/

dummy = (node *)malloc(sizeof(node));
dummy_child = (node *)malloc(sizeof(node));
dummy->n_type = 324;
dummy->n_str = NULL;
dummy->n_lineno = n->n_lineno;
dummy->n_col_offset = n->n_col_offset;
dummy->n_nchildren = 1;

まずはdummyに色々な情報をセットしている.n_typeは,nodeの状態を表す数字で,Grammar/Grammarによって自動生成されたInclude/graminit.hに定義が書かれている.324は「atom」を表すtypeである(この数字はGrammar/Grammarを変更したら変わる可能性がある).linenoやcol_offsetは,ソース上の位置の情報であるので,元々のノードであるnの値を使っている.nchildrenは,nodeの持つ子供の数である.dummy_childしかいないので1にしている.

    dummy_child->n_type = 1;

dummy_child->n_str = "print";
dummy_child->n_lineno = n->n_lineno;
dummy_child->n_col_offset = n->n_col_offset;
dummy_child->n_nchildren = 0;
dummy_child->n_child = NULL;

次にダミーの子供の定義をしている.typeが1となるのは「名前(NAME)」である.名前はいわゆる変数名や関数名などのことだと思っている.atomの子供がnameだと,atomはnameにあるn_strの名前を持ったオブジェクトであると解釈される.

 dummy->n_child = dummy_child;

/* calculate the stmt_type for the print function*/
print_func = ast_for_atom(c, dummy);

ast関数を呼び出して,atomのノードをASTに変換する.(中身がどのように動いているのかは知らない)

     e = ast_for_call(c, CHILD(n, 1), print_func);

ここは肝となる部分である.printという名前を持ったオブジェクトは関数であることは僕たちは知っている.だから,関数呼び出しを行うast_for_call関数を使ってASTを作っている.

関数呼び出しには,呼び出す関数と,引数が必要である.呼び出す関数は,先ほど作ったprint_func ASTである.引数の方はというと,元々printx_stmtの1番目の子供を突っ込んでいる.ここでGrammar/Grammarに追記したprintx_stmtを見てみよう.


Grammar/Grammar

printx_stmt: 'printx' arglist


ここから分かるように,printx_stmtノードは2つの子供を持ち,0番目が'printx'というNAMEノード,1番目がarglistノードになっている.arglistノードは,関数の引数として使うことができるので,ast_for_callの引数として使っている.


ast_for_printx_stmt

   return Expr(e, LINENO(n), n->n_col_offset, c->c_arena);


最後に後々の処理のために,作ったAST木eと,その他の情報を返している.c_arenaはメモリ管理についての情報,linenoやn_col_offsetはノードのソース上の位置に関する情報だと思う(詳しくは調べていない)

Exprマクロは,これら4つの情報を_stmt構造体に詰めるものである.これによって返り値を_stmt構造体のポインタ(stmt_ty)にしないと,ast_for_stmtの返り値と型が合わずコンパイルエラーになる.

これで printx "HOGE" などの命令文が使えるようになった.


でも"print"命令文ではないですよね?〜詳説'print '命令文編

そうなんです.それはprint()関数との共存を図る関係で'print'を予約語にできないのが原因なのですが...

'print'は無理,でもうまくprint命令文っぽく見せたい!ということで,妥協を図った.


'print '命令文

そう,'print'ではなく'print '(最後に空白が含まれている)を予約語にして,print()関数の時には'print',print命令文の時は'print 'としてprintが認識されるようにして両者を区別することにした.

 そこで問題になるのが," "(space)である.spaceは,ソースからトークンを切り出す時に,不必要な情報として切り落とされてしまうのである.print命令文の時だけ空白を一つ見逃してもらう必要がある.そのためにトークンの切り出しを行っているtokenizer.cを改変した.


tokenizer.c

tokenizer.cの中でも,get_tok関数が実際のトークンの判定を行っている関数である.まず宣言を見てみよう.


get_tok

static int

tok_get(struct tok_state *tok, char **p_start, char **p_end)

引数のtokには,ソースの情報や現在位置の情報などが全て入っている.そしてp_startとp_endが呼び出し元に今回認識されたトークンの,ソースにおける位置を教えるためのポインタである.そして返り値のintとは,ノードのTYPEを表す数字のことである.これはInclude/graminit.hなどで宣言されている.

tok_getが'if'や'for'などの予約語に対してつけるtypeは,全てNAMEである.つまりNAMEの場合は,その後'if'や'for'等の予約後かどうかのチェックが入るということである.よって'print 'トークンも,返り値はNAMEタイプとすればうまくやってくれるだろうと予想できる.

では,トークンを切り出した時に,そのトークンの文字列が'print'だったとしよう.この時その'print'がprint命令文のprintなのか,print()関数のプリントなのかは,次のトークンが'('なのかどうかで判定できる.そこで,'print'だった時は内部でtok_getを用いて次のトークンを見て,それが'('かによって動作を変えれば良いことが分かる.(ちなみに,似たような動作を'async','await'トークンに対して行っており,すごく参考になった)よってtok_get関数に以下のような追加をした.


tokenizer.c/tok_get

/* async/await parsing block. */

if (tok->cur - tok->start == 5) {
/* Current token length is 5. */
//ここから追加
//すごく都合のいいことにprintもtoken名が5だぞ???
if(memcmp(tok->start, "print", 5) == 0) {
//printだった。
struct tok_state ahead_tok;
char *ahead_tok_start = NULL, *ahead_tok_end = NULL;
int ahead_tok_kind;
memcpy(&ahead_tok, tok, sizeof(ahead_tok));
ahead_tok_kind = tok_get(&ahead_tok, &ahead_tok_start,
&ahead_tok_end);

if (ahead_tok_kind == LPAR) {
//do-nothing
}else {
*p_end += 1;
return NAME;
}
}


元々async,awaitトークンの判定をしている部分を,偶然printも文字数が前者と同じ5だったので使いまわしている.tok->curはソースにおける現在見ている文字列の位置を表している.よって if(tok->cur - tok->start == 5) は今のトークンの長さが5文字であるということになる.その語,if(memcmp(tok->start, "print", 5) == 0)でトークンと認識されている部分のソースが"print"かどうか見ている.ここから次のトークンを見る作業に移る.


tok_get

    struct tok_state ahead_tok;

char *ahead_tok_start = NULL, *ahead_tok_end = NULL;
int ahead_tok_kind;
memcpy(&ahead_tok, tok, sizeof(ahead_tok));
ahead_tok_kind = tok_get(&ahead_tok, &ahead_tok_start,
&ahead_tok_end);

ここで次のトークンを確認する用の変数を定義している.ahead_tokがtokの代わり,ahead_tok_startとahead_tok_endがそれぞれp_start,p_endの代わりである.

そしてahead_tokにtokの内容をコピーしてtok_getを呼び出すことで,次のトークンのtypeをahead_tok_kindに入れている.


tok_get

 if (ahead_tok_kind == LPAR) {

//do-nothing
}else {
*p_end += 1;
return NAME;
}

そして次のトークンのtypeがLPAR('('であることを示すタイプ)である時,printはprint()関数呼び出しのトークンであるので何もしないが,そうでない時は,print命令文だろうとして,p_endを1文字分後ろにずらしている.(つまり,printの後ろが空白であることを期待して,一つずらしている)そして'print 'トークンのtypeであるNAMEを返り値に返している.

こうすることで,print()関数の時は'print'トークン,そうでない時は'print 'トークンと識別することができ,print()関数には何も影響を与えずにprint命令文を書くことができる.

ただし,printの後ろが空白であることを期待して作っているので,print"HOGE"や,

print\

"HOGEEEEE"


は正しく認識されない.(python2.xでは認識される)

これらも認識できるように改変することは可能だと思うが,単にp_startとp_endに'print 'を埋め込むだけでは上手く動かなかったので改良していない.

これで,全ての改変部分の説明を終わったので,最後に感想を述べる


感想

正直Pythonをあんまり使ってなかったので,使っていればあぁこの機能だなと思うところでつまづいたりもしたが,普通にPythonを使っていれば気にしないような部分について深く知れたので,良い実験だった.

そしてコンパイラの常套手段(字句解析=>構文解析=>...)も知らなかったり,計算論の知識(正規言語,文脈自由言語,プッシュダウンオートマトン...)が丁度習いたてでそれらがどう利用ないし実装されているのかを知れて,逆に字句解析等の概念をPythonのtokenizerみたいなもの,のように身近に感じることができるようになった(もしもPythonの実装が特殊なものであったら悪い直感になるかもしれないけどそうでないと信じてる)

そして大規模ソフトウェアを手探る上での公式ドキュメントの重要性概念の重要性を知ることが出来た.本当にドキュメントを読まないで手探るのは,職人技を目で盗むようなもので,素人には無理があることが分かった.又CFL等の概念は,ソースコードやドキュメントを理解するための要となる部分だった.今回はいわば"現場で育つ"ような感じだったが,真面目に授業に出て勉強するとか教科書を読んで理解しておくと特に最初のとっかかりは楽だったろうなあと感じた.楽をするために勉強,しよう(おわり)