|
0
|
1 \chapter{Continuation based C (CbC)}
|
|
|
2 \label{chp:cbc}
|
|
|
3 Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。
|
|
2
|
4 我々は様々な視点からこのCbCを使った研究を行っている。本章ではそのCbCの
|
|
|
5 仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。
|
|
0
|
6
|
|
|
7 \section{CbCの要求仕様}
|
|
|
8 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ
|
|
|
9 あり、70 年代、80 年代に設計された言語は矛盾を抱えて来ている。
|
|
|
10
|
|
|
11 オブジェクト指向技術とそれに基づいたJava などの言語が注目されているが
|
|
|
12 、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ
|
|
1
|
13 ベルな言語による記述に比べて、余分な条件判断（Method search, Meta level
|
|
|
14 での実行） を増やしてしまい、コンパクトで高速な応答を期待される
|
|
0
|
15 Real-time 処理や組み込み用途には適さない。
|
|
|
16
|
|
|
17 ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記
|
|
|
18 述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー
|
|
|
19 ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル
|
|
|
20 チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため
|
|
|
21 に既存の言語に対するコンパイラを一々設計し直すことが必要になってきてい
|
|
|
22 る。
|
|
|
23
|
|
|
24 VHDL, Verilog などのハードウェア記述言語は有限状態遷移の中に閉じており
|
|
|
25 、オブジェクト指向などの抽象化とはまったく別なものとなってしまっている。
|
|
|
26
|
|
|
27 このように3 つは全く異なる方向を向いている。コンパイラの自動生成などが
|
|
|
28 重要な研究テーマとなると考えられるが、ハードウェア記述言語、アセンブラ
|
|
|
29 、プログラミング言語の3 つが全く独立したものであれば困難なものになると
|
|
|
30 考えられる。
|
|
|
31
|
|
|
32 そこでCbC はこの3 つを埋めるべく以下のような要求仕様に従って設計された。
|
|
|
33 \begin{itemize}
|
|
|
34 \item ハードウェアとスタックマシンの中間言語
|
|
|
35
|
|
|
36 インタプリタ記述やコンパイラターゲットとして優れること。アーキテク
|
|
|
37 チャ依存性が少ないこと、また、アーキテクチャ依存性をモデル化できる。
|
|
|
38
|
|
|
39 \item C 言語よりも下位の言語
|
|
|
40
|
|
|
41 アセンブラよりも汎用性と記述性に優れC と互換であること。C をCbC に
|
|
|
42 コンパイルでき、ハンドコンパイルの結果を同値なコードに変換できる。
|
|
|
43
|
|
|
44 \item 明確な実行モデル
|
|
|
45
|
|
|
46 C++やProlog のような複雑な実行モデルは好ましくなく、ハードウェアに
|
|
|
47 実行順序の変更を許す範囲を広くする。
|
|
|
48
|
|
|
49 \item 状態遷移を直接記述できる
|
|
|
50
|
|
|
51 Yacc のような表駆動やC のような巨大なswitch 文ではなく直接に状態遷
|
|
|
52 移ができ実行できる。
|
|
|
53
|
|
|
54 \item Thread を実行モデルに内蔵できる
|
|
|
55
|
|
|
56 並列処理記述法ではなく状態遷移として表現できる。
|
|
|
57
|
|
|
58 \item クリティカルパスの最適化
|
|
|
59
|
|
|
60 全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出
|
|
|
61 して最適化できる。
|
|
|
62 \end{itemize}
|
|
|
63
|
|
|
64 これらの仕様はハードウェア記述とソフトウェア記述の両方を同時に行いつつ
|
|
|
65 、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ
|
|
|
66 グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移
|
|
|
67 記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に
|
|
1
|
68 適した言語を作ることを考え、スタックマシンを避けてContinuation（継続）
|
|
0
|
69 が導入されている。
|
|
|
70
|
|
|
71
|
|
|
72 \section{コードセグメントと継続}
|
|
|
73
|
|
|
74 \subsection{call-returnから継続制御へ}
|
|
|
75 Cなどの一般的な手続き型言語では、呼び出した手続きの処理のあと、呼出し
|
|
|
76 元の環境に復帰する。そのためプログラム全体においてスタックが用意され、
|
|
|
77 呼出し元はスタックに復帰先アドレス及び環境を保持しておく事で呼出し先か
|
|
|
78 らの復帰を可能とする。これはcall-return制御と呼ばれるものである（図
|
|
|
79 \ref{fig:call-return}）。
|
|
1
|
80 しかし復帰先が決まっていて環境を受け継ぐことができれば、この
|
|
|
81 call-return制御は図 \ref{fig:continuation}の様に手続き呼び出しの前後で
|
|
|
82 分割する事ができ、スタック操作を伴わないシーケンシャルな呼び出しに変換
|
|
|
83 する事ができる。
|
|
0
|
84 これは継続制御構造と呼ばれている。schemeのcall-with-continuationの実装
|
|
|
85 や、 Java,C++の例外処理、Cのsetjmp()/longjmp()による大域脱出もこの継続
|
|
|
86 制御の一種である。
|
|
|
87 \begin{figure}[hptb]
|
|
|
88 \begin{center}
|
|
|
89 %\includegraphics[width=\textwidth,bb=0 0 595 842]{figures/call-return.pdf}
|
|
|
90 \includegraphics[width=.6\textwidth]{figures/call-return.eps}
|
|
|
91 \end{center}
|
|
|
92 \caption{call-return制御}
|
|
|
93 \label{fig:call-return}
|
|
|
94 \end{figure}
|
|
|
95 \begin{figure}[hptb]
|
|
|
96 \begin{center}
|
|
|
97 \includegraphics[width=.6\textwidth]{figures/continuation.eps}
|
|
|
98 \end{center}
|
|
|
99 \caption{継続制御}
|
|
|
100 \label{fig:continuation}
|
|
|
101 \end{figure}
|
|
|
102
|
|
|
103 CbCはこの継続制御を基本として設計されており、その実現のためにコードセ
|
|
|
104 グメントと軽量継続という概念を用いている。
|
|
|
105 以下ではその二つについて説明する。
|
|
|
106
|
|
|
107 \subsection{コードセグメント}
|
|
|
108 CbCは図\ref{fig:continuation}の様に分割された手続きのそれぞれを一つの
|
|
|
109 処理単位として用い、これを``コードセグメント''(code-segment)と呼ぶ。
|
|
|
110
|
|
|
111 コードセグメントはキーワード``code''を用いてCの関数の様に定義される。
|
|
2
|
112 引数部分はインタフェイスと呼ばれ、継続前のコードセグメントからの出力に
|
|
|
113 あたる。例として、引数で与えられた数xの階乗を求めるプログラムをコード
|
|
0
|
114 \ref{code:factorial}に示した。
|
|
2
|
115
|
|
|
116 \lstinputlisting[caption=CbCプログラムの例（階乗計算）,label=code:factorial]{sources/factorial.cbc}
|
|
0
|
117
|
|
|
118 %コードセグメントは手続きを細かく分割したものなので、Cの関数と比べより
|
|
|
119 %小さい処理単位となる。しかしコードセグメント内部ではCのステートメント
|
|
|
120 %と同様の記述が可能であり、処理単位としてはステートメントより大きいもの
|
|
|
121 %となる。
|
|
|
122
|
|
1
|
123 \subsection{軽量継続(light-weight continuation)}
|
|
0
|
124 コードセグメントはCにおける関数とは違い、呼出し元への復帰は存在しない。
|
|
|
125 そのためコードセグメントの処理の末尾で別のコードセグメントへ継続するこ
|
|
|
126 とになる。CbCではこの継続制御を``軽量継続''(light-weight continuation)
|
|
|
127 と呼ぶ。
|
|
|
128
|
|
|
129 軽量継続はキーワード``goto''のあとにコードセグメント名とそのコードセグ
|
|
|
130 メントのインタフェイスに渡す引数列を並べて記述する。（同じく軽量継続の
|
|
|
131 例がコード \ref{code:factorial}にみられる。）
|
|
|
132
|
|
|
133 %この引数列は継続前のコードセグメントの状態、つまりインタフェイスの値に
|
|
|
134 %よって一意に決まる
|
|
|
135
|
|
2
|
136 この例の様に、プログラムはforやwhileなどのループ制御構造を含んでいない
|
|
|
137 。代わりに、コードセグメント\verb|factorial0|の様に自分自身への軽量継
|
|
|
138 続を用いることで繰り返し処理を実現している。Cでは再帰関数を使うことで
|
|
|
139 同じことを行えるが、そこにはスタックの拡張という処理が入る。しかしCbC
|
|
|
140 ではスタックの拡張は行われず、元の環境に戻ることはない。
|
|
0
|
141
|
|
|
142
|
|
|
143 \section{状態遷移に適した言語}
|
|
|
144 Continuation based Cは値を返すプログラムよりも、状態遷移記述に適している。
|
|
|
145
|
|
|
146 従来の言語での状態遷移記述は
|
|
|
147 \begin{itemize}
|
|
|
148 \item 表を使った状態遷移インタプリタ
|
|
|
149 \item 巨大なswitch文
|
|
|
150 \end{itemize}
|
|
|
151 などが用いられてきた。しかしこれらは記述性が悪く、効率も良くない。
|
|
|
152
|
|
|
153 表を使った状態遷移インタプリタはコンパイラ言語とは考えられない。また、
|
|
|
154 それをハードウェア記述に落とすことは難しい。
|
|
|
155
|
|
|
156 巨大なswitch文は、コンパイルが複雑になり、適切な最適化を行うことが難し
|
|
|
157 い。また、人間が読む場合にも読みやすいとは言えない。
|
|
|
158
|
|
|
159 CbCは元々状態遷移を直接記述することを目的として設計されており、
|
|
|
160 手続きの様に環境の保持を伴わないため、その時々に実行中のコードセグメン
|
|
|
161 トとその引数を直接プログラムの状態とみなす事ができる。
|
|
|
162
|
|
|
163 特にゲームやGUIを用いたプログラムなどでは状態遷移記述が多用されており
|
|
|
164 、そのようなプログラムでは CbCを状態記述言語として使うことにより、直接
|
|
|
165 実行による実行の高速化と既存の言語と状態遷移記述の整合性の向上をはかる
|
|
|
166 ことができる。
|
|
|
167
|
|
|
168
|
|
|
169 \section{C with Continuation}
|
|
2
|
170 数学的検証や組み込み用途を目的として提案されたCbCであるが、既存のソフ
|
|
|
171 トウェアやシステムは膨大な数にのぼり、これらをCbCに置き換えるのは無理
|
|
|
172 がある。そのため、少なくともソースコードのレベルでCとの互換性を持つこ
|
|
|
173 とが望ましい。
|
|
|
174 Continuation based Cの名のとおり、CbCからCの関数の呼び出しは問題なく行
|
|
|
175 える。しかしCbCをCと相互に利用するためには、Cの関数から継続を行った場
|
|
|
176 合に元の環境に戻るための、特殊な継続を導入する必要がある。これを環境付
|
|
|
177 き継続と呼ぶ。
|
|
0
|
178
|
|
|
179 この環境付き継続を導入した言語はC with Continuation(CwC)と呼ばれ、Cと
|
|
|
180 CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え
|
|
|
181 られるので（図 \ref{fig:cwc}）、CwCのコンパイラをCbCに使用する事ができ
|
|
|
182 る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc
|
|
1
|
183 共に実際にはCwCのコンパイラとして実装されている。すなわち、Cの関数や
|
|
|
184 forなどを使うことができ、mcでは環境付き継続も実装されている。
|
|
0
|
185
|
|
|
186 \begin{figure}[htpb]
|
|
|
187 \begin{center}
|
|
|
188 \includegraphics[width=.6\textwidth]{figures/CwC.eps}
|
|
|
189 \end{center}
|
|
|
190 \caption{C with Continuationとそのサブセット}
|
|
|
191 \label{fig:cwc}
|
|
|
192 \end{figure}
|
|
|
193
|
|
|
194
|
|
2
|
195 \subsection{環境付き継続}\label{ssec:gotowithenv}
|
|
0
|
196 環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に
|
|
|
197 \_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ
|
|
1
|
198 ード\ref{code:cbcreturn}参照。
|
|
0
|
199 継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する
|
|
|
200 事で元のCの環境に復帰することが可能となる。
|
|
|
201 ただし復帰先は\_\_returnを参照した関数が終了する位置である。
|
|
1
|
202 図\ref{fig:cbcreturn}にこの様子を表した。
|
|
2
|
203 \lstinputlisting
|
|
|
204 [caption=\_\_returnの例,
|
|
|
205 label=code:cbcreturn,
|
|
|
206 emph=\_\_return]
|
|
1
|
207 {sources/cbcreturn.cbc}
|
|
|
208 この様な形にすることでcode segment側では関数から呼ばれたか、コードセグ
|
|
|
209 メントからの継続かを考慮する必要がない。また、\verb|funcA|からもその内
|
|
|
210 部でコードセグメントが使われていることを隠蔽できる。
|
|
|
211 \begin{figure}[htpb]
|
|
|
212 \begin{center}
|
|
|
213 \includegraphics[width=.6\textwidth]{figures/cbcreturn.eps}
|
|
|
214 \end{center}
|
|
|
215 \caption{\_\_returnの例}
|
|
|
216 \label{fig:cbcreturn}
|
|
|
217 \end{figure}%
|
|
0
|
218
|
|
|
219
|
|
|
220
|
|
|
221
|
|
2
|
222
|
|
|
223 \section{CbCの用途・先行研究}
|
|
|
224 CbCによるプログラム記述の例として本研究室における研究例を紹介する。
|
|
|
225
|
|
|
226 \subsection{プログラムの検証}
|
|
|
227 計算機科学の進歩により、ソフトウェアは大規模かつ複雑なものになっている
|
|
|
228 。しかしそれに応じて、設計段階において誤りが生じる可能性も高くなってき
|
|
|
229 ており、設計されたシステムに誤りがないことを保証するための論理設計や検
|
|
|
230 証手法及びデバッグ手法の確立が重要な課題となっている。
|
|
|
231
|
|
|
232 どんなプログラムでも状態と状態遷移が存在し、その全てを網羅的に探索する
|
|
|
233 ことでデッドロックなどの望ましくない状態を検出することができる。探索に
|
|
|
234 はさまざまな手法が考えられるが、プログラムを直接状態遷移として記述でき
|
|
|
235 ればこの探索に有利となる。
|
|
|
236
|
|
|
237 本研究室の下地らはこの特徴を持つCbCを用いて線形時相論理による検証を提
|
|
|
238 案し、その有用性を示した。\cite{bib:shimoji}
|
|
|
239
|
|
|
240
|
|
|
241 \subsection{ゲームプログラミングにおけるデモンストレーション}
|
|
|
242 我々は家庭用ゲーム機で動作するゲームプログラムのオープンな開発フレーム
|
|
|
243 ワークに関する研究も行ってきた。家庭用ゲーム機の多くは特殊なアーキテク
|
|
|
244 チャをもち、そのためゲームプログラムには汎用性や冗長性が極めて小さく、
|
|
|
245 移植が困難という問題がある。
|
|
|
246
|
|
|
247 その問題の解決に、ゲームプログラム全体を小規模なプログラムの集合である
|
|
|
248 ``デモンストレーション''に分割するという手法を本研究室の金城らが提案し
|
|
|
249 た。\cite{bib:kinjo},\cite{bib:chiaki}
|
|
|
250
|
|
|
251 このデモンストレーション手法はプログラムを細かく分割するため、ゲーム機
|
|
|
252 や組み込みなどの資源が制約された環境ではサブルーチンによるスタック操作
|
|
|
253 がネックとなる。そのためこの手法ではプログラム分割の実現にCbCを用いて
|
|
|
254 おり、CからCbCへの機械的な変換方法について述べている。
|
|
|
255
|
|
|
256
|
|
|
257 \subsection{ハードウェア記述、ソフトウェアプログラミング}
|
|
|
258 % TODO
|
|
|
259
|
|
|
260 \subsection{軽量継続を用いたプログラミング}
|
|
|
261 以上の研究はそれぞれ軽量継続というCbC言語の特徴を利用して進められている。
|
|
|
262
|
|
0
|
263
|
|
|
264
|
|
|
265 \section{gccベースコンパイラの現時点の問題点}
|
|
1
|
266 \label{sec:cbc-problem}
|
|
0
|
267
|
|
|
268 当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ
|
|
|
269 り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも
|
|
2
|
270 って\bibref{kent-2008}GCCによる実装が行われた。この研究によりコードセグメント、継
|
|
0
|
271 続制御構造などは実装され、一通りのCbCプログラムのコンパイルが可能とな
|
|
|
272 った。
|
|
|
273
|
|
|
274 しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制
|
|
|
275 御構造の実装方法の影響により、いくつかの問題が発生している。
|
|
|
276 以下にその問題点を列記する。
|
|
|
277 %この問題に対せる解決を \ref{chp:impl}章にて説明する。
|
|
|
278
|
|
|
279 \begin{itemize}
|
|
|
280 \item 環境付き継続
|
|
|
281
|
|
|
282 これは未実装の機能である。
|
|
|
283 変更された新しい仕様の方に対応したい。
|
|
|
284
|
|
|
285 \item 並列代入
|
|
|
286
|
|
|
287 CbCでは現在のコードセグメントのインタフェイスと次に継続するコード
|
|
1
|
288 セグメントの引数は同じメモリスペース（もしくはレジスタ）に格納して
|
|
|
289 いる。そのためコード\ref{code:paralell_example}のように変数の値を
|
|
|
290 入れ替えるような処理では並列代入が行われることになる。
|
|
0
|
291 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる
|
|
|
292 複雑な並列代入ではバグが見つかっている。
|
|
2
|
293 \lstinputlisting
|
|
|
294 [caption=並列代入の例,
|
|
|
295 label=code:parallel-example]
|
|
0
|
296 {sources/parallel-example.cbc}
|
|
|
297
|
|
|
298 \item PowerPCにおける間接継続(indirect goto)
|
|
|
299
|
|
|
300 CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し
|
|
|
301 (indirect call)の様にコードセグメントポインタを用いた間接継続が可
|
|
|
302 能である。
|
|
|
303 \lstinputlisting[
|
|
1
|
304 caption=間接継続の例（2つめのgoto文）,
|
|
0
|
305 label=code:indirect-example]
|
|
|
306 {sources/indirect-example.cbc}
|
|
|
307 しかしPowerPCアーキテクチャでは最適化の問題でこの機能が働かないこ
|
|
|
308 とが分かっている。
|
|
|
309
|
|
1
|
310 間接継続はCbCでのプログラミングには必須であり、また本研究室の主要
|
|
|
311 プロジェクトであるCeriumはPS3をメインターゲットとしているため、こ
|
|
|
312 の対応は必須のものである。
|
|
|
313
|
|
0
|
314 \item プロトタイプ宣言
|
|
|
315
|
|
|
316 Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。
|
|
|
317 しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記
|
|
|
318 述という性質上、プログラムを記述する際は上から下に実行順にコードセ
|
|
|
319 グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大
|
|
|
320 な数になる。
|
|
1
|
321 これはプログラミングにおける障害とも言える。
|
|
0
|
322
|
|
|
323 \item x86での継続制御のオーバヘッド
|
|
|
324
|
|
|
325 mc実装ではx86アーキテクチャでのコードセグメント継続の際には引数を
|
|
|
326 レジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォルト
|
|
|
327 では全ての引数をメモリに格納する。コードセグメントは関数をベースに
|
|
|
328 作られているため、このABIに引きずられ実効速度に影響をもたらす。
|
|
|
329
|
|
|
330
|
|
|
331 \end{itemize}
|
|
|
332
|
|
1
|
333 これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ
|
|
|
334 ていた。
|
|
|
335 %特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。
|
|
|
336 次章ではこれらの問題の解決を行う。
|
|
0
|
337
|
|
1
|
338
|
|
|
339
|
