|
23
|
1 \chapter{Continuation Based C}
|
|
25
|
2 \section{CbCの概要}
|
|
113
|
3 Continuation Based C (CbC) は当研究室で開発を行っているプログラミング言語である。\cite{gcccbc}\cite{llvmcbc}
|
|
114
|
4 現在はCコンパイラであるgcc及びllvmをバックエンドとしたclang、 MicroCコンパイラ上の3種類の実装がある。\cite{cbcgcc}\cite{cbcllvm}\cite{imcbllvm}
|
|
25
|
5
|
|
|
6 C言語を用いてプログラミングを行い場合、本来プログラマが行いたい処理の他に、 mallocなどの関数を利用したメモリのアロケートなどのメモリ管理が必要となる。
|
|
|
7 他にもエラーハンドリングなどの雑多な処理が必要となる。
|
|
|
8
|
|
|
9 これらの処理をmeta computationと呼ぶ。
|
|
|
10 実装しているプログラムにおけるエラーの原因が、 通常の処理かmeta computationなのか区別を行いたい。
|
|
|
11 また、 プログラム自身の検証や証明も、 通常の関数などと meta computationは区別したい。
|
|
|
12 通常C言語などを用いたプログラミングの場合、 meta computationと通常の処理を分割を行おうとすると、 それぞれ事細やかに関数やクラスを分割せねばならず容易ではない。
|
|
|
13
|
|
|
14 CbCでは関数よりmeta computationを細かく記述する為に、 CodeGearと呼ばれる単位を導入する。
|
|
|
15 CodeGearでは、 データの入出力としてDetaGearという単位を導入する。
|
|
|
16 CbCでは、 これらCodeGear と DetaGearを基本単位として実装していくプログラミングスタイルを取る。
|
|
27
|
17
|
|
|
18 \section{CodeGear}
|
|
|
19
|
|
|
20 CbCではC言語の関数の代わりに CodeGear を導入する。
|
|
|
21 CodeGearはC言語の関数宣言の型名の代わりに \_\_codeと書く事で宣言出来る。
|
|
82
|
22 \_\_codeはCbCコンパイラでの扱いはvoidと同じ型として扱うが、 CbCプログラミングではCodeGearである事を示す識別子として利用する。
|
|
28
|
23
|
|
35
|
24 CodeGearは通常のC言語の関数とは異なり、 返り値を持たない。
|
|
|
25 そのためreturn文や返り値の型などの情報が存在しない。
|
|
|
26
|
|
27
|
27 CodeGear間の移動はgoto文で行い、 gotoの後に対応するCodeGear名を記述することで遷移する。
|
|
28
|
28 通常C言語の関数呼び出しでは、 スタックポインタを操作し、 ローカル変数や、 レジスタ情報をスタックに保存する。
|
|
|
29 これらは通常アセンブラのcall命令として処理される。
|
|
|
30
|
|
29
|
31 CbCの場合、 スタックフレームを操作せずに次のCodeGearに遷移する。
|
|
|
32 この際Cの関数呼び出しとは異なり、 プロラムカウンタを操作するのみのjmp命令として処理される。
|
|
28
|
33 通常Schemeのcall/ccなどの継続と呼ばれる処理は、 現在のプログラムまでの位置や情報を、 環境として所持した状態で遷移する。
|
|
82
|
34 CbCの場合これら環境を持たず遷移する為、 通常の継続と比較して軽量であるから軽量継続であると言える。
|
|
35
|
35 軽量継続を利用する為、 ループ文を軽量継続の再帰呼び出しなどで実現する事が可能となる。
|
|
27
|
36
|
|
|
37 CodeGear間の入出力の受け渡しは引数を利用して行う。
|
|
32
|
38
|
|
85
|
39 これは軽量継続時に、 CodeGearの入出力のインターフェイスを揃えることで、 引数で与えられたレジスタを変更せずに遷移する事が可能であるためである。
|
|
27
|
40
|
|
|
41
|
|
41
|
42 実際にCbCで書いたコード例をソースコード\ref{cbc_example_test}に示し、 コード中での状態遷移を図\ref{fig:cbc_example_test}に示す。
|
|
27
|
43
|
|
28
|
44 \lstinputlisting[frame=lrbt, label=cbc_example_test, caption=加算と文字列を設定するCbCコードの例]{./codes/cbc_example_test.cbc}
|
|
33
|
45 \begin{figure}[ht]
|
|
|
46 \caption{ソースコード\ref{cbc_example_test}におけるCodeGearの状態遷移}
|
|
|
47 \begin{center}
|
|
|
48 \includegraphics[width=150mm]{./fig/cbc_next_sample.pdf}
|
|
|
49 \end{center}
|
|
|
50 \label{fig:cbc_example_test}
|
|
|
51 \end{figure}
|
|
|
52
|
|
41
|
53 この例では、 cg1, cg2, cg3という CodeGear を用意し、これらを図\ref{fig:cbc_example_test}の通り、 cg1,cg2,cg3の順で軽量継続していく。
|
|
|
54 それぞれのCodeGearへは、 goto文を利用する。
|
|
|
55 入出力としてmain関数で生成したTEST構造体を受け渡し、 cg1で数値の加算を、 cg2で文字列の設定を行う。
|
|
84
|
56 main関数からcg1へのgoto文では、 Cの関数からCodeGearへの移動となる為、 jmp命令ではなくcall命令で行われる。
|
|
41
|
57 cg1からcg2、 またcg2からcg3へは、 CodeGear間での移動となるためjmp命令での軽量継続で処理される。
|
|
|
58 この例では最終的に test.number には1が、 test.stringにはHelloが設定される。
|
|
|
59
|
|
|
60
|
|
32
|
61 CbCでは関数呼び出しの他に、 for文やwhile文などのループ制御を廃している。
|
|
|
62 CbCでループ相当の物を記述する際は、 再帰呼び出しを利用する。
|
|
42
|
63 C言語で、ループを再帰呼び出しで表現する場合、 再帰呼び出しの度にスタックに値が積まれていく為に、 スタック領域を埋め尽くしてしまいスタックオーバーフローが発生する。
|
|
82
|
64 これを回避するには末尾再帰と呼ばれる形でのプログラミングが要求される。
|
|
|
65 CbCの場合、 CodeGear同士の軽量継続は強制的に末尾再帰の形になる。
|
|
|
66 また、 CodeGearからCodeGearへの遷移はスタックを利用しない。
|
|
42
|
67 その為、 CodeGearの再帰呼び出しを利用しても、 スタックオーバーフローを発生させることがない。
|
|
82
|
68 この処理を末尾呼び出し除去(tail call elimination)と呼び、 CbCコンパイラは各CodeGearの遷移を末尾再帰に変換する。
|
|
42
|
69
|
|
75
|
70 実際にある数の階乗を計算するプログラムをCbC書いた場合のコードをソースコード\ref{cbc_fact}に示す。
|
|
29
|
71
|
|
75
|
72 \lstinputlisting[frame=lrbt, label=cbc_fact, caption=階乗を求めるCbCのサンプルコード]{./codes/fact.c}
|
|
42
|
73
|
|
116
|
74 ソースコード\ref{cbc_fact}では、 コマンドライン引数として与えられた数値をinitalizeというCodeGearでint型整数に変換している。
|
|
|
75 initalizeはfactに軽量継続し、 factでは与えられた数である変数curが0を上回る数値の間、 第2引数resultに変数curを乗算する。
|
|
|
76 その後curをデクリメントし、 自分自身の軽量継続を繰り返している。
|
|
|
77 curの値が0となった場合、 最後の1まで乗算したことになるので、printルーチンへと移動する。
|
|
|
78 このコードにおける、CodeGearの状態遷移を図\ref{fig:cbc_fact}に示す。
|
|
|
79
|
|
|
80 \begin{figure}[ht]
|
|
|
81 \caption{ソースコード\ref{cbc_fact}におけるCodeGearの状態遷移}
|
|
|
82 \begin{center}
|
|
|
83 \includegraphics[width=80mm]{./fig/loop_cbc.pdf}
|
|
|
84 \end{center}
|
|
|
85 \label{fig:cbc_fact}
|
|
|
86 \end{figure}
|
|
|
87
|
|
42
|
88
|
|
32
|
89 \section{Cとの互換性}
|
|
|
90
|
|
|
91 CbCコンパイラはコンパイル対象のソースコードが、 CbCであるかC言語であるかを判断する。
|
|
|
92 この際にCodeGearを利用していない場合は、 通常のCプログラムとしてコンパイルを行う。
|
|
|
93 本研究で検証するMoarVMのビルドにおいても、 CbCで書き換えたソースコードがあるMoarVMと、 手を加えていないオリジナルのC言語で実装されたMoarVMを同一のCbCコンパイラでビルドする事が可能である。
|
|
|
94
|
|
85
|
95 また、C言語の関数からCodeGearへ遷移することはgoto文で可能である。
|
|
32
|
96 CodeGear中でCの関数を呼び出し、 その結果を受取り、 次のCodeGearに遷移する事も通常のCのプログラミング同様可能である。
|
|
|
97
|
|
|
98 しかしCodeGearからCの関数に再び戻り、 CodeGear同士の遷移から外れるように実装したい場合がある。
|
|
|
99 この際は環境付きgotoと呼ばれる手法を取る。
|
|
|
100 これは\_CbC\_return及び、 \_CbC\_environmentという変数を使用する。
|
|
36
|
101 この変数は \_CbC\_return が元の環境に戻る際に利用する CodeGear を指し、 \_CbC\_environment は復帰時に戻す元の環境である。
|
|
82
|
102 復帰する場合、 呼び出した位置には帰らず呼び出した関数の終了する位置に帰る。
|
|
38
|
103 実際に環境付き継続を利用した場合のサンプルコードをソースコード\ref{cbc_return_src}に示す。
|
|
|
104
|
|
|
105 \lstinputlisting[frame=lrbt, label=cbc_return_src, caption=環境付き継続の例]{./codes/src/return.cbc}
|
|
|
106
|
|
|
107 この例では、 通常 c\_funcの返り値が-1である為、 変数testには-1が設定されるかの様に見える。
|
|
82
|
108 しかし関数 c\_func内でCodeGearである cgに軽量継続しており、 cgでは環境付きgotoを利用して1を返り値としてCの関数に戻る。
|
|
|
109 この場合、 呼び出し元 c\_funcの返り値である -1 の代わりに、 環境付きgotoで渡される1が優先され変数testには1が代入される。
|
