\chapter{トランスコンパイラによるメタ計算}

GearsOSはCbCで実装を行う。
CbCはC言語よりアセンブラに近い言語である。
すべてを純粋なCbCで記述すると記述量が膨大になる。
またノーマルレベルの計算とメタレベルの計算を、全てプログラマが記述する必要がでる。
メタ計算では値の取り出しなどを行うが、 これはノーマルレベルのCodeGearのAPIが決まれば一意に決定される。
したがってノーマルレベルのみ記述すれば、 機械的にメタ部分の処理は概ね生成可能となる。
また、メタレベルのみ切り替えたいなどの状況が存在する。
ノーマルレベル、メタレベル共に同じコードの場合は記述の変更量が膨大であるが、 メタレベルの作成を分離するとこの問題は解消される。

GearsOSではメタレベルの処理の作成にPerlスクリプトを用いており、 ノーマルレベルで記述されたCbCから、 メタ部分を含むCbCへと変換する。
変換前のCbCをGearsCbCと呼ぶ。

\section{トランスコンパイラ}
プログラミング言語から実行可能ファイルやアセンブラを生成する処理系のことを、一般的にコンパイラと呼ぶ。
特定のプログラミング言語から別のプログラミング言語に変換するコンパイラのことを、 トランスコンパイラと呼ぶ。
トランスコンパイラとしてはJavaScriptを古い規格のJavaScriptに変換するBabel\cite{babel}がある。

またトランスコンパイラは、変換先の言語を拡張した言語の実装としても使われる。
JavaScriptに強い型制約をつけた拡張言語であるTypeScriptは、 TypeScriptから純粋なJavaScriptに変換を行うトランスコンパイラである。
すべてのTypeScriptのコードはJavaScriptにコンパイル可能である。
JavaScriptに静的型の機能を取り込みたい場合に使われる言語であり、 JavaScriptの上位の言語と言える。


GearsOSはCbCにノーマルレベル、メタレベルの書き別けの機能などを追加した拡張言語であると言える。
コンパイル時にCMakeによって呼び出される2種類のPerlスクリプトで等価な純粋なCbCに変換される。
これらのPerlスクリプトはGearsOSのCbCから純粋なCbCへと変換している為に一種のトランスコンパイラと言える。

\section{トランスコンパイラによるメタレベルのコード生成}
トランスコンパイラはノーマルレベルで記述されたGearsOSを、メタレベルを含むCbCへと変換する役割である。
変換時に様々なメタ情報をCbCのファイルに書き出すことが可能である。
従来はStubの生成や、 引数の変更などを行っていたが、 さらにメタレベルのコードをトランスコンパイラで作製したい。
トランスコンパイラ上でメタレベルのコードを作製することによって、 GearsOS上でのアプリケーションの記述が容易になり、かつメタレベルのコードを柔軟に扱うことができる。
本研究では様々なメタレベルのコードを、トランスコンパイラで生成することを検討した。


\section{トランスコンパイラ用のPerlライブラリ作製}
従来のPerlトランスコンパイラはgenerate\_stub.plとgenerate\_context.plの2種類のスクリプトで構築されていた。
これらのスクリプトはそれぞれ独立した処理を行っていた。

しかし本研究を進めるにつれて、 Interfaceのパーサーやメタ計算部分の操作を行うAPIなど、 Perlスクリプトで共通した実装が見られた。
さらにgenerate\_stub.plらPerlスクリプトの行数や処理の複雑度が上がり、 適切に処理をモジュール化する必要が生じた。
この為新しく実装したPerlトランスコンパイラが利用するAPIは、 Perlのモジュール機能を利用しモジュールの形で実装した。
以下に実装したモジュールファイルと、その概要を示す。

\begin{itemize}
  \item \texttt{Gears::Context}
  \begin{itemize}
    \item context.hの自動生成時に呼び出されるモジュール
    \item 変換後のCbCのコードを解析し、使用されているDataGearの数え上げを行う
  \end{itemize}
  \item \texttt{Gears::Interface}
  \begin{itemize}
    \item InterfaceおよびImplementのパーサー
  \end{itemize}
  \item \texttt{Gears::Template}
  Gears::Template以下はPerlスクリプトが生成する際に、テンプレートとして呼び出すファイルの定義などがある
  \begin{itemize}
    \item \texttt{Gears::Template::Context}
    \begin{itemize}
      \item context.hのテンプレート
    \end{itemize}
    \item \texttt{Gears::Template::Context::XV6}
    \begin{itemize}
      \item CbC Xv6 専用のcontext.hのテンプレート
    \end{itemize}
    \item \texttt{Gears::Template::Gmain}
    \begin{itemize}
      \item GearsOS Main関数のテンプレート
    \end{itemize}
  \end{itemize}
  \item \texttt{Gears::Stub}
  \begin{itemize}
    \item Stub Code Gear生成時に呼び出されるモジュール
  \end{itemize}
