この記事は CAMPHOR- Advent Calendar 2018 4日目の記事です．

1. はじめに

プログラミング言語 Python は汎用の動的型付き言語で，機械学習や Web 開発を中心に幅広く使われています．特にここ数年の Python 人気は凄まじいものがあり，某大学生協の本屋では，プログラミング系の平積みコーナーが一面Python 関連書籍で埋め尽くされています．所属しているコミュニティの関係でプログラミング初心者の学生にもよく会うのですが，第一言語が Python という方が非常に多く，まさに猫も杓子も Python といった状況です．

そんなわけで，人々がこぞって Python でプログラムを書いているわけですが，「Python 自体がプログラムである」という事実に目を向けたことのある人は非常に少ないと思います．みなさんが Python のプログラムを書いて実行する時，実際には，処理系（インタプリタ）と呼ばれるプログラムが起動し，みなさんが書いたプログラムを読み込んで実行しています．みなさんが日々入力している python というコマンドもまた，処理系というプログラムなのです．

最も主要な Python の処理系（つまり Python のソースコードを読み込んで実行するプログラム）はC言語で書かれた CPython で，「Pythonをインストールする」と言った時は，大抵この CPython をコンパイルしてできた実行ファイルをインストールしています．CPython はオープンソースソフトウェアで，誰でもソースコードを閲覧したり開発に参加することができます．CPython のソースコードは Python の振る舞いをより深く知るのにはうってつけの資料で，CPython の開発に携わっていなくとも，サービスのボトルネック発見といった課題のためにC言語で書かれたソースコードを読む破目になる人もいることでしょう．

しかしこの CPython，ソースコードが膨大で，最初は読むべき場所を探し当てるのが非常に難しいです．CPython のデータ構造や実行の全体像といった内容については有志の解説記事がそれなりに存在しますが，コードの読み方にまで踏み込んだ情報はなかなか存在せず，とっかかりを見つけるのがとても大変です．

この記事は，そうした厳しい状況を少しでも改善することを目的とした，CPython 入門者のためのハンドブックです．「CPython を改造して 1 + 1 = 3 にする」というお題を通して，CPython の基礎知識から，CPython のコードの読み方まで解説します．次の2章では，CPython に関する最低限（本記事を理解するのに必要なだけ）の知識を説明します．3章では，「CPython を改造して 1 + 1 = 3にする」というお題を通して，実際のソースコードを追いかけてみます．ここでは，ただ変更箇所を示すのではなく，どのように変更箇所を探し当てるのかという部分に焦点を当てて解説します．4章では，3章のコードリーディングからエッセンスを抽出し，CPython のソースコードを自力で読んで行くための一般的な知見を説明します．5章でさらに掘り下げていくための資料をいくつか紹介し，6章でまとめとします．CPython の構造体や実行方法についてぼんやり知っているという人は，2章を飛ばして3章から読んでも良いでしょう．

2. CPython 基礎知識

この章では「データ構造」と「実行」の二つの側面から CPython の基礎知識を説明します．前者の「データ構造」は，例えば，1 という Python の整数が，C言語ではどういうデータ構造で表現されているかといったことです．後者の「実行」は，例えば，1 + 1 という Python の式がC言語上でどのように実行され Python の 2 になるかといったことです．この二つの側面をおさえることが CPython 入門の第一歩となります．

2.1 データ構造

Python における全てのオブジェクトは，その種類ごとにC言語の構造体が宣言されています．例えば，Python の整数に対応する PyLongObject 構造体は以下のようになっています．コードを参照している人は，簡単のためにマクロや構造体の入れ子を展開していることに注意してください．

typedef struct _longobject {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    digit ob_digit[1];
} PyLongObject;

まずは各フィールドの説明をしましょう．

