% withpage: ページ番号をつける (著者確認用)
% english: 英語原稿用フォーマット
\documentclass{ipsjprosym}
%\documentclass[withpage,english]{ipsjprosym}

\usepackage[dvipdfmx]{graphicx}
\usepackage{latexsym}
\usepackage{comment}
\usepackage{listings}
\lstset{
  language=C,
  tabsize=2,
  frame=single,
  basicstyle={\ttfamily\footnotesize},% 
  identifierstyle={\footnotesize},% 
  commentstyle={\footnotesize\itshape},% 
  keywordstyle={\footnotesize\bfseries},% 
  ndkeywordstyle={\footnotesize},% 
  stringstyle={\footnotesize\ttfamily},
  breaklines=true,
  captionpos=b,
  columns=[l]{fullflexible},% 
  xrightmargin=0zw,% 
  xleftmargin=1zw,% 
  aboveskip=1zw,
  numberstyle={\scriptsize},% 
  stepnumber=1,
  numbersep=0.5zw,% 
  lineskip=-0.5ex,
}
\renewcommand{\lstlistingname}{Code}
\usepackage{caption}
\captionsetup[lstlisting]{font={small,tt}}
\usepackage{url}
\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{CbCを用いたPerl6処理系}

%\affiliate{IPSJ}{情報処理学会}
\affiliate{IERYUKYU}{琉球大学工学部情報工学科}

\author{清水 隆博}{Takahiro SHIMIZU}{IERYUKYU}[anatofuz@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji KONO}{IERYUKYU}[kono@ie.u-ryukyu.ac.jp]

%概要
\begin{abstract}
スクリプト言語であるPerl5の後継言語としてPerl6が現在開発されている．
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)という言語を一部用いる．
本論文ではCbCを用いてMoarVMの一部を書き換える事を検討し，得られた知見についてに述べる．


\end{abstract}

\begin{jkeyword}
プログラミング言語, コンパイラ, CbC, Perl6, MoarVM
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{研究目的}
現在も広く使われているスクリプト言語PerlことPerl5の後継言語としてPerl6が開発されている．
Perl6は設計と実装が区分されており，現在広く使われている実装はRakudoと呼ばれるプロジェクトである．
Rakudoの実装はPerl6コンパイラ開発者用のサブセットであるNQP(NotQuitPerl)で実装されているPerl6の事を指す．
現在RakudoはNQPを解釈できる実行環境として,C言語で実装されたMoarVM,JVM,Javascript上で動作する様に開発されている．
Rakudoとして主に使われている処理系はMoarVMであるが,MoarVMの処理時間がPerl5などの多くのスクリプト言語と比較し非常に低速である．
その為現在日本国内ではPerl6を実務として利用するケースは概ね存在しない．
Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため実用的な処理速度に達すれば言語の利用件数が向上することが期待される．
この問題を解決するために現在当研究室で開発しているContinuation Based C(以下CbC)を用いて改良を行う．
CbCはCよりさらにきめ細やかな記述が可能であるためスクリプト言語などのプログラミング言語の記述と親和性が高い事が推測される．
故に本研究はCbCをスクリプト言語の実装に適応した場合，どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う．
本稿ではまずCbC,Perl6の特徴及び現在の実装について述べ，次に改良を行うMoarVMの一連の処理流れについて述べる．
そして今回改良した一部分と今後の展開について記す．

\section{CbC}
\subsection{CbCの概要}
CbCは当研究室で開発しているプログラミング言語である．
Cレベルでのプログラミングを行う場合，本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどが存在する．
これらをmeta computationと呼ぶ．これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる．
しかしC言語などを用いたプログラミングで分離を行おうとすると，それぞれ事細かに関数やクラスを分割せねばならず容易ではない．
CbCでは関数よりmeta computationを細かく記述する為にCodeSegmentという単位を導入した．
CbCではCodeSegment,DetaSegmentを基本単位として記述するプログラミングスタイルを取る．

\subsection{CodeSegmentとDataSegment}
CbCではCの関数の代わりにCodeSegmentを導入する．
CodeSegmentはCの関数宣言の型名の代わりに\_\_codeと書くことで 宣言できる．
\_\_codeはCbCコンパイラの扱いはvoidと同じ型であるが，CbCプログラミングではCodeSegmentである事を示す識別子としての意味で利用する．

