2020-11-02

Pythonにrep文を追加してみた

はじめに

この記事はEEIC(東京大学工学部電気電子工学科/電子情報工学科)3年の後期実験「大規模ソフトウェアを手探る」のレポートとして書かれています。

環境

OS: Ubuntu 20.04 on WSL2
Python: Python3.7.9

動機

repマクロとは, 指定した回数の繰り返し処理を簡潔に書くためのマクロである. repマクロが用いられるのは, 競技プログラミングでC++を使用する場合などである. n回の繰り返し処理を行う場合, for文だと

for (int i = 0; i < n; i++) {
    処理
}

と記述するところを, repマクロだと

rep(i , n) {
    処理
}

と短く記述することができる. このように, 指定した回数の繰り返し処理を簡潔に記述するための機能がPythonにもあれば便利だと考え, Pythonにrepマクロと似た機能をもつrep文を追加しようと試みた.

仕様

当初の目標としたのは, n回の繰り返し処理を

REP i, n:
    処理

と記述する仕様である. だが, 実際にできたのは

REP i, range(n):
    処理

と記述する仕様であった.

ビルド

ビルドについてはを参照

コード変更

変更箇所

変更を加えたファイルは以下の5つである.

Grammar/Grammar
Parser/Python.asdl
Python/ast.c
Python/symtable.c
Python/compile.c

変更を加えるべきファイルを探すうえでは, https://www.python.org/dev/peps/pep-0306/ のChecklistが参考になるだろう.

Grammar/Grammar

ファイル名からして, 文法を規定するファイルだと思われる. https://docs.python.org/3.7/reference/grammar.html によると,

This is the full Python grammar, as it is read by the parser generator and used to parse Python source files

とのことである.

今回追加したいrep文は, for文を似た機能を有する. そこで, for_stmtの記述を参考に, Grammar/Grammarの70行目にrep_stmtを追加する.

# 変更前
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt

# 変更後
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt | rep_stmt

さらに, その下に, 以下の1行を追加する.

rep_stmt: 'REP' expr ',' testlist ':' suite ['else' ':' suite]

Parser/Python.asdl

Paser/Python.asdlは, https://www.python.org/dev/peps/pep-0306/によると,

Parser/Python.asdl may need changes to match the Grammar. Run make to regenerate Include/Python-ast.h and Python/Python-ast.c.

とのことである. 抽象構文木(AST)に関係するファイルの再生成に関係がありそうだ.

35行目のfor文に関する記述を参考に, 以下の1行を追加する.

| Rep(expr target, expr iter, stmt* body, stmt* orelse)

Python/ast.c

ファイル名からして, 抽象構文木(AST)の生成に関係がありそうだ. https://www.python.org/dev/peps/pep-0306/によると,

Python/ast.c will need changes to create the AST objects involved with the Grammar change.

とのことである.

ast_for_for_stmt()関数を参考に, ast_for_rep_stmt()関数を追加する.

static stmt_ty
ast_for_rep_stmt(struct compiling *c, const node *n0, bool is_async)
{
    const node * const n = is_async ? CHILD(n0, 1) : n0;
    asdl_seq *_target, *seq = NULL, *suite_seq;
    expr_ty expression;
    expr_ty target, first;
    const node *node_target;
    /* rep_stmt: 'REP' expr ',' test ':' suite ['else' ':' suite] */
    REQ(n, rep_stmt);

    if (NCH(n) == 9) {
        seq = ast_for_suite(c, CHILD(n, 8));
        if (!seq)
            return NULL;
    }

    node_target = CHILD(n, 1);
    _target = ast_for_exprlist(c, node_target, Store);
    if (!_target)
        return NULL;
    /* Check the # of children rather than the length of _target, since
       for x, in ... has 1 element in _target, but still requires a Tuple. */
    first = (expr_ty)asdl_seq_GET(_target, 0);
    if (NCH(node_target) == 1)
        target = first;
    else
        target = Tuple(_target, Store, first->lineno, first->col_offset, c->c_arena);

    expression = ast_for_testlist(c, CHILD(n, 3));
    if (!expression)
        return NULL;
    suite_seq = ast_for_suite(c, CHILD(n, 5));
    if (!suite_seq)
        return NULL;

    if (is_async)
        return AsyncFor(target, expression, suite_seq, seq,
                        LINENO(n0), n0->n_col_offset,
                        c->c_arena);
    else
        return For(target, expression, suite_seq, seq,
                   LINENO(n), n->n_col_offset,
                   c->c_arena);
}

