Mercurial > hg > Events > OSC2019
view slide.md @ 18:1fc9d0bd924f default tip
update
| author | anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 20 Apr 2019 18:06:35 +0900 |
| parents | a176ea5c0264 |
| children |
line wrap: on
line source
title: Perl6の内部表現 author: Takahiro Shimizu profile: lang: Japanese ## このセッションの内容 - Perl6の主要な実装であるRakudoの内部構造を探ります - Rakudoの内部で利用されているVMや， Perl6のサブセットなどについて探索します - スクリプト言語で主に使われているバイトコードインタプリタの気持ちになります ## 内容 - Perl6とは? - スクリプト言語処理系の動き - Perl6の内部構造 - NQP - MoarVM - NQPとMoarVMのバイトコード対応 - バイトコードインタプリタのC言語実装 - MoarVMの詳細 - MoarVMのバイトコード実行 - まとめ ## Perl6とは - 当初Perl5の時期バージョンとして開発されていたプログラミング言語 - 現在は別の言語として開発がそれぞれ進んでいる - 仕様と実装が分離しており， 現在はテストが仕様となっている - 実装は歴史上複数存在しているが，主流な実装はRakudo - Haskellで実装されたPugs - Pythonとの共同基板を目指したParrot - 言語的にはスクリプト言語であり， 漸進的型付き言語 - 動作環境は、独自のVMのMoarVM, JVM、一部JavaScript上で動作する <img src="fig/2000px-Camelia.svg.png" alt="" style="width: 31%; height: auto;"> ## 現在のPerl6 - 現在のバージョンは `6.d` - [ブラウザ上で実行可能な環境](https://perl6.github.io/6pad/)が存在する - [IDE](https://commaide.com/)が開発されている - WebApplicationFrameworkなども開発されており、 Perl5のモジュールを移行したものがいくつか存在する - 日本では趣味のプロダクト以外社会では使用されていない - 海外では実際に使われているケースも存在する - 処理速度では一部Perl5に勝っているが、それでも大分遅い ## [参考]Perl5のソースコード - Perl5時代 − スカラ、配列、ハッシュの3種類 - それぞれの変数への参照であるリファレンスが使用可能 ```perl use ustrict; use warnings; my $scalar_value = "hello!"; print "$scalar_value\n"; my @array = (1..10); print "$array[0]\n"; my %hash = ( this_is_key => "this_is_value"); print "$hash{this_is_key}\n"; my $hash_ref = \%hash; print "$hash_ref->{this_is_key}\n"; ``` ## Perl6のソースコード概要 - Perl5の文法とは比較的変更が多い - 雰囲気は似ている - 変数がオブジェクトと化した事により， 変数からsayメソッドを呼ぶことが可能 ``` my $str_value = 'hello world!'; $str_value.say; # hello world! ``` - Perl5と同様に，変数にはデフォルトでは型がないような振る舞いをする ``` my $sample_value = 'hello world!'; $sample_value.say; # hello world! $sample_value = '31'; $sample_value.say; # 31 say($sample_value * 3); ``` ## Perl6の言語的な特徴 - 漸進的型付き言語である為， 型を強制することも可能となる ``` my Int $int_value = 31; $int_value = "hello"; # Compile error! ``` ``` $ perl6 type_invalid.p6 Type check failed in assignment to $int_value; expected Int but got Str ("hello") in block <unit> at type_invalid.p6 line 4 ``` ## Perl6の言語的な特徴 - 型を独自に定義することも可能 - 入力の型によって実行する関数を変える事などができる ```perl6 my subset Fizz of Int where * %% 3; my subset Buzz of Int where * %% 5; my subset FizzBuzz of Int where Fizz&Buzz; my subset Number of Int where none Fizz|Buzz; proto sub fizzbuzz ($) { * } multi sub fizzbuzz (FizzBuzz) { "FuzzBuzz" } multi sub fizzbuzz (Fizz) { "Fizz" } multi sub fizzbuzz (Buzz) { "Buzz" } multi sub fizzbuzz (Number $number) { $number } fizzbuzz($_).say for 1..15; ``` - 型を利用したFizzBuzz ## スクリプト言語 - Perl6は現状コンパイルすることはできない - スクリプト言語の分類 - 現在広く使われているスクリプト言語(Perl,Python,Ruby...)などとPerl6の構成は類似している - 今回はPerl6の実装を追いながら、最近のスクリプト言語処理系の大まかな実装を理解する ## スクリプト言語処理系 - スクリプト言語は入力として与えられたソースコードを、 直接評価せずにバイトコードにコンパイルする形式が主流となっている - その為スクリプト言語の実装は大きく2つで構成されている - バイトコードに変換するフロントエンド部分 - バイトコードを解釈する仮想機械 <img src="fig/bytecode_sample_generally_lang.svg" width="80%"> ## Perl6以外のスクリプト言語 - 現在使われているプロセスVMは言語に組み込まれているものが多い - JVMやElixirなどのVMは複数の言語で使用されている - Java - JVM - Ruby - YARV - Python - PythonVM - Erlang - Elixir - BEAM ## Perl6の処理系の構成 - Perl6の処理系で現在主流なものはRakudoと呼ばれる実装である(歴史上複数存在する) - Rakudoは3つのレイヤーから構成されている - Perl6インタプリタ - Perl6インタプリタを記述するPerl6のサブセットNQP - Perl6のバイトコードを解釈するMoarVM - Perl6/NQPがフロントエンドに相当し、MoarVMがバックエンドに相当する ## Rakudoの構成図  (http://brrt-to-the-future.blogspot.com/2015/03/advancing-jit-compiler.html) ## Perl6とNQP - NQP(NotQuitPerl Perl) - Perl6のサブセット。Perl6っぽい言語 - Perl6、 NQP自体がNQPで記述されている - NQPもNQPで記述されている為、 セルフビルド(自分自身で自分自身をコンパイルする)を行う - NQPはPerl6の文法をベースにしているが、 制約がいくつか存在する - 元々はPerl6の主力実装がParrotだった時代に登場 - 文法がアップデートされており、当時の資料は古くなっている ``` my $value := "hello!"; say($value); ``` ## NQPスクリプト - 変数は束縛 `:=` を使う − 関数の間に空白を入れてはいけない - 再帰呼び出しを使うフィボナッチ数列 ``` #! nqp sub fib($n) { $n < 2 ?? $n !! fib($n-1) + fib($n - 2); } my $N := 29; my $z := fib($N); nqp::say("fib($N) = " ~ fib($N)); ``` ## NQPスクリプト(nまでの整数の和) ```perl6 sub add_test($n){ my $sum := 0; while ( $n > 1) { $sum := $sum + $n; --$n; } return $sum; } say(add_test(10000)); ``` ## NQP - NQPはPerl6の中で一番レイヤーが低い言語 - その為、 実行するVMのオペコード(処理単位)を使用することができる - NQPオペコードは、 Perl6の内部の抽象構文木でも使用されている - また、 Perl6と同様に型を指定することが可能 ```perl6 sub add_test(int $n){ mu $sum := 0; while nqp::isgt_i($n,1) { $sum := nqp::add_i($sum,$n); $n := nqp::sub_i($n,1); } return $sum; } ``` ## NQPとMoarVM - NQPは実行する際にMoarVM/JVMが必要となる - NQPコンパイラが各VMに対応したバイトコードに変換する - MoarVMの場合は、MoarVMのバイナリ moar に、 NQPのインタプリタのバイトコードをライブラリや入力として与える ## Perl6のVM - MoarVM, JVM , JavaScriptが選択可能 - メインで開発されているのはMoarVMであり、 他のVMは機能が実装されていないものが存在する - `rakudo-star` というPerl6のパッケージ環境では、 MoarVMがデフォルトでインストールされる ## MoarVM - Metamodel On A Runtime - C言語で記述されているPerl6専用の仮想機械 - レジスタマシン - 型情報を持つレジスタに対しての演算として処理される - Rubyなどはスタックマシンとして実装されている - Unicodeのサポートや、LuaJITなどを利用したJITコンパイルなども可能 - Perl6やNQPは、MoarVMに対してライブラリなどを設定して起動する ## バイトコード - Perl6も、Rakudo/NQPはバイトコードに変換され、 バイトコードをVMが実行する - Perl6/NQPはバイトコードにコンパイルすることが可能 - 直接実行することはできない ``` $nqp --target=mbc --output=fib.moarvm fib.nqp ``` ## バイトコード - バイナリ形式で表現される為、 VMがどのように読み取るかでバイトコードの意味が異なる - スクリプト言語系のVMは、 VMという名前の通り、 計算機をエミュレートしている - その為、通常のCPUのストア命令などに相当する命令が実装されている - スクリプト言語は、その命令の実行を繰り返すことでプログラムを評価する - スクリプト言語で重要なバイトコード表現は、「仮想機械がどの命令を実行するか」のバイトコード - CPUに対するアセンブラの数値に対応する - どういった構成なのかは仮想機械によって異なる ## バイトコードとMoarVM - MoarVMバイトコードはMoarVMの実行バイナリ `moar` でディスアセンブルすることが可能 ``` annotation: add_test.nqp:1 00003 const_i64_16 loc_2_int, 0 00004 hllboxtype_i loc_3_obj 00005 box_i loc_3_obj, loc_2_int, loc_3_obj 00006 set loc_1_obj, loc_3_obj label_1: 00007 decont loc_3_obj, loc_0_obj 00008 smrt_numify loc_4_num, loc_3_obj 00009 const_i64_16 loc_2_int, 1 00010 coerce_in loc_5_num, loc_2_int 00011 gt_n loc_2_int, loc_4_num, loc_5_num 00012 unless_i loc_2_int, label_2(00031) 00013 osrpoint annotation: add_test.nqp:3 00014 decont loc_3_obj, loc_1_obj 00015 smrt_numify loc_5_num, loc_3_obj 00016 decont loc_3_obj, loc_0_obj 00017 smrt_numify loc_4_num, loc_3_obj 00018 add_n loc_4_num, loc_5_num, loc_4_num 00019 hllboxtype_n loc_3_obj 00020 box_n loc_3_obj, loc_4_num, loc_3_obj 00021 set loc_1_obj, loc_3_obj 00022 decont loc_3_obj, loc_0_obj 00023 smrt_numify loc_4_num, loc_3_obj 00024 coerce_ni loc_6_int, loc_4_num 00025 const_i64_16 loc_7_int, 1 00026 sub_i loc_7_int, loc_6_int, loc_7_int 00027 hllboxtype_i loc_3_obj 00028 box_i loc_3_obj, loc_7_int, loc_3_obj 00029 set loc_0_obj, loc_3_obj 00030 goto label_1(00007) ``` ## NQPとバイトコードの対応 ``` say(add_test(10000)); ``` ``` annotation: add_test.nqp:1 label_1: 00020 getlex_no loc_7_obj, '&say' 00021 decont loc_7_obj, loc_7_obj 00022 const_s loc_3_str, '&add_test' 00023 getlexstatic_o loc_8_obj, loc_3_str 00024 decont loc_8_obj, loc_8_obj 00025 const_i64_16 loc_5_int, 10000 00026 prepargs Callsite_1 00027 arg_i 0, loc_5_int 00028 invoke_o loc_8_obj, loc_8_obj 00029 prepargs Callsite_0 00030 arg_o 0, loc_8_obj 00031 invoke_v loc_7_obj 00032 null loc_7_obj 00033 return_o loc_7_obj ``` - Perl6の変数は直接実態を参照せず、中身が入っているコンテナを参照するようになっている。 - その為 `decont` 命令で、コンテナの中身をレジスタに設定する必要がある - `const_i64_16` などは64bitの数という意味で、 `int` 型としてレジスタに登録している - `prepargs` で引数の確認を行い, `invoke_o` で実際にサブルーチンに移行する ## NQPとバイトコードの対応 ``` my $sum := 0; ``` ``` annotation: add_test.nqp:1 00003 const_i64_16 loc_2_int, 0 00004 hllboxtype_i loc_3_obj 00005 box_i loc_3_obj, loc_2_int, loc_3_obj 00006 set loc_1_obj, loc_3_obj ``` - まず `loc_2` レジスタをint型の整数0で初期化する - 変数 `$sum` はint型の指定がないので、 obj型で登録しなければならない - その為, 整数として登録された `loc_2` から、 obj型に一旦キャストし、 `loc_3` レジスタに設定したものを、 `loc_1` レジスタに設定する ## NQPとバイトコードの対応 ``` while ( $n > 1) { ``` ``` label_1: 00007 decont loc_3_obj, loc_0_obj 00008 smrt_numify loc_4_num, loc_3_obj 00009 const_i64_16 loc_2_int, 1 00010 coerce_in loc_5_num, loc_2_int 00011 gt_n loc_2_int, loc_4_num, loc_5_num 00012 unless_i loc_2_int, label_2(00031) 00013 osrpoint ``` − 比較にもint型の指定がない為、 `num` 型にキャストし、 `num` 型のレジスタでの大小を比較する - 比較命令は `gt_n` であり、 結果により `unless_i` 命令で、別のラベルにジャンプする ## decode命令 ``` while ( $n > 1) { ``` ``` 00007 decont loc_3_obj, loc_0_obj ```  - 変数 `$n` と 整数 `1` を大小比較する為、 まず `$n` から値を取り出す - とりだした時点では、何の型で使うかは決定していない為、 obj型として判定する ## smrt_nomify ``` while ( $n > 1) { ``` ``` 00008 smrt_numify loc_4_num, loc_3_obj ``` - `smrt_numify` はレジスタ上のオブジェクトを、 num型に変換し、 別のレジスタに登録する命令 - 今回の整数の比較では、 int型の強制がない為、 数値として比較するためにn64型にキャストしている - numはn64型であり、 64ビットの浮動小数点定数の意味  ## const_i64_16とcoerece_in ``` while ( $n > 1) { ``` ``` 00009 const_i64_16 loc_2_int, 1 00010 coerce_in loc_5_num, loc_2_int ``` - 64ビット整数として1をレジスタ `loc_2` に設定する - その後、 numでの比較のためにキャストし, `loc_5` レジスタに設定している ## 比較とif文の判定 ``` while ( $n > 1) { ``` ``` 00011 gt_n loc_2_int, loc_4_num, loc_5_num 00012 unless_i loc_2_int, label_2(00031) ``` - `gt_n` で `loc_4` (nが入っている) レジスタと `loc_5` (1が入っているレジスタ)を比較する - 結果により `loc_2` レジスタに真偽値がint型で代入される - その結果を `unless_i` で読み取り、 値が偽であったら `label_2(00031)` にジャンプする ## C言語での実装へ - 今まではスクリプトレベルでの実装を見てきました − スクリプトが実行されるVMの実装をCレベルで見ていきましょう ## MoarVMのバイトコードインタプリタ部分 MoarVMなどの言語処理系のバイトコードインタプリタは次のことを繰り返している 1. 入力されたバイトコード列から命令に対応する部分を読み取る 2. 読み込んだ数値から、 対応する命令を取得する 3. 命令部分を実行する 4. バイトコード列を次に進め、繰り返す - この部分の実装は大体次のようなパターンで記述されている ## 巨大なswitch文を使うケース - 命令に対応するバイトコードを数値に変換できるようにし、 switch-case文で分岐させる - 実行のたびにループで先頭に戻り、次の命令を計算する必要があるので低速 ``` while( pc != NULL) { switch(pc){ case ADD_INSTRUCTION: // instruction.... break; case SUBD_INSTRUCTION: // instruction.... break; } } ``` ## Cコンパイラのラベルgotoを使うケース - 巨大なcase文とループではなく、 次の命令の実行場所に直接jmpで移動する - GCC拡張でサポートしている場合「`&&ラベル名` 」でラベルのアドレスが取得できる - 取得したアドレスに対して「goto アドレス」でgoto文でjmpする - 次の命令に対応するラベルを取得する必要があるが、 ループする必要がなく高速 - ラベルgotoであり、 Cコンパイラの拡張機能として搭載されている - gccおよびLLVM/clangには実装されている ``` static const void *CODES[] = {&&ADD_INSTRUCTION, &&SUB_INSTRCUTION}; goto *CODES[pc]; ADD_INSTRUCTION: // instruction... pc++; goto *CODES[pc]; SUB_INSTRUCTION: // instruction... pc++; goto *CODES[pc]; ``` ## MoarVMでは - ラベルgotoが利用できる場合は利用する - 使えないコンパイラの場合は、 switch文を利用する - この判断はマクロで処理をしている − 一般的にはラベルgotoの方が高速である為、他のスクリプト言語でもラベルgotoが使われている ## MoarVMのC言語での実装 - [GitHub上にリポジトリ](https://github.com/MoarVM/MoarVM)がある - `src/core/interp.c` がバイトコードインタプリタの実装コード - この中でマクロを使いつつ、 バイトコードに対応した命令を処理している - `MVM_interp_run`が実際にバイトコードを解釈している ``` /* This is the interpreter run loop. We have one of these per thread. */ void MVM_interp_run(MVMThreadContext *tc, void (*initial_invoke)(MVMThreadContext *, void *), void *invoke_data) { #if MVM_CGOTO #include "oplabels.h" #endif /* Points to the place in the bytecode right after the current opcode. */ /* See the NEXT_OP macro for making sense of this */ MVMuint8 *cur_op = NULL; /* The current frame's bytecode start. */ MVMuint8 *bytecode_start = NULL; /* Points to the base of the current register set for the frame we * are presently in. */ MVMRegister *reg_base = NULL; /* Points to the current compilation unit. */ MVMCompUnit *cu = NULL; /* The current call site we're constructing. */ MVMCallsite *cur_callsite = NULL; /* Stash addresses of current op, register base and SC deref base * in the TC; this will be used by anything that needs to switch * the current place we're interpreting. */ tc->interp_cur_op = &cur_op; tc->interp_bytecode_start = &bytecode_start; tc->interp_reg_base = ®_base; tc->interp_cu = &cu; /* With everything set up, do the initial invocation (exactly what this does * varies depending on if this is starting a new thread or is the top-level * program entry point). */ initial_invoke(tc, invoke_data); ``` ## MoarVMのレジスタ構成 - レジスタはそれぞれの型を共用体のデータ構造で持っている - 型名は各命令の接尾辞に対応している ``` /* Different views of a register. */ union MVMRegister { MVMObject *o; MVMString *s; MVMint8 i8; MVMuint8 u8; MVMint16 i16; MVMuint16 u16; MVMint32 i32; MVMuint32 u32; MVMint64 i64; MVMuint64 u64; MVMnum32 n32; MVMnum64 n64; }; ``` ## MVM_interp_runの登場人物 - `cur_op` が読み取るのバイトコード列の先頭ポインタを保存している - `op` が現在実行する命令の数値が入っている - `reg_base` がMoarVMのレジスタの集合配列 ``` /* Points to the place in the bytecode right after the current opcode. */ /* See the NEXT_OP macro for making sense of this */ MVMuint8 *cur_op = NULL; /* The current frame's bytecode start. */ MVMuint8 *bytecode_start = NULL; /* Points to the base of the current register set for the frame we * are presently in. */ MVMRegister *reg_base = NULL; ``` ## MVM_interp_runメインループ - `runloop`がメインのループで処理を行っている - `DISPATCH`部分で命令をバイトコード列から取り出している ``` /* Enter runloop. */ runloop: { MVMuint16 op; #if MVM_TRACING if (tracing_enabled) { char *trace_line; trace_line = MVM_exception_backtrace_line(tc, tc->cur_frame, 0, cur_op); fprintf(stderr, "Op %d%s\n", (int)*((MVMuint16 *)cur_op), trace_line); /* slow tracing is slow. Feel free to speed it. */ MVM_free(trace_line); } #endif /* The ops should be in the same order here as in the oplist file, so * the compiler can can optimise the switch properly. To check if they * are in the same order as the oplist use the * tools/compare-oplist-interp-order.sh helper script. */ DISPATCH(NEXT_OP) { OP(no_op): goto NEXT; OP(const_i8): OP(const_i16): OP(const_i32): MVM_exception_throw_adhoc(tc, "const_iX NYI"); OP(const_i64): GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2); cur_op += 10; goto NEXT; ``` ## MVM_interp_runメインループ - `DISPATCH`はマクロになっている - ラベルgotoが使えるケースはDISPATCHは何も意味を持たない - 使えない場合はswitch文に展開される - `op` に実行する命令の数値が格納されているので、 これに応じてswitchで飛ぶ ``` #if MVM_CGOTO #define DISPATCH(op) #define OP(name) OP_ ## name #define NEXT *LABELS[NEXT_OP] #else #define DISPATCH(op) switch (op) #define OP(name) case MVM_OP_ ## name #define NEXT runloop #endif ``` ## MVM_interp_runメインループ - `OP` が命令のスコープを切るマクロとなっている - gotoが使える場合 - `##name` に展開され、 それぞれの命令の名前を持つラベルになる - gotoが使えない場合 - case文に展開される ``` #if MVM_CGOTO #define DISPATCH(op) #define OP(name) OP_ ## name #define NEXT *LABELS[NEXT_OP] #else #define DISPATCH(op) switch (op) #define OP(name) case MVM_OP_ ## name #define NEXT runloop #endif ``` ## MVM_interp_runメインループ - 次の命令には `NEXT` マクロで移動する - gotoが使える場合 - 次のラベルに対応したアドレスを配列LABELSから取り出しgotoする - gotoが使えない場合 - `runloop`に対してgotoする(先頭へのループ) ``` #if MVM_CGOTO #define DISPATCH(op) #define OP(name) OP_ ## name #define NEXT *LABELS[NEXT_OP] #else #define DISPATCH(op) switch (op) #define OP(name) case MVM_OP_ ## name #define NEXT runloop #endif ``` ## それぞれの命令の実装 - マクロ `GET_REG` でレジスタ情報を取得する - 末尾で型を指定する - よしなに処理をした後に、バイトコード列 `cur_op` をインクリメントする - 計算機のプログラムカウンタを進めることに対応する ``` OP(add_i): GET_REG(cur_op, 0).i64 = GET_REG(cur_op, 2).i64 + GET_REG(cur_op, 4).i64; cur_op += 6; goto NEXT; OP(sub_i): GET_REG(cur_op, 0).i64 = GET_REG(cur_op, 2).i64 - GET_REG(cur_op, 4).i64; cur_op += 6; goto NEXT; OP(mul_i): GET_REG(cur_op, 0).i64 = GET_REG(cur_op, 2).i64 * GET_REG(cur_op, 4).i64; cur_op += 6; goto NEXT; ``` ## 本日の展示について - 現在当研究室で開発しているContinuationBasedC(CbC)で一部Perl6の処理系を書いています - また、 CbCを用いたGearsOSの展示も行っています ## まとめ - Perl6の内部構造に迫りました - スクリプト言語の中身も通常の計算機と同じような処理をしています - OSSなので皆さん読んで改造してみましょう!!