\subsection{軽量継続}
TBD

\subsection{現在の実装}
CbCは現在主要なCコンパイラであるgcc及びllvmをバックエンドとしたclang上の2種類の実装が存在する．
gccはバージョン9.0.0に,clangは7.0.0に対応している．

\subsection{CbCコンパイラのバグ}
% 局所変数のポインタを握ったままgotoするとtail callにならない
CbCコンパイラは現在も開発中であり幾つかのバグが発見されている．
まずCodeSegment内で宣言した局所変数のポインタを別の変数などで確保した状態でgotoしてしまうとtail call最適化が切られる．
これはただの関数呼び出しになってしまう為，直接的な被害はないもののCbCとしての利点が損なわれてしまう．
また本来は操作しないはずのスタック領域の操作が入ってしまうため，プログラマの意図と反したスタックポインタなのど操作が行われてしまいバグが発生する可能性が存在する．

\subsection{CbCとCの互換性}
CbCコンパイラは内部的に与えられているソースコードがCbCであるかどうかを判断する．
この際にCodeSegmentを利用していない場合は通常のCプログラムとして動作する．
これはCbCコンパイラがCコンパイラであるgccとllvm/clang上に実装している為である．
その為MoarVMのビルドにおいてもCbCで書き換えたソースコードがあるターゲットと，手を加えていないオリジナルのターゲットの2種類を同一のCbCコンパイラでビルドする事が可能である．


\subsection{言語処理系におけるCbCの応用}
CbCを言語処理系，特にスクリプト言語に応用すると幾つかの箇所に置いて利点があると推測される．
CbCにおけるCSはコンパイラの基本ブロックに相当する．
その為従来のスクリプト言語では主にcase文で記述していた命令コードディスパッチの箇所をCodeSegmentの遷移として記述する事が可能である．
CbCは状態を単位として記述が可能であるため，命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる．


\section{Perl6の概要}
この章では現在までのPerl6の遍歴及びPerl6の言語的な特徴について記載する．
\subsection{Perl6の構想と初期の処理系}
Perl6は2002年にLarryWallがPerlを置き換える言語として設計を開始した．
Perl5の言語的な問題点であるオブジェクト指向機能の強力なサポートなどを取り入れた言語として設計された．
Perl5は設計と実装が同一であり，Larryらによって書かれたC実装のみだった．Perl6は設計と実装が分離しており様々な処理系が開発されきた．
まず2005年に唐鳳によってHaskellで実装されたPugs\cite{pugs}が登場した．
Pugsは最初に登場したPerl6実装であり，この実装を基にしてPerl6の仕様も修正された．
現在Pugsは歴史的な実装となっており，更新はされていない．

\subsection{Parrot}
その後Pythonとの共同動作環境としてParrot\cite{parrot}が実装された．
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から名前を取り\texttt{Raku}という言語名に変更しようという動きが一部存在している．

\subsection{Rakudo}

RakudoとはParrotで構想に上がったNQP,NQPに基づくPerl6を基にしたプロジェクトである．
RakudoがPerl6のコンパイラかつインタプリタであると考えても良い．
Rakudoにおけるコンパイラとは厳密には2種類存在する．
まず第1のものがPerl6,もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである．
次にそのNQPが出力したバイトコードをネイティブコードに変換するVMの2種類である．
このVMは現在MoarVM,JavaVM,Javascript,GraalVMを選択可能である．
Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド，VMの部分をバックエンド\cite{rani1}と呼称している．
NQPで主に書かれたPerl6のことをRakudoと呼ぶ．
Perl6はNQP以外にもPerl6独自の一種のシンタックスシュガーの様な物を持っており，これはNQPコンパイラ側で処理を行う．

\subsection{NQP}

