\chapter{Continuation based C (CbC)}
\label{chapter:CbC}
CbC の構文は C と同じであるが, for文, while文といったループ制御構文や関数呼び出しを取り除き\footnote{言語仕様としては存在しないが while や for を使用することは可能である. }, code segment と goto による軽量継続を導入している.
以下の図\ref{fig:cs}は code segment 同士の関係を表したものであり, 図中の丸が code segment を, 矢印が goto による継続を表している.

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

\section{CbC における Code Segment}
CbC では処理の単位として code segment を用いる。code segment は CbC における最も基本的な処理単位であり, C の関数と異なり戻り値を持たない.
code segment の宣言は C の関数の構文と同じように行い, 型に \_\_code を用いる. ただし, これは \_\_code 型の戻り値を返すという意味ではない. 前述した通り, code segment は戻り値を持たないので, \_\_code はそれが関数ではなく code segment であることを示すフラグのようなものである. 
code segment の処理内容の定義も C の関数同様に行うが, 前述した通り CbC にはループ制御構文が存在しないので, ループ処理は自分自身への再帰的な継続を行うことで実現する.

現在の code segment から次の code segment への処理の移動は goto の後に code segment 名と引数を並べて記述するという CbC 独自の構文を用いて行う. この goto による処理の遷移を継続と呼ぶ.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていくが, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無くスタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. 

以下に CbC を用いたコードの例として, 与えられた数値の階乗を算出するプログラムを示す. このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する.
\begin{lstlisting}[frame=lrbt,label=factorial,caption={\footnotesize 階乗を求める CbC プログラムの例}]
__code print_factorial(int prod)
{
  printf("factorial = %d\n",prod);
  exit(0);
}

__code factorial0(int prod, int x)
{
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
  }else{
    goto print_factorial(prod);
  }
  
}

__code factorial(int x)
{
  goto factorial0(1, x);
}

int main(int argc, char **argv)
{
  int i;
  i = atoi(argv[1]);
  
  goto factorial(i);
}
\end{lstlisting}

\section{環境付き継続}
\label{sec:withEnv}
環境付き継続は C との互換性のために必要な機能である. CbC と C の記述を交える際, CbC の code segment から C の関数の呼び出しは問題なく行える. しかし, C の関数から CbC の code segment へと継続する場合, 呼び出し元の環境に戻るための特殊な継続が必要となる. これを環境付き継続と呼ぶ.

この環境付き継続を導入した言語は C with Continuation (CwC) と呼ばれ, C と CbC の両方の機能を持つ言語となる. また, C, CbC は CwC のサブセットと考えられるので, CwC のコンパイラを CbC に使用することができる. これまでに実装されてきた CbC コンパイラは実際には CwC のコンパイラとして実装されている. 

環境付き継続を用いる場合, C の関数から code segment へ継続する際に \_\_return, \_\_environment という変数で表される特殊変数を渡す. \_\_return は環境付き継続先が元の環境に戻る際に利用する code segment, \_\_environment は元の関数の環境を表す.  リスト\ref{gotoWithTheEnv}では関数 funcB から code segment cs に継続する際に環境付き継続を利用している. cs は funcB から渡された code segment へ継続することで元の C の環境に復帰することが可能となる. 但し復帰先は \_\_return を渡した関数が終了する位置である. このプログラムの例では, 関数 funcA は戻り値として funcB の終わりにある -1 ではなく, 環境付き継続によって渡される 1 を受け取る. 図\ref{fig:gotoWithTheEnv}にこの様子を表した.

\begin{lstlisting}[frame=lrbt,label=gotoWithTheEnv,caption={環境付き継続}]
__code cs(__code (*ret)(int, void*), void *env){
  /* C0 */
  goto ret(1, env);
}

int funcB(){
  /* B0 */
  goto cs(__return, __environment);
  /* B1 (never reached). */
  return -1;
}

int funcA(){
  /* A0 */
  int retval;
  retval = funcB();
  /* A1 */
  printf("retval = %d\n", retval);
  /* retval should not be -1 but be 1. */
}

\end{lstlisting}

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.55}{\includegraphics{fig/gotowithenv.pdf}}
 \end{center}
 \caption{環境付き継続}
 \label{fig:gotoWithTheEnv}
\end{figure}


このような形にすることで, code segment 側では関数から呼ばれたか, code segment からの継続かを考慮する必要がなくなる. また, funcA から見た場合にも, 呼び出した関数の内部で code segment が使われているかどうかが隠蔽され, code segment の有無を考慮しなくて良い.

\section{Gears OS サポート}
\label{sec:Gears}
Gears OS は当研究室で開発している並列フレームワークで, CbC で記述している. Gears では通常の CbC には存在しないメタレベルの処理を表す meta code segment, データの単位である data segment, data segment や code segment 等の情報を管理する context 等がある. これらを現在の CbC の機能のみを用いて記述するとリスト\ref{gears}のようになり, 多くの労力を要する. そのためこの記述を助ける機能が必要であり, 本研究ではこれらを利用するプログラミングをサポートするために以下の機能を提案した.

\begin{itemize}
\item code segment から meta code segment への自動接続
\item 継続時に context から必要な情報を取得する stub の自動生成
\item code segment 内での context の隠蔽
\end{itemize}

\begin{lstlisting}[frame=lrbt,label=gears,caption={Gears OS コード例}]
__code meta(struct Context* context, enum Code next) {
  goto (context->code[next])(context);
}

__code code1_stub(struct Context* context) {
  goto code1(context, &context->data[Allocate]->allocate);
}

__code code1(struct Context* context, struct Allocate* allocate) {
  allocate->size = sizeof(long);
  allocator(context);
  goto meta(context, Code2);
}


__code code2(struct Context* context, long* count) {
  *count = 0;
  goto meta(context, Code3);
}

__code code2_stub(struct Context* context) {
  goto code2(context, &context->data[Count]->count);
}
\end{lstlisting}