|
3
|
1 \chapter{Hoare Logic}
|
|
|
2
|
|
|
3 \section{Hoare Logic}
|
|
|
4 Hoare Logic\ref{hoare} とは C.A.R Hoare、
|
|
|
5 R.W Floyd が考案したプログラムの検証の手法である。
|
|
|
6 これは、「プログラムの事前条件(P)が成立しているとき、コマンド(C)実行して停止すると事後条件(Q)が成り立つ」
|
|
|
7 というもので、CbCの実行を継続するという性質に非常に相性が良い。
|
|
|
8 Hoare Logic を表記すると以下のようになる。
|
|
|
9 $$ \{P\}\ C \ \{Q\} $$
|
|
|
10 この3つ組は Hoare Triple と呼ばれる。
|
|
|
11
|
|
|
12 Hoare Triple の事後条件を受け取り、
|
|
|
13 異なる条件を返す別の Hoare Triple を繋げることでプログラムを記述していく。
|
|
|
14
|
|
|
15 Hoare Logic の検証では、
|
|
|
16 「条件がすべて正しく接続されている」かつ「コマンドが停止する」ことが必要である。
|
|
|
17 これらを満たし、
|
|
|
18 事前条件から事後条件を導けることを検証することで Hoare Logic の健全性を示すことができる。
|
|
|
19
|
|
4
|
20 \section{Hoare Logic による Code Gear の検証手法 }
|
|
3
|
21
|
|
|
22 \figref{hoare}が agda にて Hoare Logic を用いて Code Gear を検証する際の流れになる。
|
|
|
23 input DataGear が Hoare Logic上の Pre Condition(事前条件)となり、
|
|
|
24 output DataGear が Post Conditionとなる。
|
|
|
25 各DataGear が Pre / Post Condition を満たしているかの検証は、
|
|
|
26 各 Condition を Meta DataGear で定義し、
|
|
|
27 条件を満たしているのかをMeta CodeGear で検証する。
|
|
|
28
|
|
4
|
29 \begin{figure}[H]
|
|
|
30 \begin{center}
|
|
|
31 \includegraphics[height=3.4cm]{pic/hoare_cg_dg.pdf}
|
|
|
32 \end{center}
|
|
|
33 \caption{CodeGear、DataGear での Hoare Logic}
|
|
|
34 \label{hoare}
|
|
|
35 \end{figure}
|
|
|
36
|
|
11
|
37 \begin{comment}
|
|
4
|
38 \section{CbCでの Hoare Logic を用いた検証}
|
|
|
39 先行研究で行われている While Loop の Hoare Logic での検証を元に、
|
|
|
40 実際の Hoare Logic を用いた検証手法について解説する。
|
|
|
41
|
|
|
42 \subsection{CbC でのコードとそれに対応したAgdaのコード}
|
|
|
43
|
|
|
44 元となる CbC での コードとそれと対応した Agda のコードを以下に示す。
|
|
|
45
|
|
|
46 \subsection{}
|
|
|
47
|
|
|
48 実装の際には、(next : Env → t)で Continuation に対応していた。
|
|
|
49 これに加えてHoare Triple に対応する。
|
|
|
50 そのため Env → t の間に Meta Data Gear を記述する
|
|
|
51 以下は Meta Data Gear の記述
|
|
|
52 % Meta Data Gearのソースコードを貼る
|
|
|
53
|
|
|
54 s1 が初期状態、
|
|
11
|
55 \end{comment}
|
|
3
|
56
|
|
|
57
|
