changeset 8:f65aa05c8c52

mini fixes
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Fri, 23 May 2014 17:25:35 +0900
parents b82e226f56ff
children 170a67c4198c
files slide.md
diffstat 1 files changed, 75 insertions(+), 62 deletions(-) [+]
line wrap: on
line diff
--- a/slide.md	Fri May 23 16:42:38 2014 +0900
+++ b/slide.md	Fri May 23 17:25:35 2014 +0900
@@ -31,7 +31,7 @@
 
 # Agda をはじめよう
 * emacs に agda-mode があります
-* module < filename > where
+* module filename where
 * を先頭に書く必要があります
 * 証明を定義していく
 * C-c C-l で型チェック(証明チェック)ができます
@@ -50,12 +50,12 @@
 * data 型を使います
 
 ```
-    data Int : Set where
-      O : Int
-      S : Int -> Int
+  data Int : Set where
+    O : Int
+    S : Int -> Int
 ```
-* O は Int, S は Int を受けとって Int を返す、と読めます
-* Set は組込みで存在する型です。「成り立つ」といった感じです。
+* Int は O か、 Int に S がかかったもののみ
+* Set は組込みで存在する型です。「成り立つ」と考えてもらえれば良いです。
 
 
 # 自然数の例
@@ -75,10 +75,10 @@
 
 # Agda における自然数に対する演算の定義
 ```
-    infixl 30 _+_
-    _+_ : Int -> Int -> Int
-    x + O     = x
-    x + (S y) = S (x + y)
+  infixl 30 _+_
+  _+_ : Int -> Int -> Int
+  x + O     = x
+  x + (S y) = S (x + y)
 ```
 
 * Agda tips : C-c C-n すると式を評価することができます
@@ -87,13 +87,13 @@
 
 # Agda における関数定義のSyntax
 * Agda において、関数は
-  * 関数名                        : 型
-  * 関数名 <スペース区切りで引数> = 関数の定義や値
+  * 関数名                      : 型
+  * 関数名 引数はスペース区切り = 関数の定義や値
 * のように定義します
 * 中置関数は _ で挟みます
 
 
-# Agda における引数を持つ関数の型の表記法
+# Agda で複数の引数がある関数の型
 * func : A -> (A -> B) -> B
 
 * 引数の型 -> 返り値の型
@@ -105,6 +105,7 @@
 # パターンマッチ
 * Agda においてはデータ型は引数で分解することができます
 * ある型に続している値が、どのコンストラクタにおいて構成されたかをパターンで示せます
+* Int は O か Int に S が付いたもの、でした
   * double : Int -> Int
   * double O     = O
   * double (S x) = S (S (double x))
@@ -113,10 +114,10 @@
 
 # もういちど : 自然数に対する演算の定義
 ```
-    infixl 30 _+_
-    _+_ : Int -> Int -> Int
-    x + O     = x
-    x + (S y) = S (x + y)
+  infixl 30 _+_
+  _+_ : Int -> Int -> Int
+  x + O     = x
+  x + (S y) = S (x + y)
 ```
 * 中置、関数、パターンマッチが使われています
 * infixl は左結合を意味します。数値は結合強度です
@@ -145,7 +146,7 @@
 * 関数なら normal form が同じなら同じ
   * lambda-term : (A : Set)  -> (\(x : A) -> x) ≡ (\(y : A) -> y)
   * lambda-term A = refl
-* 関数による変形は形が違う等しいものとして扱います
+* 関数による式変形は等しいものとして扱います
 
 
 # 交換法則を型として定義する
@@ -156,11 +157,11 @@
 
 # 交換法則を証明していく
 ```
-sum-sym : (x y : Int)  -> x + y ≡ y + x
-sum-sym    O     O  = refl
-sum-sym    O  (S y) = cong S (sum-sym O y)
-sum-sym (S x)    O  = cong S (sum-sym x O)
-sum-sym (S x) (S y) = ?
+  sum-sym : (x y : Int)  -> x + y ≡ y + x
+  sum-sym    O     O  = refl
+  sum-sym    O  (S y) = cong S (sum-sym O y)
+  sum-sym (S x)    O  = cong S (sum-sym x O)
+  sum-sym (S x) (S y) = ?
 ```
 
 # trans による等式変形