\end{itemize}

これらはgenerate\_stub.plおよびgenerate\_context.plおよび、本研究で作製したPerlのツールセットからも呼び出される。

\section{context.hの自動生成}
GearsOSのContextの定義はcontext.hにある。
ContextはGearsOSの計算で使用されるすべてのCodeGear、 DataGearの情報を持っている。
context.hではDataGearに対応する\texttt{union Data}型の定義も行っている。
Data型はCの共用体であり、 Dataを構成する要素として各DataGearがある。
各DataGearは構造体の形で表現されている。
各DataGear自体の定義もcontext.hのunion Dataの定義の中で行われている。

DataGearの定義はInterfaceファイルで行っていた。
InterfaceファイルはGearsOS用に拡張されたシンタックスのヘッダファイルを使っており、 直接CbCからロードすることができない。
その為従来はプログラマが静的にInterfaceファイルをCbCの文脈に変換し、 context.hに構造体に変換したものを書いていた。
この手法では手書きでの構築のために自由度は高かったが、 GearsOSの例題によっては使わないDataGearも、 context.hから削除しない限りcontextに含んでしまう問題があった。
さらにInterfaceファイルで定義した型をcontext.hに転記し、それをもとにImplの型を考えてCbCファイルを作製する必要があった。
これらをすべてユーザーが行うと、ファイルごとに微妙な差異が発生したりとかなり煩雑な実装を要求されてしまう。
DataGearの定義はInterfaceファイルを作製した段階で決まり、 使用しているDataGear、CodeGearはコンパイル時に確定するはずである。
使用している各Gearがコンパイル時に確定するならば、 コンパイルの直前に実行されるPerlトランスコンパイラでもGearの確定ができるはずである。
ここからcontext.hをコンパイルタイミングでPerlスクリプト経由で生成する手法を考案した。

\subsection{context.hの作製フロー}
GearsCbCからメタ計算を含むCbCファイルに変換するgenerate\_stub.plは各CbCファイルを1つ1つ呼び出していた。
context.hを生成しようとする場合、 プロジェクトで利用する全CbCファイルを扱う必要がある。

Contextの初期化ルーチンを作製するgenerate\_context.plは、その特性上すべてのCbCファイルをロードしていた。
したがってcontext.hを作製する場合はこのスクリプトで行うと現状のCMakeに手をつけずに変更ができる。

\subsection{context.hのテンプレートファイル}

Perlのモジュールとして\texttt{Gears::Template::Context}を作製した。
xv6プロジェクトの場合は一部ヘッダファイルに含める情報が異なる。

派生モジュールとして\texttt{Gears::Template::Context::XV6}も実装した。
これらのテンプレートモジュールはgenerate\_context.plの実行時のオプションで選択可能である。

呼び出しにはPerlの動的モジュールロード機能を利用している。
各モジュールに共通のAPIを記述しており、 テンプレートに限らず共通して呼び出すことが可能である。


\section{メタ計算部分の入れ替え}
GearsOSでは次のCodeGearに移行する前のMetaCodeGearとして、 デフォルトでは\texttt{\_\_code meta}が使われている。
\texttt{\_\_code meta}はcontextに含まれているCodeGearの関数ポインタを、 enumからディスパッチして次のStub CodeGearに継続するものである。

例えばモデル検査をGearsOSで実行する場合、 通常のStub CodeGearのほかに状態の保存などを行う必要がある。
この状態の保存に関する一連の処理は明らかにメタ計算であるので、 ノーマルレベルのCodeGearではない箇所で行いたい。
ノーマルレベル以外のCodeGearで実行する場合は、 通常のコード生成だとStubCodeGearの中で行うことになる。
StubCodeGearは自動生成されてしまうため、 値の取り出し以外のことを行う場合は自分で実装する必要がある。
しかしモデル検査に関する処理は様々なCodeGearの後に行う必要があるため、 すべてのCodeGearのStubを静的に実装するのは煩雑である。

