\chapter{Gears におけるメタ計算}
Gears 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 に閉じているため、
これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。

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

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.7}{\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 の一例である。

\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 へ戻ることはない。
軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。

\section{Data Gear}
Data Gear は Gears におけるデータの単位である。
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=100mm]{fig/IO_DataGear.pdf}
 \end{center}
 \caption{CodeGear と DataGear}
 \label{fig:IODataGear}
\end{figure}

ソースコード \ref{Gears_code} は Gears OS での Stack の操作の Code Gear の例である。
popSingleLinkedStack での引数 stack が Input Data Gear、next は継続先の Code Gear のアドレス、
next の引数の data が Output Data Gear、... は可変長引数であることを示している。
pop の操作を行った後に 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 で表現する。
Meta Code Gear は通常の 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 と呼ぶ。
%code を入れる
stub Code Gear は Code Gear 毎にあり、次の Code Gear へと継続する前に挿入される。
つまり goto による継続を行うと、実際には次の Code Gear の stub Code Gear を呼び出す。
stub Code Gear では、継続先が求める Input Code Gear、Output Code Gear を Context から参照している。


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 に格納される。

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

これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。
Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。


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

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