Mercurial > hg > Papers > 2020 > soto-midterm
view tex/spec.tex @ 7:acad18934981
add description of rbtree
author | soto@cr.ie.u-ryukyu.ac.jp |
---|---|
date | Mon, 14 Sep 2020 05:41:23 +0900 |
parents | 35f0e5f12fe6 |
children | 27a6616b6683 |
line wrap: on
line source
\section{検証手法} 手法は模索中であり、大半が先行研究と同じ手法を考えている。 本章では先行研究で述べられている検証手法について説明する。 流れとしては、Hoare Logic は事前条件がある際、コマンド実行後の事後条件が成り立つ場合に コマンドの部分的な正当性を導けることを前述した。 その為、agdaでのcbcの検証は下図のようになる。 流れを説明すると、 CodeGear の引数となる DataGear が事前条件となり、 それを検証する為のPre Conditionを検証する為の Meta Gearsが存在する。 その後、さらに事後条件となる DetaGear も Meta Gears にて検証する。 \subsection{CbC記法で書くagda} CbCプログラムの検証をするに当たり、agdaコードもCbC記法で記述を行う。つまり継続渡しを用いて記述する必要がある。 以下が例となるコードである。 \lstinputlisting[caption= Agdaでの CodeGear の例, label=agda-cg]{src/cbc-agda.agda} 前述した加算を行うコードと比較すると、不定の型 (t) により継続を行なっている部分が見える。 これがAgdaで表現された CodeGear となる。 \subsection{agda による Meta Gears} 通常の Meta Gears はノーマルレベルの CodeGear、 DataGear では扱えないメタレベルの計算を扱う単位である。 今回はその Meta Gears をagdaによる検証の為に用いる。 \begin{itemize} \item Meta DataGear \mbox{}\\ Agda 上で Meta DataGear を持つことでデータ構造自体が関係を持つデータを作ることができる。 これを用いることで、仕様となる制約条件を記述することができる。 \item Meta CodeGear\mbox{}\\ Meta CodeGear は 通常の CodeGear では扱えないメタレベルの計算を扱う CodeGear である。Agda での Meta CodeGear は Meta DataGear を引数に取りそれらの関係を返 す CodeGear である。故に、Meta CodeGear は Agda で記述した CodeGear の検証そのものである \end{itemize} \subsection{Code Gear の 遷移の検証} これまで述べた手法にて、CodeGear の検証をすることができる。 しかし、CodeGear から 次の CodeGear へ正しく事後条件と事前条件が遷移していることを検証する必要がある。 % また、各 CodeGear が正しく停止することも重要である。 遷移の検証のために implies という data 型を導入する。 \lstinputlisting[label=implies, caption=implies] {src/implies.agda} これにより CodeGear が正しく遷移できることを検証する。