ast_for_stmt()関数内のswitch文に, case for_stmtを参考にcase rep_stmtを追加する.

     case rep_stmt:
            return ast_for_rep_stmt(c, ch, 0);

Python/symtable.c

https://www.python.org/dev/peps/pep-0306/によると,

Python/symbtable.c: This handles the symbol collection pass that happens immediately before the compilation pass.

とのことである. コンパイルに関係がありそうだ.

symtable_visit_stmt()関数内のswitch文に, case For_kindの記述を参考に, case Rep_kindを追加する.

    case Rep_kind:
        VISIT(st, expr, s->v.Rep.target);
        VISIT(st, expr, s->v.Rep.iter);
        VISIT_SEQ(st, stmt, s->v.Rep.body);
        if (s->v.Rep.orelse)
            VISIT_SEQ(st, stmt, s->v.Rep.orelse);
        break;

Python/compile.c

ファイル名からして, コンパイルに関係がありそうだ. https://www.python.org/dev/peps/pep-0306/によると,

Python/compile.c: You will need to create or modify the compiler_* functions to generate opcodes for your productions.

とのことである.

find_ann()関数内のswitch文に, case For_kindを参考に, case Rep_kindを追加する.

case Rep_kind:
              res = find_ann(st->v.Rep.body) ||
                  find_ann(st->v.Rep.orelse);
              break;

compiler_for()関数を参考に, compiler_rep()関数を追加する.

static int
compiler_rep(struct compiler *c, stmt_ty s)
{
    basicblock *start, *cleanup, *end;

    start = compiler_new_block(c);
    cleanup = compiler_new_block(c);
    end = compiler_new_block(c);
    if (start == NULL || end == NULL || cleanup == NULL)
        return 0;
    ADDOP_JREL(c, SETUP_LOOP, end);
    if (!compiler_push_fblock(c, LOOP, start))
        return 0;
    VISIT(c, expr, s->v.Rep.iter);
    ADDOP(c, GET_ITER);
    compiler_use_next_block(c, start);
    ADDOP_JREL(c, FOR_ITER, cleanup);
    VISIT(c, expr, s->v.Rep.target);
    VISIT_SEQ(c, stmt, s->v.Rep.body);
    ADDOP_JABS(c, JUMP_ABSOLUTE, start);
    compiler_use_next_block(c, cleanup);
    ADDOP(c, POP_BLOCK);
    compiler_pop_fblock(c, LOOP, start);
    VISIT_SEQ(c, stmt, s->v.Rep.orelse);
    compiler_use_next_block(c, end);
    return 1;
}

compiler_visit_stmt()関数内のswitch文に, case For_kindを参考に, case Rep_kindを追加する.

    case Rep_kind:
        return compiler_rep(c, s);

再ビルド

Python-3.7.9ディレクトリに移動し, ビルドする. このとき, makeの代わりにmake regen-allを実行する. https://docs.python.org/ja/3.6/whatsnew/3.6.html#new-make-regen-all-build-targetによると, make regen-allはPython 3.6.2から追加されたコマンドであり, 必要なファイルを自動で生成してくれるらしい.

$ cd ~/Python-3.7.9
$ make clean
$ make regen-all
$ make install

動作検証

REP i, range(n):
    処理

と記述することで, n回の繰り返し処理が行われることを確認した.

$ ./python3.7
>>> REP i, range(5):
...    print('1')
...
1
1
1
1
1

課題

今回追加したrep文は,

REP i, range(n):
    処理

という記述で, n回の繰り返し処理が行われるものである. しかし, この記述では, Python 3の元々のfor文

for i in range(n):
    処理

と比較したときに, ほとんど短くなっていない. n回の繰り返し処理を簡潔に記述するという動機に立ち返ると, やはり

REP i, n:
    処理

と記述できるようにしたいところだ.

そのためのヒントになるのではないかと考え, 今回追加したrep文のバイトコードを調べることにした. バイトコードについては, https://yigarashi.hatenablog.com/entry/cpythonが参考になると思う.

rep文を使うrep.pyを作成し, -m disというオプションを付けて, python3.7を実行した. このオプションにより, バイトコードが表示されるらしい.

# rep.py
REP i, range(5):
    print(1)

