\chapter{Continuation based C (CbC)}
\label{chp:cbc}

Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも
上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを用いた
研究を行っている。本章ではそのCbCの仕様と現在の状況について説明し、ま
たCbCを用いた研究例についても紹介する。

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

オブジェクト指向技術とそれに基づいたJavaなどの言語が注目されテイルが、
Javaではガベージコレクタや実行時コンパイルにより、余分
な処理が必要となる。そのため軽量かつ高速な応答が要求される Real-time処
理や組込み用途には適さない。この用途にはハードウェアに近い記述が要求さ
れる。

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

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

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

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

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

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

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

  \item 明確な実行モデル

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

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

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

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

    %並列処理記述法ではなく状態遷移として表現できる。
    状態遷移記述とCbC上のスケジューラ実装によりスレッドを実現可能にす
    る。

  \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}

\subsection{Schemeにおける継続制御}
継続とは一般的には「現在の処理を続行するための情報」と解釈されている。
継続制御はその情報をプログラム記述で操作するための構文である。
例としてSchemeでの継続の使用をコード\ref{code:scheme-cont}に挙げる。

%\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/
\lstinputlisting
  [caption=Schemeでの継続制御の例,
   label=code:scheme-cont,
   language=Lisp,
   morekeywords={cont,cont-test},
   emph={gosh},
   emphstyle=\bfseries\underbar]
  {sources/scheme-cont-out.scmout}

この例では関数\verb|cont-test|内にて\verb|call/cc|を呼ぶことで、現在の
計算処理の``継続''を関数として変数\verb|cont|に保持している。

その後、\verb|(cont)|という命令でその関数を実行すると、contが代入され
た位置に処理が復帰する。そのため、直前の``before''は出力されずに
``after''が出力されていることが分かる。\verb|cont|では関数の継続処理だ
けでなく、引数などの環境も一緒に保持しているので、この\verb|cont|は呼
ばれる度に \verb|i|カウントアップし、その値を返すことになる。


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

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

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

\lstinputlisting[caption=CbCプログラムの例（階乗計算）,label=code:factorial]{sources/factorial.cbc}

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

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

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

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

この例の様に、プログラムはforやwhileなどのループ制御構造を含んでいない
。代わりに、コードセグメント\verb|factorial0|の様に自分自身への軽量継
続を用いることで繰り返し処理を実現している。Cでは再帰関数を使うことで
同じことを行えるが、そこにはスタックの拡張という処理が入る。しかしCbC
ではスタックの拡張は行われず、元の環境に戻ることはない。


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

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

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

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

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

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


\section{C with Continuation}
数学的検証や組み込み用途を目的として提案されたCbCであるが、既存のソフ
トウェアやシステムは膨大な数にのぼり、これらをCbCに置き換えるのは無理
がある。そのため、少なくともソースコードのレベルでCとの互換性を持つこ
とが望ましい。
Continuation based Cの名のとおり、CbCからCの関数の呼び出しは問題なく行
える。しかしCbCをCと相互に利用するためには、Cの関数から継続を行った場
合に元の環境に戻るための、特殊な継続を導入する必要がある。これを``環境
付き継続''と呼ぶ。

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

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


\subsection{環境付き継続}\label{ssec:gotowithenv}
環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に
\verb|__return|という変数で表される特殊なコードセグメントポインタを渡
す。コード\ref{code:cbcreturn}では関数\verb|funcB|からコードセグメント
\verb|cs|に継続する際に\verb|__return|を渡している。
継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する
事で元のCの環境に復帰することが可能となる。
ただし復帰先は\verb|__return|を参照した関数が終了する位置である。この
プログラムの例では、関数\verb|funcA|からは\verb|funcB|が正常に終了した
ように見える。図\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}%

環境付き継続は実際にはCにおける\verb|setjmp()/longjmp()|とほぼ同じ処理であ
る。この二つの関数はCで継続を実現するために用いられる。

例としてコード \ref{code:setjmp}を挙げる。このコードでは\verb|setfunc|
内で \verb|setjmp|を使用している。\verb|setjmp|は通常は0を返すため、if
文の内部は実行されないが、その後\verb|longjmp|が実行されると、関連する
\verb|setjmp|が呼び出された環境に``継続''し、非零を返すためif文の中が
実行されることになる。この時、\verb|longjmp|の呼出側（この例では
\verb|jmpfunc|）の環境は失われる。

環境付き継続もこの動作によく似ており、if文内でreturnのみを記述すること
に相当する。

\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/
\lstinputlisting
  [caption=setjmp/longjmpの例,
   basicstyle=\footnotesize\ttfamily,%
   commentstyle=\footnotesize\itshape\rmfamily,%
   label=code:setjmp,
   emph={setjmp,longjmp}]
  {sources/setjmp.c}
\lstset{morecomment=[s]{/*}{*/}} % /*元に戻す*/



\section{CbCの用途・先行研究}
CbCによるプログラム記述の例として本研究室における研究例を紹介する。

\subsection{プログラムの検証}
計算機科学の進歩により、ソフトウェアは大規模かつ複雑なものになっている
。しかしそれに応じて、設計段階において誤りが生じる可能性も高くなってき
ており、設計されたシステムに誤りがないことを保証するための論理設計や検
証手法及びデバッグ手法の確立が重要な課題となっている。

