|
1
|
1 \chapter{Gears におけるメタ計算}
|
|
|
2 Gears OS ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を用いる。
|
|
3
|
3 プログラムの処理の単位を Code Gear、データの単位を Data Gear と呼ぶ。
|
|
5
|
4
|
|
3
|
5 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、
|
|
|
6 これらを用いてメタ計算を実現する。
|
|
5
|
7
|
|
3
|
8 Gears OS は処理やデータの構造が Code Gear、Data Gear に閉じているため、
|
|
|
9 これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
|
|
|
10
|
|
|
11 \section{Continuation based C}
|
|
|
12 CbC は処理を Code Gear とした単位を用いて記述するプログラミング言語である。
|
|
|
13 Code Gear 間では軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
|
|
|
14 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
|
|
|
15
|
|
|
16 \begin{figure}[htpb]
|
|
|
17 \begin{center}
|
|
|
18 \scalebox{0.7}{\includegraphics{fig/codesegment.pdf}}
|
|
|
19 \end{center}
|
|
|
20 \caption{goto による code gear 間の継続}
|
|
|
21 \label{fig:cs}
|
|
|
22 \end{figure}
|
|
|
23
|
|
|
24
|
|
|
25 CbC は LLVM\cite{llvm} と GCC\cite{gcc} 上で実装されている。
|
|
|
26 Gears OS はこの CbC を用いて記述されている。
|
|
|
27
|
|
|
28 \section{Code Gear}
|
|
|
29
|
|
|
30 Code Gear は CbC における最も基本的な処理単位である。
|
|
|
31 リスト \ref{code_simple} はCbC における Code Gear の一例である。
|
|
|
32
|
|
|
33 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
|
|
|
34 __code cs0(int a, int b){
|
|
|
35 goto cs1(a+b);
|
|
|
36 }
|
|
|
37
|
|
|
38 __code cs1(int c){
|
|
|
39 goto cs2(c);
|
|
|
40 }
|
|
|
41 \end{lstlisting}
|
|
|
42
|
|
|
43 Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。
|
|
|
44 Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
|
|
|
45 次の Code Gear への遷移は goto Code Gear 名 (引数) で次の Code Gear への遷移を記述する。
|
|
|
46 リスト \ref{code_simple} での goto cs1(a+b); がこれにあたる。
|
|
|
47 この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
|
|
|
48 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
|
|
|
49 したがってこれを軽量継続と呼ぶこともある。
|
|
|
50 cs1 へ継続した後は cs0 へ戻ることはない。
|
|
|
51 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
|
|
|
52
|
|
|
53 \section{Data Gear}
|
|
|
54 Data Gear は Gears におけるデータの単位である。
|
|
|
55 Gears OS では Code Gear は Input Data Gear、Output Data Gear を引数に持ち、
|
|
|
56 任意の Input Data Gear を参照し、Output Data Gear を書き出す。\ref{fig:IODataGear}
|
|
|
57 Code Gear はこのとき渡された引数の Data Gear 以外を参照することはない。
|
|
|
58 この Data Gear の対応から依存関係の解決を行う。
|
|
1
|
59
|
|
|
60 \begin{figure}[ht]
|
|
|
61 \begin{center}
|
|
6
|
62 \includegraphics[width=100mm]{fig/IO_DataGear.pdf}
|
|
3
|
63 \end{center}
|
|
|
64 \caption{CodeGear と DataGear}
|
|
|
65 \label{fig:IODataGear}
|
|
|
66 \end{figure}
|
|
|
67
|
|
4
|
68 リスト \ref{Gears_code} は Gears OS での Stack の操作の Code Gear の例である。
|
|
|
69 popSingleLinkedStack での引数 stack が Input Data Gear、next は継続先の Code Gear のアドレス、
|
|
|
70 next の引数の data が Output Data Gear、... は可変長引数であることを示している。
|
|
|
71 pop の操作を行った後に goto next で引数で受けた次の Code Gear へと継続する。
|
|
|
72
|
|
|
73 \begin{lstlisting}[frame=lrbt,label=Gears_code,caption={\footnotesize Gears でのStack pop}]
|
|
|
74
|
|
|
75 __code stackTest3(struct Stack* stack) {
|
|
|
76 goto stack->pop(assert3);
|
|
|
77 }
|
|
|
78
|
|
|
79 __code popSingleLinkedStack(struct SingleLinkedStack* stack, __code next(union Data* data, ...)) {
|
|
|
80 if (stack->top) {
|
|
|
81 data = stack->top->data;
|
|
|
82 stack->top = stack->top->next;
|
|
|
83 } else {
|
|
|
84 data = NULL;
|
|
|
85 }
|
|
|
86 goto next(data, ...);
|
|
|
87 }
|
|
|
88
|
|
|
89 __code assert3(struct Node* node, struct Stack* stack) {
|
|
|
90 assert(node->color == Red);
|
|
|
91 goto exit_code(0);
|
|
|
92 }
|
|
|
93
|
|
|
94 \end{lstlisting}
|
|
|
95
|
|
3
|
96 \section{Meta Code Gear、Meta Data Gear}
|
|
|
97 Gears OS ではメタ計算 を Meta Code Gear、Meta Data Gear で表現する。
|
|
|
98 Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。
|
|
1
|
99
|
|
3
|
100 Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。
|
|
|
101 Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。
|
|
|
102 しかし Context を通常の計算から直接扱うのはセキュリティ上好ましくない。
|
|
|
103 そこで Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear を定義し、
|
|
|
104 これを介して間接的に必要な Data Gear にアクセスする。
|
|
|
105 この Meta Code Gear を stub Code Gear と呼ぶ。
|
|
4
|
106 %code を入れる
|
|
3
|
107 stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する前に挿入される。
|
|
|
108 goto による継続を行うと、実際には次の Code Gear の stub Code Gear を呼び出す。
|
|
|
109
|
|
4
|
110 \section{Meta Gear の自動生成}
|
|
3
|
111
|
|
4
|
112 メタレベルの記述は Perl スクリプトによって生成される。
|
|
|
113 stub Code Gear と meta によって Code Gear で記述される。
|
|
5
|
114 リスト \ref{MetaCodeGear} は生成された Meta Code Gear のコードである。
|
|
|
115
|
|
|
116 \begin{lstlisting}[frame=lrbt,label=Gears_code,caption={\footnotesize MetaCodeGear}]
|
|
|
117
|
|
|
118 __code popSingleLinkedStack_stub(struct Context* context) {
|
|
|
119 SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
|
|
|
120 enum Code next = Gearef(context, Stack)->next;
|
|
|
121 Data** O_data = &Gearef(context, Stack)->data;
|
|
|
122 goto popSingleLinkedStack(context, stack, next, O_data);
|
|
|
123 }
|
|
|
124
|
|
|
125 __code popSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack, enum Code next,union Data **O_data) {
|
|
|
126 Data* data = *O_data;
|
|
|
127 if (stack->top) {
|
|
|
128 data = stack->top->data;
|
|
|
129 stack->top = stack->top->next;
|
|
|
130 } else {
|
|
|
131 data = NULL;
|
|
|
132 }
|
|
|
133 *O_data = data;
|
|
|
134 goto meta(context, next);
|
|
|
135 }
|
|
|
136
|
|
|
137 __code meta(struct Context* context, enum Code next) {
|
|
|
138 goto (context->code[next])(context);
|
|
|
139 }
|
|
|
140
|
|
|
141 \end{lstlisting}
|
|
|
142
|
|
|
143 Gears OS では継続先の Code Gear へと継続する前に Meta Code Gear である
|
|
|
144 stub Code Gear へと継続する。
|
|
|
145
|
|
|
146 stub Code Gear では、継続先が求める Input Code Gear、Output Code Gear を Context から参照している。
|
|
|
147 Gearef は Context から Data Gear を参照するためのマクロである。
|
|
|
148 stub Code Gear は自動生成されるため、ユーザーレベルでは Context を直接触ることなくプログラミングできる。
|
|
|
149
|
|
|
150 また、Code Gear は継続の際 meta へと goto する。
|
|
|
151 Context はすべての Code Gear のリストを持っており、継続先の Code Gear のアドレスは
|
|
|
152 enum で対応付けられた Code Gear のアドレスのリストを参照して継続を行う。
|
|
|
153
|
|
1
|
154
|
|
|
155 Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
|
|
|
156 Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
|
|
|
157 Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
|
|
|
158 Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。
|
|
4
|
159 一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Context に格納される。
|
|
1
|
160
|
|
5
|
161 Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。
|
|
|
162 これを記述するために継続に不定長引数を追加する構文をスクプリトの変換機能として用意した。
|
|
|
163 メタ計算側ではこれらの Context を常に持ち歩いているので goto 文で引数を用いることはなく、
|
|
|
164 行き先は Code Gear の番号のみで指定される。
|
|
1
|
165
|
|
|
166 これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。
|
|
|
167 Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。
|
|
5
|
168
|
|
1
|
169
|
|
|
170 Context を複製して複数の CPU に割り当てることにより並列実行を可能になる。
|
|
|
171 これによりメタ計算として並列処理を記述したことになる。
|
|
|
172 Gears のスレッド生成は Agda の関数型プログラミングに対応して行われるのが望ましい。
|
|
|
173 そこで、par goto 構文を導入し、Agda の継続呼び出しに対応させることにした。
|
|
|
174 par goto では Context の複製、入力の同期、タスクスケジューラーへの Context の登録などが行われる。
|
|
|
175 par goto 文の継続として、スレッドの join に相当する \_\_exit を用意した。
|
|
|
176 \_\_exit により par goto で分岐した Code Gear の出力を元のスレッドで受け取ることができる。
|
|
|
177
|
|
|
178 関数型プログラムではメモリ管理は GC などを通して暗黙に行われる。
|
|
|
179 Gears OS ではメモリ管理は stub などのメタ計算部分で処理される。
|
|
|
180 例えば、寿命の短いスレッドでは使い捨ての線形アロケーションを用いる。
|
|
|
181
|
