# HG changeset patch # User Takahiro SHIMIZU # Date 1542602408 -32400 # Node ID 8e5e2521d1dba0e26a8b832318d0977071d3c554 # Parent 6f876697210cd68ce14c66a082ac6970389396f5 insert space after , diff -r 6f876697210c -r 8e5e2521d1db Paper/anatofuz.pdf Binary file Paper/anatofuz.pdf has changed diff -r 6f876697210c -r 8e5e2521d1db Paper/anatofuz.tex --- a/Paper/anatofuz.tex Mon Nov 19 13:28:46 2018 +0900 +++ b/Paper/anatofuz.tex Mon Nov 19 13:40:08 2018 +0900 @@ -74,7 +74,7 @@ Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため, 実用的な処理速度に達すれば, 言語の利用件数が向上することが期待される． その為本研究では, CbCを用いた言語処理系の実装の一例としてMoarVMをCbCで書き換えたCbCMoarVMを提案する． 本研究はCbCをスクリプト言語の実装に適応した場合, どのような利点やプログラミング上の問題点に遭遇するか, CbCの応用としての側面でも行う． -本稿ではまずCbC, Perl6の特徴及び現在の実装について述べ,本研究で行ったCbCで書き換えたMoarVMについてデバッグ手法も含め解説する. +本稿ではまずCbC, Perl6の特徴及び現在の実装について述べ, 本研究で行ったCbCで書き換えたMoarVMについてデバッグ手法も含め解説する. そして本研究で得られたCbCを言語処理系に適応した場合の利点と欠点について述べ, 今後の展望について記載する. \section{CbC} @@ -130,7 +130,7 @@ またCからCbCへの遷移時に, 再びCの関数に戻るように実装したい場合がある． その際は環境付きgotoと呼ばれる手法を取る．これは\_CbC\_return及び\_CbC\_environmentという変数を渡す． この変数は\_CbC\_returnが元の環境に戻る際に利用するCodeGearを指し, \_CbC\_environmentは復帰時に戻す元の環境である． -復帰する場合, 呼び出した位置には帰らず,呼び出した関数の終了する位置に帰る． +復帰する場合, 呼び出した位置には帰らず, 呼び出した関数の終了する位置に帰る． \lstinputlisting[label=cbcreturn, caption=環境付き継続の例]{./src/return.cbc} Code\ref{cbcreturn}に示す例ではc\_funcから環境付き継続でcgに継続している． 通常c\_funcの返り値は-1であるが, cgから環境付き継続でmainに帰る為にcgから渡される1がtestの値となる． @@ -170,9 +170,9 @@ RakudoがPerl6のコンパイラかつインタプリタであると考えても良い． Rakudoは図\ref{fig:perl6construction}に示す構成になっている． Rakudoにおけるコンパイラとは厳密には2種類存在する． -まず第1のものがPerl6, もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである． +まず第1のものがPerl6, もしくはNQPをMoarVM, JVMのバイトコードに変換するNQPコンパイラである． 次にそのNQPが出力したバイトコードをネイティブコードに変換するVMの2種類である． -このVMは現在MoarVM, JavaVM,JavaScriptを選択可能である． +このVMは現在MoarVM, JavaVM, JavaScriptを選択可能である． Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド, VMの部分をバックエンド\cite{rani1}と呼称している． NQPで主に書かれ, MoarVMなどNQPが動作する環境で動くPerl6のことをRakudoと呼ぶ． Perl6はNQP以外にものNQPを拡張したPerl6自身で書かれている箇所が存在し, これはNQPコンパイラ側でMoarVMが解釈可能な形へ変換を行う． @@ -187,7 +187,7 @@ \subsection{NQP} -RakudoにおけるNQP\cite{nqp}は現在MoarVM, JVM上で動作し,MoarVMを一部利用することでNodeJSからも動作させる事が可能である． +RakudoにおけるNQP\cite{nqp}は現在MoarVM, JVM上で動作し, MoarVMを一部利用することでNodeJSからも動作させる事が可能である． NQPはPerl6のサブセットであるため, 主な文法などはPerl6に準拠しているが幾つか異なる点が存在する． NQPは最終的にはNQP自身でブートストラップする言語であるが, ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする． このMoarVMByteCodeの状態をStage0と言い, ディレクトリ名として設定されている． @@ -213,7 +213,7 @@ NQPのビルドフローを図\ref{fig:nqpbuild}に示す． 実際にPerl6の処理系であるperl6を動かすためにはself buildしたNQPコンパイラが必要となる．その為にStage0を利用してStage1をビルドしNQPコンパイラを作成する． -Stage1は中間的な出力であり, 生成されたNQPファイルはStage2と同一であるが,MoarVMのバイトコードが異なる． +Stage1は中間的な出力であり, 生成されたNQPファイルはStage2と同一であるが, MoarVMのバイトコードが異なる． Perl6では完全なセルフコンパイルを実行したNQPが要求される為, Stage1を利用してもう一度ビルドを行いStage2を作成する． Perl6のテストスイートであるRoast\cite{roast}やドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている． @@ -223,8 +223,8 @@ \subsection{Rakudo Perl6} Rakudo実装上におけるPerl6はRakudo Perl6と呼ばれているGitリポジトリで管理されているプログラムのことである． 前述した通りRakudo Perl6はPerl6のサブセットであるNQPを用いて記述されている． -従ってyaccやlexと言ったPerl5の文字解析, 構文解析に利用していたプログラムは利用せず,NQP側で構文定義などを行っている． -NQPはNQP自身でBootstrappingされている為, Rakudo Perl6のbuild時にはNQPの実行環境として要したVM,それに基づいてbuildしたNQPがそれぞれ必要となる． +従ってyaccやlexと言ったPerl5の文字解析, 構文解析に利用していたプログラムは利用せず, NQP側で構文定義などを行っている． +NQPはNQP自身でBootstrappingされている為, Rakudo Perl6のbuild時にはNQPの実行環境として要したVM, それに基づいてbuildしたNQPがそれぞれ必要となる． 言語的な特徴としては独自にPerl6の文法を拡張可能なGrammar, Perl5と比較した場合のオブジェクト指向言語としての進化も見られる． またPerl6は漸進的型付け言語である. @@ -307,16 +307,16 @@ \subsection{MoarVMのバイトコードのディスパッチ} MoarVMのバイトコードインタプリタはsrc/core/interp.cで定義されている． この中の関数MVM\_interp\_runで命令に応じた処理を実行する． -関数内では命令列が保存されているcur\_op, 現在と次の命令を指し示すop,Threadの環境が保存されているThreadcontextなどの変数を利用する． +関数内では命令列が保存されているcur\_op, 現在と次の命令を指し示すop, Threadの環境が保存されているThreadcontextなどの変数を利用する． 命令実行は大きく二種類の動作があり, Cのgotoが利用できる場合はCode\ref{orig_macro}に示すMVM\_CGOTOフラグが立ちラベル遷移を利用する． それ以外の場合は巨大なcase文として命令を実行する． -ラベル遷移を利用する場合はCode\ref{oplabelsh}に示すラベルテーブルLABELSにアクセスし, テーブルに登録されているアドレスを取得し,マクロNEXTで遷移する． +ラベル遷移を利用する場合はCode\ref{oplabelsh}に示すラベルテーブルLABELSにアクセスし, テーブルに登録されているアドレスを取得し, マクロNEXTで遷移する． Code\ref{cbc_dispatch_c}に示すno\_opは何もせず次の命令に移動する為, goto NEXT;のみ記述されている． このラベルテーブルの中身はラベルが変換されたアドレスであるため, 実際に呼ばれている命令コードの名前はデバッガレベルでは確認できない． Cレベルでのデバッグ時にはアドレスと実際に呼ばれる箇所を確認する事に手間がかかる． -巨大なcase文として実行された場合, 実行時間が遅いだけでなく,ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する． +巨大なcase文として実行された場合, 実行時間が遅いだけでなく, ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する． \lstinputlisting[label=oplabelsh, caption=ラベルテーブルの一部分]{./src/oplabels.h} @@ -325,7 +325,7 @@ \lstinputlisting[label=dispatch_c, caption=オリジナル版MoarVMのバイトコードディスパッチ]{./src/dispatch.c} interp.cでは命令コードのディスパッチはマクロを利用したcur\_opの計算及びラベルの遷移, もしくはマクロDISPATCHが展開するswitch文で行われていた． -CbCMoarVMではこの問題を解決するために, それぞれの命令に対応するCodeGearを作成し,CodeGear名前を要素として持つCbCのCodeGearのテーブルを作成した． +CbCMoarVMではこの問題を解決するために, それぞれの命令に対応するCodeGearを作成し, CodeGear名前を要素として持つCbCのCodeGearのテーブルを作成した． このCodeGearのテーブルを参照するCodeGearはcbc\_nextであり, この中のマクロNEXTはinterp.cのマクロNEXTをCbC用に書き直したものである． \lstinputlisting[label=cbc_dispatch_c, caption=CbCMoarVMのバイトコードディスパッチ]{./src/cbc-interp-next.cbc} @@ -386,7 +386,7 @@ またcbc\_pushcompscではMVMROOTに局所変数scを渡している為, これをstaticで宣言し直している． 現在CbCで記述されたOSであるGearsOSにはInterfaceが導入されている． -これはJavaのinterface, Haskellの型クラスに該当する概念であり,次のCodeGearにInterface経由で継続する事が可能である． +これはJavaのinterface, Haskellの型クラスに該当する概念であり, 次のCodeGearにInterface経由で継続する事が可能である． Interfaceは現在のMoarVMには実装されていない為, 今後ThreadeCodeの実装を行うにあたり導入を検討している． \section{MoarVMのデバッグ} @@ -422,11 +422,11 @@ \lstinputlisting[label=debug_cbcmoar, caption=CbCMoarVMのバイトコードのトレース]{./src/trace_cbc.txt} オリジナル版では実際に実行する命令処理はラベルに変換されてしまう為名前をデバッガ上では出力できないが, CbCでは出力する事が可能である． -CbCとオリジナルのCODES, LABELの添字は対応している為,ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する． +CbCとオリジナルのCODES, LABELの添字は対応している為, ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する． これらはscriptコマンドが作成したログを元に異なる箇所を発見するスクリプトを用意し自動化する．(Code \ref{logs2}) \lstinputlisting[label=logs2, caption=バイトコードの差分検知の一部分]{./src/logs2.txt} -違いが生じている箇所が発見できた場合, その前後のCodeGear及びディスパッチ部分にbreak pointをかけ,それぞれの変数の挙動を比較する． +違いが生じている箇所が発見できた場合, その前後のCodeGear及びディスパッチ部分にbreak pointをかけ, それぞれの変数の挙動を比較する． 主にcbc\_return系の命令が実行されている場合は, その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが,この周辺で何かしらの違いが発生している可能性が高い． また主に次のCodeGearに遷移する際にCbCコンパイラのバグが生じている可能性もある為, アセンブラレベルの命令を確認しながらデバッグを進めることとなる． @@ -439,8 +439,8 @@ \subsection{CbCコンパイラによるバグ} これまでのCbCに関する研究においては, 複数個の入出力をCodeGearに与えるユースケースで利用していた． -CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの, MoarVMの様な巨大なプロジェクトのCodeGearをコンパイルを実行する場合,予期せぬバグが発生した． -主にCodeGear間のgotoにおけるtail callフラグの除去や, DataGearとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい,通常のCの関数をcallした際にローカル変数の領域がDataGearのアドレスの周辺を利用してしまう． +CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの, MoarVMの様な巨大なプロジェクトのCodeGearをコンパイルを実行する場合, 予期せぬバグが発生した． +主にCodeGear間のgotoにおけるtail callフラグの除去や, DataGearとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい, 通常のCの関数をcallした際にローカル変数の領域がDataGearのアドレスの周辺を利用してしまう． その為DataGearの構造体の値が書き換わり, CからDataGearにreturnした際にDataGearの構造体が破壊されるバグである． このバグは先程の並列デバッグを行いながらプログラムカウンタや変数の動きをトレースする事などで発見することが出来る． 現状ではCbCコンパイラがプログラマの意図と反する挙動を取るためCbCコンパイラのバグを回避するプログラミングが要求されている． @@ -469,7 +469,7 @@ 従ってCodeGear内部の処理を別の箇所から使用する事も可能となる為再利用性も向上する． -ThrededCodeを実装する場合, 通常命令ディスパッチの箇所と,実際に実行される命令処理を大幅に変更しなければならない． +ThrededCodeを実装する場合, 通常命令ディスパッチの箇所と, 実際に実行される命令処理を大幅に変更しなければならない． CbCを用いた実装の場合, 命令処理はただのCodeGearの集合である． その為CodeGearをThrededCodeに対応した並びとして選択する事ができれば命令処理部分の修正をほぼせずにThrededCodeを実現する事が可能である． @@ -481,10 +481,10 @@ その為, 直接ラベルにbreak pointをかける事が出来ない． 作業者がデバッガが読み込んでいるCソースコードの位置を把握し, 行番号を指定してdebug pointを設定する必要があった． -CbCMoarVMの場合, CodeGear単位でバイトコードの処理単位を記述している為,通常の関数と同じく直接CodeGearにデバッグポイントをかける事が可能である． +CbCMoarVMの場合, CodeGear単位でバイトコードの処理単位を記述している為, 通常の関数と同じく直接CodeGearにデバッグポイントをかける事が可能である． これはCプログラミングの関数に対してのデバッグで, 状態ごとにbreak pointをかける事が出来ることを意味する． 通常のC言語で言語処理系を実装した場合と比較して扱いやすくなっていると言える． -さらにラベルテーブルでの管理の場合, 次のバイトコード箇所は数値でしか確認できず,実際にどこに飛ぶのかはラベルテーブル内と数値を作業者が手作業で確認する必要があった． +さらにラベルテーブルでの管理の場合, 次のバイトコード箇所は数値でしか確認できず, 実際にどこに飛ぶのかはラベルテーブル内と数値を作業者が手作業で確認する必要があった． スクリプトなどを組めば効率化は出来るがデバッガ上で完結しない為手間がかかる． CbC実装ではCODESテーブル内は次のCodeGearの名前が入っている為, 数値からCodeGearの名前をデバッガ上で確認する事が出来る ． @@ -510,7 +510,7 @@ CbCコンパイラはgccとllvm/clangに実装している為, これらのアップデートに追従する必要がある． しかしコンパイラのバージョンに応じてCbCで利用するコンパイラ内のAPIが異なる場合が多く, APIの変更に伴う修正作業などを行う必要がある． -CbCMoarVMではCからCodeGearへ, CodeGearからCへの遷移などが複数回繰り返されているが,この処理中のCodeGearでのtail callの強制が非常に難関である． +CbCMoarVMではCからCodeGearへ, CodeGearからCへの遷移などが複数回繰り返されているが, この処理中のCodeGearでのtail callの強制が非常に難関である． tail callの強制には関数定義の箇所や引数, スタック領域のサイズ修正などを行う必要がある． 現在のバグではCodeGear内部での不要なスタック操作命令を完全に排除しきれていない． @@ -579,7 +579,7 @@ GCの制御を効率的に行えば本来は必要ない処理であり, 実行するとCodeGearの優位性が損なわれてしまう． 従ってMoarVMのGCの最適化を行う． -また高速化という面では, Perlの特徴である正規表現に着目し,正規表現の表現のみ高速で動く最適化の導入なども検討している． +また高速化という面では, Perlの特徴である正規表現に着目し, 正規表現の表現のみ高速で動く最適化の導入なども検討している． 他にrakudoのコンパイラ系統からCbCのコードを直接生成させ, それをllvmでコンパイルすることによってLLVMの最適化フェーズを得て 高速化することも可能であると推測できる．