annotate paper/chapter2.tex @ 32:f496aa679126

update
author anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Tue, 12 Feb 2019 18:37:15 +0900 (2019-02-12)
parents 3ad581842874
children 3b4eeb606909
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
23
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
1 \chapter{Continuation Based C}
25
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
2 \section{CbCの概要}
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
3 Continuation Based C (CbC) は当研究室で開発を行っているプログラミング言語である。
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
4 現在はCコンパイラであるgcc及びllvmをバックエンドとしたclang、 MicroCコンパイラ上の3種類の実装がある。
25
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
5
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
6 C言語を用いてプログラミングを行い場合、本来プログラマが行いたい処理の他に、 mallocなどの関数を利用したメモリのアロケートなどのメモリ管理が必要となる。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
7 他にもエラーハンドリングなどの雑多な処理が必要となる。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
8
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
9 これらの処理をmeta computationと呼ぶ。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
10 実装しているプログラムにおけるエラーの原因が、 通常の処理かmeta computationなのか区別を行いたい。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
11 また、 プログラム自身の検証や証明も、 通常の関数などと meta computationは区別したい。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
12 通常C言語などを用いたプログラミングの場合、 meta computationと通常の処理を分割を行おうとすると、 それぞれ事細やかに関数やクラスを分割せねばならず容易ではない。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
13
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
14 CbCでは関数よりmeta computationを細かく記述する為に、 CodeGearと呼ばれる単位を導入する。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
15 CodeGearでは、 データの入出力としてDetaGearという単位を導入する。
4d81332c0ab3 update chap3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
16 CbCでは、 これらCodeGear と DetaGearを基本単位として実装していくプログラミングスタイルを取る。
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
17
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
18 \section{CodeGear}
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
19
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
20 CbCではC言語の関数の代わりに CodeGear を導入する。
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
21 CodeGearはC言語の関数宣言の型名の代わりに \_\_codeと書く事で宣言出来る。
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
22 \_\_codeはCbCコンパイラでの扱いはvoidと同じ型として扱うが、 CbCプログラミングではCodeGearである事を示す、 識別子として利用する。
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
23
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
24 CodeGear間の移動はgoto文で行い、 gotoの後に対応するCodeGear名を記述することで遷移する。
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
25 通常C言語の関数呼び出しでは、 スタックポインタを操作し、 ローカル変数や、 レジスタ情報をスタックに保存する。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
26 これらは通常アセンブラのcall命令として処理される。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
27
29
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
28 CbCの場合、 スタックフレームを操作せずに次のCodeGearに遷移する。
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
29 この際Cの関数呼び出しとは異なり、 プロラムカウンタを操作するのみのjmp命令として処理される。
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
30 通常Schemeのcall/ccなどの継続と呼ばれる処理は、 現在のプログラムまでの位置や情報を、 環境として所持した状態で遷移する。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
31 CbCの場合これら環境を持たず遷移する為、 通常の継続と比較して軽量であるから、 軽量継続であると言える。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
32 CbCは軽量継続を利用するためにレジスタレベルでの実装が可能となり、 Cよりも低級な言語と言える。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
33
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
34
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
35 CodeGear間の入出力の受け渡しは引数を利用して行う。
32
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
36
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
37 これは軽量継続時に、 CodeGearの入出力のインターフェイスを揃えることで、 引数で与えられたレジスタを変更せずに繊維する事が可能であるためである。
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
38
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
39
32
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
40 実際にCbCで書いたコード例をソースコード\ref{cbc_example_test}に示す。
27
da266bef2120 update chapter3
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
41
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
42 \lstinputlisting[frame=lrbt, label=cbc_example_test, caption=加算と文字列を設定するCbCコードの例]{./codes/cbc_example_test.cbc}
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
43
29
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
44 この例では、 cg1, cg2, cg3という CodeGear を用意し、これらをcg1,cg2,cg3の順で軽量継続していく。
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
45 入出力としてmain関数で生成したTEST構造体を受け渡し、 cg1で数値の加算を、 cg2で文字列の設定を行う。
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
46 main関数からcg1へのgoto文では、 Cの関数からCodeGearへの移動となる為、 call命令ではなくjmp命令で行われる。
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
47 cg1からcg2、 またcg2からcg3へは、 CodeGear間での移動となるためjmp命令での軽量継続で処理される。
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
48 この例では最終的に test.number には1が、 test.stringにはHelloが設定される。
28
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
49
32
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
50 CbCでは関数呼び出しの他に、 for文やwhile文などのループ制御を廃している。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
51 CbCでループ相当の物を記述する際は、 再帰呼び出しを利用する。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
52 実際にある数の階乗を計算するCプログラムと、 このプログラムをCbCで書き直した場合のソースコードを示す。
29
96e9cf9c2ea2 add source files
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
53
32
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
54 \section{Cとの互換性}
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
55
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
56 CbCコンパイラはコンパイル対象のソースコードが、 CbCであるかC言語であるかを判断する。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
57 この際にCodeGearを利用していない場合は、 通常のCプログラムとしてコンパイルを行う。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
58 本研究で検証するMoarVMのビルドにおいても、 CbCで書き換えたソースコードがあるMoarVMと、 手を加えていないオリジナルのC言語で実装されたMoarVMを同一のCbCコンパイラでビルドする事が可能である。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
59
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
60 また、C言語の関数からCodeGearへ繊維することはgoto文で可能である。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
61 CodeGear中でCの関数を呼び出し、 その結果を受取り、 次のCodeGearに遷移する事も通常のCのプログラミング同様可能である。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
62
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
63 しかしCodeGearからCの関数に再び戻り、 CodeGear同士の遷移から外れるように実装したい場合がある。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
64 この際は環境付きgotoと呼ばれる手法を取る。
anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
65 これは\_CbC\_return及び、 \_CbC\_environmentという変数を使用する。