ノーマルレベルのCodeGearの処理の後に、StubCodeGear以外のMeta Code Gearを実行したい。
Stub Code Gearに直ちに遷移してしまう\texttt{\_\_code meta}以外のMeta CodeGearに、 特定のCodeGearの計算が終わったら遷移したい。
このためには、特定のCodeGearの遷移先のMetaCodeGearをユーザーが定義できるAPIが必要となる。
このAPIを実装すると、ユーザーが柔軟にメタ計算を選択することが可能となる。
これはいわゆるリフレクション処理に該当する。

GearsOSのビルドシステムのAPIとして\texttt{meta.pm}を作製した。
これはPerlのモジュールファイルとして実装した。
meta.pmはPerlで実装されたGearsOSのトランスコンパイラであるgenerate\_stub.plから呼び出される。
meta.pmの中のサブルーチンである\texttt{replaceMeta}に変更対象のCodeGearと変更先のMetaCodeGearへのgotoを記述する。
ユーザーはmeta.pmのPerlファイルをAPIとしてGearsOSのトランスコンパイラにアクセスすることが可能となる。

具体的な使用例をコード\ref{src:metapm}に示す。
meta.pmはサブルーチン\texttt{replaceMeta}が返すリストの中に、特定のパターンで配列を設定する。
各配列の0番目には、goto metaを置換したいCodeGearの名前を示すPerl正規表現リテラルを入れる。
コード\ref{src:metapm}の例では、\texttt{PhilsImpl}が名前に含まれるCodeGearを指定している。
すべてのCodeGearのgotoの先を切り替える場合は\texttt{qr/.*\//}などの正規表現を指定する。

\lstinputlisting[label=src:metapm, caption=meta.pm]{src/meta.pm}

generate\_stub.plはGears CbCファイルの変換時に、 CbCファイルがあるディレクトリにmeta.pmがあるかを確認する。
meta.pmがある場合はモジュールロードを行う。
meta.pmがない場合はmeta Code Gearにgotoするものをデフォルト設定として使う。
これらの処理はPerlのクロージャの形で表現しており、 トランスコンパイラ側では共通のAPIで呼び出すことが可能である。
各Gode Gearが\texttt{goto文}を呼び出したタイミングでreplaceMetaを呼び出し、 ルールにしたがってgoto文を書き換える。
変換するCodeGearがルールになかった場合は、 デフォルト設定が呼び出される。



\section{コンパイルタイムでのコンストラクタの自動生成}

\section{InterfaceのAPIの自動保管}



\section{別Interfaceからの書き出しを取得する必要があるCodeGear}

従来のMetaCodeGearの生成では、 別のInterfaceからの入力を受け取るCodeGearのStubの生成に問題があった。
具体的なこの問題が発生する例題をソースコード\ref{src:insertTest1}に示す。
\lstinputlisting[label=src:insertTest1, caption=別Interfaceからの書き出しを取得するCodeGearの例]{src/pop2test.cbc}
この例では\texttt{pop2Test}Code Gearから \texttt{stack->pop2}を呼び出し、 継続として\texttt{pop2Test1}を渡している。
\texttt{pop2Test}自体はStackTest Interfaceであり、 \texttt{stack->pop2}の\texttt{stack}はStack Interfaceである。
例題ではStack Interfaceの実装はSingleLinkedStackである。
SingleLinkedStackの\texttt{pop2}の実装をソースコード\ref{src:pop2}に示す。
\lstinputlisting[label=src:pop2, caption=SingleLinkedStackのpop2]{src/pop2.cbc}
pop2はスタックから値を2つ取得するAPIである。
pop2の継続は\texttt{next}であり、 継続先に\texttt{data}と\texttt{data1}を渡している。
data、 data1は引数で受けている\texttt{union Data*}型の変数であり、 それぞれstackの中の値のポインタを代入している。
この操作でstackから値を2つ取得している。


このコードをgenerate\_stub.pl経由でメタ計算を含むコードに変換する。
変換した先のコードを\ref{src:pop2meta}に示す。
\lstinputlisting[label=src:pop2meta, caption=SingleLinkedStackのpop2のメタ計算]{src/pop2meta.cbc}
実際は\texttt{next}は\texttt{goto meta}に変換されてしまう。
data、data1は\texttt{goto meta}の前にポインタ変数\texttt{O\_data}が指す値にそれぞれ書き込まれる。
\texttt{O\_data}はpop2のStub CodeGearである\texttt{pop2SingleLinkedStack\_stub}で作製している。
つまり\texttt{O\_data}はcontext中に含まれているStack Interfaceのデータ保管場所にある変数dataのアドレスである。
\texttt{pop2}のAPIを呼び出すと、 Stack Interface中の\texttt{data}にStackに保存されていたデータのアドレスが書き込まれる。


当初Perlスクリプトが生成した\texttt{pop2Test1}のstub CodeGearはソースコード\ref{src:pop2stub-origin}のものである。
CodeGear間で処理されるデータの流れの概要図を図\ref{fig:stackTest1}に示す。
\lstinputlisting[label=src:pop2stub-origin, caption=生成されたStub]{src/pop2stub-origin.cbc}
\texttt{\_\_code pop2Test}で遷移する先のCodeGearはStackInterfaceであり、 呼び出しているAPIは\texttt{pop2}である。
pop2で取り出したデータは、 上記で確認した通りContext中のStack Interfaceのデータ格納場所に書き込まれる。
しかしソースコード\ref{src:pop2stub-origin}の例では\texttt{Gearef(context, StackTest)}でContext中の\texttt{StackTest} Interfaceのdataの置き場所から値を取得している。
これはInterfaceのImplのCodeGearは、Interfaceから値を取得するというGearsOSのルールの為である。
現状ではpop2でせっかく取り出した値をStubCodeGearで取得できない。

ここで必要となってくるのは、 実装しているInterface以外の呼び出し元のInterfaceからの値の取得である。
今回の例ではStackTest InterfaceではなくStack Interfaceからdata、 data1を取得したい。
どのInterfaceから呼び出されているかは、 コンパイルタイムには確定できるのでPerlのトランスコンパイラでStub Codeを生成したい。

\begin{figure}[h]
  \begin{center}
   \includegraphics[width=130mm]{drawio/stackTest1.pdf}
  \end{center}
  \caption{stackTest1のstubの概要}
  \label{fig:stackTest1}
 \end{figure}

別Interfaceから値を取得するには別の出力があるCodeGearの継続で渡されたCodeGearをまず確定させる。
今回の例では\texttt{pop2Test1}が該当する。
このCodeGearの入力の値と、 出力があるCodeGearの出力を見比べ、 出力をマッピングすれば良い。
Stack Interfaceのpop2はdataとdata1に値を書き込む。
pop2Test1の引数はdata, data1, stackであるので、前2つにpop2の出力を代入したい。

Contextから値を取り出すのはメタ計算であるStub CodeGearで行われる。
別Interfaceから値を取り出そうとする場合、 すでにPerlトランスコンパイラが生成しているStubを書き換える方法も取れる。
しかしStubCodeGearそのものを、 別Interfaceから値を取り出すように書き換えてはいけない。
これは別Interfaceの継続として渡されるケースと、 次のgoto先として遷移するケースがあるためである。
前者のみの場合は書き換えで問題ないが、 後者のケースで書き換えを行ってしまうとStubで値を取り出す先が異なってしまう。
どのような呼び出し方をしても対応できるようにするには、 Stubを別に別ける必要がある。


GearsOSでは継続として渡す場合や、 次のgoto文で遷移する先のCodeGearはノーマルレベルではenumの番号として表現されていた。
enumが降られるCodeGearは、厳密にはCodeGearそのものではなくStub CodeGearに対して降られる。
StubCodeGearを実装した分だけenumの番号が降られるため、 \texttt{goto meta}で遷移する際にenumの番号さえ合わせれば独自定義のStubに継続させることが可能である。
別Interfaceから値を取り出したいケースの場合、 取り出してくる先のInterfaceと呼び出し元のCodeGearが確定したタイミングで別のStubCodeGearを生成する。
呼び出し元のCodeGearが継続として渡すStubCodeGearのenumを、独自定義したenumに差し替えることでこの問題は解決する。
この機能をPerlのトランスコンパイラである\texttt{generate\_stub.pl}に導入した。

\section{別Interfaceからの書き出しを取得するStubの生成}
別Interfaceからの書き出しを取得する場合、 generate\_stub.plでは次の点をサポートする機能をいれれば実現可能である。

\begin{itemize}
  \item goto先のCodeGearが出力を持つInterfaceでかつ継続で渡しているCodeGearが別Interfaceの場合の検知
  \begin{itemize}
    \item この場合はgotoしている箇所で渡している継続のenumを、新たに作製したstubのenumに差し替える
  \end{itemize}
  \item 継続で実行された場合に別にInterfaceから値をとってこないといけないCodeGear自身
  \begin{itemize}
    \item Stubを別のInterfaceから値をとる実装のものを別に作製する
  \end{itemize}
\end{itemize}


\texttt{generate\_stub.pl}内では変換対象のCbCのソースコードを2度読み込む。
最初の読み込み時に継続の状況を確認し、 2度目の読み込み時に状況を踏まえてコードを生成すれば良い。
初回の読み込み時にInterface経由の\texttt{goto}文があった場合に、別Interfaceからの出力があるかなどの情報を確認したい。

\subsection{初回CbCファイル読み込み時の処理}

Interface経由でのgoto文は\texttt{goto interface->method()}の形式で呼び出される。
ソースコード\ref{src:parsedOutputStub.pl}はこの形式で来ていた行を読み込んだタイミングで実行される処理である。
\lstinputlisting[label=src:parsedOutputStub.pl, caption=goto時に使用するinterfaceの解析]{src/parsedOutputStub.pl}

1行目の正規表現はInterface経由でのgoto文の正規表現パターンである。
変数\texttt{\$instance}はInterfaceのインスタンスである。正規表現パターンでは\texttt{interface->method}の\texttt{->}の前に来ている変数名に紐づけられる。
変数\texttt{\$method}はgoto先のInterfaceのAPIである。正規表現パターンでは\texttt{interface->method}の\texttt{->}の後に来ているAPI名である。
ソースコード\ref{src:insertTest1}の\texttt{pop2Test}では、 \texttt{stack->pop2}の呼び出しをしているため、 \texttt{stack}がインスタンスであり、 \texttt{pop2}がAPIである。
現在解析しているgoto文が含まれているCodeGearの名前は、変数\texttt{\$currentCodeGear}で別途保存している。
連想配列である\texttt{\$codeGearInfo}の中には、 各CodeGearで使われている変数と変数の型などの情報が格納されている。
ソースコード\ref{src:parsedOutputStub.pl}の9行目では、 \texttt{\$codeGearInfo}経由でInterfaceのインスタンスから、具体的にどの型が呼ばれているかを取得する。
\texttt{pop2Test}では、 インスタンス\texttt{stack}に対応する型名は\texttt{Stack}と解析される。

ソースコード\ref{src:parsedOutputStub.pl}の10行目で実行されている\texttt{findExistsOutputDataGear}はgenerate\_stub.pl内の関数である。
これはInterfaceの名前とメソッド名を与えると、 Interfaceの定義ファイルのパース結果から出力の有無を確認する動きをする。
出力がある場合は出力している変数名の一覧を返す。
ソースコード\ref{src:insertTest1}の例では\texttt{pop2}は\texttt{data}と\texttt{data1}を出力している為、 これらがリストとして関数から返される。
出力がない場合は偽値を返すために13行目からのif文から先は動かない。
出力があった場合はgenerate\_stub.plの内部変数に出力する変数名と、 Interfaceの名前の登録を行う。
生成するStubは命名規則は、 Stubの本来のCodeGearの名前の末尾に\texttt{\_}に続けて数値をいれる。
\texttt{\_\_code CodeGearStub}の場合は、 \texttt{\_\_code CodeGearStub\_1}となる。
この数値は変換した回数となるため、 この回数の計算を行う。


27行目で\texttt{\$generateHaveOutputStub}のlist要素に現在のCodeGearの名前と、 出力に関する情報を代入している。
現在のCodeGearの名前を保存しているのは、この後のコード生成部分でenumの番号を切り替える必要があるためである。
ソースコード\ref{src:insertTest1}の例では\texttt{pop2Test}が使うenumを書き換える必要がある為、 ここの\texttt{\$currentCodeGear}はpop2Testとなる。
ここで作製した\texttt{\$outputStubElem}は、返還後のCbCコードを生成しているフェーズで呼びされる。

\subsection{enumの差し替え処理}

ソースコード\ref{src:generatePickNext.pl}の箇所は遷移先のenumをPerlスクリプトで生成し、 GearsOSが実行中にenumをcontextに書き込むコードを生成するフェーズである。
\lstinputlisting[label=src:generatePickNext.pl, caption=Gearefのコード生成部分]{src/generatePickNext.pl}
if文で条件判定をしているが、前者は出力があるケースかどうかのチェックである。
続く条件式はGearsOSのビルドルールとして静的に書いたstubの場合は変更を加えない為に、 静的に書いているかどうかの確認をしている。
変数\texttt{\$pick\_next}で継続先のCodeGearの名前を作製している。
CodeGearの名前は一度目の解析で確認した継続先に\texttt{\_}とカウント数をつけている。
ここで作製したCodeGearの名前を、3行目でcontextに書き込むCbCコードとして生成している。


実際に生成された例題をソースコード\ref{src:replaceenum}に示す。
\lstinputlisting[label=src:replaceenum, caption=enumの番号が差し替えられたCodeGear]{src/replaceenum.cbc}


\section{ジェネリクスのサポート}