Mercurial > hg > Papers > 2019 > mitsuki-master

comparison paper/meta_computation.tex @ 22:d5f62ca8d3e9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update
author mir3636
date Sun, 03 Feb 2019 03:55:49 +0900
parents 9295b0c90a84
children 5927917e1832
comparison
equal deleted inserted replaced
21:2f235b4308d2 22:d5f62ca8d3e9
8 Gears OS は処理やデータの構造が Code Gear、Data Gear に閉じているため、 8 Gears OS は処理やデータの構造が Code Gear、Data Gear に閉じているため、
9 これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。 9 これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
10 10
11 \section{Continuation based C} 11 \section{Continuation based C}
12 CbC は処理を Code Gear とした単位を用いて記述するプログラミング言語である。 12 CbC は処理を Code Gear とした単位を用いて記述するプログラミング言語である。
13 Code Gear 間では軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。 13 Code Gear 間では軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、
14 状態遷移ベースのプログラミングに適している。
14 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。 15 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
15 16
16 \begin{figure}[htpb] 17 \begin{figure}[htpb]
17 \begin{center} 18 \begin{center}
18 \scalebox{0.7}{\includegraphics{fig/codesegment.pdf}} 19 \scalebox{0.9}{\includegraphics{fig/codesegment.pdf}}
19 \end{center} 20 \end{center}
20 \caption{goto による code gear 間の継続} 21 \caption{goto による code gear 間の継続}
21 \label{fig:cs} 22 \label{fig:cs}
22 \end{figure} 23 \end{figure}
23 24
26 Gears OS はこの CbC を用いて記述されている。 27 Gears OS はこの CbC を用いて記述されている。
27 28
28 \section{Code Gear} 29 \section{Code Gear}
29 30
30 Code Gear は CbC における最も基本的な処理単位である。 31 Code Gear は CbC における最も基本的な処理単位である。
31 リスト \ref{code_simple} はCbC における Code Gear の一例である。 32 ソースコード \ref{code_simple} はCbC における Code Gear の一例である。
32 33
33 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}] 34 \begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
34 __code cs0(int a, int b){ 35 __code cs0(int a, int b){
35 goto cs1(a+b); 36 goto cs1(a+b);
36 } 37 }
41 \end{lstlisting} 42 \end{lstlisting}
42 43
43 Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。 44 Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。
44 Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。 45 Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
45 次の Code Gear への遷移は goto Code Gear 名 (引数) で次の Code Gear への遷移を記述する。 46 次の Code Gear への遷移は goto Code Gear 名 (引数) で次の Code Gear への遷移を記述する。
46 リスト \ref{code_simple} での goto cs1(a+b); がこれにあたる。 47 ソースコード \ref{code_simple} での goto cs1(a+b); がこれにあたる。
47 この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。 48 この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
48 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。 49 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
49 したがってこれを軽量継続と呼ぶこともある。 50 したがってこれを軽量継続と呼ぶこともある。
50 cs1 へ継続した後は cs0 へ戻ることはない。 51 cs1 へ継続した後は cs0 へ戻ることはない。
51 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。 52 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
52 53
53 \section{Data Gear} 54 \section{Data Gear}
54 Data Gear は Gears におけるデータの単位である。 55 Data Gear は Gears OS におけるデータの単位である。
55 Gears OS では Code Gear は Input Data Gear、Output Data Gear を引数に持ち、 56 Gears OS では Code Gear は Input Data Gear、Output Data Gear を引数に持ち、
56 任意の Input Data Gear を参照し、Output Data Gear を書き出す。\ref{fig:IODataGear} 57 任意の Input Data Gear を参照し、Output Data Gear を書き出す。図\ref{fig:IODataGear}
57 Code Gear はこのとき渡された引数の Data Gear 以外を参照することはない。 58 Code Gear はこのとき渡された引数の Data Gear 以外を参照することはない。
58 この Data Gear の対応から依存関係の解決を行う。 59 この Data Gear の対応から依存関係の解決を行う。
59 60
60 \begin{figure}[ht] 61 \begin{figure}[ht]
61 \begin{center} 62 \begin{center}
62 \includegraphics[width=100mm]{fig/IO_DataGear.pdf} 63 \includegraphics[width=130mm]{fig/IO_DataGear.pdf}
63 \end{center} 64 \end{center}
64 \caption{CodeGear と DataGear} 65 \caption{CodeGear と DataGear}
65 \label{fig:IODataGear} 66 \label{fig:IODataGear}
66 \end{figure} 67 \end{figure}
67 68
68 ソースコード \ref{Gears_code} は Gears OS での Stack の操作の Code Gear の例である。 69 ソースコード \ref{Gears_code} は Gears OS での Stack の pop 操作の Code Gear の例である。
69 popSingleLinkedStack での引数 stack が Input Data Gear、next は継続先の Code Gear のアドレス、 70 popSingleLinkedStack での引数 stack が Input Data Gear、next は継続先の Code Gear のアドレス、
70 next の引数の data が Output Data Gear、... は可変長引数であることを示している。 71 next の引数の data が Output Data Gear、... は可変長引数であることを示している。
71 pop の操作を行った後に goto next で引数で受けた次の Code Gear へと継続する。 72 Input Data Gear で受け取った Stack に対して pop の操作を行った後に、
73 取り出したデータを Output Data Gear として書き出し、goto next で引数で受けた次の Code Gear へと継続する。
72 74
73 \begin{lstlisting}[frame=lrbt,label=Gears_code,caption={\footnotesize Gears でのStack pop}] 75 \begin{lstlisting}[frame=lrbt,label=Gears_code,caption={\footnotesize Gears でのStack pop}]
74 76
75 __code stackTest3(struct Stack* stack) { 77 __code stackTest3(struct Stack* stack) {
76 goto stack->pop(assert3); 78 goto stack->pop(assert3);
93 95
94 \end{lstlisting} 96 \end{lstlisting}
95 97
96 \section{Meta Code Gear、Meta Data Gear} 98 \section{Meta Code Gear、Meta Data Gear}
97 Gears OS ではメタ計算 を Meta Code Gear、Meta Data Gear で表現する。 99 Gears OS ではメタ計算 を Meta Code Gear、Meta Data Gear で表現する。
98 Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。 100 Meta Code Gear は通常の Code Gear の直前、直後に遷移され、メタ計算を実行する。
101 Code Gear はノーマルレベルでは図 \ref{fig:normal_Code_Gear} のように見える。
102 メタレベルでは Code Gear は図 \ref{fig:meta_Code_Gear} のように継続を行なっている。
103
104 \begin{figure}[ht]
105 \begin{center}
106 \includegraphics[width=60mm]{fig/normal_Code_Gear.pdf}
107 \end{center}
108 \caption{ノーマルレベルの Code Gear の継続}
109 \label{fig:normal_Code_Gear}
110 \end{figure}
111
112 \begin{figure}[ht]
113 \begin{center}
114 \includegraphics[width=100mm]{fig/meta_Code_Gear.pdf}
115 \end{center}
116 \caption{メタレベルの Code Gear の継続}
117 \label{fig:meta_Code_Gear}
118 \end{figure}
99 119
100 Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。 120 Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。
101 Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。 121 Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。
102 しかし Context を通常の計算から直接扱うのはセキュリティ上好ましくない。 122 しかし Context を通常の計算から直接扱うのはセキュリティ上好ましくない。
103 そこで Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear を定義し、 123 そこで Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear を定義し、
104 これを介して間接的に必要な Data Gear にアクセスする。 124 これを介して間接的に必要な Data Gear にアクセスする。
105 この Meta Code Gear を stub Code Gear と呼ぶ。 125 この Meta Code Gear を stub Code Gear と呼ぶ。
106 %code を入れる
107 stub Code Gear は Code Gear 毎にあり、次の Code Gear へと継続する前に挿入される。 126 stub Code Gear は Code Gear 毎にあり、次の Code Gear へと継続する前に挿入される。
108 つまり goto による継続を行うと、実際には次の Code Gear の stub Code Gear を呼び出す。 127 つまり goto による継続を行うと、実際には次の Code Gear の stub Code Gear を呼び出す。
109 stub Code Gear では、継続先が求める Input Code Gear、Output Code Gear を Context から参照している。 128 stub Code Gear では、継続先が求める Input Code Gear、Output Code Gear を Context から参照している。
110 129
130 図 \ref{fig:Context_ref} はメタレベルで見た Data Gear へのアクセスを図示したものである。
131 メタレベルでは Code Gear は Context が持つ Data Gear へのポインタを渡されており、
132 そこへ Output を行う。
133 stub Code Gear は Meta Data Gear である Context が持つ Data Gear を、
134 Input Data Gear、Output Data Gear として参照し、
135 継続先のノーマルレベルの Code Gear へと遷移する。
136
137 \begin{figure}[ht]
138 \begin{center}
139 \includegraphics[width=140mm]{fig/Context_ref.pdf}
140 \end{center}
141 \caption{Context が持つ Data Gear へのアクセス}
142 \label{fig:Context_ref}
143 \end{figure}
111 144
112 Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。 145 Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
113 Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。 146 Interface は使用される全ての Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
114 Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。 147 Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
115 Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。 148 Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。
116 一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Context に格納される。 149 一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Context に格納される。
117 150
118 Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。 151 Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。