|
17
|
1 \chapter{Continuation Based C}
|
|
41
|
2 Continuation Based C(CbC)とはC言語の下位言語であり、 関数呼び出しではなく継続を導入したプログラミング言語である。
|
|
|
3 CbCでは通常の関数呼び出しの他に、 関数呼び出し時のスタックの操作を行わず、次のコードブロックに\texttt{jmp}命令で移動する継続が導入されている。
|
|
|
4 この継続はSchemeのcall/ccなどの環境を持つ継続とは異なり、 スタックを持たず環境を保存しない継続である為に軽量である事から軽量継続と呼べる。
|
|
|
5 またCbCではこの軽量継続を用いて\texttt{for}文などのループの代わりに再起呼び出しを行う。
|
|
|
6 これは関数型プログラミングでのTail callスタイルでプログラミングすることに相当する。
|
|
|
7 Agda よる関数型のCbCの記述も用意されている。
|
|
57
|
8 実際のOSやアプリケーションを記述する場合には、GCC\cite{cbcgcc}及びLLVM/clang上\cite{cbcllvm}のCbC実装を用いる。
|
|
41
|
9
|
|
55
|
10
|
|
42
|
11 \section{CodeGear}
|
|
41
|
12 CbCでは関数の代わりにCodeGearという単位でプログラミングを行う。
|
|
|
13 CodeGearは通常のCの関数宣言の返り値の型の代わりに\texttt{\_\_code}で宣言を行う。
|
|
|
14 各CodeGearはDataGearと呼ばれるデータの単位で入力を受け取り、 その結果を別のDataGearに書き込む。
|
|
|
15 入力のDataGearをInputDataGearと呼び、 出力のDataGearをOutputDataGearと呼ぶ。
|
|
|
16 CodeGearがアクセスできるDataGearは、 InputDataGearとOutputDataGearに限定される。
|
|
17
|
17
|
|
58
|
18 CodeGearは関数呼び出し時のスタックを持たない為、一度あるCodeGearに遷移すると元の処理に戻ってこれない。
|
|
41
|
19 しかしCodeGearを呼び出す直前のスタックは保存される。
|
|
|
20 部分的にCbCを適用する場合はCodeGearを呼び出す\texttt{void}型などの関数を経由することで呼び出しが可能となる。
|
|
|
21
|
|
58
|
22 この他にCbCからCへ復帰する為のAPIとして、 環境付きgotoがある。
|
|
41
|
23 これは呼び出し元の関数を次のCodeGearの継続対象として設定するものである。
|
|
|
24 これはGCCでは内部コードを生成を行う。
|
|
|
25 LLVM/clangでは\texttt{setjmp}と\texttt{longjmp}を使い実装している。
|
|
|
26 したがってプログラマから見ると、通常のCの関数呼び出しの返り値をCodeGearから取得する事が可能となる。
|
|
|
27
|
|
55
|
28 \section{DataGearとMetaDataGear}
|
|
|
29 DataGearはCbCでのデータの単位である。
|
|
|
30 基本はC言語の構造体そのものであるが、 DataGearの場合はデータに付随するメタ情報も取り扱う。
|
|
|
31 これはデータ自身がどういう型を持っているかなどの情報である。
|
|
|
32 ほかに計算を実行するCPU、 GPUの情報や、 計算に必要なすべてのDataGearの管理などの実行環境のメタデータもDataGearの形で表現される。
|
|
|
33 このメタデータを扱うDataGearをMetaDataGearと呼ぶ。
|
|
42
|
34
|
|
|
35
|
|
|
36 \section{CbCを使ったシステムコールディスパッチの例題}
|
|
|
37 CbCを用いてMITが開発した教育用のOSであるxv6\cite{xv6}の書き換えを行った。
|
|
|
38 CbCを利用したシステムコールのディスパッチ部分をソースコード\ref{src:cbc_syscall_example}に示す。
|
|
|
39 この例題では特定のシステムコールの場合、 CbCで実装された処理に\texttt{goto}文をつかって継続する。
|
|
|
40 例題ではCodeGearへのアドレスが配列\texttt{cbccodes}に格納されている。
|
|
|
41 引数として渡している\texttt{cbc\_ret}は、 システムコールの返り値の数値をレジスタに代入するCodeGearである。
|
|
|
42 実際に\texttt{cbc\_ret}に継続が行われるのは、 \texttt{read}などのシステムコールの一連の処理の継続が終わったタイミングである。
|
|
|
43
|
|
|
44 \lstinputlisting[label=src:cbc_syscall_example, caption=CbCを利用したシステムコールのディスパッチ]{src/xv6_syscall.cbc}
|
|
47
|
45
|
|
|
46 軽量継続を持つCbCを利用して、 証明可能なOSを実装したい。
|
|
|
47 その為には証明に使用される定理証明支援系や、 モデル検査機での表現に適した状態遷移単位での記述が求められる。
|
|
|
48 CbCで使用するCodeGearは、 状態遷移モデルにおける状態そのものとして捉えることが可能である。
|
|
|
49 CodeGearを元にプログラミングをするにつれて、 CodeGearの入出力のDataも重要であることが解ってきた。
|
|
|
50
|
|
50
|
51 \section{メタ計算}
|
|
55
|
52 プログラミング言語からメタ計算を取り扱う場合、 言語の特性に応じて様々な手法が使われてきた。
|
|
|
53 関数型プログラミングの見方では、 メタ計算はモナドの形で表現されていた。\cite{moggi-monad}
|
|
56
|
54 OSの研究ではメタ計算の記述に型付きアセンブラを用いることもある。\cite{Yang:2010:SLI:1806596.1806610}
|
|
50
|
55
|
|
55
|
56 CbCでのメタ計算はCodeGear、 DataGearの単位がそのまま使用できる。
|
|
|
57 メタ計算で使われるこれらの単位はそれぞれ、 MetaCodeGear、 MetaDataGearと呼ばれる。
|
|
50
|
58
|
|
47
|
59 \section{MetaCodeGear}
|
|
|
60
|
|
|
61 GearsOSでは、 CodeGearとDataGearを元にプログラミングを行う。
|
|
|
62 遷移する各CodeGearの実行に必要なデータの整合性の確認などのメタ計算は、 MetaCodeGearと呼ばれる各CodeGearごと実装されたCodeGearで計算を行う。
|
|
|
63 このMetaCodeGearの中で参照されるDataGearをMetaDataGearと呼ぶ。
|
|
|
64 また、 対象のCodeGearの直前で実行されるMetaCodeGearをStubCodeGearと呼ぶ。
|
|
|
65 MetaCodeGearやMetaDataGearは、プログラマが直接実装することはなく、 現在はPerlスクリプトによってGearsOSのビルド時に生成される。
|
|
|
66 CodeGearから別のCodeGearに遷移する際のDataGearなどの関係性を、図\ref{meta-cg-dg}に示す。
|
|
|
67
|
|
|
68 \begin{figure}[tb]
|
|
|
69 \begin{center}
|
|
|
70 \includegraphics[width=150mm]{./fig/meta-cg-dg.pdf}
|
|
|
71 \end{center}
|
|
|
72 \caption{CodeGearとMetaCodeGear}
|
|
|
73 \label{meta-cg-dg}
|
|
|
74 \end{figure}
|
|
|
75
|
|
|
76 通常のコード中では入力のDataGearを受け取りCodeGearを実行、 結果をDataGearに書き込んだ上で別のCodeGearに継続する様に見える。
|
|
|
77 この流れを図\ref{meta-cg-dg}の上段に示す。
|
|
|
78 しかし実際はCodeGearの実行の前後に実行されるMetaCodeGearや入出力のDataGearをMetaDataGearから取り出すなどのメタ計算が加わる。
|
|
|
79 これは図\ref{meta-cg-dg}の下段に対応する。
|
|
|
80
|
|
|
81 \section{MetaDataGear}
|
