|
0
|
1 \chapter{Continuation based C と Agda}
|
|
5
|
2 \label{c:cbc_agda}
|
|
|
3 現在 Agda は CbC の上位言語として使用されており、
|
|
|
4 Agda で記述された CbC のプログラムはメタ計算を含む形で記述される。
|
|
|
5 しかし、
|
|
|
6
|
|
0
|
7
|
|
4
|
8 本章では当研究室で推奨している単位を用いての検証を行うため、
|
|
|
9 Agda 上で DataGear、 CodeGear の表現を示す。
|
|
2
|
10 また、Gear の単位と Hoare Logic を対応させ、
|
|
4
|
11 CbC 上での Hoare Logic について示す。
|
|
2
|
12
|
|
|
13
|
|
0
|
14
|
|
4
|
15 \section{DataGear、 CodeGear と Agdaの対応}
|
|
|
16 DataGear は Agda で使うことのできるすべてのデータに対応する。
|
|
|
17 また、Agda での記述はメタ計算として扱われるので Context を通してデータを
|
|
|
18 扱う必要はない。
|
|
|
19
|
|
2
|
20 CodeGear は DataGear を受け取って処理を行い DataGear を返す。
|
|
|
21 また、CodeGear 間の移動は継続を用いて行われる。
|
|
|
22 継続は関数呼び出しとは異なり、呼び出した後に元のコードに戻らず、
|
|
|
23 次の CodeGear へ継続を行う。
|
|
4
|
24
|
|
2
|
25 これは、関数型プログラミングでは末尾関数呼び出しを行うことに相当するため、
|
|
|
26 継続渡し(Continuation Passing Style) で書かれた Agda の関数と対応する。
|
|
3
|
27 継続は不定の型 (\verb/t/) を返す関数で表される。
|
|
|
28 CodeGear は次に実行する関数の型を引数として受け取り不定の型\verb/t/を返す関数として記述され、
|
|
|
29 CodeGear 自体も同じ型 \verb/t/ を返す関数となる。
|
|
4
|
30 コード \ref{agda-while} は Agda で記述した CodeGear の例である。
|
|
0
|
31
|
|
4
|
32 \lstinputlisting[caption= whileTest の型, label=agda-while]{src/while-test.agda.replaced}
|
|
2
|
33 %% Agda のとこで Level の話を…！
|
|
3
|
34 ここでは \verb/c10/ と名付けた自然数を受け取った後、
|
|
|
35 \verb/Env/ を受け取って不定の型\verb/t/を返す関数を受け取り、
|
|
|
36 \verb/t/を返す CodeGear を定義している。
|
|
2
|
37
|
|
|
38
|
|
4
|
39 \section{Meta CodeGear の表現と Meta DataGear}
|
|
2
|
40 Meta CodeGear は 通常の CodeGear では扱えないメタレベルの計算を扱う CodeGear である。
|
|
|
41 Agda での Meta CodeGear は通常の CodeGear を引数に取りそれらの関係などの上位概念を返す CodeGear である。
|
|
|
42 これは(図を入れる)のような Code Gear となる。
|
|
|
43
|
|
4
|
44 % \lstinputlisting[label=src:agda-mcg, caption= Agda における Meta CodeGear 型の定義] {src/MetaCodeGear.agda.replaced}
|
|
|
45
|
|
|
46 Meta DataGear については不確かであるが、 DataGear が持つ同値関係や、大小関係などの関係を表す DataGear がそれに当たると考えている。
|
|
|
47 Agda 上では Meta DataGear を持つことで性質を持ったデータ構造を作ることができる。
|
|
|
48
|
|
2
|
49 % \lstinputlisting[label=src:agda-cs, caption= Agda における CodeGear 型の定義] {src/CodeSegment.agda.replaced}
|
|
|
50
|
|
0
|
51 \section{CbC 上での HoareLogic の実現}
|
|
2
|
52 CbC 上の Hoare Logic は引数として事前条件、次の CodeGear に渡す値に事後条件を含めることで記述する。
|
|
|
53 その際に事前条件が CodeGear で変更され、事後条件を導く形になる。
|
|
|
54 例として while プログラムの CbC 記述についてみる。
|
|
|
55
|
|
4
|
56
|
|
2
|
57 %% コード
|
|
|
58 ここでは~
|
|
|
59
|
|
4
|
60 Hoare Logic の記述を行い、部分的な整合性を示すことができている。
|
|
2
|
61 全体の検証を行うためには接続されているすべての CodeGear が実行されたときの健全性(Soundness)が担保される必要がある。
|
|
|
62 そのため、検証用の Meta CodeGear を記述する。
|
|
|
63 例として while プログラムの健全性を担保するプログラムをみる。
|
|
|
64 %% コード
|
|
|
65 このコードでは CodeGear をつなげて終了状態まで実行したとき最後の事後条件が成り立っているため、これらの実行が正しく終了することを示すことができる。
|
