\chapter{Gears におけるメタ計算}
プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。
これらの計算をメタ計算と呼ぶ。

従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
実行時にメタ計算の変更を行う場合には、OS 内部のパラメータの変更を使用し、
実行されるユーザープログラム自体への変更は限定的である。
しかし、メタ計算は性能測定、あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で
実際のシステムコール単位では不十分である。
例えば、モデル検査ではアセンブラあるいはバイトコード、インタプリタレベルでのメタ計算が必要になる。
しかし、バイトコードレベルでは粒度が細かすぎて扱いが困難になっている。
具体的にはメタ計算の実行時間が大きくなってしまう。

メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
プログラムの処理の単位を Code Gear、データの単位を Data Gear と呼ぶ。 
これによりシステムコードよりも細かくバイトコードよりも大きなメタ計算の単位を提供できる。

Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、
これらを用いてメタ計算を実現する。

Gears OS は処理やデータの構造が Code Gear、Data Gear に閉じているため、
これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。

Gears OS には Context と呼ばれる全ての Code Gear、Data Gear のリストを持つ Meta Data Gear が存在する。
Gears OS ではこの Context を常に持ち歩いているが、これはノーマルレベルでは見えることはない。 

ノーマルレベルの処理とメタレベルを含む処理は同じ動作を行う。
しかしメタレベルの計算を含むプログラムとノーマルレベルでは、Data Gear の扱いなどでギャップがある。
ノーマルレベルでは Code Gear は Data Gear を引数の集合として引き渡しているが、
メタレベルでは Context に格納されており、ここを参照することで Data Gear を扱っている。

このギャップを解消するためにメタレベルでは stub Code Gear と呼ばれる Context から Data Gear の参照を行う
Meta Code Gear が Code Gear 継続前に揷入されこれを解決する。

\section{Continuation based C}
CbC は処理を Code Gear とした単位を用いて記述するプログラミング言語である。
Code Gear 間では軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、
状態遷移ベースのプログラミングに適している。
図\ref{fig:cs}は Code Gear 間の処理の流れを表している。

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.9}{\includegraphics{fig/codesegment.pdf}}
 \end{center}
 \caption{goto による code gear 間の継続}
 \label{fig:cs}
\end{figure}


CbC は LLVM\cite{llvm} と GCC\cite{gcc} 上で実装されている。
Gears OS はこの CbC を用いて記述されている。

\section{Code Gear}

Code Gear は CbC における最も基本的な処理単位である。
関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
ソースコード \ref{code_simple} はCbC における Code Gear の一例である。

\newpage

\begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
__code cs0(int a, int b){
  goto cs1(a+b);
}

__code cs1(int c){
  goto cs2(c);
}
\end{lstlisting}

Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。
Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
次の Code Gear への遷移は goto Code Gear 名 (引数) で次の Code Gear への遷移を記述する。
ソースコード \ref{code_simple} での goto cs1(a+b); がこれにあたる。
この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
したがってこれを軽量継続と呼ぶこともある。
cs1 へ継続した後は cs0 へ戻ることはない。
軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。

CbC は軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。

\section{Data Gear}
Data Gear は Gears OS におけるデータの単位である。
Gears OS では Code Gear は Input Data Gear、Output Data Gear を引数に持ち、
任意の Input Data Gear を参照し、Output Data Gear を書き出す。図\ref{fig:IODataGear}
Code Gear はこのとき渡された引数の Data Gear 以外を参照することはない。
この Data Gear の対応から依存関係の解決を行う。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=130mm]{fig/IO_DataGear.pdf}
 \end{center}
 \caption{CodeGear と DataGear}
 \label{fig:IODataGear}
\end{figure}

ソースコード \ref{Gears_code} は Gears OS での Stack の pop 操作の Code Gear の例である。
popSingleLinkedStack での引数 stack が Input Data Gear、next は継続先の Code Gear を示す。
また、next の引数の data が Output Data Gear、... は可変長引数であることを示している。
Input Data Gear で受け取った Stack に対して pop の操作を行った後に、
取り出したデータを Output Data Gear として書き出し、goto next で引数で受けた次の Code Gear へと継続する。

\begin{lstlisting}[frame=lrbt,label=Gears_code,caption={\footnotesize Gears でのStack pop}]

__code stackTest3(struct Stack* stack) {
    goto stack->pop(assert3);
}

__code popSingleLinkedStack(struct SingleLinkedStack* stack, __code next(union Data* data, ...)) {
    if (stack->top) {
        data = stack->top->data;
        stack->top = stack->top->next;
    } else {
        data = NULL;
    }
    goto next(data, ...);
}