ob_refcnt
- このオブジェクトに対する参照の数を記録するためのフィールドです．ここではあまり重要ではありません．詳細は「参照カウント」で調べてください．
ob_type
- オブジェクトの型で，Python の type 関数によって返されるオブジェクトが格納されるフィールドです．PyLongObject であれば，int かint の子クラスを表すオブジェクトが入ることになります．
ob_size
- オブジェクトのサイズや長さを表すフィールドです．例えば，タプルに対応する PyTupleObject ではタプルの要素数になります．PyLongObject では整数を表現するために確保したC言語上の配列の長さと考えれば良いです．Python は任意桁の整数をサポートするのでこのようになっていますが，詳細はこの記事では取り扱いません．
ob_digit
- 実際の値を格納する配列です．

これらのうち，ob_refcnt と ob_type は全てのオブジェクトに共通のフィールドです．ob_size は長さの概念がある全てのオブジェクトに共通のフィールドです．ob_digit は PyLongObject に固有のフィールドです．

（CPython では，最初の2つのフィールドのみを持った構造体としてPyObject が，最初の3つのフィールドのみを持った構造体としてPyVarObject がそれぞれ定義されており，どちらも基底クラスのように使われています．CPython を理解する上では重要なポイントですが，本記事の内容には必要ないので割愛します．気になる方は5章の資料をいくつかあたってみてください）

特に重要なのは ob_type フィールドです．Python の全てのオブジェクトは ob_type フィールドにオブジェクトの型を持っており，その型がオブジェクトの振る舞いの大部分を決定します．Python の型もまた Python のオブジェクトであり，それに対応する PyTypeObject というC言語の構造体が宣言されています．次はそれを見てみましょう．フィールドの数がとても多い構造体なので，説明に必要な部分だけ抜粋します．本記事全体を通して，... は引用時に省略された部分を表します．

typedef struct _typeobject {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    const char *tp_name;
    ...
    PyNumberMethods *tp_as_number;
    ...
    initproc tp_init;
    ...
} PyTypeObject;

最初の3つのフィールドは先ほど説明した共通のフィールドです．tp_nameは型の名前です．int 型なら "int" という文字列が入りますし，ユーザーが class A: ... として定義したクラスなら "A" が入ります．次のtp_as_number は一旦飛ばしてすぐ後で説明します．tp_init は Pythonのクラスの __init__ メソッドに対応するフィールドです．例えば，Pythonのインタプリタに (42).__init__ と入力して返ってくる値は，int オブジェクトの tp_init フィールドの関数をラップしたものです．他にも，PyTypeObject の省略された部分には，__call__ や __str__ といったPython クラスの特殊なメソッドに対応するフィールドがずらりと並んでいます．

さて，一旦飛ばした tp_as_number を説明しましょう．名前の通り，ここにはオブジェクトを数値だと思って操作する際のメソッド群が格納されます．例えば，Python の整数であれば，整数の足し算や引き算を行うための関数が格納されています．また，ユーザーが定義した Python のクラスであれば__add__ や __sub__ といったメソッドが格納されます．PyNumberMethods は，以下のようになっています．nb_add が Python クラスの __add__ メソッドに対応し，nb_sbtract が Python クラスの__sub__ に対応しています．

typedef struct {
    binaryfunc nb_add;
    binaryfunc nb_subtract;
    ...
} PyNumberMethods;

重要なのは，ここまで説明した PyTypeObject が単なる骨組みであるということです．PyTypeObject のフィールドをどのように埋めるかによって，そのオブジェクトは Python の int にも str にも，はたまた全く新しい型にもなります．実際の例として，CPython には Python のint に対応する PyLong_Type というオブジェクトが定義されています．これは，tp_init や nb_add，nb_substract といったフィールドを整数専用の処理で埋めたものです．CPython は，オブジェクトを表す構造体（例えばPyLongObject）とカスタマイズ可能な PyTypeObject を組み合わせることによって，実装を抽象化し，Python の豊かな言語機能をスマートに実現しています．

2.2 実行

CPython では，Python のプログラムを「バイトコード」と呼ばれる仮想スタックマシンの命令列にコンパイルし，スタックマシン上でプログラムを実行します．スタックマシンとは，データを格納するのにスタックを用いる計算モデルのことです．類似する概念としては，レジスタマシンがあります．これはデータをいくつかのレジスタに格納する方式で，みなさんが持っているコンピュータは大抵レジスタマシンのはずです．

