Papers/2019/anatofuz-prosym: Paper/anatofuz.tex comparison

comparison Paper/anatofuz.tex @ 24:d8f77d0a3452

update environemt return and bib

author	Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
date	Thu, 08 Nov 2018 23:16:52 +0900
parents	7689b70a1a79
children	7a2d604607d8

comparison

equal deleted inserted replaced

-:7689b70a1a79
+:d8f77d0a3452
 Perl6は設計と実装が区分されており様々な処理系が開発されている．現在主流なPerl6はRakudoと言われるプロジェクトである．
 RakudoではPerl6自体をNQP(NotQuitPerl)と言われるPerl6のサブセットで記述し,NQPをVMが解釈するという処理流れになっている．
 このVMは任意のVMが選択できるようになっており，現在はMoarVM,JavaVM,Javascriptが動作環境として選択可能である．
 主に利用されているVMにCで書かれたMoarVMが存在する．
 MoarVMはJITコンパイルなどをサポートしているが，全体的な起動時間及び処理速度がPerl5と比較し非常に低速である．
-この問題を解決するためにContinuation based C (CbC)という言語を一部用いる．
+この問題を解決するためにContinuation based C (CbC)という言語を一部用いてMoarVMの書き換えを行う．
-本論文ではCbCを用いてMoarVMの一部を書き換える事を検討し，得られた知見についてに述べる．
+本論文ではCbCを用いたMoarVMの書き換えを検討し，得られた知見について述べる．
 \end{abstract}
 \begin{jkeyword}
 Rakudoとして主に使われている処理系はMoarVMであるが,MoarVMの処理時間がPerl5などの多くのスクリプト言語と比較し非常に低速である．
 その為現在日本国内ではPerl6を実務として利用するケースは概ね存在しない．
 Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため実用的な処理速度に達すれば言語の利用件数が向上することが期待される．
 この問題を解決するために現在当研究室で開発しているContinuation Based C(以下CbC)を用いて改良を行う．
 CbCはCよりさらにきめ細やかな記述が可能であるためスクリプト言語などのプログラミング言語の記述と親和性が高い事が推測される．
-故に本研究はCbCをスクリプト言語の実装に適応した場合，どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う．
+本研究はCbCをスクリプト言語の実装に適応した場合，どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う．
 本稿ではまずCbC,Perl6の特徴及び現在の実装について述べ，次に改良を行うMoarVMの一連の処理流れについて述べる．
 そして今回改良した一部分と今後の展開について記す．
 \section{CbC}
 \subsection{CbCの概要}
 CbCは当研究室で開発しているプログラミング言語である．
-Cレベルでのプログラミングを行う場合，本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどが存在する．
+Cレベルでのプログラミングを行う場合，本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどを記述する必要がある．
-これらをmeta computationと呼ぶ．これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる．
+これらの処理をmeta computationと呼ぶ．これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる．
-しかしC言語などを用いたプログラミングで分離を行おうとすると，それぞれ事細かに関数やクラスを分割せねばならず容易ではない．
+しかしC言語などを用いたプログラミングでmeta computationの分離を行おうとすると，それぞれ事細かに関数やクラスを分割せねばならず容易ではない．
 CbCでは関数よりmeta computationを細かく記述する為にCodeSegmentという単位を導入した．
 またCodeSegmentの実行に必要なデータをDataSegmentという単位で受け渡す．
 CbCではCodeSegment,DetaSegmentを基本単位として記述するプログラミングスタイルを取る．
 \subsection{CodeSegmentとDataSegment}
 \subsection{軽量継続}
 %TBD
 CbCでは次のCodeSegmentに移行する際，Cのgoto文を利用する．
 通常のCの関数呼び出しの場合，スタックポインタを操作しローカル変数などをスタックに保存する．
 CbCの場合スタックフレームを操作せず，レジスタの値を変更せずそのまま次のCodeSegmentに遷移する事が可能である．
-これは通常の継続と比較し軽量に動作するため軽量継続と呼ぶ．
+通常Sechemeのcall/ccなどの継続は現在の位置までの情報を環境として所持した状態で遷移する．
+対してCbCは環境を持たず遷移する為，通常の継続と比較して軽量であることから軽量継続であると言える．
 CbCは軽量継続を利用するためレジスタレベルでのきめ細やかな実装が可能となっている．
 \subsection{現在の実装}
 CbCは現在主要なCコンパイラであるgcc及びllvmをバックエンドとしたclang上の2種類の実装が存在する．
 gccはバージョン9.0.0に,clangは7.0.0に対応している．
 また本来は操作しないはずのスタック領域の操作が入ってしまうため，プログラマの意図と反したスタックポインタなのど操作が行われてしまいバグが発生する可能性が存在する．
 \subsection{CbCとCの互換性}
 CbCコンパイラは内部的に与えられているソースコードがCbCであるかどうかを判断する．
 この際にCodeSegmentを利用していない場合は通常のCプログラムとして動作する．
