|
0
|
1 \chapter{Agda}
|
|
2
|
2 Adga \cite{agda} とは定理証明支援器であり、関数型言語である。
|
|
|
3 Agda は依存型という型システムを持っており、型を第一級オブジェクトとして扱うことができる。
|
|
|
4 また、型システムは Curry-Howard 同型対応により命題と型付きラムダ計算が一対一で対応ため
|
|
|
5 Agda では記述したプログラムを証明することができる。
|
|
1
|
6
|
|
|
7 本章では Agda で証明をするために必要な要素について説明を行う。
|
|
|
8 また、定理証明支援器としての Agda について解説する。
|
|
|
9
|
|
|
10 \section{Agda の文法}
|
|
|
11
|
|
2
|
12 Agda はインデントが意味を持ち、スペースの有無もチェックされる。
|
|
|
13 コメントは \verb/-- comment/ や \verb/{-- comment --}/ のように記述される。
|
|
1
|
14
|
|
2
|
15 Agda のプログラムは全てモジュール内部に記述されるため、各ファイルのトップレベルにモ
|
|
|
16 ジュールを定義する必要がある。トップレベルのモジュールはファイル名と同一である。
|
|
1
|
17
|
|
|
18 通常のモジュールをインポートする時は \verb/import/ キーワードを指定する。
|
|
2
|
19 インポートを行なう際、モジュール内部の関数を別名に変更するには \verb/as/ キーワードを用いる。
|
|
|
20 他にも、モジュールから特定の関数のみをインポートする場合は \verb/using/ キーワード、
|
|
1
|
21 関数名を、関数の名前を変える時は \verb/renaming/キーワードを、特定の関数のみを隠
|
|
|
22 す場合は \verb/hiding/ キーワードを用いる。
|
|
2
|
23 なお、モジュールに存在する関数をトップレベルで用いる場合は \verb/open import/ キーワードを使うことで展開できる。
|
|
1
|
24 モジュールをインポートする例をリスト~\ref{src:agda-import}に示す。
|
|
0
|
25
|
|
1
|
26 \lstinputlisting[label=src:agda-import, caption=Agdaにおけるモジュールのインポート] {src/AgdaImport.agda}
|
|
|
27
|
|
|
28
|
|
|
29 \section{Agda のデータ}
|
|
2
|
30 Agda における型指定は : を用いて行う。 変数 x が型 A を持つ、ということを表すには x : A と記述する。
|
|
1
|
31 データ型は、代数的なデータ構造で、その定義には data キーワードを用いる。
|
|
2
|
32 data キーワードの後に data の名前と、型、 where 句を書きインデントを深くした後、
|
|
1
|
33 値にコンストラクタとその型を列挙する。
|
|
|
34
|
|
|
35 例えば Bool 型を定義するとリスト~\ref{src:agda-bool}のようになる。
|
|
|
36 Bool はコンストラクタ \verb/true/ と \verb/false/ を持つデータ型である。
|
|
|
37 Bool 自身の型は \verb/Set/ であり、これは Agda が組み込みで持つ「型集合の型」である。
|
|
|
38 Set は階層構造を持ち、型集合の集合の型を指定するには Set1 と書く
|
|
|
39
|
|
|
40 \lstinputlisting[label=src:agda-bool, caption=Agdaにおけるデータ型 Bool の定義] {src/AgdaBool.agda}
|
|
|
41
|
|
0
|
42
|
|
2
|
43 Agda には C における構造体に相当するレコード型というデータも存在する、
|
|
|
44 例えば x と y の二つの自然数からなるレコード \verb/Point/ を定義するとリスト~\ref{src:agda-record}のようになる。
|
|
|
45 レコードを構築する際は \verb/record/ キーワードの後の \verb/{}/ の内部に \verb/fieldName = value/ の形で値を列挙していく。
|
|
|
46 複数の値を列挙する際は \verb/;/ で区切る。
|
|
|
47
|
|
|
48 \lstinputlisting[label=src:agda-record, caption=Agdaにおけるレコード型の定義] {src/AgdaRecord.agda}
|
|
1
|
49
|
|
|
50
|
|
2
|
51 \section{Agda の関数}
|
|
|
52
|
|
|
53 Agda での関数の定義は、関数名と型を記述した後に関数の本体を \verb/=/ の後に記述する。
|
|
1
|
54 関数の型には $ \rightarrow $ 、 または\verb/->/ を用いる。
|
|
|
55
|
|
2
|
56 例えば引数が型 \verb/A/ で返り値が型 \verb/B/ の関数は \verb/A -> B/ のように書くことができる。
|
|
1
|
57 また、複数の引数を取る関数の型は \verb/A -> A -> B/ のように書ける。この
|
|
|
58 時の型は \verb/A -> (A -> B)/のように考えられる。
|
|
|
59 Bool 変数 \verb/x/ を取って true を返す関数 \verb/f/はリスト~\ref{src:agda-function}のようになる。
|
|
|
60
|
|
|
61 \lstinputlisting[label=src:agda-function, caption=Agda における関数定義] {src/AgdaFunction.agda}
|
|
|
62
|
|
|
63 引数は変数名で受けることもでき、具体的なコンストラクタを指定することでそのコンストラクタが渡された時の挙動を定義できる。
|
|
|
64 これはパターンマッチと呼ばれ、コンストラクタで case 文を行なっているようなもので
|
|
|
65 例えば Bool 型の値を反転する \verb/not/ 関数を書くとリスト~\ref{src:agda-not}のようになる。
|
|
|
66
|
|
|
67 \lstinputlisting[label=src:agda-not, caption=Agdaにおける関数 not の定義] {src/AgdaNot.agda}
|
|
|
68
|
|
|
69 パターンマッチでは全てのコンストラクタのパターンを含まなくてはならない。
|
|
|
70 例えば、Bool 型を受け取る関数で \verb/true/ の時の挙動のみを書くことはできない。
|
|
|
71 なお、コンストラクタをいくつか指定した後に変数で受けると、変数が持ちうる値は指定した以外のコンストラクタとなる。
|
|
|
72 例えばリスト~\ref{src:agda-pattern}の not は x には true しか入ることは無い。
|
|
|
73 なお、マッチした値以外の挙動をまとめて書く際には \verb/_/ を用いることもできる。
|
|
|
74
|
|
|
75 \lstinputlisting[label=src:agda-pattern, caption=Agdaにおけるパターンマッチ] {src/AgdaPattern.agda}
|
|
|
76
|
|
|
77 Agda にはラムダ計算が存在している。ラムダ計算とは関数内で生成できる無名の関数であり、
|
|
|
78 \verb/\arg1 arg2 -> function body/ のように書くことができる。
|
|
|
79 例えば Bool 型の引数 \verb/b/ を取って not を適用する \verb/not-apply/ をラムダ計算で書くとリスト~\ref{src:agda-lambda}のようになる。
|
|
|
80 関数 \verb/not-apply/ をラムダ計算を使わずに定義すると \verb/not-apply-2/ になるが、この二つの関数は同一の動作をする。
|
|
|
81
|
|
|
82 \lstinputlisting[label=src:agda-lambda, caption=Agda におけるラムダ計算] {src/AgdaLambda.agda}
|
|
|
83
|
|
|
84 Agda では特定の関数内のみで利用できる関数を \verb/where/ 句で記述できる。
|
|
|
85 スコープは \verb/where/句が存在する関数内部のみであるため、名前空間が汚染させることも無い。
|
|
|
86 例えば自然数3つを取ってそれぞれ3倍して加算する関数 \verb/f/ を定義するとき、 \verb/where/ を使うとリスト~\ref{src:agda-where} のように書ける。
|
|
|
87 これは \verb/f'/ と同様の動作をする。
|
|
|
88 \verb/where/ 句は利用したい関数の末尾にインデント付きで \verb/where/ キーワードを記述し、改行の後インデントをして関数内部で利用する関数を定義する。
|
|
|
89
|
|
|
90 \lstinputlisting[label=src:agda-where, caption=Agda における where 句] {src/AgdaWhere.agda}
|
|
|
91
|
|
|
92
|
|
|
93 \section{定理証明支援器としての Agda}
|
|
|
94 Agda での証明では型部分に証明すべき論理式、 $\lambda$ 項部分にそれを満たす証明を書くことで証明が完成する。
|
|
|
95 証明の例として Code \ref{proof} を見る。
|
|
|
96 ここでの $+zero$ は右から zero を足しても $\equiv$ の両辺は等しいことを証明している。
|
|
|
97 これは、引数として受けている y が Nat なので、 zero の時と suc y の二つの場合を証明する必要がある。
|
|
|
98
|
|
|
99 $y = zero$ の時は両辺が zero とできて、左右の項が等しいということを表す refl で証明することができる。
|
|
|
100 $y = suc y$ の時は x == y の時 fx == fy が成り立つという cong を使って、y の値を 1 減らしたのちに再帰的に $+zero y$
|
|
|
101 を用いて証明している。
|
|
0
|
102
|
|
1
|
103 \lstinputlisting[caption=等式変形の例,label=proof]{src/zero.agda.replaced}
|
|
|
104 %% \begin{lstlisting}[caption=等式変形の例,label=proof]
|
|
|
105 %% +zero : { y : ℕ } → y + zero ≡ y
|
|
|
106 %% +zero {zero} = refl
|
|
|
107 %% +zero {suc y} = cong ( λ x → suc x ) ( +zero {y} )
|
|
|
108 %% \end{lstlisting}
|
|
|
109
|
|
|
110 また、他にも $\lambda$ 項部分で等式を変形する構文が存在している。
|
|
|
111 Code \ref{agda-term-pre}、 \ref{agda-term-post} は等式変形の例である。
|
|
|
112 始めに等式変形を始めたいところで $let open \equiv-Reasoning in begin$と記述する。
|
|
|
113 Agda 上では分からないところを ? と置いておくことができるので、残りを ? としておく。
|
|
|
114 $--$ は Agda 上ではコメントである。
|
|
|
115
|
|
|
116 \lstinputlisting[caption=等式変形の例1/2,label=agda-term-pre]{src/term1.agda.replaced}
|
|
|
117 %% \begin{lstlisting}[caption=等式変形の例1/3,label=agda-term-pre]
|
|
|
118 %% stmt2Cond : {c10 : ℕ} → Cond
|
|
|
119 %% stmt2Cond {c10} env = (Equal (varn env) c10) ∧ (Equal (vari env) 0)
|
|
|
120
|
|
|
121 %% lemma1 : {c10 : ℕ} → Axiom (stmt1Cond {c10}) (λ env → record { varn = varn env ; vari = 0 }) (stmt2Cond {c\
|
|
|
122 %% 10})
|
|
|
123 %% lemma1 {c10} env = impl⇒ ( λ cond → let open ≡-Reasoning in
|
|
|
124 %% begin
|
|
|
125 %% ? -- ?0
|
|
|
126 %% ≡⟨ ? ⟩ -- ?1
|
|
|
127 %% ? -- ?2
|
|
|
128 %% ∎ )
|
|
|
129
|
|
|
130 %% -- ?0 : Bool
|
|
|
131 %% -- ?1 : stmt2Cond (record { varn = varn env ; vari = 0 }) ≡ true
|
|
|
132 %% -- ?2 : Bool
|
|
|
133 %% \end{lstlisting}
|
|
|
134
|
|
|
135 この状態で実行すると ? 部分に入る型を Agda が示してくれる。
|
|
|
136 始めに変形する等式を ?0 に記述し、?1 の中に $x == y$ のような変形規則を入れることで等式を変形して証明することができる。
|
|
|
137
|
|
|
138 ここでは \ref{agda-term-mid} の Bool 値 x を受け取って $x \wedge true$ の時必ず x であるという証明 $\wedge$true と 値と Env を受け取って Bool 値を返す stmt1Cond を使って等式変形を行う。
|
|
|
139 \lstinputlisting[caption=使っている等式変形規則,label=agda-term-mid]{src/term2.agda.replaced}
|
|
|
140 %% \begin{lstlisting}[caption=等式変形の例2/3,label=agda-term-mid]
|
|
|
141 %% ∧true : { x : Bool } → x ∧ true ≡ x
|
|
|
142 %% ∧true {x} with x
|
|
|
143 %% ∧true {x} | false = refl
|
|
|
144 %% ∧true {x} | true = refl
|
|
|
145
|
|
|
146 %% stmt1Cond : {c10 : ℕ} → Cond
|
|
|
147 %% stmt1Cond {c10} env = Equal (varn env) c10
|
|
|
148 %% \end{lstlisting}
|
|
|
149
|
|
|
150 最終的な証明は\ref{agda-term-post} のようになる。
|
|
|
151 \lstinputlisting[caption=等式変形の例2/2,label=agda-term-post]{src/term3.agda.replaced}
|
|
|
152 %% \begin{lstlisting}[caption=等式変形の例2/2,label=agda-term-post]
|
|
|
153 %% lemma1 : {c10 : ℕ} → Axiom (stmt1Cond {c10}) (λ env → record { varn = varn env ; vari = 0 }) (stmt2Cond {c\
|
|
|
154 %% 10})
|
|
|
155 %% lemma1 {c10} env = impl⇒ ( λ cond → let open ≡-Reasoning in
|
|
|
156 %% begin
|
|
|
157 %% (Equal (varn env) c10 ) ∧ true
|
|
|
158 %% ≡⟨ ∧true ⟩
|
|
|
159 %% Equal (varn env) c10
|
|
|
160 %% ≡⟨ cond ⟩
|
|
|
161 %% true
|
|
|
162 %% ∎ )
|
|
|
163 %% \end{lstlisting}
|
|
|
164
|
|
0
|
165
|