早速バイトコードを見てみましょう．例えば，Python の 1 + 2 という式は以下のようなバイトコードに変換されます．実際はコンパイラの最適化により定数の計算がつぶれてしまうのですが，ここでは最適化前の結果を示しています．実際の結果はバイト列で読むのが非常に大変なので，逆アセンブルした結果を簡単に示します．

LOAD_CONST  (1)
LOAD_CONST  (2)
BINARY_ADD

LOAD_CONST は定数をスタックにプッシュする命令です．BINARY_ADD はスタックから値を2つポッブして，それらを足した結果をスタックにプッシュする命令です．もちろん，このときスタックに保存されているのは2.1章で説明した PyLongObject 構造体へのポインタです．以下では，バイトコードにコメントで各行を実行した後のスタックの状態を付け足して示します．確かに，1 + 2 を計算した結果がスタックに保存されていることがわかると思います．

                  # []    （初期状態，左側をスタックの先頭だと考える）
LOAD_CONST  (1)   # [1]   （定数1をプッシュする）
LOAD_CONST  (2)   # [2, 1]（定数2をプッシュする）
BINARY_ADD        # [3]   （値を2つポップして足した結果をプッシュする）

この記事を理解する上で重要なのは，CPython が Python プログラムを仮想スタックマシンのバイトコードに変換して実行しているということだけです．具体的なコンパイルの手法や，他のバイトコード命令などが気になる人は5章に示す資料を参照してください．

3. CPython を改造して 1 + 1 = 3 にする

この章では，実際に CPython のコードを追いかけ，1 + 1 = 3 となるように変更を加えます．今回読むコードの情報を以下に示します．

リポジトリ
- https://github.com/python/cpython/
commit
- 1bf9cc509326bc42cd8cb1650eb9bf64550d817e

これは Python 3.7.0 リリース時のコミットです．この記事だけで分かるようにソースコードは適宜抜粋しますが，自分の手元でも試したい人は，コードをクローンしてきて，指定したコミットをチェックアウトしてください．masterの HEAD とは既にある程度の差異があるはずで，具体的な実装や行番号が食い違って苦しむ可能性があるので，なるべく同じコミットのコードを参照してください．また，今回の記事ではとても丁寧にコードを追いかけます．慣れればもっとショートカット（具体的には直接 3.4 章にジャンプ）できるということは述べておきます．それではやっていきましょう．

3.1. 足し算に対応するバイトコード命令を探す

まずは Python の足し算がどのようなバイトコードに変換されるかを調べます．既に2.2章でネタバレをしてしまいましたが，具体的なコマンド等を含めてもう一度みてみましょう．以下の Python プログラムを保存します．

# test.py

x = 1
y = 1
x + y

上のテストプログラムでは，最適化で足し算がつぶれてしまうのを避けるために，定数を一度変数に格納しています．次に，ターミナルで以下のコマンドを実行します．dis は Python のバイトコードを逆アセンブルするためのモジュールです．ドキュメントはこちらを参照してください．

> python -m dis test.py

  1           0 LOAD_CONST               0 (1)
              2 STORE_NAME               0 (x)

  2           4 LOAD_CONST               0 (1)
              6 STORE_NAME               1 (y)

  3           8 LOAD_NAME                0 (x)
             10 LOAD_NAME                1 (y)
             12 BINARY_ADD
             14 POP_TOP
             16 LOAD_CONST               1 (None)
             18 RETURN_VALUE

dis モジュールには全てのバイトコード命令が解説されており，それを手元に置いて上の命令列を眺めると，どうやら BINARY_ADD 命令が足し算を行っていそうなことが分かります．これが最初の手がかりです．

3.2. スタックマシンの実装を見る

BINARY_ADD 命令が手がかりであることが分かったので，次はその命令に従って処理を行なっている部分を探しにいきます．2.2 章で「BINARY_ADD がスタックから値を2つポップして，それらを足した結果をスタックにプッシュする」と述べましたが，それをやっているコードがどこかにはあるはずですね．

