High-Order Functions 다른 함수를 다룰 수 있는 함수를 고차 함수(higher-order function)라고 한다.
Definition do3times {X:Type} (f:X->X) (a:X) : X := f (f (f a)). >> Check @do3times : @do3times : forall X : Type, (X -> X) -> X -> X 이 do3times는 함수 f와 인자 a를 받아 a에 f를 3번 적용한 결과를 돌려준다. 함수를 인자로 제공한다는게 어떤 의미인지 살펴보자
>> Definition doubleMe (n:nat) : nat := n+n. >> Compute do3times doubleMe 3. : 24 : nat Filter 이제 좀더 유용한 고차 함수들에 대해 알아보자. filter는 X타입의 리스트(list X)와 원소 X에 대한 판정함수(predicate, \(f:X\rightarrow bool\))를 받아 주어진 predicate를 만족하는(i.e. true를 리턴하는) 원소들만을 남긴다.
Polymorphic Lists 이전 장에서 natlist, 다시 말해 nat으로 이루어진 리스트에 대해 다뤘다. 마찬가지 방법으로 문자열 리스트, bool 리스트, 리스트의 리스트 등 다양한 리스트를 정의할 수 있다. 예를 들어 bool 리스트는
Inductive boollist : Type := | bool_nil | bool_cons (b : bool) (l : boollist). 로 정의된다.
그런데 매번 새로운 타입의 리스트가 필요할 때마다 (거의) 동일한 정의를 다시 써주는 건 낭비일 것이다. 새로운 타입에 맞게 정의를 다시 쓴다는 말은 단순히 nil이나 cons의 문제가 아니라, length, reverse, append 등 앞서 natlist에서 정의했던 모든 함수를 전부 새로 작성해야 한다는 의미가 된다. 이런 불필요한 중복을 피하기 위해 Coq에서는 다형적(polymorphic) 타입을 지원한다.
Reasoning About Lists 리스트에 대한 간단한 정리를 증명해보자.
Theorem nil_app : forall l:natlist, [] ++ l = l. Proof. reflexivity. Qed. 대상이 natlist라는 점만 제외하면 이전의 forall n:nat, 0+n=n과 같은 형태이다. nat에서와 마찬가지로 natlist도 destruct를 통해 생성규칙에 따라 경우를 나눌 수 있다.
Theorem tl_length_pred : forall l:natlist, pred (length l) = length (tl l). Proof. intros l. destruct l as [| n l'] eqn:E. - (* l = [] *) reflexivity. - (* l = n::l' *) reflexivity. 마찬가지로 수학적 귀납법(induction tactic) 역시 적용 가능하다. nat에서의 귀납법과 마찬가지로 base step과 induction step으로 이루어져 있으며, 각각
본 챕터에서는 Structured Data, 그중에서도 List에 대해 다룬다.
Pairs of Numbers 지난번 nybble을 정의할 때 언급했듯이, Coq의 생성자(constructor)는 여러 개의 인자를 받을 수 있다.
Inductive natprod : Type := | pair (n1 n2 : nat). 이렇게 정의된 natprod에는 오직 하나의 생성규칙만 존재한다.(ex: pair 3 5)
Proof by Case Analysis 다뤄야 하는 대상이 복잡해지면 simpl이나 rewrite만으로는 충분하지 않은 경우가 있다. 잠시 예전 글에서 정의했던 is_equal을 가져오면서 여기에 새로운 Notation을 추가하자.
Fixpoint is_equal (n m : nat) : bool := match n with | O => match m with | O => true | S m' => false end | S n' => match m with | O => false | S m' => is_equal n' m' end end. Notation "x =? y" := (eqb x y) (at level 70) : nat_scope. 이제 거의 비슷하게 생긴 다음 두 명제를 증명해보자.
이제 Coq를 이용해 간단한 증명을 직접 작성해보자.
Notation 본론을 시작하기에 앞서 전에 만들었던 plus, mult 에 infix notation을 정의하자.
Notation "x + y" := (plus x y) (at level 50, left associativity) : nat_scope. Notation "x * y" := (mult x y) (at level 40, left associativity) : nat_scope. 이전에 bool에 대해 x && y 를 정의하던 때보다 뭔가 이것저것 늘어났다. prefix, postfix notation과는 달리 infix notation에서는 모호한(ambiguous) 문장이 생길 수 있다. 일반적으로 (x+y*z)라는 표현식을 쓸 때 우리는 ((x+y)*z)가 아닌 (x+(y*z))를 의도한다. 위 코드에서의 역할을 간단히 요약하면
Define Numbers 이전 글에서는 day, bool, color 와 같이 원소의 개수가 유한한 타입, 다시 말해 타입 \(T\)에 대해 \(\{x \| x \mathrm\{\,has\,type\,\}T\} \)가 유한집합인 경우만을 다뤘다. 무한한 원소를 가지는 타입을 정의하려면 어떻게 해야 할까? 집합론에서와 마찬가지로 자연수에서 시작해보자. 페아노 공리계(Peano axioms)에서 필요한 부분을 빌려오자. 크게 중요하지 않은 공리들은 생략했다
Introduction 여기서는 Coq에서 사용되는 Galina라는 functional programming language의 기초적인 사용법과, Coq에서 증명에 실제 활용되는 기초적인 tactic에 대해 다룬다.
Data and Functions Days of the Week 먼저 Coq에서 타입을 선언하는 법을 알아보자. 모든 Coq 구문은 .(마침표)로 끝남에 유의하자
Coq를 공부해보겠다는 막연한 목표와 함께 이런저런 자료를 찾아보고 그만두기를 반복하던 중, DeepSpec Summer School 세미나에서 나온 영상을 발견했다. 유투브에서 찾은 다른 영상들이 4,5년 전 자료였던 반면 DeepSpec에서는 최근인 2017, 2018년까지 꾸준히 학습자료와 세미나 영상이 업로드되고 있다.
사실 예전 LaTeX을 익힐 때에도 이것저것 찾아보기만 하다가 결국 학교 과제를 LaTeX으로 작성해보고서야 익숙해졌는데, 이번에도 실 사용 없이 공부하는게 얼마나 갈지는 잘 모르겠다.. 자료 초반에 “All the core chapters are suitable for both upper-level undergraduate and graduate students.” 라는 말이 있던데, 물론 저런 말들이 다 그렇듯이 전부 거짓말이겠지만 이젠 undergraduate 신분이라는 핑계도 사라졌으니 좀더 확실히 짚고 넘어가야겠다는 생각도 든다.
