0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \chapter{Continuation based C (CbC)}
|
|
4
|
2 \label{chapter:CbC}
|
|
17
|
3 CbC では関数ではなく code segment を処理の単位とする. code segment は入力と出力を持ち, CbC では引数が入出力となっている. code segment は次の code segment への遷移で処理を終え, 引数として出力を与える. CbC は C との行き来に環境付き継続を使用する.
|
|
|
4
|
|
|
5 \section{CbC における Code Segment}
|
|
|
6 code segment は CbC における最も基本的な処理単位である. リスト \ref{code_simple} は最も基本的な CbC のコードの一例で, 図 \ref {fig:code_simple}はそれを図示したものである.
|
|
|
7 code segment の宣言は C の関数の構文と同じように行い, 型に \_\_code を用いる. ただし, これは \_\_code 型の戻り値を返すという意味ではない. \_\_code はそれが関数ではなく code segment であることを示すフラグのようなものである.
|
|
|
8
|
|
|
9 現在の code segment から次の code segment への処理の移動は goto の後に code segment 名と引数を並べて記述する リスト \ref{code_simple} の goto cs1(a+b); などがこれにたる. これを軽量継続と呼び, このときの a+b が次のコードセグメントへの出力と成る.
|
|
|
10
|
|
|
11 通常 Secheme の call/cc 等の継続はトップレベルから現在の位置までの位置を環境として保持する. ここで環境は現在のスタックの状態のことを指す.
|
|
|
12 CbC の軽量継続は呼び出し元の環境を持たない. つまりスタックの情報を破棄して処理を続けていくのである.
|
|
|
13
|
|
|
14 リスト \ref{code_simple} の場合, cs0 は cs1 に継続すると cs0 の環境は破棄されてしまうため, cs0 に戻ることは出来ない.
|
|
|
15 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
|
|
|
16 __code cs0(int a, int b){
|
|
|
17 goto cs1(a+b);
|
|
|
18 }
|
|
|
19
|
|
|
20 __code cs1(int c){
|
|
|
21 goto cs2(c);
|
|
|
22 }
|
|
|
23 \end{lstlisting}
|
|
1
|
24
|
|
|
25 \begin{figure}[htpb]
|
|
|
26 \begin{center}
|
|
17
|
27 \scalebox{0.55}{\includegraphics{fig/codesegment.pdf}}
|
|
1
|
28 \end{center}
|
|
17
|
29 \caption{code segment の軽量継続}
|
|
|
30 \label{fig:code_simple}
|
|
1
|
31 \end{figure}
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32
|
|
1
|
33
|
|
17
|
34 もう少し複雑な CbC のプログラムの例が以下のリスト \ref{factorial} である. これは与えられた数値の階乗を算出するプログラムである. このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する.
|
|
1
|
35
|
|
|
36 \begin{lstlisting}[frame=lrbt,label=factorial,caption={\footnotesize 階乗を求める CbC プログラムの例}]
|
|
|
37 __code print_factorial(int prod)
|
|
|
38 {
|
|
|
39 printf("factorial = %d\n",prod);
|
|
|
40 exit(0);
|
|
|
41 }
|
|
|
42
|
|
|
43 __code factorial0(int prod, int x)
|
|
|
44 {
|
|
|
45 if ( x >= 1) {
|
|
|
46 goto factorial0(prod*x, x-1);
|
|
|
47 }else{
|
|
|
48 goto print_factorial(prod);
|
|
|
49 }
|
|
|
50
|
|
|
51 }
|
|
|
52
|
|
|
53 __code factorial(int x)
|
|
|
54 {
|
|
|
55 goto factorial0(1, x);
|
|
|
56 }
|
|
|
57
|
|
|
58 int main(int argc, char **argv)
|
|
|
59 {
|
|
|
60 int i;
|
|
|
61 i = atoi(argv[1]);
|
|
|
62
|
|
|
63 goto factorial(i);
|
|
|
64 }
|
|
|
65 \end{lstlisting}
|
|
|
66
|
|
17
|
67 \begin{figure}[htpb]
|
|
|
68 \begin{center}
|
|
|
69 \scalebox{0.55}{\includegraphics{fig/factorial.pdf}}
|
|
|
70 \end{center}
|
|
|
71 \caption{階乗を求める CbC プログラムの軽量継続図}
|
|
|
72 \label{fig:factorial}
|
|
|
73 \end{figure}
|
|
|
74
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 \section{環境付き継続}
|
|
1
|
76 \label{sec:withEnv}
|
|
|
77 環境付き継続は C との互換性のために必要な機能である. CbC と C の記述を交える際, CbC の code segment から C の関数の呼び出しは問題なく行える. しかし, C の関数から CbC の code segment へと継続する場合, 呼び出し元の環境に戻るための特殊な継続が必要となる. これを環境付き継続と呼ぶ.
|
|
|
78
|
|
17
|
79 環境付き継続を用いる場合, C の関数から code segment へ継続する際に \_\_return, \_\_environment という変数を渡す. \_\_return は \_\_code (*)(return\_type, void*) 型の変数で環境付き継続先が元の環境に戻る際に利用する code segmentを表す. \_\_environment は void** 型の変数で元の関数の環境を表す. リスト\ref{gotoWithTheEnv}では関数 funcB から code segment cs に継続する際に環境付き継続を利用している. cs は funcB から渡された code segment へ継続することで元の C の環境に復帰することが可能となる. 但し復帰先は \_\_return を渡した関数が終了する位置である. このプログラムの例では, 関数 funcA は戻り値として funcB の終わりにある -1 ではなく, 環境付き継続によって渡される 1 を受け取る. 図\ref{fig:gotoWithTheEnv}にこの様子を表した.
|
|
1
|
80
|
|
|
81 \begin{lstlisting}[frame=lrbt,label=gotoWithTheEnv,caption={環境付き継続}]
|
|
|
82 __code cs(__code (*ret)(int, void*), void *env){
|
|
|
83 /* C0 */
|
|
|
84 goto ret(1, env);
|
|
|
85 }
|
|
|
86
|
|
|
87 int funcB(){
|
|
|
88 /* B0 */
|
|
|
89 goto cs(__return, __environment);
|
|
|
90 /* B1 (never reached). */
|
|
|
91 return -1;
|
|
|
92 }
|
|
|
93
|
|
|
94 int funcA(){
|
|
|
95 /* A0 */
|
|
|
96 int retval;
|
|
|
97 retval = funcB();
|
|
|
98 /* A1 */
|
|
|
99 printf("retval = %d\n", retval);
|
|
|
100 /* retval should not be -1 but be 1. */
|
|
17
|
101 return 0;
|
|
1
|
102 }
|
|
|
103
|
|
|
104 \end{lstlisting}
|
|
|
105
|
|
|
106 \begin{figure}[htpb]
|
|
|
107 \begin{center}
|
|
|
108 \scalebox{0.55}{\includegraphics{fig/gotowithenv.pdf}}
|
|
|
109 \end{center}
|
|
|
110 \caption{環境付き継続}
|
|
|
111 \label{fig:gotoWithTheEnv}
|
|
|
112 \end{figure}
|
|
|
113
|
|
|
114
|
|
17
|
115 このように, 環境付き継続を用いることで C, CbC 間の処理の移動が可能になる.
|
|
1
|
116
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 \section{Gears OS サポート}
|
|
5
|
118 \label{sec:Gears}
|
|
17
|
119 Gears OS は当研究室で開発している並列フレームワークで, CbC で記述している. Gears では通常の CbC には存在しない meta code segment, data segment, context 等を用いる. meta code segment は meta computation を行う code segment で, メモリの確保やネットワーク管理等が meta computation にあたる. data segment はデータの単位であり, code segment の入出力になる. context は meta data segment に相当し, code segment や data segment を管理している.
|
|
|
120
|
|
|
121 また meta computation を用いる場合, code segment から code segment への軽量継続の間に meta code segment によって meta computation が行われる. これを図示したのが図 \ref{fig:metaCS} である.
|
|
|
122
|
|
|
123 \begin{figure}[htpb]
|
|
|
124 \begin{center}
|
|
|
125 \scalebox{0.55}{\includegraphics{fig/metaCS.pdf}}
|
|
|
126 \end{center}
|
|
|
127 \caption{meta computation}
|
|
|
128 \label{fig:metaCS}
|
|
|
129 \end{figure}
|
|
|
130
|
|
|
131 これらを現在の CbC の機能のみを用いて記述するとリスト\ref{gears}のようになり, 多くの労力を要する. そのためにこの記述を助ける機能を実装する必要があり, 本研究では以下の機能を提案した.
|
|
1
|
132
|
|
|
133 \begin{itemize}
|
|
|
134 \item code segment から meta code segment への自動接続
|
|
|
135 \item 継続時に context から必要な情報を取得する stub の自動生成
|
|
|
136 \item code segment 内での context の隠蔽
|
|
|
137 \end{itemize}
|
|
|
138
|
|
|
139 \begin{lstlisting}[frame=lrbt,label=gears,caption={Gears OS コード例}]
|
|
|
140 __code meta(struct Context* context, enum Code next) {
|
|
|
141 goto (context->code[next])(context);
|
|
|
142 }
|
|
|
143
|
|
|
144 __code code1_stub(struct Context* context) {
|
|
|
145 goto code1(context, &context->data[Allocate]->allocate);
|
|
|
146 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147
|
|
1
|
148 __code code1(struct Context* context, struct Allocate* allocate) {
|
|
|
149 allocate->size = sizeof(long);
|
|
|
150 allocator(context);
|
|
|
151 goto meta(context, Code2);
|
|
|
152 }
|
|
|
153
|
|
|
154
|
|
|
155 __code code2(struct Context* context, long* count) {
|
|
|
156 *count = 0;
|
|
|
157 goto meta(context, Code3);
|
|
|
158 }
|
|
|
159
|
|
|
160 __code code2_stub(struct Context* context) {
|
|
|
161 goto code2(context, &context->data[Count]->count);
|
|
|
162 }
|
|
|
163 \end{lstlisting}
|