RakudoにおけるNQP\cite{nqp}は現在MoarVM,JVM上で動作し，MoarVMを一部利用することでNodeJSからも動作させる事が可能である．
NQPはPerl6のサブセットであるため主な文法などはPerl6に準拠しているが幾つか異なる点が存在する．
NQP自身はStage0と呼ばれる名前空間上のモジュールのみ動作環境のVMのバイトコードを必要とするが，それ以外はNQPで記述されておりBootstrappingされている言語である．
Perl6の一部はNQPを拡張したもので書かれている為,Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる．
現在のNQPではMoarVM,JVMに対応するStage0はそれぞれMoarVMbytecode,jarファイルが用意されており，Javascriptではバイトコードの代わりにランタイム独自のModuleLoaderなどが設計されている．
MoarVMのModuleLoaderはStage0あるMoarVMbytecodeで書かれた一連のファイルが該当する．

Stage0にあるファイルをmoarvmに与えることでnqpのインタプリタが実行される様になっている．
これはStage0の一連のファイルはmoarvm bytecodeなどで記述されたNQPコンパイラのモジュールである為である．
NQPは6modelと呼ばれるオブジェクトモデルを採用としているが，これを構築する為に必要なNQPCORE,正規表現系のQRegex,MoarVMのModuleLoaderなどがmoarvmbytecodeで記述されている．これらMoarVMBytecodeの拡張子は.moarvmである．
MoarVMに対してStage0のディレクトリにライブラリパスを設定し，nqp.moarvmを実行させることでnqpの対話型環境が起動する．

実際にperl6を動かすためにはself buildしたNQPコンパイラが必要となる．その為にstage0を利用してStage1をビルドしNQPコンパイラを作成する．

Roastやドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている．
現在の公表されているNQPのオペコードはNQPのGitHubリポジトリ\cite{nqpopcode}に記述されているものである．


\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がそれぞれ必要となる．

言語的な特徴としてはPerl5とは違いアトミックに演算を行う事が可能な絵文字で実装されたatom演算子や，すべてがオブジェクトであるオブジェクト指向言語としての進化も見られる．
またPerl6は漸進的型付け言語である.
従来のPerlの様に変数に代入する対象の型や文脈に応じて型を変更する動的型言語としての側面を持ちつつ独自に定義した型を始めとする様々な型に静的に変数の型を設定する事が可能である．

\subsection{現在のPerl6}
Perl6の言語仕様\cite{perl6design}とその時点での実装状況を纏めた公式ドキュメント\cite{perl6doc}は分離している．
従来は言語仕様は自然言語の仕様書であったが，現在はテストスイートである「Roast\cite{roast}」そのものと定義されている．
現在のPerl6の仕様を読む場合Roastを確認し，現在rakudo上に実装されている機能を見る場合は公式ドキュメントを確認する必要がある．


\section{CbCによるMoarVM}
この章では改良を行ったPerl6処理系であるMoarVMについて述べる．
\subsection{方針}
MoarVMそのものをCbCで書き換えることも考えられるがMoarVM自体既に巨大なプロジェクトである為すべてを書き換える事は困難である．
その為まず比較的CbCで書き換えることが容易な箇所を修正する．
前章までに述べた通りCbCのCodeSegmentはコンパイラの基本ブロックに該当する．
従ってMoarVMにおける基本ブロックの箇所をCodeSegmentに書き換える事が可能である．
MoarVMにおける基本ブロックはインタプリタが実行するバイトコードごとの処理に該当する．

\subsection{MoarByteCodeのディスパッチ}
MoarVMのバイトコードインタプリタはsrc/core/interp.cで定義されている．
この中の関数MVM\_interp\_runで命令に応じた処理を実行する．
関数内では命令列が保存されているcur\_op,現在と次の命令を指し示すop，Threadの環境が保存されているThreadcontextなどの変数を利用する．
命令実行は大きく二種類の動作があり，Cのgotoが利用できる場合はMVM\_CGOTOフラグが立ちラベル遷移を利用する．
それ以外の場合は巨大なcase文として命令を実行する．

ラベル遷移を利用する場合はラベルテーブルにアクセスし，テーブルに登録されているアドレスを取得し，NEXTで遷移する．
このラベルテーブルの中身はラベルが変換されたアドレスであるため，Cレベルでのデバッグ時にはアドレスと実際に呼ばれる箇所を確認する事に手間がかかる．
巨大なcase文として実行された場合，実行時間が遅いだけでなく，ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する．

CbCMoarVMではこの問題を解決するために，それぞれの命令に対応するCodeSegmentを作成し，これらへのポインタを持つCbCのCodeSegmentのテーブルを作成した．

