\chapter{Continuation based C (CbC)}
\label{chp:cbc}
Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。
我々は\ref{chp:first}章に述べたように様々な視点からこのCbCを使った研究を行っている。
本章ではそのCbCの仕様について説明する。


\section{CbCの要求仕様}
90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ
あり、70 年代、80 年代に設計された言語は矛盾を抱えて来ている。

オブジェクト指向技術とそれに基づいたJava などの言語が注目されているが
、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ
ベルな言語による記述に比べて、余分な条件判断（Method search, Meta level
での実行） を増やしてしまい、コンパクトで高速な応答を期待される
Real-time 処理や組み込み用途には適さない。

ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記
述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー
ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル
チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため
に既存の言語に対するコンパイラを一々設計し直すことが必要になってきてい
る。

VHDL, Verilog などのハードウェア記述言語は有限状態遷移の中に閉じており
、オブジェクト指向などの抽象化とはまったく別なものとなってしまっている。

このように3 つは全く異なる方向を向いている。コンパイラの自動生成などが
重要な研究テーマとなると考えられるが、ハードウェア記述言語、アセンブラ
、プログラミング言語の3 つが全く独立したものであれば困難なものになると
考えられる。

そこでCbC はこの3 つを埋めるべく以下のような要求仕様に従って設計された。
\begin{itemize}
  \item ハードウェアとスタックマシンの中間言語

    インタプリタ記述やコンパイラターゲットとして優れること。アーキテク
    チャ依存性が少ないこと、また、アーキテクチャ依存性をモデル化できる。

  \item C 言語よりも下位の言語

    アセンブラよりも汎用性と記述性に優れC と互換であること。C をCbC に
    コンパイルでき、ハンドコンパイルの結果を同値なコードに変換できる。

  \item 明確な実行モデル

    C++やProlog のような複雑な実行モデルは好ましくなく、ハードウェアに
    実行順序の変更を許す範囲を広くする。

  \item 状態遷移を直接記述できる

    Yacc のような表駆動やC のような巨大なswitch 文ではなく直接に状態遷
    移ができ実行できる。

  \item Thread を実行モデルに内蔵できる

    並列処理記述法ではなく状態遷移として表現できる。

  \item クリティカルパスの最適化

    全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出
    して最適化できる。
\end{itemize}

これらの仕様はハードウェア記述とソフトウェア記述の両方を同時に行いつつ
、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ
グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移
記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に
適した言語を作ることを考え、スタックマシンを避けてContinuation（継続）
が導入されている。


\section{コードセグメントと継続}

\subsection{call-returnから継続制御へ}
Cなどの一般的な手続き型言語では、呼び出した手続きの処理のあと、呼出し
元の環境に復帰する。そのためプログラム全体においてスタックが用意され、
呼出し元はスタックに復帰先アドレス及び環境を保持しておく事で呼出し先か
らの復帰を可能とする。これはcall-return制御と呼ばれるものである（図
\ref{fig:call-return}）。
しかし復帰先が決まっていて環境を受け継ぐことができれば、この
call-return制御は図 \ref{fig:continuation}の様に手続き呼び出しの前後で
分割する事ができ、スタック操作を伴わないシーケンシャルな呼び出しに変換
する事ができる。
これは継続制御構造と呼ばれている。schemeのcall-with-continuationの実装
や、 Java,C++の例外処理、Cのsetjmp()/longjmp()による大域脱出もこの継続
制御の一種である。
\begin{figure}[hptb]
  \begin{center}
    %\includegraphics[width=\textwidth,bb=0 0 595 842]{figures/call-return.pdf}
    \includegraphics[width=.6\textwidth]{figures/call-return.eps}
  \end{center}
  \caption{call-return制御}
  \label{fig:call-return}
\end{figure}
\begin{figure}[hptb]
  \begin{center}
    \includegraphics[width=.6\textwidth]{figures/continuation.eps}
  \end{center}
  \caption{継続制御}
  \label{fig:continuation}
\end{figure}

CbCはこの継続制御を基本として設計されており、その実現のためにコードセ
グメントと軽量継続という概念を用いている。
以下ではその二つについて説明する。

\subsection{コードセグメント}
CbCは図\ref{fig:continuation}の様に分割された手続きのそれぞれを一つの
処理単位として用い、これを``コードセグメント''(code-segment)と呼ぶ。

コードセグメントはキーワード``code''を用いてCの関数の様に定義される。
例として引数で与えられた数xの階乗を求めるプログラムをコード
\ref{code:factorial}に示した。
引数部分はインタフェイスと呼ばれ、継続前のコードセグメントからの出力に
あたる。

%コードセグメントは手続きを細かく分割したものなので、Cの関数と比べより
%小さい処理単位となる。しかしコードセグメント内部ではCのステートメント
%と同様の記述が可能であり、処理単位としてはステートメントより大きいもの
%となる。

\subsection{軽量継続(light-weight continuation)}
コードセグメントはCにおける関数とは違い、呼出し元への復帰は存在しない。
そのためコードセグメントの処理の末尾で別のコードセグメントへ継続するこ
とになる。CbCではこの継続制御を``軽量継続''(light-weight continuation)
と呼ぶ。

軽量継続はキーワード``goto''のあとにコードセグメント名とそのコードセグ
メントのインタフェイスに渡す引数列を並べて記述する。（同じく軽量継続の
例がコード \ref{code:factorial}にみられる。）


