|
0
|
1 \chapter{Continuation based C (CbC)}
|
|
|
2 \section{Continuation based C (CbC)}
|
|
|
3 CbC は 処理を Code Gear とした単位を用いて記述するプログラミング言語である。
|
|
6
|
4 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
|
|
|
5 Code Gear から次の Code Gear へと goto による継続で遷移で処理を行い、引数として出力を与える。
|
|
0
|
6 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
|
|
|
7
|
|
|
8 \begin{figure}[htpb]
|
|
|
9 \begin{center}
|
|
|
10 \scalebox{0.7}{\includegraphics{fig/codesegment.pdf}}
|
|
|
11 \end{center}
|
|
|
12 \caption{goto による code gear 間の継続}
|
|
|
13 \label{fig:cs}
|
|
|
14 \end{figure}
|
|
|
15
|
|
|
16 \section{Code Gear}
|
|
|
17 Code Gear は CbC における最も基本的な処理単位である。
|
|
|
18 リスト \ref{code_simple} は最も基本的な CbC のコードの一例で、図 \ref{fig:code_simple}はそれを図示したものである。
|
|
|
19 CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
|
|
6
|
20 ただし、これは \_\_code 型の戻り値を返すという意味ではなく、Code Gear であることを示すフラグのようなものである。
|
|
|
21
|
|
4
|
22 Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
|
|
|
23 goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。
|
|
6
|
24 リスト \ref{code_simple} の goto cs1(a+b); などがこれにたる。
|
|
|
25 この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
|
|
4
|
26 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
|
|
|
27 したがってこれを軽量継続と呼ぶこともある。
|
|
0
|
28 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
|
|
|
29
|
|
|
30 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
|
|
|
31 __code cs0(int a, int b){
|
|
|
32 goto cs1(a+b);
|
|
|
33 }
|
|
|
34
|
|
|
35 __code cs1(int c){
|
|
|
36 goto cs2(c);
|
|
|
37 }
|
|
|
38 \end{lstlisting}
|
|
|
39
|
|
|
40 \begin{figure}[htpb]
|
|
|
41 \begin{center}
|
|
|
42 \scalebox{0.55}{\includegraphics{fig/codesegment2.pdf}}
|
|
|
43 \end{center}
|
|
|
44 \caption{code segment の軽量継続}
|
|
|
45 \label{fig:code_simple}
|
|
|
46 \end{figure}
|
|
|
47
|
|
4
|
48 もう少し複雑な CbC のプログラムの例が以下のリスト \ref{factorial} である。
|
|
|
49 これは与えられた数値の階乗を算出するプログラムである。
|
|
|
50 このコードの factorial0 という Code Gear に注目すると、条件判別を行い、その結果に応じて自分自身への再帰的な継続を行うか別の Code Gear への継続を行うかという処理を行っていることがわかる。
|
|
|
51 CbC ではこのようにしてループ処理を制御する。
|
|
|
52
|
|
|
53 \begin{lstlisting}[frame=lrbt,label=factorial,caption={\footnotesize 階乗を求める CbC プログラムの例}]
|
|
|
54 __code print_factorial(int prod)
|
|
|
55 {
|
|
|
56 printf("factorial = %d\n",prod);
|
|
|
57 exit(0);
|
|
|
58 }
|
|
|
59
|
|
|
60 __code factorial0(int prod, int x)
|
|
|
61 {
|
|
|
62 if ( x >= 1) {
|
|
|
63 goto factorial0(prod*x, x-1);
|
|
|
64 }else{
|
|
|
65 goto print_factorial(prod);
|
|
|
66 }
|
|
|
67
|
|
|
68 }
|
|
|
69
|
|
|
70 __code factorial(int x)
|
|
|
71 {
|
|
|
72 goto factorial0(1, x);
|
|
|
73 }
|
|
|
74
|
|
|
75 int main(int argc, char **argv)
|
|
|
76 {
|
|
|
77 int i;
|
|
|
78 i = atoi(argv[1]);
|
|
|
79
|
|
|
80 goto factorial(i);
|
|
|
81 }
|
|
|
82 \end{lstlisting}
|
|
|
83
|
|
6
|
84 \begin{figure}[htpb]
|
|
|
85 \begin{center}
|
|
|
86 \scalebox{0.55}{\includegraphics{fig/factorial.pdf}}
|
|
|
87 \end{center}
|
|
|
88 \caption{階乗を求める CbC プログラムの軽量継続図}
|
|
|
89 \label{fig:factorial}
|
|
|
90 \end{figure}
|
|
|
91
|
|
0
|
92 \section{環境付き継続}
|
|
|
93 環境付き継続は C との互換性のために必要な機能である。
|
|
|
94 CbC と C の記述を交える際、CbC の Code Gear から C の関数の呼び出しは問題なく行える。
|
|
|
95 しかし、C の関数から CbC の Code Gear へと継続する場合、呼び出し元の環境に戻るための特殊な継続が必要となる。
|
|
|
96 これを環境付き継続と呼ぶ。
|
|
|
97
|
|
|
98 環境付き継続を用いる場合、C の関数から Code Gear へ継続する際に \_\_ return、\_\_environment という変数を渡す。
|
|
|
99 \_\_return は \_\_code (*)(return\_type, void*) 型の変数で環境付き継続先が元の環境に戻る際に利用する Code Gear を表す。
|
|
|
100 \_\_environment は void** 型の変数で元の関数の環境を表す。
|
|
|
101 リスト\ref{gotoWithTheEnv}では関数 funcB から Code Gear cs に継続する際に環境付き継続を利用している。
|
|
|
102 cs は funcB から渡された Code Gear へ継続することで元の C の環境に復帰することが可能となる。
|
|
|
103 但し復帰先は \_\_return を渡した関数が終了する位置である。
|
|
|
104 このプログラムの例では、関数 funcA は戻り値として funcB の終わりにある -1 ではなく、環境付き継続によって渡される 1 を受け取る。
|
|
|
105 図\ref{fig:gotoWithTheEnv}にこの様子を表した。
|
|
|
106
|
|
|
107 \begin{lstlisting}[frame=lrbt,label=gotoWithTheEnv,caption={環境付き継続}]
|
|
|
108 __code cs(__code (*ret)(int, void*), void *env){
|
|
|
109 /* C0 */
|
|
|
110 goto ret(1, env);
|
|
|
111 }
|
|
|
112
|
|
|
113 int funcB(){
|
|
|
114 /* B0 */
|
|
|
115 goto cs(__return, __environment);
|
|
|
116 /* B1 (never reached). */
|
|
|
117 return -1;
|
|
|
118 }
|
|
|
119
|
|
|
120 int funcA(){
|
|
|
121 /* A0 */
|
|
|
122 int retval;
|
|
|
123 retval = funcB();
|
|
|
124 /* A1 */
|
|
|
125 printf("retval = %d\n", retval);
|
|
|
126 /* retval should not be -1 but be 1. */
|
|
|
127 return 0;
|
|
|
128 }
|
|
|
129
|
|
|
130 \end{lstlisting}
|
|
|
131
|
|
|
132 \begin{figure}[htpb]
|
|
|
133 \begin{center}
|
|
|
134 \scalebox{0.55}{\includegraphics{fig/gotowithenv.pdf}}
|
|
|
135 \end{center}
|
|
|
136 \caption{環境付き継続}
|
|
|
137 \label{fig:gotoWithTheEnv}
|
|
|
138 \end{figure}
|
|
|
139
|
|
|
140 このように、環境付き継続を用いることで C、CbC 間の処理の移動が可能になる。
|
|
|
141
|
|
|
142 %Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
|
|
|
143
|
|
|
144 %Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
|
145 %また、接続された Data Gear 以外には参照を行わない。
|
|
|
146
|
|
|
147 %処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
|
|
|
148
|
