\section{ Continuation based C}

CbC (Continuation based C)は、Cからサブルーチンやループ構造
を除いたCの下位言語であり、ハードウェアとソフトウェア、特に
組込みシステムの記述言語として本研究室で提案している言語で
ある。

Cの関数の代わりに、
たコード・
セグメントという単位を持つ。コードセグメントには、入口に相当する
Input interface と、出口に相当するParameterized goto 文が存在する。

\begin{figure}[htb]
\begin{center}
\includegraphics[width=6cm]{fig/code.eps}
\end{center}
\label{fig000}
\end{figure}


以下は簡単なCbCのプログラムである。

{\small
\begin{verbatim}
    code fact(int n,int result, 
           code print()){
        if(n>0){
            result *= n;
            n--;
            goto fact(n,result,print);      
        } else  
            goto (*print)(result);  
    }
\end{verbatim}
}

間接gotoと、直接gotoが、プログラムの単位の結び付きをボトムアップに
規定して、自然なグループを構成する。

CbCの継続は、Schemeなどの継続とは異なり環境(関数の呼び出し履歴)を持たない。
コードセグメントは、関数呼び出しではないので環境を持つ必要がない。

Cにコードセグメントと引数つきgoto文を付加したCwCは、Cのスーパセット
であり、
コードセグメント内から通常のCの関数を呼び出すことも可能ある。また、
通常の関数からコードセグメントへgotoしたり、コードセグメントから、
呼び出された関数へ値を戻すことも出来る。

コードセグメントは状態遷移記述と対応しているので、ハードウェア記述
とも相性が良い。

CbCコンパイラは、micro-C base のものと GCC base, TCC base のものが
動いており、実用的に使うことができる。{\tt sourceforge.jp} 上\cite{cbc-sourceforge}で公開されている。


\subsection{ CからCbCへの変換}

Cのスタックを明示的に構成することによりCのプログラムをCbCに
変換することが可能である。

{\small
\begin{verbatim}
        j = g(i+3);

\end{verbatim}
}

のようなCの関数呼び出しは、 \verb+struct f_g0_save+ などの
明示的なスタックの中身を表す構造体を用いて、
{\small
\begin{verbatim}
        struct f_g0_interface *c = 
          (struct f_g0_save *)(sp -= 
          sizeof(struct f_g0_save));
        c = sp;
        c->ret = f_g1;
        goto g(i+3,sp);
\end{verbatim}
}

のような形で、明示的なスタック操作に変換される。これは変換の
一例であり、他の方法、例えばリンクトリストなどを用いても良い。
\verb+f_g1+ は、関数呼び出しの後の継続であり、\verb+g+ では、
{\small
\begin{verbatim}
    code g(int i,stack sp) {
        goto (* ((struct 
         f_g0_save *)sp)->ret)
           (i+4,sp);
    }
\end{verbatim}
}

のように間接的に呼び出される。スタックの中は、継続と
中間変数などを格納する構造体である。スタックそのものは、
これらの構造体を格納するメモリである。

これらの変換は自動的に行うことが出来き、試作変換系を実装した
報告\cite{kono01g}もあるが、実用レベルの変換系はまだ存在しない。
現在は変換と、その後の最適化はは手動で行う必要がある。

\subsection{ CbCでの並列実行記述}

並列実行記述ではタスクの生成と同期機構の記述が問題になる。Verilog
やVHDLなどでも並列タスクの記述があり、POSIX Thread ではライブラリ
コールとして\verb+pthread_create+や\verb+pthread_mutex_lock+などが
ある。

これらの動作記述は、マニュアルやFormal Description で示されている。
例えば、以下のような記述である。
{\tt
The pthread\_mutex\_lock() function locks mutex. If the mutex
is already locked, the calling thread will block until the 
mutex becomes available. 
}

このようは記述は曖昧で誤解を招きやすい。しかし、同期機構の検証
では、これらの動作の正確な意味を知る必要がある。

CbC ではad-hoc な並列記述プリミティブは必要ではなく、自分自身で
並列実行を記述することが可能である。これは、コードセグメントには
隠された情報が存在しないので、実行に必要な情報をすべてInput
interface から取得できるからである。

実行キューを作成しCbC自体でSchedulerを記述することにより、
並列実行を記述する。この場合の並列実行単位はコードセグメン
トとなる。goto 文を規則的にscheduler へのgoto文に書き換える
ことにより、並列実行を記述することが出来る。

以下は、CbCで記述した Dining Philosopher の状態の一部である。
{\small
\begin{verbatim}
    code pickup_rfork(PhilsPtr self)
    {
        if (self->right_fork->owner == NULL) {
                self->right_fork->owner = self;
                goto eating(self);
        } else {
                goto hungry2(self);
        }
    }

\end{verbatim}
}

これを並列実行するためには、

{\small
\begin{verbatim}
    code pickup_rfork(PhilsPtr self, TaskPtr current_task)
    {
        if (self->right_fork->owner == NULL) {
                self->right_fork->owner = self;
                self->next = eating;
                goto scheduler(self, current_task);
        } else {
                self->next = hungry2;
                goto scheduler(self, current_task);
        }
    }

\end{verbatim}
}

という形に記述を変える。Scheduler の実装は例えば、FIFOであれば、

{\small
\begin{verbatim}
    code scheduler(PhilsPtr self, TaskPtr list)
    {
        TaskPtr t = list;
        TaskPtr e;
        list = list->next;
        goto list->phils->next(list->phils,list);
    }

\end{verbatim}
}

という形になる。このように自分自身で並列実行スケジューラを
記述できることがCbCの特徴である。同期機構であるが、ここでは
\verb+right_fork+の排他制御は、
コードセグメントが同時に実行されることはないので、自動的に
保証されている。条件付変数のような待ち合わせを実現したい場合は、
TaskPtr への操作として実現すれば良い。

\subsection{ CbCでの並列実行の実装}

FIFO scheduler を例えば Cell のSPUのactive task queue への
挿入とし、active task queue を各SPUが自律的に取得するように
する(SPU scheduler)と、実際にCbCのコードセグメントを並列実
行することが出来る。

FIFO schedulerと実際の並列実行の同期機構が一致するようにする
のは、一般的には自明ではない。同期機構をコードセグメントで記述
して、SPU scheduler によって実現しても良いし、コードセグメント
内部で、例えば、\verb+pthread_mutex_lock+を呼び出しても良い。