@@ -177,22 +178,22 @@
 * ≡-reasoning という等式変形の拡張構文が Standard Library にあります
 
 ```
-   begin
-     変換前の式
-       ≡⟨ 変換する関数 ⟩
-     変換後の式
-   ∎
+  begin
+    変換前の式
+      ≡⟨ 変換する関数 ⟩
+    変換後の式
+  ∎
 ```
 
 
 # ≡-reasoning による最初の定義
 
 ```
-sum-sym (S x) (S y) = begin
-    (S x) + (S y)
-  ≡⟨ ? ⟩
-    (S y) + (S x)
-  ∎
+  sum-sym (S x) (S y) = begin
+      (S x) + (S y)
+    ≡⟨ ? ⟩
+      (S y) + (S x)
+    ∎
 ```
 
 
@@ -200,13 +201,13 @@
 * 上から + の定義により変形
 
 ```
-sum-sym (S x) (S y) = begin
-    (S x) + (S y)
-  ≡⟨ refl ⟩
-    S (S x + y)
-  ≡⟨ ? ⟩
-    (S y) + (S x)
-  ∎
+  sum-sym (S x) (S y) = begin
+      (S x) + (S y)
+    ≡⟨ refl ⟩
+      S (S x + y)
+    ≡⟨ ? ⟩
+      (S y) + (S x)
+    ∎
 ```
 
 
@@ -221,11 +222,12 @@
 ```
 
 
-# 交換法則の証明 : 加法の時に左側からSを移動させることができない
+# 加法の時に左側からSを移動させられない
 
 * 加法の定義は
   * x + (S y) = S (x + y)
-* left-operand から S を取る方法が無い
+* left-operand にかかっている S を移動させる方法が無い
+* たしかに
   * S (y + S x) ≡ S y + S x
 * にあてはまるものを入れてくれ、と出てきている
 
@@ -242,7 +244,7 @@
 
 
 # left-operand からSを移動させる
-* left-increment は (S x) + y ≡ S (x + y) なので逆にしないと使えない
+* left-increment は (S x) + y ≡ S (x + y) なので逆にして使う
 
 ```
     ...
@@ -255,15 +257,15 @@
 
 # 加法の交換法則 : (x + y) = (y + x)
 ```
-sum-sym (S x) (S y) = begin
-    (S x) + (S y)
-  ≡⟨ refl ⟩
-    S ((S x) + y)
-  ≡⟨ cong S (sum-sym (S x) y) ⟩
-    S (y + (S x))
-  ≡⟨ (sym (left-increment y (S x))) ⟩
-    (S y) + (S x)
-  ∎
+  sum-sym (S x) (S y) = begin
+      (S x) + (S y)
+    ≡⟨ refl ⟩
+      S ((S x) + y)
+    ≡⟨ cong S (sum-sym (S x) y) ⟩
+      S (y + (S x))
+    ≡⟨ (sym (left-increment y (S x))) ⟩
+      (S y) + (S x)
+    ∎
 ```
 
 
@@ -273,6 +275,7 @@
   * ≡ で証明したい式を定義
   * 定義に証明を書く
   * 必要ならば等式を変形していく
+* ちなみに x + y + z は infixl なので ((x + y) + z) となります
 
 
 # Agda による証明方法のまとめ
@@ -285,28 +288,38 @@
 
 # 乗法の定義
 ```
-infixl 40 _*_
-_*_ : Int -> Int -> Int
-n *    O  = O
-n * (S O) = n
-n * (S m) = n + (n * m)
+  infixl 40 _*_
+  _*_ : Int -> Int -> Int
+  n *    O  = O
+  n * (S O) = n
+  n * (S m) = n + (n * m)
 ```
 
-* _+_ よりも結合強度を上げる必要がある
+* _+_ よりも結合強度を上げるといわゆる自然数の演算
 
 
-# 乗法の交換法則 : (a * b) = (b * a)
+# 乗法の交換法則 : (x * y) = (y * x)
 ```
-mult-sym : (n m : Int) -> n * m ≡ m * n
+  mult-sym : (x y : Int) -> x * y ≡ y * x
 ```
 
 途中で
 
 ```
-(n m : Int) -> (S n) * m ≡ m + (n * m)
+  (x y : Int) -> (S x) * y ≡ y + (x * y)
 ```
 
-が必要になる
+が必要になることが分かる
+
+
+# Agdaにおいて何ができるのか
+* 証明の正しさを対話的に教えてくれる
+  * それに必要な証明が結果的に分かることもある
+* 今回は Int に対する演算だった
+  * lambda-term に落とせれば Agda で証明していける
+* 他にも命題論理の証明などがある
+* プログラミング言語そのものに対するアプローチ
+  * lambda-term の等価性によってリファクタリングなど
 
 
 <!-- vim: set filetype=markdown.slide: -->