|
2
|
1 \section{Gears Agda でのモデル検査}
|
|
0
|
2 \pagenumbering{arabic}
|
|
|
3
|
|
4
|
4 思い思いにプログラムを書くと,冗長なコードができてしまい,
|
|
2
|
5 実行時間も遅い場合がある。
|
|
|
6
|
|
|
7 この場合にコードに対してアルゴリズムを適応すると実行が最適化され
|
|
4
|
8 実行時間が減り,かつ第三者がコードを読んだ際にロジックが統一されているため理解が容易くなる。
|
|
|
9 つまり,一般的に良いコードが作成できる。
|
|
0
|
10
|
|
4
|
11 しかし,世の中にはすでに大量のアルゴリズムが存在するため,
|
|
|
12 これを一人のプログラマーが全て覚え,適応できる場面を思いつくというのは不可能に近い。
|
|
2
|
13 その道に詳しい人が複数人いる場面というのも稀だと考えられる。
|
|
|
14
|
|
4
|
15 そのため,人が書いたコードに対してアルゴリズムを使用するコードに変換できるようにしたい。
|
|
0
|
16
|
|
4
|
17 この際,アルゴリズム適応前後で処理が変わっていないか検証するのは普通のプログラミング言語では難しい。
|
|
|
18 一般的なプログラミング言語では,関数の遷移が自由であることから,関数遷移などで発生した
|
|
2
|
19 暗黙の環境が存在するためである。
|
|
|
20
|
|
4
|
21 この問題を解決するため,Gears Agda を用いる。
|
|
0
|
22
|
|
4
|
23 Gears Agda とは当研究室で開発している Continuation based C (CbC) の概念を取り入れた記法で書かれた Agda のことで,
|
|
2
|
24 通常のプログラミング言語では関数を実行する際にはメインルーチンからサブルーチンに遷移する。
|
|
4
|
25 この際メインルーチンで使用していた変数などの環境はスタックされ,サブルーチンが終了した際にメインルーチンに戻り,
|
|
2
|
26 スタックしていた変数をもとに戻す流れとなる。
|
|
4
|
27 CbCの場合はサブルーチンコールの際にアセンブラで言うjmpで関数遷移を行うことができ,スタックを持たず環境を保持しない。
|
|
2
|
28 更に遷移後にメインルーチンに戻ることもない。
|
|
4
|
29 つまり関数の実行では暗黙な環境が存在せず,関数が受け取った引数のみを使用する。
|
|
|
30 これにより限定的な実行条件を作成でき,検証がしやすくなる。
|
|
2
|
31
|
|
4
|
32 現在,アルゴリズムの適応可否は以下の方法を考えている。
|
|
0
|
33
|
|
4
|
34 あらかじめ,アルゴリズムの実装と検証をおこなったアルゴリズムSetsを用意しておく。
|
|
2
|
35
|
|
4
|
36 書いたコードが事前に定義していたアルゴリズムの仕様を満たしているかを検証していき,
|
|
2
|
37 満たしているコードがあった場合にそのコードを事前に定義してあるアルゴリズムに入れ替える方針を考えている。
|
|
|
38
|
|
4
|
39 この際,実装が仕様を満たしているか検証する手法には,定理証明やモデル検査などが挙げられる。
|
|
0
|
40
|
|
4
|
41 アルゴリズムの入れ替え可否判定には Gears Agda でモデル検査を行い,
|
|
|
42 アルゴリズムの仕様がコードに適応できるか検証するのが妥当だと考えている。
|
|
|
43 思い思いに書いたコードに対して定理証明を行うのはコストが高く,適応するものの内部動作が一致しない場合定理証明を行っても使えないためである。
|
|
0
|
44
|
|
2
|
45 本論文では Gears Agda でのモデル検査の先駆けとして Dining philosophers problem (DPP) のモデル検査を行う。
|
|
0
|
46
|
