changeset 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
files Paper/anatofuz.pdf Paper/anatofuz.tex Paper/reference.bib Paper/src/return.cbc
diffstat 4 files changed, 56 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/anatofuz.pdf has changed
--- a/Paper/anatofuz.tex	Thu Nov 08 19:29:49 2018 +0900
+++ b/Paper/anatofuz.tex	Thu Nov 08 23:16:52 2018 +0900
@@ -51,8 +51,8 @@
 このVMは任意のVMが選択できるようになっており,現在はMoarVM,JavaVM,Javascriptが動作環境として選択可能である.
 主に利用されているVMにCで書かれたMoarVMが存在する.
 MoarVMはJITコンパイルなどをサポートしているが,全体的な起動時間及び処理速度がPerl5と比較し非常に低速である.
-この問題を解決するためにContinuation based C (CbC)という言語を一部用いる.
-本論文ではCbCを用いてMoarVMの一部を書き換える事を検討し,得られた知見についてに述べる.
+この問題を解決するためにContinuation based C (CbC)という言語を一部用いてMoarVMの書き換えを行う.
+本論文ではCbCを用いたMoarVMの書き換えを検討し,得られた知見について述べる.
 
 
 \end{abstract}
@@ -74,16 +74,16 @@
 Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため実用的な処理速度に達すれば言語の利用件数が向上することが期待される.
 この問題を解決するために現在当研究室で開発しているContinuation Based C(以下CbC)を用いて改良を行う.
 CbCはCよりさらにきめ細やかな記述が可能であるためスクリプト言語などのプログラミング言語の記述と親和性が高い事が推測される.
-故に本研究はCbCをスクリプト言語の実装に適応した場合,どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う.
+本研究はCbCをスクリプト言語の実装に適応した場合,どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う.
 本稿ではまずCbC,Perl6の特徴及び現在の実装について述べ,次に改良を行うMoarVMの一連の処理流れについて述べる.
 そして今回改良した一部分と今後の展開について記す.
 
 \section{CbC}
 \subsection{CbCの概要}
 CbCは当研究室で開発しているプログラミング言語である.
-Cレベルでのプログラミングを行う場合,本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどが存在する.
-これらをmeta computationと呼ぶ.これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる.
-しかしC言語などを用いたプログラミングで分離を行おうとすると,それぞれ事細かに関数やクラスを分割せねばならず容易ではない.
+Cレベルでのプログラミングを行う場合,本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどを記述する必要がある.
+これらの処理をmeta computationと呼ぶ.これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる.
+しかしC言語などを用いたプログラミングでmeta computationの分離を行おうとすると,それぞれ事細かに関数やクラスを分割せねばならず容易ではない.
 CbCでは関数よりmeta computationを細かく記述する為にCodeSegmentという単位を導入した.
 またCodeSegmentの実行に必要なデータをDataSegmentという単位で受け渡す.
 CbCではCodeSegment,DetaSegmentを基本単位として記述するプログラミングスタイルを取る.
@@ -102,7 +102,8 @@
 CbCでは次のCodeSegmentに移行する際,Cのgoto文を利用する.
 通常のCの関数呼び出しの場合,スタックポインタを操作しローカル変数などをスタックに保存する.
 CbCの場合スタックフレームを操作せず,レジスタの値を変更せずそのまま次のCodeSegmentに遷移する事が可能である.
-これは通常の継続と比較し軽量に動作するため軽量継続と呼ぶ.
+通常Sechemeのcall/ccなどの継続は現在の位置までの情報を環境として所持した状態で遷移する.
+対してCbCは環境を持たず遷移する為,通常の継続と比較して軽量であることから軽量継続であると言える.
 CbCは軽量継続を利用するためレジスタレベルでのきめ細やかな実装が可能となっている.
 
 \subsection{現在の実装}
@@ -119,7 +120,15 @@
 \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の応用}
@@ -128,7 +137,6 @@
 その為従来のスクリプト言語では主にcase文で記述していた命令コードディスパッチの箇所をCodeSegmentの遷移として記述する事が可能である.
 CbCは状態を単位として記述が可能であるため,命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる.
 