\subsection{命令実行箇所のCodeSegmentへの変換}
ラベルテーブルやcase文のswitch相当の命令実行箇所をCbCに変換し，CodeSegmentの遷移として利用する．
interp.cは?に示す様なスタイルで記述されている．
OP(.*)の.*に該当する箇所はバイトコードの名前である．通常このブロックにはLABELから遷移する為，バイトコードの名前はLABELSの配列の添字に変換されている．
そのため対象となるCodeSegmentをLABLESの並びと対応させ，配列CODESに設定すればCodeSegmentの名前は問わない．
今回はCodeSegmentである事を示す為にsuffixとしてcbc\_をつける．

\subsection{MoarVMのBytecodeのデバッグ}
moarに対してmoarvm bytecodeをdumpオプションを付けて読み込ませるとmoarvmのbytecodeがアセンブラの様に出力される．
しかしこれはmoarvmが実行したbytecodeのトレースではなくmoarvm bytecodeを変換したものに過ぎない．
また，明らかに異なる挙動を示す両者のmoarを利用しても同じ結果が返ってきてしまう．
そのため今回のMoarVMBytecodeインタプリタの実装のデバッグにはこの方法は適さない．
従って実際に実行した命令を確認するにはgdbなどのCデバッガを利用してMoarVMを直接トレースする必要がある．

\subsection{MoarVMの並列デバッグ手法}
しかしMoarVMが実行する命令は膨大な数がある．
その為gdbでMoarVMをCbCとオリジナル版での並列デバッグを人間が同時に行うことは困難である．
Perlなどのスクリプトを用いて自動的に解析したいため，ログを残す為にscriptコマンドを実行した状態でgdbを起動する．
CbC側はcbc\_nextにbreak pointを設定し，オリジナル側は次のオペコードの設定のマクロにダミーの関数を呼び出すように修正し，そこにbreak pointを設定する．
CbC側ではCodeSegmentの名前を直接確認できるが，オリジナル版はLABLEの配列の添え字から自分でどのオペコードに対応しているかを探す必要がある．
CbCとオリジナルのCODES,LABELの添字は対応している為，ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する．
違いが生じている箇所が発見できた場合，その前後のCodeSegment及びディスパッチ部分にbreak pointをかけ，それぞれの変数の挙動を比較する．
主にcbc\_return系の命令が実行されている場合は,その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが，この周辺で何かしらの違いが発生している可能性が高い．
その為，アセンブラレベルの命令を確認しながらデバッグを進めることとなる．



\subsection{CbCコンパイラによるバグ}
現在までのCbCは複数個の入出力をCodeSegmentに与えるユースケースで利用していた．
CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの，MoarVMの様な巨大なプロジェクトのCSをコンパイルを実行する場合，予期せぬバグが発生した．
主にCS間のgotoにおけるtail callフラグの除去や，DSとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい，通常のCの関数をcallした際にローカル変数の領域がDSのアドレスの周辺を利用してしまう．
その為DSの構造体の値が書き換わり，CからDSにreturnした際にDSの構造体が破壊されるバグである．
このバグは先程の並列デバッグを行いながらプログラムカウンタや変数の動きをトレースする事などで発見することが出来る．
現状ではCbCコンパイラがプログラマの意図と反する挙動を取るためCbCコンパイラのバグを回避するプログラミングが要求されている．
本来コンパイラ側のバグを回避するプログラミングをプログラマに要求するスタイルは好ましくない．
従ってCbCコンパイラ自身の信頼性を向上させる事も今後の課題となっている．

\subsection{Threaded Code}
CbCはCodeSegmentで末尾最適化(Tail call optimization)を行う．
これはCodeSegmentは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である．
現在のCbCコンパイラの実装ではCodeSegmentからCの関数に戻る場合は末尾最適化を切り，CodeSegment間の遷移では末尾最適化が行われる．
末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる．\cite{threadedcode}

現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeSegmentで処理している．
これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する．
CbCMoarVMではラベルに対しての遷移の代わりにMoarVMの命令のCodeSegmentの集合体である配列CODESにアクセスし，その要素であるCodeSegmentに対して遷移する形を取っている．
この一連の処理がオーバーヘッドになる為，今後はcbc\_fixt\_nextというCodeSegmentを導入し直接次の命令に該当するCodeSegmentへgotoする様に実装する予定である．