$ ./python3.7 -m dis rep.py
  1           0 SETUP_LOOP              24 (to 26)
              2 LOAD_NAME                0 (range)
              4 LOAD_CONST               0 (5)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                12 (to 24)
             12 STORE_NAME               1 (i)

  2          14 LOAD_NAME                2 (print)
             16 LOAD_CONST               1 (1)
             18 CALL_FUNCTION            1
             20 POP_TOP
             22 JUMP_ABSOLUTE           10
        >>   24 POP_BLOCK
        >>   26 LOAD_CONST               2 (None)
             28 RETURN_VALUE

これと比較するため, 当初の目標としていた形のrep文を使うrep2.pyを作成し, 同様にバイトコードを調べてみる.

# rep2.py
REP i, 5:
    print(1)

$ ./python3.7 -m dis rep2.py
  1           0 SETUP_LOOP              20 (to 22)
              2 LOAD_CONST               0 (5)
              4 GET_ITER
        >>    6 FOR_ITER                12 (to 20)
              8 STORE_NAME               0 (i)

  2          10 LOAD_NAME                1 (print)
             12 LOAD_CONST               1 (1)
             14 CALL_FUNCTION            1
             16 POP_TOP
             18 JUMP_ABSOLUTE            6
        >>   20 POP_BLOCK
        >>   22 LOAD_CONST               2 (None)
             24 RETURN_VALUE

rep2.pyのバイトコードをみると, rep.pyのバイトコードの, 2行目の2 LOAD_NAME 0 (range), 4行目の6 CALL_FUNCTION 1が欠けていることがわかる. それならば, 不足した2行を追加できるように変更を加えれば, 当初の目標としていた

REP i, n:
    処理

という形のrep文を実装することができるのだろうか. バイトコードの生成に関係しているのは, Python/compile.cのcompiler_rep()関数である. この関数を変更すれば, バイトコードに変更を加えられそうだ. 追加したいバイトコードは,

2 LOAD_NAME 0 (range)
6 CALL_FUNCTION 1

の2行である. 後者については, compiler_rep()関数にADDOP(c, GET_ITER);の1行を加えれば, 追加できるかもしれない. だが, 前者を追加する方法がわからず, これ以上の変更は断念することとなった.

感想

変更するファイルが複数あり, 慣れないうちは大変だった. 聞くところによると, これでも以前よりは, Pythonの機能を変更するのが簡単になっているらしい. Pythonに新たな機能を追加するのはいい経験になった. 今回できたrep文は, 当初の目標とは違う形となってしまったが, いつの日か当初の目標通りのrep文を実装できたらと思う.

2020-11-02

Python 3で異なるデータ型を等価比較したときに警告を表示する機能を追加してみた

はじめに

この記事はEEIC(東京大学工学部電気電子工学科/電子情報工学科)3年の後期実験「大規模ソフトウェアを手探る」のレポートとして書かれています。

環境

OS: Ubuntu 20.04 on WSL2
Python: Python3.7.9
デバッガ: GDB

動機

Python 3では, 異なるデータ型の等価比較(==および!=)ができる. 異なるデータ型を等価比較すると, 等しくないと判定される.

>>> 1 == '1'
False
>>> 1 != [1]
True

しかし, 異なるデータ型の等価比較ができることは, バグの原因になりうるのではないだろうか. たとえば, 標準入力から受け取った整数が, 1と等しいか判定する場合を考える. この場合, 以下のコードを書けばよいだろう.

# ok.py
a == int(input())
if a == 1: print('Yes')
else: print('No')

実行例を以下に示す.

$ python3 ok.py
1
Yes
$ python3 ok.py
0
No

だが, (少なくとも私は)2行目のint()を書き忘れ, 以下のコードを書いてしまうことがある.

# ng.py
a = input()
if a == 1: print('Yes')
else: print('No')

実行例を以下に示す

$ python3 ng.py
1
No
$ python3 ng.py
0
No

上のように, ng.pyでは, 1を入力してもNoと出力される. str型の'1'と, int型の1という, 異なるデータ型を等価比較していることが原因である. だが, このときエラーや警告が発生しないため, 原因をすぐには突き止められない可能性がある. このように, 異なるデータ型を等価比較できることで, 予期せぬ挙動を示すことが起こりうる. そこで, Python 3で異なるデータ型を等価比較したときに, 警告を表示する機能を追加することにした.

ビルド

Python 3.7.9のアーカイブを入手し, 解凍する.

