Mercurial > hg > Papers > 2010 > kent-master
comparison cbc.tex @ 2:50e23a4b2f40
add many files.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 05 Feb 2010 10:00:05 +0900 |
parents | aa09c34b90d3 |
children | d2999e94b97d |
comparison
equal
deleted
inserted
replaced
1:aa09c34b90d3 | 2:50e23a4b2f40 |
---|---|
1 \chapter{Continuation based C (CbC)} | 1 \chapter{Continuation based C (CbC)} |
2 \label{chp:cbc} | 2 \label{chp:cbc} |
3 Continuation based C(以下CbC)は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。 | 3 Continuation based C(以下CbC)は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。 |
4 我々は\ref{chp:first}章に述べたように様々な視点からこのCbCを使った研究を行っている。 | 4 我々は様々な視点からこのCbCを使った研究を行っている。本章ではそのCbCの |
5 本章ではそのCbCの仕様について説明する。 | 5 仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。 |
6 | |
7 | 6 |
8 \section{CbCの要求仕様} | 7 \section{CbCの要求仕様} |
9 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ | 8 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ |
10 あり、70 年代、80 年代に設計された言語は矛盾を抱えて来ている。 | 9 あり、70 年代、80 年代に設計された言語は矛盾を抱えて来ている。 |
11 | 10 |
108 \subsection{コードセグメント} | 107 \subsection{コードセグメント} |
109 CbCは図\ref{fig:continuation}の様に分割された手続きのそれぞれを一つの | 108 CbCは図\ref{fig:continuation}の様に分割された手続きのそれぞれを一つの |
110 処理単位として用い、これを``コードセグメント''(code-segment)と呼ぶ。 | 109 処理単位として用い、これを``コードセグメント''(code-segment)と呼ぶ。 |
111 | 110 |
112 コードセグメントはキーワード``code''を用いてCの関数の様に定義される。 | 111 コードセグメントはキーワード``code''を用いてCの関数の様に定義される。 |
113 例として引数で与えられた数xの階乗を求めるプログラムをコード | 112 引数部分はインタフェイスと呼ばれ、継続前のコードセグメントからの出力に |
113 あたる。例として、引数で与えられた数xの階乗を求めるプログラムをコード | |
114 \ref{code:factorial}に示した。 | 114 \ref{code:factorial}に示した。 |
115 引数部分はインタフェイスと呼ばれ、継続前のコードセグメントからの出力に | 115 |
116 あたる。 | 116 \lstinputlisting[caption=CbCプログラムの例(階乗計算),label=code:factorial]{sources/factorial.cbc} |
117 | 117 |
118 %コードセグメントは手続きを細かく分割したものなので、Cの関数と比べより | 118 %コードセグメントは手続きを細かく分割したものなので、Cの関数と比べより |
119 %小さい処理単位となる。しかしコードセグメント内部ではCのステートメント | 119 %小さい処理単位となる。しかしコードセグメント内部ではCのステートメント |
120 %と同様の記述が可能であり、処理単位としてはステートメントより大きいもの | 120 %と同様の記述が可能であり、処理単位としてはステートメントより大きいもの |
121 %となる。 | 121 %となる。 |
128 | 128 |
129 軽量継続はキーワード``goto''のあとにコードセグメント名とそのコードセグ | 129 軽量継続はキーワード``goto''のあとにコードセグメント名とそのコードセグ |
130 メントのインタフェイスに渡す引数列を並べて記述する。(同じく軽量継続の | 130 メントのインタフェイスに渡す引数列を並べて記述する。(同じく軽量継続の |
131 例がコード \ref{code:factorial}にみられる。) | 131 例がコード \ref{code:factorial}にみられる。) |
132 | 132 |
133 | |
134 %この引数列は継続前のコードセグメントの状態、つまりインタフェイスの値に | 133 %この引数列は継続前のコードセグメントの状態、つまりインタフェイスの値に |
135 %よって一意に決まる | 134 %よって一意に決まる |
136 | 135 |
137 \lstinputlisting[caption=コードセグメント例(階乗計算),label=code:factorial]{sources/factorial.cbc} | 136 この例の様に、プログラムはforやwhileなどのループ制御構造を含んでいない |
137 。代わりに、コードセグメント\verb|factorial0|の様に自分自身への軽量継 | |
138 続を用いることで繰り返し処理を実現している。Cでは再帰関数を使うことで | |
139 同じことを行えるが、そこにはスタックの拡張という処理が入る。しかしCbC | |
140 ではスタックの拡張は行われず、元の環境に戻ることはない。 | |
138 | 141 |
139 | 142 |
140 \section{状態遷移に適した言語} | 143 \section{状態遷移に適した言語} |
141 Continuation based Cは値を返すプログラムよりも、状態遷移記述に適している。 | 144 Continuation based Cは値を返すプログラムよりも、状態遷移記述に適している。 |
142 | 145 |
162 実行による実行の高速化と既存の言語と状態遷移記述の整合性の向上をはかる | 165 実行による実行の高速化と既存の言語と状態遷移記述の整合性の向上をはかる |
163 ことができる。 | 166 ことができる。 |
164 | 167 |
165 | 168 |
166 \section{C with Continuation} | 169 \section{C with Continuation} |
167 \ref{chp:intro}でも述べたようにCbCはCと互換性を持つことが望ましい。 | 170 数学的検証や組み込み用途を目的として提案されたCbCであるが、既存のソフ |
168 CbCをCと相互に利用するためには、Cの関数から継続を行った場合に元の環境 | 171 トウェアやシステムは膨大な数にのぼり、これらをCbCに置き換えるのは無理 |
169 に戻るための、特殊な継続を導入する必要がある。これを環境付き継続と呼ぶ。 | 172 がある。そのため、少なくともソースコードのレベルでCとの互換性を持つこ |
173 とが望ましい。 | |
174 Continuation based Cの名のとおり、CbCからCの関数の呼び出しは問題なく行 | |
175 える。しかしCbCをCと相互に利用するためには、Cの関数から継続を行った場 | |
176 合に元の環境に戻るための、特殊な継続を導入する必要がある。これを環境付 | |
177 き継続と呼ぶ。 | |
170 | 178 |
171 この環境付き継続を導入した言語はC with Continuation(CwC)と呼ばれ、Cと | 179 この環境付き継続を導入した言語はC with Continuation(CwC)と呼ばれ、Cと |
172 CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え | 180 CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え |
173 られるので(図 \ref{fig:cwc})、CwCのコンパイラをCbCに使用する事ができ | 181 られるので(図 \ref{fig:cwc})、CwCのコンパイラをCbCに使用する事ができ |
174 る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc | 182 る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc |
182 \caption{C with Continuationとそのサブセット} | 190 \caption{C with Continuationとそのサブセット} |
183 \label{fig:cwc} | 191 \label{fig:cwc} |
184 \end{figure} | 192 \end{figure} |
185 | 193 |
186 | 194 |
187 \subsection{環境付き継続} | 195 \subsection{環境付き継続}\label{ssec:gotowithenv} |
188 環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に | 196 環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に |
189 \_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ | 197 \_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ |
190 ード\ref{code:cbcreturn}参照。 | 198 ード\ref{code:cbcreturn}参照。 |
191 継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する | 199 継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する |
192 事で元のCの環境に復帰することが可能となる。 | 200 事で元のCの環境に復帰することが可能となる。 |
193 ただし復帰先は\_\_returnを参照した関数が終了する位置である。 | 201 ただし復帰先は\_\_returnを参照した関数が終了する位置である。 |
194 図\ref{fig:cbcreturn}にこの様子を表した。 | 202 図\ref{fig:cbcreturn}にこの様子を表した。 |
195 \lstinputlisting[ | 203 \lstinputlisting |
196 caption=\_\_returnの例, | 204 [caption=\_\_returnの例, |
197 label=code:cbcreturn, | 205 label=code:cbcreturn, |
198 emph=\_\_return] | 206 emph=\_\_return] |
199 {sources/cbcreturn.cbc} | 207 {sources/cbcreturn.cbc} |
200 この様な形にすることでcode segment側では関数から呼ばれたか、コードセグ | 208 この様な形にすることでcode segment側では関数から呼ばれたか、コードセグ |
201 メントからの継続かを考慮する必要がない。また、\verb|funcA|からもその内 | 209 メントからの継続かを考慮する必要がない。また、\verb|funcA|からもその内 |
202 部でコードセグメントが使われていることを隠蔽できる。 | 210 部でコードセグメントが使われていることを隠蔽できる。 |
203 \begin{figure}[htpb] | 211 \begin{figure}[htpb] |
209 \end{figure}% | 217 \end{figure}% |
210 | 218 |
211 | 219 |
212 | 220 |
213 | 221 |
214 %CbCにおける環境付き継続の構文は幾度か改訂されている。 | 222 |
215 % TODO _CbC_return | 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 | |
216 | 263 |
217 | 264 |
218 \section{gccベースコンパイラの現時点の問題点} | 265 \section{gccベースコンパイラの現時点の問題点} |
219 \label{sec:cbc-problem} | 266 \label{sec:cbc-problem} |
220 | 267 |
221 当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ | 268 当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ |
222 り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも | 269 り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも |
223 って\ref{}GCCによる実装が行われた。この研究によりコードセグメント、継 | 270 って\bibref{kent-2008}GCCによる実装が行われた。この研究によりコードセグメント、継 |
224 続制御構造などは実装され、一通りのCbCプログラムのコンパイルが可能とな | 271 続制御構造などは実装され、一通りのCbCプログラムのコンパイルが可能とな |
225 った。 | 272 った。 |
226 | 273 |
227 しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制 | 274 しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制 |
228 御構造の実装方法の影響により、いくつかの問題が発生している。 | 275 御構造の実装方法の影響により、いくつかの問題が発生している。 |
241 セグメントの引数は同じメモリスペース(もしくはレジスタ)に格納して | 288 セグメントの引数は同じメモリスペース(もしくはレジスタ)に格納して |
242 いる。そのためコード\ref{code:paralell_example}のように変数の値を | 289 いる。そのためコード\ref{code:paralell_example}のように変数の値を |
243 入れ替えるような処理では並列代入が行われることになる。 | 290 入れ替えるような処理では並列代入が行われることになる。 |
244 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる | 291 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる |
245 複雑な並列代入ではバグが見つかっている。 | 292 複雑な並列代入ではバグが見つかっている。 |
246 \lstinputlisting[ | 293 \lstinputlisting |
247 caption=並列代入の例, | 294 [caption=並列代入の例, |
248 label=code:parallel-example] | 295 label=code:parallel-example] |
249 {sources/parallel-example.cbc} | 296 {sources/parallel-example.cbc} |
250 | 297 |
251 \item PowerPCにおける間接継続(indirect goto) | 298 \item PowerPCにおける間接継続(indirect goto) |
252 | 299 |
253 CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し | 300 CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し |