Pythonを改造してみた 排他的論理のブール演算子作った
Pythonでは、ブール演算で排他的論理を表現する場合、以下のような書き方があります。*1
#and or not演算子を組み合わせて記述 a and not b or not a and b #bool()関数の返り値が不一致であるか判定する bool(a) != bool(b) #operatorモジュール使用 from operator import xor xor(a, b)
しかし、これらの記法は一見どのような演算をやっているのかわかりづらいです。また三項以上への拡張性も。よろしくありません。
and
やor
のようにa exor b
と記述すれば排他的論理をを計算してくれる演算子があれば、コードの可読性が向上しそうです。
そこで今回はPythonのコンパイラを改造して、排他的論理和の演算子exor
を実装してみました。
文法の追加
ビルドまでの経緯はこちら
Grammar/Grammar
とPaser/Python.asdl
から、and
やor
が記述されている部分を探し出し、exor
の処理を新たに追加します。
# #if EXOR_TEST test: exor_test ['if' exor_test 'else' test] | lambdef test_nocond: exor_test | lambdef_nocond lambdef: 'lambda' [varargslist] ':' test lambdef_nocond: 'lambda' [varargslist] ':' test_nocond # #if EXOR_TEST exor_test: or_test ('exor' or_test)* or_test: and_test ('or' and_test)* and_test: not_test ('and' not_test)* not_test: 'not' not_test | comparison comparison: expr (comp_op expr)*
どうやらこの部分でand
、or
、not
の優先順位を決めているようです。今回はexor
はor
より優先順位が低いという設定にしました。全体の優先順位は
先 not
> and
> or
> exor
後
になります。
Python.asdl
の変更は以下の一行だけ。ブール演算子の種類にexor
を付け加えます。
boolop = And | Or | Exor
astの書き換え
Python/ast.c
はand
/or
の真似をするだけです。
#if EXOR_TEST//変更後のコード case exor_test: case or_test: case and_test: : : if (!strcmp(STR(CHILD(n, 1)), "and")) return BoolOp(And, seq, LINENO(n), n->n_col_offset, c->c_arena); if (!strcmp(STR(CHILD(n, 1)), "exor")) return BoolOp(Exor, seq, LINENO(n), n->n_col_offset, c->c_arena); assert(!strcmp(STR(CHILD(n, 1)), "or")); return BoolOp(Or, seq, LINENO(n), n->n_col_offset, c->c_arena); #else//もとのコード case or_test: case and_test: : : if (!strcmp(STR(CHILD(n, 1)), "and")) return BoolOp(And, seq, LINENO(n), n->n_col_offset, c->c_arena); assert(!strcmp(STR(CHILD(n, 1)), "or")); return BoolOp(Or, seq, LINENO(n), n->n_col_offset, c->c_arena); #endif
Python/symtable.c
にはブール演算子特有の処理がひとつもなかったので書き換える場所はありませんでした。
コンパイラ
肝心のコンパイラ部分の書き換えです。exor
はand
/or
よりずっと複雑な処理が必要なのでexor
使用時にコンパイラが生成するコードを自分で作る必要がありました。
and
/or
が動く仕組み
Pythonはcompile.c
で作成した擬似的な機械語をPython/ceval.c
が処理するという動きで動作しています。
プログラムの処理中に一時的に使用するデータは、一時的にFILO形式のスタック領域にロードされて処理されます。
例えばa + b
の処理をする場合、
- aをスタックに格納
- bをスタックに格納
- スタックの先頭から2つのデータを削除し、和をスタックに格納
という順序で処理されます。 Pythonが内部で生成している擬似的なオペコードはdisモジュールを用いることで見ることができます。
>>> import dis >>> def f(a, b): ... a + b ... >>> dis.dis(f) 2 0 LOAD_FAST 0 (a)#aをスタックに格納 3 LOAD_FAST 1 (b)#bをスタックに格納 6 BINARY_ADD #ススタックの先頭から2つのデータを削除し、和をスタックに格納 7 POP_TOP 8 LOAD_CONST 0 (None) 11 RETURN_VALUE >>>
and
/or
の場合はどのようになっているかというと、例としてa and b
の場合、
- aをスタックに格納
- スタック先頭の真偽値を参照し真ならスタックの先頭を削除、偽なら4にジャンプ
- bをスタックに格納
- 次の処理
と処理されます。*2
>>> import dis >>> def f(a, b): ... a and b ... >>> dis.dis(f) 2 0 LOAD_FAST 0 (a)#aをスタックに格納 3 JUMP_IF_FALSE_OR_POP 9 #スタック先頭の真偽値を参照し、真ならスタックの先頭を削除、偽ならジャンプ 6 LOAD_FAST 1 (b)#bをスタックに格納 >> 9 POP_TOP #次の処理(今回は関数を終える処理) 10 LOAD_CONST 0 (None) 13 RETURN_VALUE >>>
この時、「4.次の処理」の行でスタックの先頭はaかbのどちらかなのですが、その真偽値は論理積の真偽値と一致しています(真偽値表などを書いて確認してみてください)。
なぜ、ブール型(True
やFalse
)ではなくa、bの値をそのまま使うのかというと、「スタックの先頭を削除してTrue
/False
をスタックに格納」という処理を省略して処理を早めるためだと思われます。 思わぬところでバグが生じそうな気もしますが……
http://qiita.com/keisuke-nakata/items/e0598b2c13807f102469
この仕様は、a1 and a2 and a3 ...
のように複数の演算子が複数並ぶ場合に、最初の方で偽の値を見つけたら、後半の多くを確認することなく結果が得られるのでかなりの時間短縮が見込めます。
排他的論理和は根本的に別物
先程「exor
はand
/or
よりずっと複雑」と述べました。それは exor
は絶対に全部の式を判定しなければならない ので、and
やor
のように 場合によっては後半の値を確認しない 演算と根本的に異なるということです。これまでのように他の部分を真似るのではなく、自分で実装を考える必要があります。
とりあえず、exor
は専用の関数を用意して処理することにしました。
//compile.c static int compiler_visit_expr(struct compiler *c, expr_ty e) { : : switch (e->kind) { case BoolOp_kind:// #if EXOR_TEST if(e->v.BoolOp.op == Exor) return compiler_exor(c, e);//exorだけ別の処理を行う #endif return compiler_boolop(c, e);//and/orはどちらもこの関数で処理される : :
内部の処理はどうしましょうか。例えば、a exor b
の場合、とりあえず「aをスタックに格納」→「bをスタックに格納」という処理は必要そうです。
Pythonの既存のオペコードには、POP_JUMP_IF_FALSE
というものが存在します。これは「スタック先頭の真偽値を参照し、真ならジャンプ。真偽にかかわらずスタック先頭のデータは消す」という処理を行います。
またUNARY_NOT
というオペコードもあります。これは「スタック先頭の真偽値を反転」という処理です。*3
また、UNARY_NOT
で反転された値はブール型に変換されます。
>>> not 0.000 #もとが数値や True >>> not "A" #文字列でも結果はブール型になる False >>>
POP_JUMP_IF_FALSE
とUNARY_NOT
を組み合わせればexor
を実現できそうです。
a exor b exor c exor ...
の場合、
- aをスタックに格納
- bをスタックに格納
- スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
- スタック先頭の真偽値を反転
- cをスタックに格納
- スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
- スタック先頭の真偽値を反転
- 以下繰り返し
という順番に処理を行えば排他的論理和の計算ができます。ちょうど下図のように式を変形していくイメージです。 *4
試行錯誤の結果以下のようなコードを作成しました。
#if EXOR_TEST static int compiler_exor(struct compiler *c, expr_ty e) { basicblock **buf, *end; Py_ssize_t i, n; asdl_seq *s; assert(e->kind == BoolOp_kind); assert(e->v.BoolOp.op == Exor); end = compiler_new_block(c); s = e->v.BoolOp.values; n = asdl_seq_LEN(s) - 1; buf = (basicblock**)malloc(sizeof(basicblock*)*n); VISIT(c, expr, (expr_ty)asdl_seq_GET(s, 0));//「aをスタックに格納」に相当する処理 assert(n >= 0); for (i = 1; i < n; ++i) { buf[i-1] = compiler_new_block(c); VISIT(c, expr, (expr_ty)asdl_seq_GET(s, i));//「bをスタックに格納」 ADDOP_JABS(c, POP_JUMP_IF_FALSE, buf[i-1]); ADDOP(c, UNARY_NOT); compiler_use_next_block(c, buf[i-1]); } VISIT(c, expr, (expr_ty)asdl_seq_GET(s, n)); buf[n-1] = compiler_new_block(c); ADDOP_JABS(c, POP_JUMP_IF_TRUE, buf[n-1]); ADDOP(c, UNARY_NOT); compiler_use_next_block(c, buf[n-1]); ADDOP(c, UNARY_NOT); compiler_use_next_block(c, end); return 1; } #endif
この実装だと、最初以外全部偽だった場合だけ最初の項の値がそのまま出力されてしまうので、 最後に一度は否定を挟むようにして、結果をブール型で統一してあります。速さは犠牲になりますが、わかりやすさを重視しました。
使ってみた
ビルドして実際にexor
演算子を使ってみました。
>>> 1 exor 1 False >>> 0 exor 1 True >>> True exor 0 True >>> False exor False False
どうやらちゃんと動いているようです。
disassembleモジュールで分析した結果が以下になります。
>>> import dis >>> def f(a, b, c): ... a exor b exor c ... >>> dis.dis(f) 2 0 LOAD_FAST 0 (a) 3 LOAD_FAST 1 (b) 6 POP_JUMP_IF_FALSE 10 9 UNARY_NOT >> 10 LOAD_FAST 2 (c) 13 POP_JUMP_IF_TRUE 17 16 UNARY_NOT >> 17 UNARY_NOT 18 POP_TOP 19 LOAD_CONST 0 (None) 22 RETURN_VALUE
次は何やろう
本シリーズは講義のレポートも兼ねて執筆しています。その講義ですが、ちょうどexor
の実装ができたところで終盤になり、残り時間も少なくなってきました。*5
講義中にgdbの使い方を教わったのに全く活用していないのは少し残念ですし、言語仕様以外も軽くいじってみたいという思いもありました。
そこで残り時間でPythonはCUI部分をいじって--hoge
みたいな新しいオプションとちょっとした機能の追加をやってみました。次回はその様子を説明します。