$ cd ~
$ wget https://www.python.org/ftp/python/3.7.9/Python-3.7.9
$ tar xvf Python-3.7.9.tgz

解凍してできたPython-3.7.9ディレクトリに移動する.

$ cd ~/Python-3.7.9

インストール先のディレクトリを指定し, コンパイルする. ここでは, インストール先を, /home/d01phn/python_installとする.

$ CFLAGS="-O0 -g" ./configure --prefix=/home/d01phn/python_install
$ make
$ make install

すると, 指定したディレクトリにインストールされる.

コード変更 1

前述のとおり, Python 3では, 異なるデータ型の等価比較(==および!=)ができる. しかし, 順序比較(<, >, <=, >=)については, エラーが生じる.

>>> 1 < '1'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'int' and 'str'
>>> 1 >= [1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '>=' not supported between instances of 'int' and 'list'

このときに表示されるエラー文を検索すれば, 異なるデータ型の比較を行う箇所を特定できると考えられる. そこで, Python-3.7.9ディレクトリ内で, grepコマンドを用いて, エラー文を検索する.

$ grep -I -r -n "not supported between instances of"
Lib/test/test_dataclasses.py:284:                                                    f"not supported between instances of '{cls.__name__}' and '{cls.__name__}'"):
Lib/test/test_dataclasses.py:313:                                                    f"not supported between instances of '{cls.__name__}' and '{cls.__name__}'"):
Lib/test/test_dataclasses.py:350:                                                    f"not supported between instances of '{cls.__name__}' and '{cls.__name__}'"):
Lib/test/test_dataclasses.py:402:                                            "not supported between instances of 'B' and 'C'"):
Objects/object.c:720:                     "'%s' not supported between instances of '%.100s' and '%.100s'",
Doc/howto/argparse.rst:550:   TypeError: '>=' not supported between instances of 'NoneType' and 'int'
Doc/library/pathlib.rst:203:   TypeError: '<' not supported between instances of 'PureWindowsPath' and 'PurePosixPath'
Doc/library/enum.rst:325:    TypeError: '<' not supported between instances of 'Color' and 'Color'

Objects/object.cの720行目が怪しそうなので, 見てみると, do_richcompare()関数の内部だとわかる.

/* Perform a rich comparison, raising TypeError when the requested comparison
   operator is not supported. */