-その為MoarVMのビルドにおいてもCbCで書き換えたソースコードがあるターゲットと，手を加えていないオリジナルのターゲットの2種類を同一のCbCコンパイラでビルドする事が可能である．
+その為今回検証するMoarVMのビルドにおいてもCbCで書き換えたソースコードがあるMoarVMと，手を加えていないオリジナルのMoarVMの2種類を同一のCbCコンパイラでビルドする事が可能である．
+またCからCbCへの遷移時に，再びCの関数に戻るように実装したい場合がある．
+その際は環境付きgotoと呼ばれる手法を取る．これは\_CbC\_return及び\_CbC\_environmentという変数を渡す．
+この変数は\_CbC\_returnが元の環境に戻る際に利用するCodeSegmentを指し，\_CbC\_environmentは復帰時に戻す元の環境である．
+復帰する場合，呼び出した位置には帰らず，呼び出した関数の終了する位置に帰る．
+\lstinputlisting[label=cbcreturn, caption=環境付き継続の例]{./src/return.cbc}
+Code\ref{cbcreturn}に示す例ではc\_funcから環境付き継続でがcsに継続している．
+通常c\_funcの返り値は-1であるが，csから環境付き継続でmainに帰る為にcsから渡される1がtestの値となる．
 \subsection{言語処理系におけるCbCの応用}
 CbCを言語処理系，特にスクリプト言語に応用すると幾つかの箇所に置いて利点があると推測される．
 CbCにおけるCSはコンパイラの基本ブロックに相当する．
 その為従来のスクリプト言語では主にcase文で記述していた命令コードディスパッチの箇所をCodeSegmentの遷移として記述する事が可能である．
 CbCは状態を単位として記述が可能であるため，命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる．
 \section{Perl6の概要}
 この章では現在までのPerl6の遍歴及びPerl6の言語的な特徴について記載する．
 \subsection{Perl6の構想と初期の処理系}
 Perl6は2002年にLarryWallがPerlを置き換える言語として設計を開始した．
 ParrotはPASMと呼ばれるバイトコードを解釈可能なレジスタマシンである．
 ParrotでのPerl6の実装はNQP(NotQuitPerl)と呼ばれるPerl6のサブセットでPerl6を記述するというアイディアの基実装された．
 ParrotVMは2006年のversion8.1.0が最後のリリースである．
 こちらもPugsと同様に現在のPerl6プロジェクトでは歴史的な実装とされている．
 現在主に使用されている実装であるRakudoは2010年にRakudo-Starという一連のツール郡としてリリースされた．
-Perl6処理系自体は現在も未完成であり，Perl6プロジェクトとして提供しているテストリポジトリ「Roast\cite{roast}」で定義されているテストケースを完全に通化する処理系は現在未だ存在しない．
 Perl6は言語仕様及び処理実装がPerl5と大幅に異なっており，言語的な互換性が存在しない．
 従って現在ではPerl6とPerl5は別言語としての開発方針になっている．
 Perl6は現在有力な処理系であるRakudoから名前を取りRakuという別名がつけられている．
 RakudoがPerl6のコンパイラかつインタプリタであると考えても良い．
 Rakudoは図\ref{fig:perl6construction}に示す構成になっている．
 Rakudoにおけるコンパイラとは厳密には2種類存在する．
 まず第1のものがPerl6,もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである．
 次にそのNQPが出力したバイトコードをネイティブコードに変換するVMの2種類である．
-このVMは現在MoarVM,JavaVM,Javascript,GraalVMを選択可能である．
+このVMは現在MoarVM,JavaVM,Javascriptを選択可能である．
 Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド，VMの部分をバックエンド\cite{rani1}と呼称している．
 NQPで主に書かれたPerl6のことをRakudoと呼ぶ．
 Perl6はNQP以外にもPerl6独自の一種のシンタックスシュガーの様な物を持っており，これはNQPコンパイラ側で処理を行う．
 \begin{figure}[ht]
 \subsection{NQP}
 RakudoにおけるNQP\cite{nqp}は現在MoarVM,JVM上で動作し，MoarVMを一部利用することでNodeJSからも動作させる事が可能である．
 NQPはPerl6のサブセットであるため主な文法などはPerl6に準拠しているが幾つか異なる点が存在する．
