読者です 読者をやめる 読者になる 読者になる

開拓馬’s blog

いろいろやる

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)

しかし、これらの記法は一見どのような演算をやっているのかわかりづらいです。また三項以上への拡張性も。よろしくありません。

andorのようにa exor bと記述すれば排他的論理をを計算してくれる演算子があれば、コードの可読性が向上しそうです。 そこで今回はPythonコンパイラを改造して、排他的論理和演算子exorを実装してみました。

文法の追加

ビルドまでの経緯はこちら

Grammar/GrammarPaser/Python.asdlから、andorが記述されている部分を探し出し、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)*

どうやらこの部分でandornotの優先順位を決めているようです。今回はexororより優先順位が低いという設定にしました。全体の優先順位は
not > and > or > exor
になります。

Python.asdlの変更は以下の一行だけ。ブール演算子の種類にexorを付け加えます。

    boolop = And | Or | Exor

astの書き換え

Python/ast.cand/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にはブール演算子特有の処理がひとつもなかったので書き換える場所はありませんでした。

コンパイラ

肝心のコンパイラ部分の書き換えです。exorand/orよりずっと複雑な処理が必要なのでexor使用時にコンパイラが生成するコードを自分で作る必要がありました。

and/orが動く仕組み

Pythoncompile.cで作成した擬似的な機械語Python/ceval.cが処理するという動きで動作しています。 プログラムの処理中に一時的に使用するデータは、一時的にFILO形式のスタック領域にロードされて処理されます。

例えばa + bの処理をする場合、

  1. aをスタックに格納
  2. bをスタックに格納
  3. スタックの先頭から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の場合、

  1. aをスタックに格納
  2. スタック先頭の真偽値を参照し真ならスタックの先頭を削除、偽なら4にジャンプ
  3. bをスタックに格納
  4. 次の処理

と処理されます。*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のどちらかなのですが、その真偽値は論理積の真偽値と一致しています(真偽値表などを書いて確認してみてください)。 なぜ、ブール型(TrueFalse)ではなくa、bの値をそのまま使うのかというと、「スタックの先頭を削除してTrue/Falseをスタックに格納」という処理を省略して処理を早めるためだと思われます。 思わぬところでバグが生じそうな気もしますが……

http://qiita.com/keisuke-nakata/items/e0598b2c13807f102469

この仕様は、a1 and a2 and a3 ...のように複数の演算子が複数並ぶ場合に、最初の方で偽の値を見つけたら、後半の多くを確認することなく結果が得られるのでかなりの時間短縮が見込めます。

排他的論理和は根本的に別物

先程「exorand/orよりずっと複雑」と述べました。それは exorは絶対に全部の式を判定しなければならない ので、andorのように 場合によっては後半の値を確認しない 演算と根本的に異なるということです。これまでのように他の部分を真似るのではなく、自分で実装を考える必要があります。

とりあえず、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_FALSEUNARY_NOTを組み合わせればexorを実現できそうです。 a exor b exor c exor ...の場合、

  1. aをスタックに格納
  2. bをスタックに格納
  3. スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
  4. スタック先頭の真偽値を反転
  5. cをスタックに格納
  6. スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
  7. スタック先頭の真偽値を反転
  8. 以下繰り返し

という順番に処理を行えば排他的論理和の計算ができます。ちょうど下図のように式を変形していくイメージです。 f:id:pf_siedler:20161105140248p:plain *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の使い方を教わったのに全く活用していないのは少し残念ですし、言語仕様以外も軽くいじってみたいという思いもありました。
そこで残り時間でPythonCUI部分をいじって--hogeみたいな新しいオプションとちょっとした機能の追加をやってみました。次回はその様子を説明します。

*1:ビット演算の排他的論理和とは別物です

*2:orなら、2行目の真偽が逆になります。これもa or bと同じ真偽値が得られます

*3:UNARY_NOTは本来not演算子を使ったときに使用される

*4:⊕は排他的論理和の記号

*5:講義は一回210分を10回、うち2回は開発以外のことをやるので、二人組で取り組んだ場合の開発時間は8回210分2人=7人日。また毎回講義中盤に進捗報告会をやるので、実際はさらに短いです。