# HG changeset patch # User Shinji KONO # Date 1486714920 -32400 # Node ID 5a354cba369469d7f7b8d25bac1ac81d6a8dfbc0 # Parent 0a4646310261482849d46daf0f8fbeb7aa0f5949 fix diff -r 0a4646310261 -r 5a354cba3694 paper/abstract.tex --- a/paper/abstract.tex Fri Feb 10 14:25:43 2017 +0900 +++ b/paper/abstract.tex Fri Feb 10 17:22:00 2017 +0900 @@ -1,14 +1,44 @@ \begin{abstract} -ソフトウェアが期待される仕様を満たすか検査することは重要である。 -特に実際に動作するソフトウェアを検証できるとなお良い。 +高い信頼性を持つソフトウェアを提供することは重要である。 +それには、ソフトウェアが期待される仕様を満たすか検査する手法と、 +仕様を直接証明する手法とがある。 +特に実際に動作するソフトウェアを検証や証明できるとなお良い。 +本論文では 検証や証明に直接使用することができる言語として +Continuation based C(CbC) 言語を用いる。 -本論文では Continuation based C(CbC) 言語で記述されたプログラムを検証用に変更せず信頼性を確保する手法を二つ提案する。 -一つはプログラムが持つ状態を数え挙げ、常に仕様を満たすことを保証するモデル検査的手法である。 -プログラムの実行を網羅的に行なうよう変更するメタ計算ライブラリ akasha を用いて赤黒木の仕様を検証する。 +CbC上に構築されたプログラムが持つ状態を数え挙げ、仕様を満たしているかどうかを調べるモデル検査的手法を提案し、 +Akasha Meta 計算ライブラリとして実装し、赤黒木の仕様を実用的な木の大きさの範囲内で検証した。 +木の大きさを制限することなく実装が仕様を満たしていることを示すには証明が必要である。 +プログラムにおける証明は Curry-Howard Isomorphism で型付き $\lambda$計算に対応していることが +知られている。本論文では証明支援系 Agda を用いた。 -もう一つの信頼性向上手法として、プログラムのデータ構造の性質を証明する手法を提案する。 -プログラムにおける証明は Curry-Howard Isomorphism により型付き $\lambda$計算に対応している。 -CbC プログラムの性質を証明できるよう、部分型を用いてCbC の型システムを定義する。 -加えて、型システムの定義を用いて証明支援系言語 Agda 上に CbC のプログラムを記述し、証明を行なう。 +部分型を用いるとCbC の型システムを定義できる。証明やモデル検査は、これらに対するメタ計算に相当する。 +CbCの計算を実装するメタ計算はCbCで記述することができ、これは、CbCの記述なので、部分型を用いた +型システムで相似的に定義できることを示した。 + +それを Agda上で定義した。 +これらの形式的定義を使い、CbC のコードの合成の結合則とSingle Linked Stackの満たす性質をAgdaで証明することができた。 + \end{abstract} + + +\begin{abstract_eng} +Provinding highly reraiable software is important. One way is checking if the specification is statisfied or not, the other +way is to prove the implementation satisfies the specification directly. +If we can check or prove actual implementations, it it much better. +In this papaer, we use Continuation base C programming language (CbC) which can be used in both proof and model checking. +We propose model checking method By enumerating bounded computational state in CbC code as a meta computation. +Aksha Meta Computation library makes it possible to check red-black tree algorythm within a practical tree size. +To assure the property for arbitrary size of tree, we need proof method. Proofs in a program is known to corresponds $\lambda$ calculus, +which is a Curry-Howward Isomorphism. We use Agda proof assistance system. + +We can define the CbC formal type system as a subtype. The proofs or model checkings are meta compuations of the formal type systems. +Meta computaion which implements CbC computation can be descripbed as a CbC oomputation, that is, it is also defined by +CbC formal tyoe system as a subtype + +Proposition and proofs have isomorphic relation to typed $\lambda$ calculus by Curry-Howard Isomorphism. + + +\end{abstract_eng} +