-NQP自身はStage0と呼ばれるディレクトリに用意されているモジュールのみ動作環境のVMのバイトコードを必要とするが，それ以外はNQPで記述されておりBootstrappingされている言語である．
+NQPは最終的にはNQP自身でブートストラップする言語であるが，ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする．
+このMoarVM~yteCodeの状態をStage0と言い，ディレクトリ名として設定されている．
 Perl6の一部はNQPを拡張したもので書かれている為,Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる．
 現在のNQPではMoarVM,JVMに対応するStage0はそれぞれMoarVMBytecode,jarファイルが用意されており，Javascriptではバイトコードの代わりにランタイム独自のModuleLoaderなどが設計されている．
 MoarVMのModuleLoaderはStage0あるMoarVMBytecodeで書かれた一連のファイルが該当する．
 NQPのビルドフローは図\ref{fig:nqpbuild}に示す．
 実際にperl6を動かすためにはself buildしたNQPコンパイラが必要となる．その為にstage0を利用してStage1をビルドしNQPコンパイラを作成する．
 Stage1は中間的な出力であり，生成されたNQPファイルはStage2と同一であるが,MoarVMBytecodeが異なる．
 Perl6では完全なセルフコンパイルを実行したNQPが要求される為，Stage1を利用してもう一度ビルドを行いStage2を作成する．
-Roastやドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている．
+Perl6のテストスイートである「Roast\cite{roast}」やドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている．
 現在の公表されているNQPのオペコードはNQPのリポジトリ\cite{nqpopcode}に記述されているものである．
 \begin{figure}[ht]
 \begin{center}
 \includegraphics[width=70mm]{fig/stagenqp.pdf}
 CbC側はcbc\_nextにbreak pointを設定し，オリジナル側は次のオペコードの設定のマクロにダミーの関数を呼び出すように修正し，そこにbreak pointを設定する．
 CbC側ではCodeSegmentの名前を直接確認できるが，オリジナル版はLABLEの配列の添え字から自分でどのオペコードに対応しているかを探す必要がある．
 CbCとオリジナルのCODES,LABELの添字は対応している為，ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する．
 違いが生じている箇所が発見できた場合，その前後のCodeSegment及びディスパッチ部分にbreak pointをかけ，それぞれの変数の挙動を比較する．
 主にcbc\_return系の命令が実行されている場合は,その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが，この周辺で何かしらの違いが発生している可能性が高い．
-その為，アセンブラレベルの命令を確認しながらデバッグを進めることとなる．
+またCbCコンパイラのバグが生じている可能性もある為，アセンブラレベルの命令を確認しながらデバッグを進めることとなる．
 \subsection{CbCコンパイラによるバグ}
 現在までのCbCは複数個の入出力をCodeSegmentに与えるユースケースで利用していた．
 \subsection{Threaded Code}
 CbCはCodeSegmentで末尾最適化(Tail call optimization)を行う．
 これはCodeSegmentは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である．
 現在のCbCコンパイラの実装ではCodeSegmentからCの関数に戻る場合は末尾最適化を切り，CodeSegment間の遷移では末尾最適化が行われる．
 末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる．\cite{threadedcode}
+またCodeSegment自体を直接次の遷移先として設定することも可能であるため，CbCならThrededCodeを実装するアプローチが複数検討出来る．
 %現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeSegmentで処理している．
 %これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する．
 %CbCMoarVMではラベルに対しての遷移の代わりにMoarVMの命令のCodeSegmentの集合体である配列CODESにアクセスし，その要素であるCodeSegmentに対して遷移する形を取っている．
 この一連の処理がオーバーヘッドになる為，今後はcbc\_fixt\_nextというCodeSegmentを導入し直接次の命令に該当するCodeSegmentへgotoする様に実装する予定である．
 \subsubsection{CbCコンパイラ}
 前章までに複数述べた通りCbCコンパイラが現在非常にバグを発生させやすい状態になっている．
 CbCコンパイラはgccとllvm/clangに実装している為，これらのアップデートに追従する必要がある．
 しかしコンパイラのバージョンに応じてCbCで利用するコンパイラ内のAPIが異なる場合が多く，APIの変更に伴う修正作業などを行う必要がある．
-CbCMoarVMではCからCbCへ，CbCからCへの遷移などが複数回繰り返されているが，CodeSegmentでのtail callの強制が非常に難関である．
+CbCMoarVMではCからCodeSegmentへ，CodeSegmentからCへの遷移などが複数回繰り返されているが，この処理中のCodeSegmentでのtail callの強制が非常に難関である．
 tail callの強制には関数定義の箇所や引数，スタック領域のサイズ修正などを行う必要がある．
 \section{今後の課題}
 本論文ではCbCによってPerl6の処理系であるMoarVMインタプリタの一部改良とその手法を示した．

Mercurial > hg > Papers > 2019 > anatofuz-prosym

comparison Paper/anatofuz.tex @ 24:d8f77d0a3452