static PyObject *
do_richcompare(PyObject *v, PyObject *w, int op)
{
    richcmpfunc f;
    PyObject *res;
    int checked_reverse_op = 0;

    if (v->ob_type != w->ob_type &&
        PyType_IsSubtype(w->ob_type, v->ob_type) &&
        (f = w->ob_type->tp_richcompare) != NULL) {
        checked_reverse_op = 1;
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if ((f = v->ob_type->tp_richcompare) != NULL) {
        res = (*f)(v, w, op);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if (!checked_reverse_op && (f = w->ob_type->tp_richcompare) != NULL) {
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    /* If neither object implements it, provide a sensible default
       for == and !=, but raise an exception for ordering. */
    switch (op) {
    case Py_EQ:
        res = (v == w) ? Py_True : Py_False;
        break;
    case Py_NE:
        res = (v != w) ? Py_True : Py_False;
        break;
    default:
        PyErr_Format(PyExc_TypeError,
                     "'%s' not supported between instances of '%.100s' and '%.100s'",
                     opstrings[op],
                     v->ob_type->tp_name,
                     w->ob_type->tp_name);
        return NULL;
    }
    Py_INCREF(res);
    return res;
}

switch文で比較演算子opに応じて場合分けがされている. Py_EQとPy_NEの場合はvとwが等価であるかが判定され, それ以外の場合はPyErr_Format()という, エラーに関係のありそうな関数が呼び出されているようである. よって, Py_EQとPy_NEの場合に, 警告を表示するコードを加えれば, 異なるデータ型を等価比較したときに, 警告を表示する機能を追加できそうである. また, エラー文と, PyErr_Format()とを見比べると, opstrings[op], v->ob_type->tp_name, w->ob_type->tp_nameが, それぞれ, 比較演算子を表す文字列, vのデータ型を表す文字列, wのデータ型を表す文字列に, 対応していると考えられる. 以上の内容を踏まえ, do_richcompare()関数に, 以下の変更を加えた.

static PyObject *
do_richcompare(PyObject *v, PyObject *w, int op)
{
...
    switch (op) {
    case Py_EQ:
        res = (v == w) ? Py_True : Py_False;
#if 1
        if (strcmp(v->ob_type->tp_name, w->ob_type->tp_name) != 0) {
        printf("Warning: '%.100s' and '%.100s' are different types but compared by '%s'\n",
           v->ob_type->tp_name,
           w->ob_type->tp_name,
           opstrings[op]);
    }
#endif     
        break;
    case Py_NE:
        res = (v != w) ? Py_True : Py_False;
#if 1
        if (strcmp(v->ob_type->tp_name, w->ob_type->tp_name) != 0) {
        printf("Warning: '%.100s' and '%.100s' are different types but compared by '%s'\n",
           v->ob_type->tp_name,
           w->ob_type->tp_name,
           opstrings[op]);
    }
#endif      
        break;
...
}

追加したコードは, #if 1と#endifで囲まれた2箇所であり, 2箇所とも全く同じ内容である. vとwのデータ型が異なる場合に, 警告文を表示する. 警告文には, vのデータ型, wのデータ型, 比較演算子の情報が含まれる.

動作検証 1

変更を加えたソースコードを再びビルドする.

$ cd ~/Python-3.7.9
$ make clean
$ make
$ make install

インストール先のディレクトリ内の, binディレクトリに移動する.

$ cd ~/python_install/bin

変更後のpython3.7を起動する.

$ ./python3.7

すると,

Warning: 'NoneType' and 'list' are different types but compared by '=='

という警告がたくさん表示されるが, いったん無視する. 異なるデータ型を比較したときに, 警告が表示されることを確認する.

>>> 1 == '1'
Warning: 'int' and 'str' are different types but compared by '=='
False
>>> 1 != [1]
Warning: 'int' and 'list' are different types but compared by '!='
True

コード変更 2

異なるデータ型を比較したときに, 警告を表示する機能は追加できた. しかし, 新たに生じた問題として, python3.7の起動時に,

Warning: 'NoneType' and 'list' are different types but compared by '=='

という警告がたくさん表示されてしまう. どうやら, Python 3では, 起動時にNoneType型とlist型の比較が行われるようである. 起動時に警告がたくさん表示されるのは鬱陶しいので, NoneType型を等価比較した場合は, 警告を表示しないようにしたい. そこで, do_richcompare()関数に, さらなる変更を加えた.

static PyObject *
do_richcompare(PyObject *v, PyObject *w, int op)
{
...
    switch (op) {
    case Py_EQ:
        res = (v == w) ? Py_True : Py_False;
#if 1
        if (strcmp(v->ob_type->tp_name, w->ob_type->tp_name) != 0 &&
        strcmp(v->ob_type->tp_name, "NoneType") != 0 &&  // added
        strcmp(w->ob_type->tp_name, "NoneType") != 0 ) { // added
        printf("Warning: '%.100s' and '%.100s' are different types but compared by '%s'\n",
           v->ob_type->tp_name,
           w->ob_type->tp_name,
           opstrings[op]);
    }
#endif     
        break;
    case Py_NE:
        res = (v != w) ? Py_True : Py_False;
#if 1
        if (strcmp(v->ob_type->tp_name, w->ob_type->tp_name) != 0 &&
        strcmp(v->ob_type->tp_name, "NoneType") != 0 &&  // added
        strcmp(w->ob_type->tp_name, "NoneType") != 0 ) { // added
        printf("Warning: '%.100s' and '%.100s' are different types but compared by '%s'\n",
           v->ob_type->tp_name,
           w->ob_type->tp_name,
           opstrings[op]);
    }
#endif      
        break;
...
}

if文の条件式に, 新たに2行ずつ加えた.

動作検証 2

動作検証1と同様に, ビルドし, python3.7を起動する.

$ cd ~/Python-3.7.9
$ make clean
$ make
$ make install
$ cd ~/python_install/bin
$ ./python3.7

すると, python3.7の起動時に, 警告が表示されないことが確認できる.

感想

「Pythonならよく使ってるし, 新しい機能を追加するのも余裕でしょ?」などという軽い気持ちで挑戦したが, 決して余裕ではなかった.
苦戦しながらも, こうして新たな機能を追加できたことはよかった(実用的かはさておき). Pythonを実行してGDBでデバッグすると, いろいろな関数を行き来することになるので, 「この関数で何が行われるのか」「この関数は飛ばしても大丈夫か」を推測する能力が求められると感じた.