\subsubsection{perlcc}
Perl5においてはperlccというモジュールが開発されている．
これはPerl5内部で利用しているPerlバイトコードを，PerlのC APIであるXS言語の様なCのソースファイルに埋め込み，それをCコンパイルでコンパイルするというものである．
perlccを利用することでPerlインタプリタが無い状況でも可動するバイナリファイルを作成する事が可能である．
しかしPerlccはPerlスクリプトが複雑になるほど正確にCに移植を行う事が出来ず，現在ではPerlのコアモジュールから外されている．
PerlccはPerlのバイトコードをCに変換しただけであり，Cで実装されているPerl経由で実行した場合と処理速度はほぼ変わらない．
またPerlccで生成されたCのソースコードは難解であり，これをデバッグするのが困難でもある．
MoarVMでthreaded codeを実現出来た場合，その箇所のみCbCプログラムとして切り出す事が可能である為perlccと似たツールを作成することも可能である．
この場合,Perl6を通常動かした際とは異なりバイトコードインタプリタに到達する前の処理が無くなる為多少の高速化が望めると推測できる.

\section{CbCを用いる事についての評価}
Perl6処理系はまずPerl6の豊富な文法に対応する物を作成せねばならず，類似する他のプログラミング言語処理系と比較してもより複雑となっている．
実際にPerl5を始めとしたスクリプト言語とPerl6がどのような処理時間の違いが見られるかを実測する．


% \subsection{単純なループ処理の測定}
% 簡単な例題としてfor文を用いて100000回ループさせ，ある変数をインクリメントするというプログラムを作成する．
% 今回の評価対象としてPerl6は2018年4月にリリースされたMoarVM,NQP,Rakudoの実装を用いる．
% Perl5は5.26.2を利用した．
% 
% \begin{table}[htb]
% 	\begin{tabular}{|c|c|c|} \hline
% 	 ループ回数 & Perl5 (sec) & Perl6(sec) \\  \hline \hline	 
% 	 1000000 & 0.131 & 1.444 \\ \hline
% 	 10000000 & 0.131 & 1.444 \\ \hline
% 	 100000000 & 3.258 & 124.69 \\ \hline
% 	\end{tabular}
% \end{table}


\section{今後の課題}
本論文ではCbCによってPerl6の処理系であるMoarVMインタプリタの一部改良とその手法を示した．
CbCのCodeSegment部分を用いることできめ細やかな記述が出来，デバッグし辛い箇所もbreakpointの設定などが容易になった．

今後CbCでの開発をより深く行っていくにあたり，CbCコンパイラそのものの信頼性を向上させる必要がある．
MoarVMの開発を行うにあたり新たに発見された複数のバグを修正し，より安定するコンパイラに改良を行う．

現在CbCMoarVMで直接バイトコードを入力した場合のnqpのテストは\%パスする．
また数値の計算と出力などの簡単なNQPの例題を作成し,オリジナルのNQP，moarvmでバイトコード化したものを入力した際も正常に動作している．
今後はさらに複雑な例題やPerl6の独自文法でも動くかどうかの実験を行う．

MoarVMではGCからオブジェクトを守る為にMVMROOTというマクロを利用し，局所変数のポインタをスタックに登録する処理を行っている．
GCの制御を効率的に行えば本来は必要ない処理であり，実行するとCodeSegmentの優位性が損なわれてしまう．
従ってMoarVMのGCの最適化を行う．

また高速化という面では，Perlの特徴である正規表現に着目し，正規表現の表現のみ高速で動く最適化の導入なども検討している．

Perl6の開発は非常に活発に行われている為，CbCMoarVMの最新版の追従も課題となっている．
現在はinterp.cからPerlスクリプトを用いて自動でCbCのCodeSegmentを生成している．
今後の開発領域の拡大と共により効率的にCbCコードへの自動変換も開発していく．

%å\subsection{MoarVMの処理流れ}
%MoarVMはC言語で実装されており,Perl5で記述されたConfigure.plを


% BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\nocite{*}
 \bibliographystyle{ipsjsort}
 \bibliography{reference}

\end{document}