開拓馬の厩

いろいろやる

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人日。また毎回講義中盤に進捗報告会をやるので、実際はさらに短いです。

Pythonを改造してみた はじめに

Pythonは実行時にソースコードから機械語を生成するインタプリタ型言語の一種です。この記事ではPythonがコードを実行する際に、内部でどのような処理を行っているのかを調査した結果を紹介します。

しかし、ただソースコードやドキュメントを読むだけでは面白くありません。また、Pythonオープンソースで誰でも自由にソースコードをいじることができます。なので「Pythonを改造して新しい予約語を追加する」という方法でインタプリタの仕組を追ってみることにしました。

このページではソースコードをダウンロードしてビルドする所までの様子をお伝えします。 実際に改造を行った部分の説明は以下の記事からご覧いただけます。

これらの記事は大規模ソフトウェアを手探るという大学の講義のレポートを兼ねています。

また、ソースコードをいじる作業やブログ記事の作成はブログ主(id:pf_siedler)ともう一名の学生の二人組で行いました。

環境

ビルド

Pythonの公式サイトからソースコード(tarball形式)をダウンロードして適当なディレクトリに展開します。 ターミナルでソースコードを展開したディレクトリに移動しconfigureを叩きます。ここで、デバッグを行いやすいように、CFLAGS-g -O0オプションを与えます((-gデバッグシンボルを付けるオプション。これを付けないとデバッガを使うことができない。-O0は最適化を行わないオプション。デバッグ時にソースコードがそのままの状態で読める。))。また、--prefixオプションでインストール先のディレクトリをホーム直下のmypythonディレクトリに指定します。

その後、makemake installを行いインストールを行いました。makeには-jオプションで複数のプロセッサを割り当て高速化しました。

% tar zxvf Python3.5.2

% cd Python3.5.2

% CFLAGS="-g -O0" ./configure --prefix=/home/(username)/mypython/

% make -j8

% make install

ビルドは問題なく完了しました。~/mypython/bin/python3を実行することでPythonを起動できます。

% ~/mypython/bin/python3
Python 3.5.2 (<<>>)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

ドキュメントを読む

とりあえずビルドはできましたが、どこから手をつければいいかわかりません。そこでネットの記事を漁って情報を仕入れることにしました。 すると、昨年度の「大規模ソフトウェア」受講者にPythonを改造した方がいたので記事を読んでみると、Changing CPython’s Grammarなるガイドラインが紹介されていました。
この講義は「同じことをしようとしている誰かの役に立つため」に最終レポートをブログ形式で一般公開することを要求されているのですが、早速後輩の役に立つとは……

ガイドによると新しい予約語を追加する場合、おおよそ以下のような変更を加えればよいそうです。

  1. Grammar/Grammarをいじる(文法をの規定)
  2. Parser/Python.asdlをいじる(構文解析部分の自動生成に使うらしい?)
  3. Python/ast.cをいじる(AST生成)
  4. Python/symtable.c(をいじるASTに意味付けを行いコンパイラに渡す)
  5. Python/compile.cをいじる(コードに従ってバイトコードを生成)

後ろ3つはC言語のコードですが、GrammarPython.asdlは独特な記法で書かれていて大きな変更しづらそうです。また、C言語のファイル3つもマクロを使用して関数を呼び出しているので、既存のコードから大幅に外れた変更は難しそうです。

なので 既存の構文とほとんど同じ動きをする構文を追加する

慣れたら少し変わったことをする
という順序で開発を行っていくことにしました。

参考資料

Python公式ページ
Developer's Guideの23. Changing CPython’s Grammarに文法を変更する手順が記載されています。

大規模ソフトウェアを手探る
この記事を書くきっかけとなった大学の講義ページです。

CPythonに後置インクリメントを加えてみた
昨年度の大規模ソフトウェアを手探る受講者の方が書いたページです。Pythonのディベロッパーズガイドはこの記事を読んで知りました。

Python internals: adding a new statement to Python
「Pythonにuntil文を追加してみた」という内容の記事です。とても参考になりました。

