Naomi's notebook

Naomi's notebook

pythonに２種類のswitch文を追加する

概要

本記事は東京大学工学部電子情報工学科の「大規模ソフトウェアを手探る」という実験の報告記事です。（2020年度前半組）

私達の班はpython3.10に新しい三項演算子・switch文・前置インクリメントを追加してみました。この記事ではswitch文について説明します。

概要 qiita.com

三項演算子 qiita.com

前置インクリメントkkti4216.hatenablog.com

環境

詳しいビルド方法などは概要の記事に書かれると思いますが、cpython3.10(https://github.com/python/cpython/tree/master)をcloneして、所定の方法(https://devguide.python.org/setup/)でビルドしました。

手探る準備

いじるのに使ったツール

gdb (+ emacs)

emacs: M-x gud-gdb

grep

grep hogehoge -r -I .

-m dis(バイトコードの表示)

python3 -m dis filename

-d(パーサーのデバッグ出力を有効にする)

python3 -d

参考にしたサイト

公式ドキュメント

24. Changing CPython’s Grammar — Python Developer's Guide

ほぼほぼこのドキュメントに従って改造することが出来ました。

dis --- Python バイトコードの逆アセンブラ — Python 3.9.0 ドキュメント

こちらも参考にしました。

pythonを改造した先人たち

山のようにあります。

CPythonに後置インクリメントを加えてみた 概要とまとめ - Qiita

Pythonを改造してみた はじめに - 開拓馬の厩

Pythonにプライベート変数を実装しようと試みた話。 - Qiita

Modifying the Python language in 6 minutes | Hacker Noon

Python処理系入門 〜1 + 1 で学ぶ処理系解読の基礎〜 - yigarashi のブログ

Pythonを改造してみた unless文を追加してみた - 開拓馬の厩

Pythonを改造してみた 排他的論理のブール演算子作った - 開拓馬の厩

その他

Python/バイトコード生成を読む - Code Reading Wiki

手探る

python.gram:構文を定義する

Grammer/python.gram:L157にある、if...elif...elseの構文の定義（以下）を真似して追加します。

if_stmt[stmt_ty]:
    | 'if' a=named_expression ':' b=block c=elif_stmt { _Py_If(a, b, CHECK((asdl_stmt_seq*)_PyPegen_singleton_seq(p, c)), EXTRA) }
    | 'if' a=named_expression ':' b=block c=[else_block] { _Py_If(a, b, c, EXTRA) }
elif_stmt[stmt_ty]:
    | 'elif' a=named_expression ':' b=block c=elif_stmt { _Py_If(a, b, CHECK(_PyPegen_singleton_seq(p, c)), EXTRA) }
    | 'elif' a=named_expression ':' b=block c=[else_block] { _Py_If(a, b, c, EXTRA) }
else_block[asdl_stmt_seq*]: 'else' ':' b=block { b }

具体的には、 Grammer/python.gram:L82

#ifdef DOSS_SWITCH
    | &'switcha' switcha_stmt
#endif

L168

#ifdef DOSS_SWITCH
switcha_stmt[stmt_ty]:
    | 'switcha' a=なにか１ ':' NEWLINE INDENT b=case_block DEDENT {_Py_Switcha(a,CHECK((asdl_stmt_seq*)_PyPegen_singleton_seq(p, b)),EXTRA)}
case_block[stmt_ty]:
    | 'case' a=なにか２ ':'  b=block c=case_block {_Py_Case(a,b, CHECK(_PyPegen_singleton_seq(p, c)),EXTRA)}
    | 'case' a=なにか２ ':'  b=block c=[default_block] {_Py_Case(a,b,c,EXTRA)}
default_block[asdl_stmt_seq*]: 'defaulta' ':' b=block {b}
#endif

のように追加すれば良いと推定できます。ここで、「なにか1」と「なにか2」は、何か値を返すものであるということなどいろいろなことを考慮して、それぞれdisjunctionとatomを指定しました。C言語やJAVAのswitch文のような、評価した結果が整数値でないといけないとか、case文の右は定数のみとするなどの制約はありません。（ここはもっと考えればより適切なものがあるかもしれません。）

なお、switch,defaultではなくswitcha,defaultaとしたのは、テストで用いられるpythonで書かれたコードの中にswitchやdefaultという名前の関数や変数が存在するようで、make installをしたときにエラーになってしまうためです。

変更が出来たら、make regen-pegenを行い、文をパースして抽象構文木を構築するプログラム(Parser/parser.c)を自動生成します。

python.asdl:関数を定義する

さきほどのpython.gramで新しい関数Py_SwitchaとPy_Caseを使ったので、それを定義します。 Parser/Python. L38

--#ifdef DOSS_SWITCH
          | Switcha(expr test,stmt* cases)
      | Case(expr test, stmt* body,stmt* orelse)
--#endif

変更できたらmake regen-astを行いInclude/Python-ast.hとPython/Python-ast.cを自動生成します。

compile.c:関数の中身を作る（バイトコードに変換する）

この時点で、（後述のようにast.cを変更する必要はあるが）switch文を実行しても構文エラーが出ないようになっているはずです。ただし何も帰ってきません。

まず、どのようなバイトコードで実現できそうかを考えます。 -m disというコマンドをつけて実行すると、pythonの仮想マシン上で実行されているバイトコードを逆アセンブルして表示してくれるようなので、if...elif...else文やfor文でどのような動作をしているのか調べてみましょう。 f:id:Naomi_Lilienthal:20201020183152p:plain これを見ると、switch文の動作もLOAD_NAME→LOAD_CONST→COMARE_OP→POP_JUMP_IF_FALSE…といったように実現できそうなことが解ります。

また、switch文の右の式を評価した結果は何度も（case文が出てくるたびに）使わなければなりませんが、これはdis --- Python バイトコードの逆アセンブラ — Python 3.9.0 ドキュメントのバイトコード命令の一覧を眺めると、DUP_TOPなどで実現できそうです。

以上のことをまとめると、だいたい以下のような実装をしたいということが想像できます。

LOAD_NAME
　DUP_TOP
　LOAD_CONST(仕様上LOAD_NAMEなどのこともある)
　COMPARE_OP
　POP_JUMP_IF_FALSE
　(処理)
　JUMP_ABSOLUTE
　DUP_TOP
　LOAD_CONST
　COMPARE_OP
　POP_JUMP_IF_FALSE
　(処理)
　JUMP_ABSOLUTE
   ...(繰り返し)
POP_TOP

自然な実装になるように、switch文の仕様は以下のようにしてあります。

  • switch文に入ったときに式を一回評価する
  • その値とcase文の式の値を==で比較し、Trueとなった一番上のcase文の中身を実行し、switch文を抜ける
  • どのcase文も実行されなかった場合defaultを実行する

あとはcompile.cの中でそれぞれのバイトコードを使っているところを検索し、それを真似して書くということを繰り返します。 以下に具体的な実装を載せておきます。

Python/compile.c L2746

#ifdef DOSS_SWITCH
static int
compiler_case(struct compiler *c, stmt_ty s)
{
  basicblock *end, *next;
  next = compiler_new_block(c);
  end = compiler_new_block(c);
  if (next == NULL || end == NULL)return 0;
  assert(s->kind == Case_kind);

  ADDOP(c, DUP_TOP);
  VISIT(c,expr,s->v.Case.test);
  cmpop_ty op=Eq;
  ADDOP_COMPARE(c,op);
  ADDOP_JUMP(c, POP_JUMP_IF_FALSE, next);
  VISIT_SEQ(c, stmt, s->v.Case.body);
  ADDOP_JUMP(c, JUMP_ABSOLUTE, end);
  compiler_use_next_block(c, next);
  if(s->v.Case.orelse){ 
    VISIT_SEQ(c,stmt,s->v.Case.orelse);
  }
  compiler_use_next_block(c, end);
  return 1;
}
static int
compiler_switch(struct compiler *c, stmt_ty s)
{
   basicblock *end, *next;
   next = compiler_new_block(c);
   end = compiler_new_block(c);
   if (next == NULL || end == NULL) {
        return 0;
    }
   assert(s->kind == Switcha_kind);
   VISIT(c,expr,s->v.Switcha.test);
   compiler_use_next_block(c, next);
   VISIT_SEQ(c,stmt,s->v.Switcha.cases);
   ADDOP(c, POP_TOP);
   compiler_use_next_block(c, end);
   return 1;
}

#endif

L3457

#ifdef DOSS_SWITCH
    case Switcha_kind:
        return compiler_switch(c, s);
    case Case_kind:
        return compiler_case(c, s);
 #endif

実際には以下のように動きます f:id:Naomi_Lilienthal:20201020195401p:plain

ceval.c:バイトコードの動作を定義する

既存のバイトコードの羅列により実装が出来てしまったので、今回この部分は触らなくてもよかったです。（前置インクリメントを作る際はこの部分も変更する必要がありました。）

その他

シンボルテーブルの作成

python.asdlを変更したあとにmake regen-allをすると、以下のようなwarningが出ます。

Python/symtable.c: In function 'symtable_visit_stmt':
Python/symtable.c:1178:5: warning: enumeration value 'Switch_kind' not handled in switch [-Wswitch]
     switch (s->kind) {
     ^~~~~~
Python/symtable.c:1178:5: warning: enumeration value 'Case_kind' not handled in switch [-Wswitch]

これはsymtable.cという「シンボルテーブル」なるものを作っているプログラムの中に、switch文とcase文に対応する動作が記されていないことに起因します。シンボルテーブルは、バイトコードを生成する前に抽象構文木から生成され、識別子のスコープを計算するのに使う表らしいです。 よくわからない点もありますが、とりあえず他の場所を真似して、以下のようにswitch文、case文から訪れるすべての行き先を記しておきます。 Python/symtable.c L1294

#ifdef DOSS_SWITCH
    case Switcha_kind:
        VISIT(st, expr, s->v.Switcha.test);
        VISIT_SEQ(st, stmt, s->v.Switcha.cases);
        break;
    case Case_kind:
      VISIT(st,expr,s->v.Case.test)
      VISIT_SEQ(st, stmt, s->v.Case.body);
        if (s->v.Case.orelse)
            VISIT_SEQ(st, stmt, s->v.Case.orelse);
    break;
#endif

抽象構文木の検証

python.asdlまで変更した時点でmake&make-installし、switch文を実行すると、以下のようなエラーが出ます。

python3: Parser/pegen.c:1146: _PyPegen_run_parser: Assertion `PyAST_Validate(res)' failed.

これをgdbで追っていくと、Python/ast.c:L539

case Interactive_kind:
        res = validate_stmts(mod->v.Interactive.body);

でvalidate_stmtsの返り値が0になっていることが問題なようです。さらにこれをgdbで追うと、validate_stmtのなかでSwitcha_kindとCase_kindがないことが問題だとわかります。よって以下のように変更すればとりあえず動きます。

Python/ast.c L404(要検証)

#ifdef DOSS_SWITCH
    case Switcha_kind:
      return 1;
    case Case_kind:
      return 1;
#endif

Python/ast.cが何をしているかというと、構文木が正しいかどうかを検証しているらしい。よってここは本来は以下のように記すことで構文木の検証をするのが正しいです。

Python/ast.c L404

#ifdef DOSS_SWITCH
    case Switcha_kind:
      return validate_expr(stmt->v.Switcha.test, Load) &&
      validate_stmts(stmt->v.Switcha.cases);
    case Case_kind:
      return validate_expr(stmt->v.Case.test, Load) &&
      validate_stmts(stmt->v.Case.body) &&
      validate_stmts(stmt->v.Case.orelse);
#endif

全変更点一覧(eqによる比較のみ)

switch

Grammer/python.gram L82

#ifdef DOSS_SWITCH
    | &'switcha' switcha_stmt
#endif

L168

#ifdef DOSS_SWITCH
switcha_stmt[stmt_ty]:
    | 'switcha' a=disjunction ':' NEWLINE INDENT b=case_block DEDENT {_Py_Switcha(a,CHECK((asdl_stmt_seq*)_PyPegen_singleton_seq(p, b)),EXTRA)}
case_block[stmt_ty]:
    | 'case' a=atom ':'  b=block c=case_block {_Py_Case(a,b, CHECK(_PyPegen_singleton_seq(p, c)),EXTRA)}
    | 'case' a=atom ':'  b=block c=[default_block] {_Py_Case(a,b,c,EXTRA)}
default_block[asdl_stmt_seq*]: 'defaulta' ':' b=block {b}
#endif

Parser/Python. L38

--#ifdef DOSS_SWITCH
          | Switcha(expr test,stmt* cases)
      | Case(expr test, stmt* body,stmt* orelse)
--#endif

Python/ast.c L404

#ifdef DOSS_SWITCH
    case Switcha_kind:
      return validate_expr(stmt->v.Switcha.test, Load) &&
      validate_stmts(stmt->v.Switcha.cases);
    case Case_kind:
      return validate_expr(stmt->v.Case.test, Load) &&
      validate_stmts(stmt->v.Case.body) &&
      validate_stmts(stmt->v.Case.orelse);
#endif

Python/compile.c L2746

#ifdef DOSS_SWITCH
static int
compiler_case(struct compiler *c, stmt_ty s)
{
  basicblock *end, *next;
  next = compiler_new_block(c);
  end = compiler_new_block(c);
  if (next == NULL || end == NULL)return 0;
  assert(s->kind == Case_kind);

  ADDOP(c, DUP_TOP);
  VISIT(c,expr,s->v.Case.test);
  cmpop_ty op=Eq;
  ADDOP_COMPARE(c,op);
  ADDOP_JUMP(c, POP_JUMP_IF_FALSE, next);
  VISIT_SEQ(c, stmt, s->v.Case.body);
  ADDOP_JUMP(c, JUMP_ABSOLUTE, end);
  compiler_use_next_block(c, next);
  if(s->v.Case.orelse){ 
    VISIT_SEQ(c,stmt,s->v.Case.orelse);
  }
  compiler_use_next_block(c, end);
  return 1;
}
static int
compiler_switch(struct compiler *c, stmt_ty s)
{
   basicblock *end, *next;
   next = compiler_new_block(c);
   end = compiler_new_block(c);
   if (next == NULL || end == NULL) {
        return 0;
    }
   assert(s->kind == Switcha_kind);
   VISIT(c,expr,s->v.Switcha.test);
   compiler_use_next_block(c, next);
   VISIT_SEQ(c,stmt,s->v.Switcha.cases);
   ADDOP(c, POP_TOP);
   compiler_use_next_block(c, end);
   return 1;
}

#endif

L3457

#ifdef DOSS_SWITCH
    case Switcha_kind:
        return compiler_switch(c, s);
    case Case_kind:
        return compiler_case(c, s);
 #endif

Python/symtable.c L1294

#ifdef DOSS_SWITCH
    case Switcha_kind:
        VISIT(st, expr, s->v.Switcha.test);
        VISIT_SEQ(st, stmt, s->v.Switcha.cases);
        break;
    case Case_kind:
      VISIT(st,expr,s->v.Case.test)
      VISIT_SEQ(st, stmt, s->v.Case.body);
        if (s->v.Case.orelse)
            VISIT_SEQ(st, stmt, s->v.Case.orelse);
    break;
#endif

おまけ：is比較を行うswitchb文を追加する

TAさんに指摘されたので、==演算子で比較するswitcha文のみでなく、is演算子で比較するswitchb文を実装してみました。

実装

大まかな流れは変わりませんが、switchの右の式の評価と一緒に評価方法(0ならeq,1ならis)をスタックにプッシュし、case文が呼ばれるたびにDUP_TOP_TWOしてそれらを使うといった感じの実装にしました。

switcha文からの変更点は以下です。

Grammer/python.gram:L84

#ifdef DOSS_SWITCH
    | &'switcha' switcha_stmt
    | &'switchb' switchb_stmt
#endif

L179

#ifdef DOSS_SWITCH
switcha_stmt[stmt_ty]:
    | 'switcha' a=disjunction ':' NEWLINE INDENT b=case_block DEDENT {_Py_Switcha(a,CHECK((asdl_stmt_seq*)_PyPegen_singleton_seq(p, b)),0,EXTRA)}
switchb_stmt[stmt_ty]:
    | 'switchb' a=disjunction ':' NEWLINE INDENT b=case_block DEDENT {_Py_Switcha(a,CHECK((asdl_stmt_seq*)_PyPegen_singleton_seq(p, b)),1,EXTRA)}
case_block[stmt_ty]:
    | 'case' a=atom ':'  b=block c=case_block {_Py_Case(a,b, CHECK(_PyPegen_singleton_seq(p, c)),EXTRA)}
    | 'case' a=atom ':'  b=block c=[default_block] {_Py_Case(a,b,c,EXTRA)}

Python/compile.c:L2746

#ifdef DOSS_SWITCH
static int
compiler_case(struct compiler *c, stmt_ty s)
{
  basicblock *start,*is,*end, *next;
  start = compiler_new_block(c);
  is = compiler_new_block(c);
  next = compiler_new_block(c);
  end = compiler_new_block(c);
  if (next == NULL || end == NULL)return 0;
  assert(s->kind == Case_kind);

  ADDOP(c, DUP_TOP_TWO);

  ADDOP_JUMP(c, POP_JUMP_IF_TRUE,is);
  //if top=0
  cmpop_ty op=Eq;
  VISIT(c,expr,s->v.Case.test);
  ADDOP_COMPARE(c,op);
  ADDOP_JUMP(c, JUMP_ABSOLUTE, start);

  //if top=1
  compiler_use_next_block(c,is);
  op=Is;
  VISIT(c,expr,s->v.Case.test);
  ADDOP_COMPARE(c,op);
  
  compiler_use_next_block(c,start);
  ADDOP_JUMP(c, POP_JUMP_IF_FALSE, next);
  VISIT_SEQ(c, stmt, s->v.Case.body);
  ADDOP_JUMP(c, JUMP_ABSOLUTE, end);
  compiler_use_next_block(c, next);
  if(s->v.Case.orelse){ 
    VISIT_SEQ(c,stmt,s->v.Case.orelse);
  }
  compiler_use_next_block(c, end);
  return 1;
}
static int
compiler_switch(struct compiler *c, stmt_ty s)
{
   basicblock *end, *next;
   next = compiler_new_block(c);
   end = compiler_new_block(c);
   if (next == NULL || end == NULL) {
        return 0;
    }
   assert(s->kind == Switcha_kind);
   VISIT(c,expr,s->v.Switcha.test);
   ADDOP_LOAD_CONST_NEW(c, PyLong_FromLong(s->v.Switcha.compare_type));
   compiler_use_next_block(c, next);
   VISIT_SEQ(c,stmt,s->v.Switcha.cases);
   ADDOP(c, POP_TOP);
   ADDOP(c, POP_TOP);
   compiler_use_next_block(c, end);
   return 1;
}

#endif

動作

上がswitcha文、下がswitchb文を使ったときの動作です。 f:id:Naomi_Lilienthal:20201020200723p:plain

感想

switch文の追加には試行錯誤含め全部で5時間程度しかかかっていないと思います。ドキュメントが整理されており、またプログラムの自動生成などが整備されており、それに従って変更すればよかったことがとても大きかったです。

また、バイトコードに変換して考えるととても考えやすかったので、文法や機能を追加したいときはこの方法を取ることをおすすめします。