%この引数列は継続前のコードセグメントの状態、つまりインタフェイスの値に
%よって一意に決まる

\lstinputlisting[caption=コードセグメント例（階乗計算）,label=code:factorial]{sources/factorial.cbc}


\section{状態遷移に適した言語}
Continuation based Cは値を返すプログラムよりも、状態遷移記述に適している。

従来の言語での状態遷移記述は
\begin{itemize}
  \item 表を使った状態遷移インタプリタ
  \item 巨大なswitch文
\end{itemize}
などが用いられてきた。しかしこれらは記述性が悪く、効率も良くない。

表を使った状態遷移インタプリタはコンパイラ言語とは考えられない。また、
それをハードウェア記述に落とすことは難しい。

巨大なswitch文は、コンパイルが複雑になり、適切な最適化を行うことが難し
い。また、人間が読む場合にも読みやすいとは言えない。

CbCは元々状態遷移を直接記述することを目的として設計されており、
手続きの様に環境の保持を伴わないため、その時々に実行中のコードセグメン
トとその引数を直接プログラムの状態とみなす事ができる。

特にゲームやGUIを用いたプログラムなどでは状態遷移記述が多用されており
、そのようなプログラムでは CbCを状態記述言語として使うことにより、直接
実行による実行の高速化と既存の言語と状態遷移記述の整合性の向上をはかる
ことができる。


\section{C with Continuation}
\ref{chp:intro}でも述べたようにCbCはCと互換性を持つことが望ましい。
CbCをCと相互に利用するためには、Cの関数から継続を行った場合に元の環境
に戻るための、特殊な継続を導入する必要がある。これを環境付き継続と呼ぶ。

この環境付き継続を導入した言語はC with Continuation(CwC)と呼ばれ、Cと
CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え
られるので（図 \ref{fig:cwc}）、CwCのコンパイラをCbCに使用する事ができ
る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc
共に実際にはCwCのコンパイラとして実装されている。すなわち、Cの関数や
forなどを使うことができ、mcでは環境付き継続も実装されている。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.6\textwidth]{figures/CwC.eps}
  \end{center}
  \caption{C with Continuationとそのサブセット}
  \label{fig:cwc}
\end{figure}


\subsection{環境付き継続}
環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に
\_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ
ード\ref{code:cbcreturn}参照。
継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する
事で元のCの環境に復帰することが可能となる。
ただし復帰先は\_\_returnを参照した関数が終了する位置である。
図\ref{fig:cbcreturn}にこの様子を表した。
\lstinputlisting[
  caption=\_\_returnの例,
  label=code:cbcreturn,
  emph=\_\_return]
  {sources/cbcreturn.cbc}
この様な形にすることでcode segment側では関数から呼ばれたか、コードセグ
メントからの継続かを考慮する必要がない。また、\verb|funcA|からもその内
部でコードセグメントが使われていることを隠蔽できる。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.6\textwidth]{figures/cbcreturn.eps}
  \end{center}
  \caption{\_\_returnの例}
  \label{fig:cbcreturn}
\end{figure}%




%CbCにおける環境付き継続の構文は幾度か改訂されている。
% TODO _CbC_return


\section{gccベースコンパイラの現時点の問題点}
\label{sec:cbc-problem}

当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ
り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも
って\ref{}GCCによる実装が行われた。この研究によりコードセグメント、継
続制御構造などは実装され、一通りのCbCプログラムのコンパイルが可能とな
った。

しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制
御構造の実装方法の影響により、いくつかの問題が発生している。
以下にその問題点を列記する。
%この問題に対せる解決を \ref{chp:impl}章にて説明する。

\begin{itemize}
  \item 環境付き継続

    これは未実装の機能である。
    変更された新しい仕様の方に対応したい。

  \item 並列代入
    
    CbCでは現在のコードセグメントのインタフェイスと次に継続するコード
    セグメントの引数は同じメモリスペース（もしくはレジスタ）に格納して
    いる。そのためコード\ref{code:paralell_example}のように変数の値を
    入れ替えるような処理では並列代入が行われることになる。
    前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる
    複雑な並列代入ではバグが見つかっている。
    \lstinputlisting[
      caption=並列代入の例,
      label=code:parallel-example]
      {sources/parallel-example.cbc}

  \item PowerPCにおける間接継続(indirect goto)

    CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し
    (indirect call)の様にコードセグメントポインタを用いた間接継続が可
    能である。
    \lstinputlisting[
      caption=間接継続の例（2つめのgoto文）,
      label=code:indirect-example]
      {sources/indirect-example.cbc}
    しかしPowerPCアーキテクチャでは最適化の問題でこの機能が働かないこ
    とが分かっている。

    間接継続はCbCでのプログラミングには必須であり、また本研究室の主要
    プロジェクトであるCeriumはPS3をメインターゲットとしているため、こ
    の対応は必須のものである。

  \item プロトタイプ宣言
   
    Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。
    しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記
    述という性質上、プログラムを記述する際は上から下に実行順にコードセ
    グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大
    な数になる。
    これはプログラミングにおける障害とも言える。

  \item x86での継続制御のオーバヘッド

    mc実装ではx86アーキテクチャでのコードセグメント継続の際には引数を
    レジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォルト
    では全ての引数をメモリに格納する。コードセグメントは関数をベースに
    作られているため、このABIに引きずられ実効速度に影響をもたらす。


\end{itemize}

これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ
ていた。
%特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。
次章ではこれらの問題の解決を行う。