我々が求めるコードは，cpython/Python/ceval.c の中の，_PyEval_EvalFrameDefault 関数の中にあります．この関数の中に，バイトコード命令を一つずつ読み出して実行するループが記述されており（開始は930行目），更にその中で，バイトコードの命令ごとに処理を振り分けるswitch 文が記述されています（開始は1057行目）．実際に BINARY_ADD を処理している部分のコードを以下に抜粋します．本記事全体を通して，ソースコード中の日本語のコメントは，処理を説明するために私が付け加えたものです．

/* cpython/Python/ceval.c 1265行目から抜粋 */

        TARGET(BINARY_ADD) {
            PyObject *right = POP();  /* 右オペランドのポップ */
            PyObject *left = TOP();   /* 左オペランドの読み出し */
            PyObject *sum;
            ...
            if (PyUnicode_CheckExact(left) &&
                     PyUnicode_CheckExact(right)) {
                /* 文字列結合 */
                sum = unicode_concatenate(left, right, f, next_instr);
                /* unicode_concatenate consumed the ref to left */
            }
            else {
                sum = PyNumber_Add(left, right);  /* 足し算の実行 */
                Py_DECREF(left);
            }
            Py_DECREF(right);
            SET_TOP(sum);  /* スタックのトップに結果を書き込む */
            if (sum == NULL)
                goto error;
            DISPATCH();
        }

まず最初の2行で，足し算の右オペランド，左オペランドの順でポップしています（厳密には左オペランドはポップせず，読み出して後で上書きしています）．その後，*sum の宣言があり，if 文が続いています．if節は，両辺が文字列の時に文字列の結合を行うための特殊ケースです．重要なのは else 節で，ここに PyNumber_Add という関数の呼び出しがあり，いかにも整数の足し算をやっていそうです．次はこれを見ていきます．

3.3. PyNumber_Add を追う

PyNumber_Add 関数は，cpython/Objects/abstract.c にあります．以下に抜粋します．

/* cpython/Objects/abstract.c 951行目から */

PyObject *
PyNumber_Add(PyObject *v, PyObject *w)
{
    PyObject *result = binary_op1(v, w, NB_SLOT(nb_add));
    ...
    return result;
}

整数の足し算に限って考えると，重要なのは関数本体の一行目だけです．NB_SLOT というマクロで，2.1 章に示した PyNumberMethods 構造体における nb_add のオフセットを求めて，足し算のオペランドと一緒にbinary_op1 関数に渡しています．NB_SLOT が良くわからない場合は，「とにかく nb_add フィールドにアクセスするために必要な情報を計算している」と納得して先に進みましょう．

さて，次は binary_op1 関数です．この関数は，PyNumber_Add と同じファイルにあります．整数同士の足し算に関係のある部分だけ以下に抜粋します．

/* cpython/Objects/abstract.c 781行目から */

static PyObject *
binary_op1(PyObject *v, PyObject *w, const int op_slot)
{
    PyObject *x;
    binaryfunc slotv = NULL;
    ...
        /* 二項演算を行う関数を読み出す．
           足し算の場合は tp_as_number->nb_add を読み出す */
        slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);
    ...
    }
        ...
        /* 読み出した関数に値を渡して計算する．*/
        x = slotv(v, w);
        if (x != Py_NotImplemented)
            return x;
    ...
}

binary_op1 はあらゆる二項演算のための汎用関数ですが，話がややこしくなるので足し算に特化して考えます．最初の2行は変数宣言で，*x は結果を格納するための変数，slotv は足し算を行う関数を格納するための変数です．次の1行で NB_BINOP マクロを使って足し算を行う関数を読み出しています．NB_BINOP は，v->ob_type->tp_as_number の先頭から op_slot 分だけ後ろのアドレスから値を読み出すマクロです．ここでは，v->ob_type->tp_as_number->nb_addと同じです．全て 2.1 章で登場済みのフィールドたちですね．2.1 章で説明した通り，これが足し算を行う関数に対応します．slotv に関数を格納したら，あとは slotv を v と w で呼び出して結果を返すだけです．