dis/inspect モジュールを使った Python のハッキング
disassembleモジュール等を使ってPythonの言語仕様を解析する内容の記事です

Pythonを改造してみた unless文を追加してみた

プログラム言語Rubyにはunlessという構文があります。これはif文の反対で与えられた条件式が偽の場合に処理を行います。

unless cond then
    print 'OK'
end
#上記の場合、condがFalseならOKが表示されます

この記事ではPythonに上記のようなunless文を実装した結果を紹介します。

文法定義をいじる

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

Pythonの公式ドキュメントに文法変更のガイドラインがあるので、これに沿って改造を施していきます。 まず、ソースファイル内のGrammar/Grammarを書き換えてunless文の定義を追加します。 GrammarファイルはPythonの文法を規定したテキストファイルです。 Grammarは独自の記法で書かれていましたが、unless文の文法構造はif文とほとんど同じなので、if文を真似れば問題なさそうです。

# #if IF_INV

compound_stmt: if_stmt | unless_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt
async_stmt: ASYNC (funcdef | with_stmt | for_stmt)
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
# #if IF_INV
unless_stmt: 'unless' test ':' suite ('elunless' test ':' suite)* ['else' ':' suite]

if文には、else ifの省略形であるelifという構文が実装されています。unless文にもとりあえずこれに対応するelunlessという構文を追加しました。なお、unless文の元ネタであるRubyにはelsifに対応するelsunlessは存在しません。今回は細かいことは気にせずにif文の実装を完全コピーしました。(実際にelunlessを使うとコードが読みにくくなるので実用性はありませんが…)

Grammarファイルでは#以降の文字列は無視されるようなので、変更した部分を検索しやすいように#if IF_INVという文字列を置いておきました。 ちなみに、Grammar内にascii文字以外の文字を書くと、たとえコメントアウトされている部分でもエラーが発生するため、日本語のコメントは書けないようです。

次にPaser/Python.asdlを書き換えます。このファイルはMake時の文法解析プログラムの自走生成に使われます。

  | If(expr test, stmt* body, stmt* orelse)
  -- #if IF_INV
  | Unless(expr test, stmt* body, stmt* orelse)

以上の2つのファイルの変更後、自動生成ファイルを書き換えてもらうために一度makeを行いました。makeは失敗しましたが(unless文が存在するが動作が定義されていないみたいなエラーが出た)自動生成ファイルの書き換えが行われました。

//Python-ast.c

static PyTypeObject *If_type;
static char *If_fields[]={
    "test",
    "body",
    "orelse",
};
//unless文に対応する部分が追加された
static PyTypeObject *Unless_type;
static char *Unless_fields[]={
    "test",
    "body",
    "orelse",
};

構文木、記号表を作り変える

Pythonは与えられた構文からAST(抽象構文木)を作成します。構文木生成プログラムはPython/ast.cに記載されていますが、このファイルはmake時に自動で書き換えてくれないので手動で書き換えます。 ast.cunless文処理用の関数を追加します。

#if IF_INV
static stmt_ty
ast_for_unless_stmt(struct compiling *c, const node *n)
{
    /* unless_stmt: 'unless' test ':' suite ('elunless' test ':' suite)* ['else' ':' suite]
    */
    char *s;
//if文処理用の関数をコピーしifをunlessに書き換える
    REQ(n, unless_stmt);

    :
    :

    //elseとelifを区別する処理
    //elifの部分をelunlessに対応させる
    s = STR(CHILD(n, 4));
    /* s[2], the third character in the string, will be
       's' for el_s_e, or
       'u' for el_u_nless
    */
    if (s[2] == 's') {
        :
        :
    }
    else if (s[2] == 'u') {
        :
        :
    }

        :
        :

}
#endif

書き換えた部分には#if IF_INVというフラグを置いておき、コンパイルオプションでOn/Offを切り替えられるようにしておきました。 コンパイルオプションで-DIF_INV=1を指定すると変更部分が反映されます。

