Mercurial > hg > Papers > 2010 > kent-master
view 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 |
line wrap: on
line source
\chapter{Continuation based C (CbC)} \label{chp:cbc} Continuation based C(以下CbC)は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。 我々は様々な視点からこのCbCを使った研究を行っている。本章ではその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}に示した。 \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のコンパイラは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{環境付き継続}\label{ssec:gotowithenv} 環境付き継続を用いる場合、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}% \section{CbCの用途・先行研究} CbCによるプログラム記述の例として本研究室における研究例を紹介する。 \subsection{プログラムの検証} 計算機科学の進歩により、ソフトウェアは大規模かつ複雑なものになっている 。しかしそれに応じて、設計段階において誤りが生じる可能性も高くなってき ており、設計されたシステムに誤りがないことを保証するための論理設計や検 証手法及びデバッグ手法の確立が重要な課題となっている。 どんなプログラムでも状態と状態遷移が存在し、その全てを網羅的に探索する ことでデッドロックなどの望ましくない状態を検出することができる。探索に はさまざまな手法が考えられるが、プログラムを直接状態遷移として記述でき ればこの探索に有利となる。 本研究室の下地らはこの特徴を持つCbCを用いて線形時相論理による検証を提 案し、その有用性を示した。\cite{bib:shimoji} \subsection{ゲームプログラミングにおけるデモンストレーション} 我々は家庭用ゲーム機で動作するゲームプログラムのオープンな開発フレーム ワークに関する研究も行ってきた。家庭用ゲーム機の多くは特殊なアーキテク チャをもち、そのためゲームプログラムには汎用性や冗長性が極めて小さく、 移植が困難という問題がある。 その問題の解決に、ゲームプログラム全体を小規模なプログラムの集合である ``デモンストレーション''に分割するという手法を本研究室の金城らが提案し た。\cite{bib:kinjo},\cite{bib:chiaki} このデモンストレーション手法はプログラムを細かく分割するため、ゲーム機 や組み込みなどの資源が制約された環境ではサブルーチンによるスタック操作 がネックとなる。そのためこの手法ではプログラム分割の実現にCbCを用いて おり、CからCbCへの機械的な変換方法について述べている。 \subsection{ハードウェア記述、ソフトウェアプログラミング} % TODO \subsection{軽量継続を用いたプログラミング} 以上の研究はそれぞれ軽量継続というCbC言語の特徴を利用して進められている。 \section{gccベースコンパイラの現時点の問題点} \label{sec:cbc-problem} 当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも って\bibref{kent-2008}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が実装不能であった。 次章ではこれらの問題の解決を行う。