さあ，もう一息です．いま v は Python の整数，つまり PyLongObjectでしたから，その ob_type->tp_as_number->nb_add フィールドが定義されている部分を探しに行けば，整数の足し算を行なっている部分にたどり着けるはずです．この場合，ob_type フィールドに入るのは PyLong_Type ですから，その定義を見にいきましょう．

3.4. PyLong_Type を追う

PyLong_Type は，cpython/Objects/longobject.c に定義されています．関連する箇所を以下に抜粋します．以下の定義を見ると，binary_op1 関数で読み出した v->ob_type->tp_as_number->nb_add は，long_add 関数であることがわかります．

/* cpython/Objects/longobject.c 5342行目から */

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    ...
};

PyTypeObject PyLong_Type = {
    ...
    &long_as_number,                            /* tp_as_number */
    ...
};

3.5 long_add 関数を変更する

おめでとうございます！ようやく整数の足し算が行われている箇所にたどり着きました．long_add 関数を以下に抜粋します．

/* cpython/Objects/longobject.c 3082行目から */

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        /* 実際に足し算を実行している箇所の一つ */
        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
    }
    ...
}

if の中の MEDIUM_VALUE(a) + MEDIUM_VALUE(b) が実際に整数の足し算を実行している箇所の一つです．実は足し算を行なっているのはここだけではないのですが，このあたりの詳細は後述します．MEDIUM_VALUE マクロでPyLongObject からC言語レベルの整数を読み出し，足した結果をPyLong_FromLong で再び PyLongObject にしています．

プログラムを次のように変更してみましょう．

-     return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
+     return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b) + 1);

コンパイルして実行した結果が以下です（Python のビルドには，ビルドしてできた Python 処理系を使った処理が含まれているようで，そのせいで makeが途中でこけていますが，処理系自体は python.exe に生成されています）．

> ./configure
...

> make
...
IndexError: list index out of range
generate-posix-vars failed
make: *** [pybuilddir.txt] Error 1

> ./python.exe