Python/symtable.cも書き換えます。symtable.cは記号表(抽象構文木に意味付けするときに使われる?)を作るプログラムです。これもif文の真似をしました。

    case If_kind:
        /* XXX if 0: and lookup_yield() hacks */
        VISIT(st, expr, s->v.If.test);
        VISIT_SEQ(st, stmt, s->v.If.body);
        if (s->v.If.orelse)
            VISIT_SEQ(st, stmt, s->v.If.orelse);
        break;
#if IF_INV
    case Unless_kind:
        VISIT(st, expr, s->v.Unless.test);
    VISIT_SEQ(st, stmt,s->v.Unless.body);
    if (s->v.Unless.orelse)
        VISIT_SEQ(st, stmt, s->v.Unless.body);
    break;
#endif

コンパイラを改造

ast.csymtable.cを書き換えたことでunless文が正しく分解されるようになりました。今度は分解された文に沿って正しいオペコードを生成するようにPython/comlipe.cを書き換えます。 これも真偽値を反転させること以外はif文の実装部分と同じなので真似して書きます。

#if IF_INV
static int
compiler_unless(struct compiler *c, stmt_ty s)
{
    :
    :
    constant = expr_constant(c, s->v.Unless.test);
    /* constant = 0: "if 0"
     * constant = 1: "if 1", "if 2", ...
     * constant = -1: rest */
    if (constant == 1) {//0と1を入れ替え
        if (s->v.Unless.orelse)
            VISIT_SEQ(c, stmt, s->v.Unless.orelse);
    } else if (constant == 0) {//0と1を入れ替え
        VISIT_SEQ(c, stmt, s->v.Unless.body);
    } else {
        if (asdl_seq_LEN(s->v.Unless.orelse)) {
            next = compiler_new_block(c);
            if (next == NULL)
                return 0;
        }
        else
            next = end;
        VISIT(c, expr, s->v.Unless.test);
        //生成するオペコードの真偽を入れ替え
        ADDOP_JABS(c, POP_JUMP_IF_TRUE, next);
        VISIT_SEQ(c, stmt, s->v.Unless.body);
        if (asdl_seq_LEN(s->v.Unless.orelse)) {
            ADDOP_JREL(c, JUMP_FORWARD, end);
            compiler_use_next_block(c, next);
            VISIT_SEQ(c, stmt, s->v.Unless.orelse);
        }
    }
    compiler_use_next_block(c, end);
    return 1;
}
#endif

実際に使ってみる

以上でunless文が実装できた。早速ビルドしてテストしてみます。

$ CFLAGS="-O0 -g -DIF_INV=1" ./configure --prefix='/home/pf-siedler/mypython/'
#コンパイルオプションに -DIF_INV=1 を追加

$ make -j8

$ make install

実際にunless文を実行してみましょう。

>>> unless False:
...     print("OK")
... 
OK
>>> unless True:
...     print("NO")
... elunless False:
...     print("YES")
... else:
...     print("NO'")
... 
YES
>>> unless True:
...     print("NO")
... else:
...     print("DONE!")
... 
DONE!
>>> 

ちゃんと条件式が偽のときに内部の命令が実行されました!

次にdisassembleモジュールでunless文のオペコードを見てみましょう。

>>> import dis
>>> def f(a):
...     unless a:
...         print("OK")
...
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (a)
              3 POP_JUMP_IF_TRUE        16

  3           6 LOAD_GLOBAL              0 (print)
              9 LOAD_CONST               1 ('OK')
             12 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             15 POP_TOP
        >>   16 LOAD_CONST               0 (None)
             19 RETURN_VALUE
>>>

3行目POP_JUMP_IF_TRUEは直前にロードした変数がTrueなら16行目に移動(つまりunless文から抜ける)、 Falseなら次の行(unless文の中身)を実行という処理で、正しくオペコードが生成されていることがわかります。

まとめ

CPythonはGrammarPython.asdlで文法を規定し、ast.csymtable.cに沿って構文木を作成、構文木に沿ってcompile.cがオペコードを生成していることがわかりました。

既存の構文に似た予約語の追加は、既存コードを少し改造するだけで実装できるので簡単に行なえます。

より複雑な構文を実装する場合、正しくオペコードを吐き出すようにcompile.cの改造に工夫を凝らす必要がありそうです。