cafebabepy PyCon JP 2018

cafebabepyというJVM上で動くPython3処理系を実装しています。 本セッションではPython3の言語仕様に悪戦苦闘し、どのように実装していったのかをお話します。

Transcript

1. cafebabepyというJVM上で 動くPython3処理系の実装詳解 PyCon JP 2018 09/18 yotchang4s (よっちゃん)
2. 注意！ 言語処理系の実装詳解というだいぶ無茶なことをやるの でスライド多めです。 気になったところがあれば後で個別にでも 質問＆スライドを公開するので見て下さい！
3. お前誰よ ❖ yotchang4s (よっちゃん) ➢ 澁谷 典明 (Yoshiaki Shibutani) https://twitter.com/yotcang4s ❖ Python歴 ➢ 1年5ヵ月くらいの初心者 (未だにfor (x in range(10)): print(x)と書いてしまうことがある… ❖ 所属 ➢ 株式会社エフ・コード
4. おしながき 1. Pythonの抽象構文木(AST)を作成する話。 2. 抽象構文木を評価(eval)する話。 3. PythonとJavaの境界線の実装。 4. Pythonの深く美しい言語仕様。 5. まとめ
5. cafebabepy!! 名前を聞いたことがある人は？
6. cafebabepy Githubリポジトリ https://github.com/cafebabepy/cafebabepy 実はcafebabepy.orgドメインも取っていたり。 (org.cafebabepyパッケージを使いたいから)
7. cafebabepyとは？ JVM上で動くPython 3の処理系。 名前の由来はJavaのクラスファイルのマジックナンバーである cafebabeから来ている。 開発開始からちょうど1年5ヵ月ほど。 私、yotchang4sが1人で作っている。 #cafebabepyハッシュタグで開発状況をつぶやいてます。 ※まだまだ実装途中であり、Python 3が完全に 　動くわけではない。まだほぼ全てのモジュールが 　importできない…
8. 開発の動機 1. Python 3でJythonを使うぞ！ 2. Python 2.7までしか対応していない。。。 3. 2015年から更新が止まっている。。。 4. ならば…
9. 自分で作ればいい！
10. 開発のモチベーション Python初心者だからPythonわかんないです＞＜ Python処理系作ったらPythonがわかるはず！ 楽しい＼(^o^)／
11. Pythonが動くざっくりとした仕組み 1. ソースコードを字句解析して字句(トークン)のストリームを作る 2. 字句のストリームから具象構文木を作る。 3. 具象構文木から構文解析をして抽象構文木(AST)を作る 4. 抽象構文木をevalする(単純なインタプリタ) (CPythonだとバイトコードを生成してVMで動かす)
12. 1. Pythonの抽象構文木(AST)を作成する
13. 字句解析をする ソースコードの文字列を解析して、構文解析の最小単位となっている トークン(字句)の並び(ストリーム)を作る。 cafebabepyではANTRL v4で生成した字句解析器をさらにカスタマイズしてい る。Pythonはインデントでブロックを表現するため、字句解析の時点でインデン トを論理的なトークンに変換する。 構文解析器はトークン(字句)に対して処理をするので、字句解析器で空白文字 であるインデントをインデントトークンに変換する必要がある。
14. 字句解析器から構文解析器への受け渡し 字句解析器 (Lexer) if 1 == 1 : <NEWLINE> <INDENT> print ( "hello" <DEDENT> <NEWLINE> ANTLR v4 if 1 == 1: print("hello") ) ポイントは論理的なトークンである<INDENT>と<DEDENT>。 Pythonでは字句解析でインデントの始まりと終わりを作る。 トークンストリーム 具象構文木 構文解析器 (Parser)
15. 字句解析におけるインデントの処理方法 int indent = getIndentCount(spaces); // インデントの幅を計算 int previous = this.indents.isEmpty() ? 0 : this.indents.peekFirst(); // 前回のインデント幅 CommonToken newLine = new CommonToken(NEWLINE, "<NEWLINE>"); emitOnly(newLine); if (indent > previous) { // 前回のインデントより今回のインデントの方が大きければインデント開始 this.indents.addFirst(indent); // 今回のインデントを追加 CommonToken indentToken = new CommonToken(INDENT, "<INDENT>"); emitOnly(indentToken); } else { // 前回のインデントより今回のインデントの方が小さければインデント終了 (デデント) while (!this.indents.isEmpty() && this.indents.peekFirst() > indent) { CommonToken dedentToken = new CommonToken(DEDENT, "<DEDENT>"); emitOnly(dedentToken); this.indents.removeFirst(); // 前回のインデントを削除 } }
16. 具象構文木 トークンのストリームから具象構文木を作る。cafebabepyでは具象構文木の作 成はANTLR v4で生成されたコードに全て任せている。 if_stmt トークンストリーム 具象構文木とは if 1 == 1 : <NEWLINE> <INDENT> print ( "hello" <DEDENT> <NEWLINE> ) if test 1 == 1 : suite if文の中の処理 この図はだいぶ省略をしているので 詳細は以下のif_stmtを参照 https://docs.python.org/ja/3/reference/gra mmar.html …
17. ANTLR v4とは ALL(*)構文解析に基づくパーサジェネレータであり、*.g4ファイルにEBNFに似 た形式で記述すると字句解析器と構文解析器を生成することができる。 構文解析器にかけると具象構文木がANTLR v4で生成されたJavaコードにて 作成され、visitor/actionにより具象構文木を走査することができる。 cafebabepyではvisitorを採用している。 ※1 visitorとはいわゆるGoFのvisitorパターンのこと ※2 JavaのコードだけじゃなくてPythonのコードもジェネレートできる。 *.g4ファイルの例 simple_stmt : small_stmt (SEMI_COLON small_stmt)* SEMI_COLON? NEWLINE ;
18. Pythonの構文ルールについて(1) Pythonの構文はLL(1)となっており、Pythonを設計する際にも これが守られている。 ※字句解析をした後のトークンストリームに限る。(インデント等) LL(1) Parserは再帰下向き構文解析で実装できる。LL(1)は1個のトークンを先 読みするだけで、構文の決定ができるような文法である。LLは左再帰すること が出来ず、LL(1)はバックトラックが発生しない。 ※1 再帰下向き構文解析とは構文木を考えたときに、根元側から枝へと 　 解析を進めていく解析方法である。 ※2 LLにおける左再帰とは Expr → Expr + Term という構文規則があった 　 ときにExprが無限再帰することを言う。 ※3 バックトラックとは例えばLL(3)で3つトークンを先読みした結果、 　 規則に合わなかった場合に前に戻って解析をやり直すことを言う。
19. Pythonの構文ルールについて(2) Pythonの構文ルールはEBNFに近い形でドキュメント化されている。 https://docs.python.org/ja/3/reference/grammar.html ANTLR v4もEBNFに近い形かつALL(*)に対応しているため、*.g4ファイルに記 述する内容はほぼ写経すればよい。(Unicode対応等を除く)
20. 何故抽象構文木をつくるのか 抽象構文木は具象構文木と違い、プログラムの実行に必要の無い情報を取り 除き、意味のある情報のみを取り出して抽象した木構造のデータ構造である。 処理系では例えば以下の構文 >>> if True: pass における「:」コロンはあくまで構文解析のために必要なトークンである。抽象構 文木にすることによって言語の意味のみを抽出できるため、評価(eval)する工 程が楽になる。
21. Pythonの抽象構文木とは Pythonでは抽象構文木にアクセスするためのAPIが仕様化されている。 より詳細な内容は https://docs.python.org/ja/3.7/library/ast.html を参照。 重要なのは「_ast」モジュールであり、ここに全ての抽象構文木の ノードがある。 _astモジュールはCPythonではPythonで書かれていないため、cafebabepyで は自力で作成している。 • _ast.While • _ast.For • _ast.Return • _ast.etc...
22. 抽象構文木の作り方(1) 具象構文木から抽象構文木を作っていく。 cafebabepyではANTLR v4を使っているため、前述の通り具象構文木は自動 生成される。その具象構文木をvisitorパターンを使ってvisitしていき抽象構文 木を作る。 return_stmt: 'return' [testlist] このようなreturn文の抽象構文木を作る構文ルールがあった場合の抽象構文 木の作成方法は次のようになる。
23. 抽象構文木の作り方(2) PyObject visitReturn_stmt(PythonParser.Return_stmtContext ctx) { // [testlist]が無い場合、つまり「return」はreturnする値はNone PyObject value = this.runtime.None(); if (ctx.testlist() != null) { // [testlist]が存在する場合、つまり「return 1」はreturnする値は1 value = visitTestlist(ctx.testlist()); } // Pythonの「_ast.Return」を生成 return this.runtime.newPyObject("_ast.Return", value); }
24. 抽象構文木の作り方(3) visitFile_inputの中でvisitStmtを呼び出して いる。具象構文木のノードの最後までたど り、戻り値で抽象構文木を返す。 具象構文木をvisitしていき、抽象構文木を構 築していく。 Module(AST) stmt(AST) visitFile_input Module(AST) visitStmt stmt(AST) visitSimple_stmt visitCompound_stmt visitXXX visitXXX Expr(AST) ... … … … 呼ぶ 呼ぶ 呼ぶ 抽象構文木 を返す
25. 抽象構文木の例 (if elif else文) (1) if文の条件式 条件を満たした時に実行される文 条件を満たしていない時に実行される文 つまり、if文の抽象構文木は • 条件式 • 条件を満たした時に実行される文の • 満たしていない時に実行される文の集合 の3つを持つ。 elifはifのネストとして扱われる。
26. 抽象構文木の例 (if elif else文) (2) >>> if 2 < 1: ... 3 ... elif 5 < 4: ... 6 ... else: ... 7 If Compare Num Gt Num Expr Num If Compare Num Gt Num Expr Num Expr Num test body orelse
27. 2. 抽象構文木を評価(eval)する
28. どうやって評価(eval)しているのか？(1) シンプルに実行するためにcafebabepyではすべてはevalメソッドを起点 とするインタプリタにしている。 抽象構文木を辿っていき、その子を更にevalすることによって木を走査 する。つまり再帰的な構造となっている。evalメソッドは各ノード専用の eval処理に振り分けているだけである。
29. どうやって評価(eval)しているのか？(2) // evalの一部 public PyObject eval(PyObject context, PyObject node) { switch (node.getName()) { case "Module": // 抽象構文木のノード名 return evalModule(context, node); case "Interactive": return evalInteractive(context, node); case "Suite": return evalSuite(context, node); case "Import": return evalImport(context, node);
30. どうやって実行(eval)しているのか？(3) eval if test body orelse if文の中には条件判定をするためのtestが存在する。 testは抽象構文木なので実行した結果が欲しい。そこでtestをeval に渡すことによってさらに再帰して実行/値を求めて結果がTrueであ るかを判定する。 これはbodyとorelseも同じで、testをevalした結果がTrueかFalseか によってevalされるかされないかが決まる。
31. どうやって実行(eval)しているのか？(4) 例：_ast.Returnをevalする private PyObject evalReturn(PyObject context, PyObject node) { PyObject value = this.runtime.getattr(node, "value"); // 抽象構文木 PyObject evalValue = eval(context, value); // 実際の値 throw new InterpreterReturn(evalValue); // 大域脱出のため例外を使用 }
32. REPL (Read Eval Print Loop)の実装 1行1行実行するREPLは単純に実装できる。 ただし、このままだと複数行に渡るブロックの処理が実行できない。 >>> if 1 < 2: . . . print(3) ここが複数行(ブロック) . . . 3 >>>
33. 複数行(ブロック)に対応したREPLの仕組み if 1 < 2: NEWLINE→通常NG 検証OK INDENT print(3) NEWLINE→通常NG 検証OK DEDENT NEWLINE→通常OK 入力があった場合、通常パースする。成功したらそのまま評価する。 パースに失敗したら検証パースを行う。検証パースにも失敗したら構文エラー。 検証パースではREPLを通すために条件を緩くしている。
34. 3. PythonとJavaの境界線の実装
35. JavaとPythonについて JavaとPythonの世界にはインピーダンスミスマッチがある。 ここではどのようにJavaの世界でPythonを表現しているか を見てみよう。
36. Javaの世界とPythonの世界 PyObject インタフェース 型のクラス/ モジュール 型のオブジェクト (Pythonクラス) Pythonの世界 オブジェクト Javaの世界 モジュールの オブジェクト (Pythonモジュール) Pythonは全てがオブジェクト。 Javaのクラス定義ではPythonの型のオブ ジェクトとして扱いづらいのでJavaのオブ ジェクトをPythonのクラスとして扱っている。 全てのPythonのオブジェクトはJava側では PyObjectインタフェースとして統一的に扱っ ている。
37. JavaでPython擬似コードを書く CPythonでもそうだがbuiltinsモジュールのようにネイティブに近い ところのコードはJavaで実装するしかない。 builtins.intの実装例を見てみよう。 @DefinePyType(name = "builtins.int") // アノテーションでPythonの型を表現 class PyIntType implements PyObject { … @DefinePyFunction(name = __add__) // アノテーションでメソッドを表現 PyObject __add__(PyObject self, PyObject other) { … } …
38. JavaのPython擬似コードからPythonの世界へ builtins モジュールを作成 Pythonのクラス (PyObject)を作成 Javaのbuiltins パッケージ Javaの PyIntTypeクラス PyFloatTypeクラス etc... sys.modulesに builtinsを登録 @DefinePyType アノテーションが 付いているクラス を検索 PyObjectに 関数を登録 @DefinePyFunction アノテーションが付い ているメソッドを検索
39. JavaのクラスとメソッドとPython Javaは静的型付き言語なので、JavaのメソッドをPythonのような動的型付き言 語のメソッド/関数として振る舞わせることは難しい。 cafebabepyでは動的にメソッドの呼び方を変えるためにJavaのリフレクション を利用して動的にJavaのメソッドの呼び出しを行っている。 ただ、リフレクションは非常に遅いため、JVMのinvokedynamic命令に置き換え る予定。 Pythonのクラスは前述したとおり、Javaのクラスではなくオブジェクトで表現し ている。
40. 4. Pythonの深く美しい言語仕様
41. ここからは処理系を作る上で必要なPythonの言語 仕様についての話が多くなります。 Python自体を知ってもらうことによって処理系では 何をしているのかを理解してもらえればと思います。
42. Pythonの特殊メソッド Pythonには特殊メソッド(プロトコル)という物がある。 特殊メソッドとはPython処理系とPythonコードとの間の プロトコル(決まり事)のこと。 例えばlen関数は引数のオブジェクトの長さを取得することができる。len関数内 部では渡されたオブジェクトの__len__メソッドを呼び出して長さを取得する。 つまり、自分で作ったオブジェクトだとしても__len__メソッドさえ定義していれば len関数に渡すとその長さを取得することができる。 ※ちなみに__len__は「だんだーれん」(dunder len)と呼ぶ(こともある)
43. Pythonの特殊メソッド/属性例 ほんの一例 __module__ __rsub__ __gt__ __getitem__ __class__ __mod__ __rgt__ __setitem__ __call__ __rmod__ __ge__ __delitem__ __new__ __mul__ __rge__ __getattribute__ __init__ __rmul__ __iter__ __getattr__ __name__ __neg__ __next__ __setattr__ __str__ __pos__ __index__ __hash__ __repr__ __invert__ __eq__ __contains__ __int__ __lt__ __bool__ __code__ __add__ __rlt__ __len__ __dict__ __radd__ __le__ __get__ __exit__ __sub__ __rle__ __set__ __enter__
44. ＿人人人人人＿ ＞　多い！　＜ ￣Y^Y^Y^Y^Y^￣
45. Pythonの__call__について 広義の意味で言えば__call__を持つオブジェクトは全て関数。(かなり暴論) __call__を持っているオブジェクトを呼び出す時には__call__を省略出来る。 functionクラスも__call__を持っている。lambdaの実体もfunction。 >>> class A: pass ... >>> x = A() >>> x <__main__.A object at 0x7fb829184c88> とした場合のA()はtypeクラスの__call__を呼んでいる。
46. typeクラスってなんだろう？ typeクラスから作られたオブジェクトがクラスである。 >>> a = 1 >>> type(a) <class 'int'> のように使うが、ここで呼び出しているのはtype.__call__メソッドである。 typeクラスの__call__は引数によって動作が変わる。 • 1つの場合はオブジェクトのtypeを返す。 • 3つの場合は新しいクラスを作成する。 以下の2つはまったく同じ結果となる。 >>> class A: b = 1 >>> A = type("A", (object,), dict(b = 1))
47. オブジェクトの生成 クラスからtypeクラスの__call__が呼ばれる際にどのようにオブ ジェクトが生成されていくのだろうか？cafebabepyで実際に行っ ている処理を説明する。 >>> class A(): >>> def __init__(self, x): >>> self.x = x の処理を例とする。
48. オブジェクトの生成フロー a = A(1) type.__call__ type.__new__ A.__init__ Aクラスのオブ ジェクト >>> a.x 1 Aクラスのスコープや継 承関係から__call__を探 す Aクラスのスコープや継承関係から __init__を探す Aクラスに__init__がなければ object.__init__が呼ばれる。 引数にクラスが渡ってくるので そのクラスのオブジェクトを生 成 __call__に渡っ てきた引数xを 渡す
49. Pythonの関数とメソッドについて(1) __get__はPythonでメソッドを作るときに重要な特殊メソッドであ る。これを理解することでメソッドの引数にselfを付ける意味がわ かる。 また、Python言語仕様の美しさがわかるだろう。 __get__はデスクリプタと呼ばれている。デスクリプタを詳細に説 明するとそれだけで終わってしまうので簡単に説明する。
50. Pythonの関数とメソッドについて(2) class A: def __get__(self, obj, type=None): print("Hello") とデスクリプタを定義するだけでは意味が無い。 class B: x = A() とすることにより >>> B.x Hello となる。つまり、他のクラスの属性にデスクリプタを設定すると、 クラスの特定の属性へのアクセスをカスタマイズすることができる。
51. Pythonの関数とメソッドについて(3) • クラスにdefで定義するものはメソッドではなく関数である。 • 関数はデスクリプタでもある。 • 関数(デスクリプタ)を属性としてクラスに定義することにより関数を参照 する時はデスクリプタとして扱われる。 関数のデスクリプタで行っていることは第一引数にレシーバーであるオブ ジェクトをバインドしたメソッドを作成する。 メソッドとは関数に対して参照元のオブジェクトを第一引数にバインドした関 数と言える。この第一引数にバインドしたオブジェクトこそがPythonのself の正体！ つまり、デスクリプタという仕組みを用意することで関数/メソッドを統一的に 扱える。
52. Pythonの関数とメソッドについて(4) >>> class T: ... def a(): pass ... >>> T.a # クラスから呼ぶとfunction <function T.a at 0x7fb827525e18> >>> tx = T() >>> tx.a # オブジェクトから呼ぶとmethod <bound method T.a of <__main__.T object at 0x7fb8275264e0>> >>> def x(self, a): ... print(self) ... print(a) >>> x.__get__(tx)(99) # デスクリプタなのでこんなこともできる <__main__.T object at 0x7fb8275265f8> 99
53. Pythonにおいて、メソッドの第一引数にself を明示的に書くことは関数とメソッドを統一 的に扱うためである。 そこが美しい！ ※個人の主観です
54. 言語処理系作成におけるComposability(1) >>> *range(10), の結果は何になるだろうか？ 答えは(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)となる。 *range(10)でイテレーターを展開した結果を元にtupleの本体であ るカンマからtupleを作っているらしい。 ※ちなみにtupleの本質は()ではなくカンマ。例(99,)や99, cafebabepyでは*range(10),に対して特殊な処理は行っていな い。 「*」でイテレーターを展開する処理、カンマでtupleを作成する処 理を作っただけである。その組み合わせがこの結果となっている。
55. 言語処理系作成におけるComposability(2) 言語処理系では小さな部品を作ってそれを組み合わせること によって大きな処理が出来るようになることが多い。 実装大変そうだ…と思った仕様を実装するためにすでに作っ てある小さな部品をちょっと組み合わせるだけで実現可能に なったりする。実装すら必要ない場合もある。 ここに言語処理系の面白さ、 そしてComposability(組立可能性)がある。
56. 今後の展望 • Python 3の文法/モジュールを全て実装 • 速度改善 ◦ invokedynamic命令等を使った高速化 ◦ リフレクションを極力少なく • PythonのコードからJavaのコードを実行 • C拡張の実行 ◦ NumPyとかSciPyがJavaから呼べると激アツでは？ ◦ JRubyで出来ていそうなので参考にできるかも？
57. まとめ 時間の都合上、まだまだ伝えきれない実装/言語仕様がいっぱい あります。その中から苦労して実装したもの、言語処理系を作って いく中で知ったPythonの美しさをピックアップしてみました。 言語処理系を作る作業は泥臭さとの戦いです。しかし自分で作っ た言語処理系で他人が書いたコードが動くこと、これが何より嬉し いことです。 最初に動いたモジュールはthis、皆さんご存じ「The Zen of Python」です。今でもその時の感動は忘れられません。今後もそ の初心を忘れず開発していきたいものですね。
58. 今後cafebabepyを 暖かく見守ってみて下さい！
59. ご静聴ありがとうございました！