Python 3.7.0 (v3.7.0-dirty:1bf9cc5093, Nov  8 2018, 14:52:09)
[Clang 9.1.0 (clang-902.0.39.2)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 + 1
3

めでたく 1 + 1 = 3 の Python が完成しました．

3.6. 落ち穂拾い

3.5 章で行なった変更は，両辺の値が - (2 ** 30 - 1) から 2 ** 30 -1である場合のみ有効です．先ほど作った処理系で検証した結果が以下です．確かに y + 1 は正しく計算されていますね．

>>> x = 2 ** 30 - 1
>>> x
1073741823
>>> x + 1
1073741825

>>> y = 2 ** 30
>>> y
1073741824
>>> y + 1
1073741825

これは Python の任意精度整数の仕様によるものです．全てのケースで変な足し算を行うためには，もう少し頑張らないといけません．興味のある方はやってみてください．

4. 知見を一般化する

3章のコードリーディングの流れは，CPython のソースコードを読む際の典型的なパターンの一つです．そこで，3章でやったことをもう少し一般的な言葉でまとめ直して，幅広く応用可能な知見に昇華させたいと思います．以下に示す方法は，バイトコード命令で表される Python の振る舞いを調べる際に有用です．

1. 手がかりとなるバイトコード命令を探す

自分が調べたい振る舞いを含んだなるべく小さな Python コードを書き，それを dis モジュールで逆アセンブルします．そうすると，めぼしいバイトコード命令が見つかるはずです．

2. `ceval.c` を足がかりにする

ceval.c を開いてバイトコード命令の名前で検索すると，概ねそのバイトコードに対応する処理の箇所にジャンプできます．

3. 具体的な処理を追う

各命令の主要な処理はたいてい別の関数に切り分けられているので，さらにその関数を追いかけます．3 章では PyNumber_Add にあたります．ここをどんどん進んでいくと，たいていどこかでob_type->tp_hogehoge を呼び出している箇所にたどり着きます．

4. 具体的な型に飛ぶ

調べたい振る舞いでよく使われるオブジェクトの型を一つ選んで，その型の tp_hogehoge フィールドを調べます．3章では，足し算で使われる代表的な型として int を例にとり，longobject.c の PyLong_Type を調べました．他の例として，イテレータに関係する処理を調べたいとなれば，list などを調べるのが良いでしょう．型の定義は cpython/Objects の中を漁れば見つかるはずです．

以上がよくあるコードリーディングのパターンです．様々な言語機能を題材にして上のパターンを繰り返すことで，CPython のかなりの範囲を読むことができるでしょう．ただ，これだけで CPython の全てを理解できるわけではありません．以下に，他の典型的な入り口をいくつか示します．

組み込み関数
- cpython/Python/bltinmodule.c
組み込みメソッド（append など）
- それぞれの型オブジェクトの tp_methods フィールド
クラス定義
- cpython/Python/bltinmodule.c の builtin___build_class__ 関数
構文解析
- cpython/Parser/parser.c
抽象構文木からバイトコードへの変換
- cpython/Python/compile.c
標準ライブラリ
- cpython/Lib

5. 資料集

https://docs.python.jp/3/reference/index.html
- 公式の言語リファレンスです．文法をはじめとした Python の仕様が記述されています．3〜5章は特に Python の振る舞いを知る上で役に立つので，目を通しても良いかもしれません．
https://docs.python.jp/3/c-api/index.html
- C言語から Python にアクセスするためのC言語ライブラリの API に関するドキュメントです．このドキュメントにある関数は，CPython 自体の実装にも使われています．もし CPython の実装で何をしているか分からない関数があったとき，このドキュメントを見ると情報を得られるかもしれません．
https://leanpub.com/insidethepythonvirtualmachine
- CPython に関する書籍です．電子版のみで，無料で読むことも可能です．CPython に関するまとまった情報を得られる貴重な資料です．
http://pgbovine.net/cpython-internals.htm
- 2014年にアメリカのロチェスター大学で行われた Python の内部実装に関する講義です．英語ですが，実際にコードを読んでいる画面や，タブレットに書いた手書きの図を見せてくれるので非常にわかりやすいです．
https://postd.cc/python-internals-pyobject/
- POSTD の翻訳記事です．私が 2.1 章で説明したような内容について，もう少し詳しく書いています．CPython のデータ構造をもう少し詳しく知りたい，という場合は読んでみても良いかもしれません．

6. おわりに

この記事では，「CPython を改造して 1 + 1 = 3　にする」というお題を通して，CPython の基礎知識やコードリーディングの知見を説明しました．本記事を読んで，「CPython，なんか読める気がする！」と思える人が一人でも増えたら本望です．

yigarashiのブログ

学んだことや考えていることを書きます

Python処理系入門〜1 + 1 で学ぶ処理系解読の基礎〜

1. はじめに

2. CPython 基礎知識

2.1 データ構造

2.2 実行

3. CPython を改造して 1 + 1 = 3 にする

3.1. 足し算に対応するバイトコード命令を探す

3.2. スタックマシンの実装を見る

3.3. PyNumber_Add を追う

3.4. PyLong_Type を追う

3.5 long_add 関数を変更する

3.6. 落ち穂拾い

4. 知見を一般化する

1. 手がかりとなるバイトコード命令を探す

2. `ceval.c` を足がかりにする

3. 具体的な処理を追う

4. 具体的な型に飛ぶ

5. 資料集

6. おわりに

1. はじめに

2. CPython 基礎知識

2.1 データ構造

2.2 実行

3. CPython を改造して 1 + 1 = 3 にする

3.1. 足し算に対応するバイトコード命令を探す

3.2. スタックマシンの実装を見る

3.3. PyNumber_Add を追う

3.4. PyLong_Type を追う

3.5 long_add 関数を変更する

3.6. 落ち穂拾い

4. 知見を一般化する

1. 手がかりとなるバイトコード命令を探す

2. ceval.c を足がかりにする

3. 具体的な処理を追う

4. 具体的な型に飛ぶ

5. 資料集

6. おわりに

2. `ceval.c` を足がかりにする