__code assert3(struct Node* node, struct Stack* stack) {
    assert(node->color == Red);
    goto exit_code(0);
}

\end{lstlisting}

\section{Meta Code Gear、Meta Data Gear}
Gears OS ではメタ計算 を Meta Code Gear、Meta Data Gear で表現する。
CbC での記述はメタ計算を含まないノーマルレベルでの記述と、 Code Gear、Data Gear の記述を含むメタレベルの記述の2種類がある。
メタレベルでもさらに、メタ計算を用いることが可能になっている。
この2つのレベルはプログラミング言語レベルでの変換として実現される。
メタレベルでの変換系は本論文では、Perl による変換スクリプトにより実装されている。

Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。
Code Gear 間の継続はノーマルレベルでは図 \ref{fig:normal_Code_Gear} のように見える。
メタレベルでは Code Gear は図 \ref{fig:meta_Code_Gear} のように継続を行なっている。


\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{fig/normal_Code_Gear.pdf}
 \end{center}
 \caption{ノーマルレベルの Code Gear の継続}
 \label{fig:normal_Code_Gear}
\end{figure}

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=140mm]{fig/meta_Code_Gear.pdf}
 \end{center}
 \caption{メタレベルの Code Gear の継続}
 \label{fig:meta_Code_Gear}
\end{figure}

\subsection{Context と stub Code Gear}

Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。
Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。
しかし Context を通常の計算から直接扱うのはセキュリティ上好ましくない。
そこで Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear を定義し、
これを介して間接的に必要な Data Gear にアクセスする。
この Meta Code Gear を stub Code Gear と呼ぶ。
stub Code Gear は Code Gear 毎にあり、次の Code Gear へと継続する前に挿入される。
つまり goto による継続を行うと、実際には次の Code Gear の stub Code Gear を呼び出す。
stub Code Gear では、継続先が求める Input Code Gear、Output Code Gear を Context から参照している。

図 \ref{fig:Context_ref} はメタレベルで見た Data Gear へのアクセスを図示したものである。
メタレベルでは Code Gear は Context が持つ Data Gear へのポインタを渡されており、
そこへ Output を行う。
stub Code Gear は Meta Data Gear である Context が持つ Data Gear を、
Input Data Gear、Output Data Gear として参照し、
継続先のノーマルレベルの Code Gear へと遷移する。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=140mm]{fig/Context_ref.pdf}
 \end{center}
 \caption{Context が持つ Data Gear へのアクセス}
 \label{fig:Context_ref}
\end{figure}

次の Code Gear に継続する際にもメタレベルでは Meta Code Gear が挟まれる。
ノーマルレベルでは goto codeGear() で次の Code Gear の継続を記述するので、直接 Code Gear へ継続するように見えるが、
実際には \_\_code meta へと継続している。
\_\_code meta では Context の持つ Code Gear のリストから目的の Code Gear へと継続している。（ソースコード \ref{codemeta}）

\newpage

\begin{lstlisting}[frame=lrbt,label=codemeta,caption={\footnotesize code meta}]

__code meta(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}

\end{lstlisting}

Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される全ての Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。
一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Context に格納される。

%Context の概念のセクション

Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。
これを記述するために継続に不定長引数を追加する構文をスクプリトの変換機能として用意した。
メタ計算側ではこれらの Context を常に持ち歩いているので goto 文で引数を用いることはなく、
行き先は Code Gear の番号のみで指定される。

これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。
Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。
%入れるのであれば
%code gear の並列実行
%ノーマルレベルでは複数の goto を持つ

\subsection{Meta Gear を用いたメタレベルの処理}

Context を複製して複数の CPU に割り当てることにより並列実行を可能になる。
これによりメタ計算として並列処理を記述したことになる。

Gears のスレッド生成は Agda の関数型プログラミングに対応して行われるのが望ましい。
そこで、par goto 構文を導入し、Agda の継続呼び出しに対応させることにした。
par goto では Context の複製、入力の同期、タスクスケジューラーへの Context の登録などが行われる。
par goto 文の継続として、スレッドの join に相当する \_\_exit を用意した。
\_\_exit により par goto で分岐した Code Gear の出力を元のスレッドで受け取ることができる。

関数型プログラムではメモリ管理は GC などを通して暗黙に行われる。
Gears OS ではメモリ管理は stub などのメタ計算部分で処理される。
例えば、寿命の短いスレッドでは使い捨ての線形アロケーションを用いる。