-
 \section{Perl6の概要}
 この章では現在までのPerl6の遍歴及びPerl6の言語的な特徴について記載する.
 \subsection{Perl6の構想と初期の処理系}
@@ -146,7 +154,6 @@
 ParrotVMは2006年のversion8.1.0が最後のリリースである.
 こちらもPugsと同様に現在のPerl6プロジェクトでは歴史的な実装とされている.
 現在主に使用されている実装であるRakudoは2010年にRakudo-Starという一連のツール郡としてリリースされた.
-Perl6処理系自体は現在も未完成であり,Perl6プロジェクトとして提供しているテストリポジトリ「Roast\cite{roast}」で定義されているテストケースを完全に通化する処理系は現在未だ存在しない.
 
 Perl6は言語仕様及び処理実装がPerl5と大幅に異なっており,言語的な互換性が存在しない.
 従って現在ではPerl6とPerl5は別言語としての開発方針になっている.
@@ -160,7 +167,7 @@
 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コンパイラ側で処理を行う.
@@ -177,7 +184,8 @@
 
 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で書かれた一連のファイルが該当する.
@@ -192,7 +200,7 @@
 Stage1は中間的な出力であり,生成されたNQPファイルはStage2と同一であるが,MoarVMBytecodeが異なる.
 Perl6では完全なセルフコンパイルを実行したNQPが要求される為,Stage1を利用してもう一度ビルドを行いStage2を作成する.
 
-Roastやドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている.
+Perl6のテストスイートである「Roast\cite{roast}」やドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている.
 現在の公表されているNQPのオペコードはNQPのリポジトリ\cite{nqpopcode}に記述されているものである.
 
 \begin{figure}[ht]
@@ -291,7 +299,7 @@
 CbCとオリジナルのCODES,LABELの添字は対応している為,ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する.
 違いが生じている箇所が発見できた場合,その前後のCodeSegment及びディスパッチ部分にbreak pointをかけ,それぞれの変数の挙動を比較する.
 主にcbc\_return系の命令が実行されている場合は,その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが,この周辺で何かしらの違いが発生している可能性が高い.
-その為,アセンブラレベルの命令を確認しながらデバッグを進めることとなる.
+またCbCコンパイラのバグが生じている可能性もある為,アセンブラレベルの命令を確認しながらデバッグを進めることとなる.
 
 
 
@@ -310,6 +318,7 @@
 これはCodeSegmentは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である.
 現在のCbCコンパイラの実装ではCodeSegmentからCの関数に戻る場合は末尾最適化を切り,CodeSegment間の遷移では末尾最適化が行われる.
 末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる.\cite{threadedcode}
+またCodeSegment自体を直接次の遷移先として設定することも可能であるため,CbCならThrededCodeを実装するアプローチが複数検討出来る.
 
 %現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeSegmentで処理している.
 %これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する.
@@ -373,7 +382,7 @@
 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の強制には関数定義の箇所や引数,スタック領域のサイズ修正などを行う必要がある.
 
 
--- a/Paper/reference.bib	Thu Nov 08 19:29:49 2018 +0900
+++ b/Paper/reference.bib	Thu Nov 08 23:16:52 2018 +0900
@@ -94,3 +94,17 @@
     year = 2006,
     month = 2,
 }
+
+@misc{threadecodes,
+    title = {Threaded Code},
+    author = {Bell, James R},
+    journal = {Communications of the ACM 16.6},
+    year = 1973,
+}
+
+@misc{optthreade,
+    title = {Optimizing direct threaded code by selective inlining},
+    author = {Piumarta, Ian and Fabio Riccardi},
+    journal = {ACM SIGPLAN Notices. Vol. 33},
+    year = 1998,
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/return.cbc	Thu Nov 08 23:16:52 2018 +0900
@@ -0,0 +1,18 @@
+__code cs(__code (*ret)(int,void *),void *env){
+  goto ret(1,env); 
+}
+
+int c_func(){
+  goto cs(_CbC_return,_CbC_environment);
+  return -1;
+}
+
+int main(){
+  int test;
+  test = c_func();
+  printf("%d\n",test);
+  return 0;
+}
+
+
+