|
0
|
1 Agda \cite{agda} は純粋関数型言語である。
|
|
|
2 Agda は依存型という型システムを持ち、型を第一級オブジェクトとして扱う。
|
|
|
3
|
|
|
4 Agda の記述ではインデントが意味を持ち、スペースの有無もチェックされる。
|
|
|
5 コメントは \verb/-- comment/ か \verb/{-- comment --}/ のように記述される。
|
|
|
6 また、\verb/_/でそこに入りうるすべての値を示すことができ、
|
|
|
7 \verb/?/でそこに入る値や型を不明瞭なままにしておくことができる。
|
|
|
8
|
|
|
9 %% データについて
|
|
|
10 Agda では型をデータや関数に記述する必要がある。
|
|
|
11 Agda における型指定は \verb/:/ を用いて \verb/name : type/ のように記述する。
|
|
|
12 このとき \verb/name/ に 空白があってはいけない。
|
|
|
13 データ型は、代数的なデータ構造で、その定義には \verb/data/ キーワードを用いる。
|
|
|
14 \verb/data/ キーワードの後に \verb/data/ の名前と、型、 \verb/where/ 句を書きインデントを深くし、
|
|
|
15 値にコンストラクタとその型を列挙する。
|
|
|
16
|
|
|
17 Code \ref{agda-nat}は自然数の型である $\mathbb{N}$ (Natural Number)を例である。
|
|
|
18
|
|
|
19 \lstinputlisting[label=agda-nat, caption=自然数を表すデータ型 Nat の定義] {src/nat.agda.replaced}
|
|
|
20
|
|
|
21 \verb/Nat/ では \verb/zero/ と \verb/suc/ の2つのコンストラクタを持つデータ型である。
|
|
|
22 \verb/suc/ は $\mathbb{N}$ を受け取って $\mathbb{N}$ を表す再帰的なデータになっており、
|
|
|
23 \verb/suc/ を連ねることで自然数全体を表現することができる。
|
|
|
24
|
|
|
25 $\mathbb{N}$ 自身の型は \verb/Set/ であり、これは Agda が組み込みで持つ「型集合の型」である。
|
|
|
26 \verb/Set/ は階層構造を持ち、型集合の集合の型を指定するには \verb/Set1/ と書く。
|
|
|
27 %% \verb/Level/ を用いることで異なる \verb/Set/ を表現できる。
|
|
|
28
|
|
|
29 Agda には C 言語における構造体に相当するレコード型というデータも存在する、
|
|
|
30 例えば \verb/x/ と \verb/y/ の二つの自然数からなるレコード \verb/Point/ を定義する。Code \ref{agda-record}のようになる。
|
|
|
31 \lstinputlisting[label=agda-record, caption=Agdaにおけるレコード型の定義] {src/env.agda.replaced}
|
|
|
32 レコードを構築する際は \verb/record/ キーワード後の \verb/{}/ の内部に \verb/FieldName = value/ の形で値を列挙する。
|
|
|
33 複数の値を列挙するには \verb/;/ で区切る必要がある。
|
|
|
34
|
|
|
35 %% 関数について
|
|
|
36 Agda での関数は型の定義と、関数の定義をする必要がある。
|
|
|
37 関数の型はデータと同様に \verb/:/ を用いて \verb/name : type/ に記述するが、入力を受け取り出力返す型として記述される。$\rightarrow$ 、 または\verb/→/ を用いて \verb/input → output/ のように記述される。
|
|
|
38 また、\verb/_+_/のように関数名で\verb/_/を使用すると引数がその位置にあることを意味し、中間記法で関数を定義することもできる。
|
|
|
39 関数の定義は型の定義より下の行に、\verb/=/ を使い \verb/name input = output/ のように記述される。
|
|
|
40
|
|
|
41 例えば引数が型 \verb/A/ で返り値が型 \verb/B/ の関数は \verb/A → B/ のように書くことができる。
|
|
|
42 また、複数の引数を取る関数の型は \verb/A → A → B/ のように書ける。
|
|
|
43 例として任意の自然数$\mathbb{N}$を受け取り、\verb/+1/した値を返す関数はCode \ref{agda-function}のように定義できる。
|
|
|
44 \lstinputlisting[label=agda-function, caption=Agda における関数定義] {src/agda-func.agda.replaced}
|
|
|
45
|
|
|
46
|
|
|
47 引数は変数名で受けることもでき、具体的なコンストラクタを指定することでそのコンストラクタが渡された時の挙動を定義できる。
|
|
|
48 これはパターンマッチと呼ばれ、コンストラクタで case 文を行なっているようなものである。
|
|
|
49 例として自然数$\mathbb{N}$の加算を関数で書くとCode \ref{agda-plus}のようになる。
|
|
|
50
|
|
|
51 \lstinputlisting[label=agda-plus, caption=自然数での加算の定義] {src/agda-plus.agda.replaced}
|
|
|
52 %% \lstinputlisting[label=agda-not, caption=Agdaにおける関数 not の定義] {src/AgdaNot.agda.replaced}
|
|
|
53
|
|
|
54 パターンマッチでは全てのコンストラクタのパターンを含む必要がある。
|
|
|
55 例えば、自然数$\mathbb{N}$を受け取る関数では \verb/zero/ と \verb/suc/ の2つのパターンが存在する必要がある。
|
|
|
56 なお、コンストラクタをいくつか指定した後に変数で受けることもでき、その変数では指定されたもの以外を受けることができる。
|
|
|
57 例えばCode \ref{agda-pattern}の減算では初めのパターンで2つ目の引数が\verb/zero/のすべてのパターンが入る。
|
|
|
58
|
|
|
59
|
|
|
60 \lstinputlisting[label=agda-pattern, caption=自然数の減算によるパターンマッチの例] {src/agda-pattern.agda.replaced}
|
|
|
61
|
|
|
62 Agda には$\lambda$計算が存在している。$\lambda$計算とは関数内で生成できる無名の関数であり、
|
|
|
63 \verb/\arg1 arg2 → function/ または $\lambda$\verb/arg1 arg2 → function/ のように書くことができる。
|
|
|
64 Code \ref{agda-function} で例とした \verb/+1/ をラムダ計算で書くとCode \ref{agda-lambda}の\verb/$\lambda$+1/ように書くことができる。この二つの関数は同一の動作をする。
|
|
|
65
|
|
|
66 \lstinputlisting[label=agda-lambda, caption=Agda におけるラムダ計算] {src/AgdaLambda.agda.replaced}
|
|
|
67
|
|
|
68 Agda では特定の関数内のみで利用できる関数を \verb/where/ 句で記述できる。
|
|
|
69 スコープは \verb/where/句が存在する関数内部のみであるため、名前空間が汚染させることも無い。
|
|
|
70 例えば自然数3つを取ってそれぞれ3倍して加算する関数 \verb/f/ を定義するとき、 \verb/where/ を使うとリストCode \ref{agda-where} のように書ける。
|
|
|
71 これは \verb/f'/ と同様の動作をする。
|
|
|
72 \verb/where/ 句は利用したい関数の末尾にインデント付きで \verb/where/ キーワードを記述し、改行の後インデントをして関数内部で利用する関数を定義する。
|
|
|
73
|
|
|
74 \lstinputlisting[label=agda-where, caption=Agda における where 句] {src/AgdaWhere.agda.replaced}
|
|
|
75
|
|
|
76 また Agda では停止性の検出機能が存在し、プログラム中に停止しない記述が存在するとコンパイル時にエラーが出る。
|
|
|
77 \verb/{-# TERMINATING #-}/のタグを付けると停止しないプログラムをコンパイルすることができるがあまり望ましくない。
|
|
|
78 Code \ref{term} で書かれた、\verb/loop/ と \verb/stop/ は任意の自然数を受け取り、0になるまでループして0を返す関数である。
|
|
|
79 \verb/loop/ では $\mathbb{N}$ の数を受け取り、 \verb/loop/ 自身を呼び出しながら 数を減らす関数 pred を呼んでいる。しかし、\verb/loop/の記述では関数が停止すると言えないため、定義するには\verb/{-# TERMINATING #-}/のタグが必要である。
|
|
|
80 \verb/stop/ では自然数がパターンマッチで分けられ、\verb/zero/のときは \verb/zero/を返し、 \verb/suc n/ のときは \verb/suc/ を外した \verb/n/ で stop を実行するため停止する。
|
|
|
81
|
|
|
82 \lstinputlisting[label=term, caption=停止しない関数 loop、停止する関数 stop] {src/termination.agda.replaced}
|
|
|
83
|
|
|
84 このように再帰的な定義の関数が停止するときは、何らかの値が減少する必要がある。
|
|
|
85
|
|
|
86
|
|
|
87 \section{定理証明支援器としての Agda}
|
|
|
88 Agda での証明では関数の記述と同様の形で型部分に証明すべき論理式、 $\lambda$ 項部分にそれを満たす証明を書くことで証明を行うことが可能である。
|
|
|
89 証明の例として Code Code \ref{proof} を見る。
|
|
|
90 ここでの \verb/+zero/ は右から \verb/zero/ を足しても ≡ の両辺は等しいことを証明している。
|
|
|
91 これは、引数として受けている \verb/y/ が \verb/Nat/ なので、 \verb/zero/ の時と \verb/suc y/ の二つの場合を証明する必要がある。
|
|
|
92 \lstinputlisting[caption=等式変形の例,label=proof]{src/zero.agda.replaced}
|
|
|
93 \verb/y = zero/ の時は $zero \equiv zero$ とできて、左右の項が等しいということを表す \verb/refl/ で証明することができる。
|
|
|
94 \verb/y = suc y/ の時は $x \equiv y$ の時 $fx \equiv fy$ が成り立つという
|
|
|
95 Code \ref{cong}の \verb/cong/ を使って、y の値を 1 減らしたのち、再帰的に \verb/+zero y/
|
|
|
96 を用いて証明している。
|
|
|
97 \lstinputlisting[caption=cong,label=cong]{src/cong.agda.replaced}
|
|
|
98
|
|
|
99 %% \begin{lstlisting}[caption=等式変形の例,label=proof]
|
|
|
100 %% +zero : { y : ℕ } → y + zero ≡ y
|
|
|
101 %% +zero {zero} = refl
|
|
|
102 %% +zero {suc y} = cong ( λ x → suc x ) ( +zero {y} )
|
|
|
103 %%
|
|
|
104 %% -- cong : ∀ (f : A → B) {x y} → x ≡ y → f x ≡ f y
|
|
|
105 %% -- cong f refl = refl
|
|
|
106 %% \end{lstlisting}
|
|
|
107
|
|
|
108 また、他にも $\lambda$ 項部分で等式を変形する構文がいくつか存在している。
|
|
|
109 ここでは \verb/rewrite/ と ≡\verb/-Reasoning/ の構文を説明するとともに、等式を変形する構文の例として加算の交換則について示す。
|
|
|
110
|
|
|
111 \verb/rewrite/ では 関数の \verb/=/ 前に \verb/rewrite 変形規則/ の形で記述し、複数の規則を使う場合は \verb/rewrite/ 変形規則1 \verb/|/ 変形規則2 のように \verb/|/を用いて記述する。
|
|
|
112 Code \ref{agda-term-post} にある \verb/+-comm/ で \verb/x/ が \verb/zero/ のパターンが良い例である。
|
|
|
113 ここでは、\verb/+zero/ を利用し、 \verb/zero + y/ を \verb/y/ に変形することで $y \equiv y$となり、左右の項が等しいことを示す \verb/refl/ になっている。
|
|
|
114
|
|
|
115 \lstinputlisting[caption=等式変形の例3/3,label=agda-term-post]{src/agda-term3.agda.replaced}
|
|
|
116 Code \ref{agda-term-post} では \verb/suc (y + x)/ $equiv$ \verb/y + (suc x)/ という等式に対して $equiv$ の対称律 \verb/sym/ を使って左右の項を反転させ\verb/y + (suc x)/ $equiv$ \verb/suc (y + x)/の形にし、\verb/y + (suc x)/が\verb/suc (y + x)/ に変形できることを \verb/+-suc/ を用いて示した。
|
|
|
117 これにより等式の左右の項が等しくなったため \verb/+-comm/ が示せた。
|
|
|
118
|
|
|
119 Agda ではこのような形で等式を変形しながら証明を行う事ができる。
|
|
|
120
|