どんなプログラムでも状態と状態遷移が存在し、その全てを網羅的に探索する
ことでデッドロックなどの望ましくない状態を検出することができる。探索に
はさまざまな手法が考えられるが、プログラムを直接状態遷移として記述でき
ればこの探索に有利となる。

本研究室の下地らはこの特徴を持つCbCを用いて線形時相論理による検証を提
案し、その有用性を示した。\cite{bib:shimoji-2006},
\cite{bib:shimoji-2007}


\subsection{ゲームプログラミングにおけるデモンストレーション}
我々は家庭用ゲーム機で動作するゲームプログラムのオープンな開発フレーム
ワークに関する研究も行ってきた。家庭用ゲーム機の多くは特殊なアーキテク
チャをもち、そのためゲームプログラムには汎用性や冗長性が極めて小さく、
移植が困難という問題がある。

その問題の解決に、ゲームプログラム全体を小規模なプログラムの集合である
``デモンストレーション''に分割することで移植性を向上する手法を本研究室
の金城らが提案した。\cite{bib:kinjo-master-2005},\cite{bib:akira-2008}

このデモンストレーション手法はプログラムを細かく分割するため、ゲーム機
や組み込みなどの資源が制約された環境ではサブルーチンによるスタック操作
がネックとなる。そのためこの手法ではプログラム分割の実現にCbCを用いて
おり、CからCbCへの機械的な変換方法について述べている。


%\subsection{CbCによる分散プログラミング}
%現在の分散プログラミングには様々な手法がある。ネットワークAPIを直接使
%う方法、SOAPやMPIなどのライブラリ、Telescripに見られる言語仕様への埋め
%込みなどがあった。これらは通信に関する複雑なセマンティクスを実現する手
%段といえる。
% TODO 分散プログラミング


\section{CbCコンパイラの現状と本研究における目標}
\label{sec:cbc-problem}

\subsection{micro-cとGCC}

CbCのコンパイラには二つの実装が用意されている。一つは2000年に当研究室
の河野らにより開発された、micro-cというCのコンパイラをベースとしたもの
である。こちらは現在安定して動作しており、アーキテクチャは PowerPC,
x86, MIPS, ARMなどに対応している。もう一つは2008年に開発された、GCCを
ベースとしたコンパイラである。 \cite{bib:kent-2008}

GCCは元より多数のアーキテクチャに対応しており、高機能な最適化も備えて
いる。これらをCbCでも活用したいという要望からコンパイラ環境の移植が行
われた。

\subsection{本研究における目標}\label{sec:gcc-problems}

この時の実装でコードセグメント、継続制御構造などは実装され、一通りの
CbCプログラムのコンパイルが可能となった。

本研究ではこのGCCベースのコンパイラをより実用的なCbCコンパイラとすべく
以下の項目を目標とする。

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

    Cとの互換性のための制御構造である環境付き継続を実装する。

  \item 並列代入
    
    これまでGCCベースのコンパイラでは、実装方法の影響から継続制御に一
    部制限が存在した。これは実行中のコードセグメントの引数と継続制御に
    渡す引数の順序が入れ替わる場合等に継続が行えないという制限である。

    並列代入を行うことで引数順序の影響はなくなり、この制限を排除できる。

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

    Cでの関数ポインタを用いた間接呼び出し(indirect call)の様に、CbCで
    用いる継続制御においても、コードセグメントポインタを用いたメモリ参
    照による間接的な継続が可能である。これを``間接継続''と呼んでいる。
    コード\ref{code:indirect-example}のcodepointerへの継続が間接継続に
    当たる。
    \lstinputlisting[
      caption=間接継続の例（2つめのgoto文）,
      label=code:indirect-example]
      {sources/indirect-example.cbc}
    しかしPowerPCアーキテクチャでは最適化の問題からこの間接継続がこれ
    まで制限されていた。

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

  \item プロトタイプ宣言の自動化
   
    Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っているが、
    CbCでは返り値が存在しないなど、あまり重要な意味をなさない。また、
    micro-cではこれを極力排除するよう設計されているため、既存の CbCプ
    ログラムとのソースコードレベルでの互換性が薄れてしまう。

    プロトタイプを自動生成することにより、この互換性を向上させる。

  \item x86での継続制御の最適化

    x86では、Cの関数呼び出し全ての引数をメモリに格納する。コードセグメ
    ントは関数をベースに作られているため、このABIに引きずられ実効速度
    に影響をもたらしている。引数の一部をレジスタに格納することで、x86
    における継続処理の高速化を行う。

  \item メンテナンス性の向上

    GCCのソースコードは200万行にものぼる。CbCコンパイラで修正するソー
    スコードはそのごく一部であるが、GCCのアップデートによる修正はCbC用
    のソースコードにも大きな影響をもたらす。
    GCCの最新リリースに追従するためには、アップデートも考慮し、洗練さ
    れたメンテナンス方法が必要になる。

\end{itemize}

%特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。
\ref{chp:impl}章ではこれらの項目の実装を行う。