Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Pythonの処理系はどのように実装され,どのように動いているのか? 我々はその実態を調査すべ...

Pythonの処理系はどのように実装され,どのように動いているのか? 我々はその実態を調査すべくアマゾンへと飛んだ.

KMC春合宿2017

utagawa kiki

March 18, 2017
Tweet

More Decks by utagawa kiki

Other Decks in Technology

Transcript

  1. 今日話すこと 1. Python の概要 2. Python のオブジェクトの構造体による内部表現 3. Python の主要なデータ型の実装

    4. Python の関数・モジュールの実装 5. Python のコードの実行・仮想機械について
  2. 1. Python の概要 2. Python のオブジェクトの構造体による内部表現 3. Python の主要なデータ型の実装 4.

    Python の関数・モジュールの実装 5. Python のコードの実行・仮想機械について どのように実装され 今日話すこと どのように動いているのか
  3. Python の特徴 • 動的型付けプログラミング言語である ◦ 型ヒントが最近導入された • インタプリタ言語である • インデントによってブロックを表現する

    (オフサイドルール) • コードがシンプルで扱いやすく設計されている • 機械学習・統計ライブラリが豊富 ◦ 日本だと機械学習目的で書いてる人が多そう [要出典]
  4. Python のコードの例 • 変数の定義 x = 12345 # int(整数型) st

    = “this is string” # str(文字列型) bo = True # bool(真偽値) obj = None # 何もない的な
  5. Python のコードの例 • 変数の定義 alist = [3, 4, 6] atuple

    = (3, 4, 6) adict = {‘hoge’: 10, ‘fuga: 20} aset = {1, 3, 5, 7}
  6. Python のコードの例 • 条件分岐 (if 文) if num < 50:

    print(“less than 50.”) elif num < 100: print(“less than 100.”) else: print(“sugo-i!!!!!!!”)
  7. Python のコードの例 • 例外処理 try: do_something_abunai() except NanikaError as e:

    print(‘例外が発生し,捕捉される場合’) else: print(‘例外が発生しなかった場合’) finally: print(‘いずれの場合にも実行される処理’)
  8. Python のコードの例 • コンテキストマネージャ ◦ あるオブジェクトに対する初期化と後片付けをまとめて記述できる ▪ Go の defer,C#

    の using 文と似ている ◦ open() されたファイルは with 文を抜ける際に必ず close() される with open(“hoge.txt”, “wt”) as f: f.write(data)
  9. Python のコードの例 • 内包表記 [x ** 2 for x in

    range(100) if x % 2 == 0] {x ** 2 for x in range(100) if x % 2 == 0} {str(x): x for x in range(100) if x % 2 == 0} (x ** 2 for x in range(100) if x % 2 == 0) # ジェネレータ
  10. CPython • van Rossum が書いた Python の標準実装 • C言語で記述されている •

    CPython を使ってライブラリを書くことができる ◦ いわゆるC拡張ですね
  11. オブジェクトを表す2つの構造体 typedef struct _object { _PyObject_HEAD_EXTRA Py_ssize_t ob_refcnt; struct _typeobject

    *ob_type; } PyObject; typedef struct { PyObject ob_base; Py_ssize_t ob_size; } PyVarObject; #define _PyObject_HEAD_EXTRA Includes/object.h L106-115 PyVarObject extends PyObject
  12. Python のデータ型 • 組み込みデータ型 ◦ int (整数), float (浮動小数点数) ◦

    str (文字列), bytes (バイナリ列) ◦ コンテナ ◦ 他にもあるけどとりあえずこれぐらい
  13. Python のデータ型 • 組み込みデータ型 ◦ int (整数), float (浮動小数点数) ◦

    str (文字列), bytes (バイナリ列) ◦ コンテナ ◦ 他にもあるけどとりあえずこれぐらい
  14. int: struct _longobject • 多倍長整数 ◦ (メモリの許す限り)いくらでも大きな整数を表すことができる struct _longobject {

    PyVarObject ob_base; digit ob_digit[1]; }; ob_digit[0] ob_digit[1] ob_digit[2] ... ob_digit[ob_size - 1]
  15. int: struct _longobject • 負の数は ob_size を負にすることで表している • 0 のときは

    ob_size == 0 • ある整数Xの絶対値に対して,次の関係が成り立つ ◦ D i は ob_digit[i] ◦ N は ob_size の絶対値 ◦ S はシフト数 (15 もしくは 30)
  16. 多倍長整数の足し算・引き算 • 多倍長整数の足し算・引き算は,筆算に似た方法で行われる ob_digit[0] ob_digit[1] ob_digit[2] ... ob_digit[ob_size - 1]

    ob_digit[0] ob_digit[1] ob_digit[2] ... ob_digit[ob_size - 1] ob_digit[0] ob_digit[1] ob_digit[2] ... ob_digit[ob_size - 1] A B A+B carry carry carry add add add add
  17. Python のコンテナ • 次の4つを取り上げます ◦ list ◦ collections.deque ◦ dict

    ◦ set • CPython では各種操作の時間計算量が規定されている ◦ https://wiki.python.org/moin/TimeComplexity
  18. list: PyListObject • list という名前をしているけど,動的配列 typedef struct { PyObject_VAR_HEAD //

    PyVarObject としての情報 PyObject **ob_item; // 要素へのポインタ Py_ssize_t allocated; // 確保しているサイズ(≠要素数) } PyListObject; [0] [1] [2] [ob_size - 1] ... ... allocated
  19. dict: PyDictObject • ハッシュテーブル typedef struct { PyObject_VAR_HEAD Py_ssize_t ma_used;

    // 辞書の要素数 uint64_t ma_version_tag; // 辞書のバージョン PyDictKeysObject *ma_keys; // 辞書のキーのリスト PyObject **ma_values; // 辞書の値を格納するテーブル } PyDictObject;
  20. モジュールの作り方 • だいたい以下の手順を踏めば CPython でライブラリが作れます • クラスや定数を意図的に無視しています 1. 関数を書く 2.

    関数の一覧を登録する 3. モジュールの情報を登録する 4. モジュールの初期化をする関数を書く
  21. 関数を書く (具体的に) • 関数は static で宣言する ◦ 外部から見えていい関数は,後述する「モジュールを初期化する関数」のみとする • 引数は

    (PyObject*, PyObject*) とする ◦ 1つ目はモジュール自身を表す (だいたい self と名付ける) ◦ 2つ目は引数を格納した Python のタプル (だいたい args と名付ける) ◦ これを PyArg_ParseTuple() 関数を使ってパースすると,所望の値が得られる • 返り値も PyObject* とする ◦ None を返すときは Py_RETURN_NONE マクロを使う
  22. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} }
  23. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} } 関数の名前
  24. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} } 関数ポインタ (PyCFunction にキャストする)
  25. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} } 引数の受け取り方
  26. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} } 関数の説明文
  27. 関数の一覧を登録する • PyMethodDef の配列に詰め込む • 終端に番兵を置く static PyMethodDef mysortmethods[] =

    { {“bubblesort”, (PyCFunction)bubblesort, METH_VARARGS, “bubblesort.”}, {NULL, NULL, 0, NULL} } 番兵(終端を表す)
  28. 実例を見る • バブルソート関数だけがある mysort というモジュールを書いた ◦ https://github.com/utgwkk/python-c-api-practice • setup.py をよしなに書くとモジュールとして配布できる

    • 組み込みライブラリの場合は CPython のビルド時によしなにされる • TODO: コードをざっと見る • TODO: インストールできることを確認する
  29. 実行の手順 (PEP 339 より) 1. コードを解析して解析木にする 2. 解析木を抽象構文木(AST)に変換する 3. 抽象構文木を制御フローグラフ(CFG)に変換する

    4. 制御フローグラフを基にしてバイトコードを生成する 5. バイトコードを仮想機械上で実行する
  30. 実行の手順 (PEP 339 より) 1. コードを解析して解析木にする 2. 解析木を抽象構文木(AST)に変換する 3. 抽象構文木を制御フローグラフ(CFG)に変換する

    4. 制御フローグラフを基にしてバイトコードを生成する 5. バイトコードを仮想機械上で実行する
  31. バイトコードへの変換 • Python のコードは最終的にバイトコード(中間コード)にコンパイルされる ◦ 1バイトで命令を表す(256通り) ◦ これと引数を組み合わせて 2バイトが命令の最小単位 •

    コンパイルされたバイトコードは仮想機械(VM)上で実行される • こういうタイプのインタプリタをバイトコードインタプリタと呼ぶ
  32. Python VM の正体 • PyFrameObject 構造体がその正体 ◦ PyCodeObject へのポインタ(バイトコードの列) ◦

    グローバル変数,ローカル変数などへのポインタ ◦ スタック ◦ 例外オブジェクト,トレースバックの情報 • 関数呼び出しごとに作られる ◦ ジェネレータが簡単に実現できる
  33. _PyEval_EvalFrameDefault() 関数 • ここに PyFrameObject を渡して PyCodeObject を実行している • 終了条件に達するまでバイトコードを順に実行する

    ◦ 無限ループ (for (;;)) の中がその実体 ◦ 終了条件 ▪ return 文が実行される ▪ 例外が送出され try~except で捕捉されない
  34. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a print
  35. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a print
  36. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a print 6
  37. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a print 6
  38. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print 6
  39. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  40. print シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0

    (a) 4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  41. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print print a
  42. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print print a
  43. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print print a
  44. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  45. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print None
  46. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print None
  47. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print None
  48. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  49. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  50. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print None
  51. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print None
  52. シミュレートしてみよう 1 0 LOAD_CONST 3 (6) 2 STORE_NAME 0 (a)

    4 LOAD_NAME 1 (print) 6 LOAD_NAME 0 (a) 8 CALL_FUNCTION 1 10 POP_TOP 12 LOAD_CONST 2 (None) 14 RETURN_VALUE 定数: None 6 名前: a = 6 print
  53. 参考 • Inside The Python Virtual Machine https://leanpub.com/insidethepythonvirtualmachine/read • About

    Python VM http://svn.coderepos.org/share/docs/jbking/vmdoc/about_python_vm.html • CPython の Git リポジトリ https://github.com/python/cpython • Python 3.6.0 Documentation http://docs.python.jp/3/