\chapter{Continuation based C (CbC)}
\label{chapter:CbC}
\section{CbCとは}
CbC の構文は C と同じであるが, for文, while文といったループ制御構文や関数呼び出しを取り除き\footnote{言語仕様としては存在しないが while や for を使用することは可能である. この場合は CbC ではなく CwC (Continuation with C) と呼ばれる. CwC については後述する.}, code segment と goto による軽量継続を導入している.
%CbC の構文は C と同じであるが, C の関数の代わりに code segment を用いて処理を記述し, code segment 間の移動に goto (軽量継続) を用いる. 
%構文は C と同じであるが, for文, while文といったループ制御や関数呼び出しが取り除かれる\footnote{言語仕様としては存在しないが while や for を使用することは可能である. この場合は CbC ではなく CwC (Continuation with C) と呼ばれる}. 
%code segment の記述は C の関数の構文と同じで型に \_\_code を使うことで宣言でき, 次の code segment への移動は goto の後に 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}


%図\ref{fig:cs}の csB, csC 間の継続から読み取れるように, code segment 間の継続は繰り返すことが可能であり, これによってループ制御が実現される.


\section{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 ではスタックに値を積んでいく必要が無くスタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. 


\section{コード例}
以下に 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){
  goto ret(1, env);
}

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

int funcA(){
  int retval;
  retval = funcB();
  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/cbcreturn.pdf}}
 \end{center}
 \caption{環境付き継続}
 \label{fig:gotoWithTheEnv}
\end{figure}
　このような形にすることで, code segment 側では関数から呼ばれたか, code segment からの継続かを考慮する必要がなくなる. また, funcA から見た場合にも, 呼び出した関数の内部で code segment が使われているかどうかが隠蔽され, code segment の有無を考慮しなくて良い.\\
%　環境付き継続は実際には C における setjmp() / longjmp() とほぼ同じ処理である.