본 챕터에서는 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 신분이라는 핑계도 사라졌으니 좀더 확실히 짚고 넘어가야겠다는 생각도 든다.
