Preface

• Overview
• Practicalities
  • Required Background
• Coq
  • System Requirements
  • Access to the Coq files
• Exercises
• Recommended reading
• For Instructors

Basics: Functional programming and reasoning about programs

• Enumerated Types
  • Days of the week
  • Booleans
  • Function Types
  • Numbers
• Proof By Simplification
• The intros tactic
• Proof by rewriting
• Case analysis
• Naming cases
• Induction
• Formal vs. informal proof
• Proofs Within Proofs
• Extra Exercises

Lists: Products, Lists and Options

• Pairs of numbers
• Lists of numbers
  • Bags via lists
• Reasoning about lists
  • Induction on lists
• Options
• The apply tactic
• Varying the Induction Hypothesis
• Additional Exercises

Poly: Polymorphism and Higher-Order Functions

• Polymorphism
  • Polymorphic lists
  • Polymorphic pairs
  • Polymorphic options
• Functions as Data
  • Higher-order functions
  • Partial application
  • Digression: Currying
  • Filter
  • Anonymous functions
  • Map
  • Fold
  • Functions For Constructing Functions
• More About Coq
  • The unfold tactic
  • Inversion
  • Using tactics on hypotheses
  • Using destruct on compound expressions
  • The remember tactic
  • The apply ... with ... tactic
  • Additional exercises

Ind: Propositions and Evidence

• Review
• Programming with Propositions
• Evidence
  • Inductively Defined Propositions
  • The Curry-Howard Correspondence
  • Implication
  • Induction Axioms for Inductively Defined Types
  • Induction Hypotheses
  • A Closer Look at the induction Tactic
  • Reasoning by Induction Over Evidence
  • Why Define Propositions Inductively?
  • Induction Principles in Prop
  • Proofs About Inductively Defined Propositions
• The Big Picture: Coq's Two Universes
  • Values
  • Inductive Definitions
  • Functions and Quantifiers
  • Functions and Implications
  • Propositions and Booleans
• Generalizing Induction Hypotheses
• Additional Exercises

Logic: Logic in Coq

• Quantification and Implication
• Conjunction
  • Iff
• Disjunction
  • Digression: Induction Principles for /\ and \/
  • Relating /\ and \/ with andb and orb
• Falsehood
  • Truth
• Negation
  • Inequality
• Existential Quantification
• Equality
  • Inversion, Again
• Relations as Propositions
  • Digression: More facts about <= and <
• Informal Proofs, Again

Rel: Properties of Relations

• Relations
• Properties
• Reflexive, Transitive Closure

Template: Patterns for Inductive Proofs

• Templates for informal proofs by induction
  • Proof by induction over an inductively defined set
  • Induction over an inductively defined proposition

SfLib: Software Foundations Library

• From the Coq standard library
• From Basics.v
• From Props.v
• From Logic.v

Imp: Simple Imperative Programs

• Arithmetic and Boolean Expressions
  • Syntax
  • Evaluation
  • Optimization
• Coq Automation
  • Tacticals
  • Defining New Tactic Notations
  • The omega Tactic
  • A Few More Handy Tactics
• Expressions With Variables
  • Identifiers
  • States
  • Syntax
  • Evaluation
• Commands
  • Syntax
  • Examples
• Evaluation
  • Evaluation Function
  • Evaluation Relation
  • Inference Rule Notation
  • Equivalence of Relational and Step-Indexed Evaluation
  • Determinacy of Evaluation
• Reasoning about programs
• Additional Exercises

ImpParser: Lexing and Parsing in Coq

• Internals
  • Lexical Analysis
  • Parsing
• Examples

Equiv: Program Equivalence

• Behavioral equivalence
  • Definitions
  • Examples
  • Program Equivalence is an Equivalence
  • Program Equivalence is a Congruence
• Case Study: Constant Folding
  • Soundness of Program Transformations
  • The Constant-Folding Transformation
  • Soundness of Constant Folding
  • Soundness of (0 + n) elimination
• Proving That Programs Are Not Equivalent
• Reasoning about Imp programs
• Additional exercises

Hoare: Hoare Logic

• Hoare Logic
  • Assertions
  • Hoare Triples
  • Weakest Preconditions
  • Proof Rules
  • Decorated Programs
• Using Hoare Logic to Reason About Programs
  • Miscellaneous Lemmas
  • Example: Slow subtraction
  • Exercise: Reduce to zero
  • Exercise: Slow addition
  • Example: Parity
  • Example: Finding square roots
  • Exercise: Factorial

MoreHoare: Hoare Logic with Lists; Formalizing Decorated Programs

• Hoare Logic with Lists
  • Extensions
  • Repeated Definitions
  • Examples
• Formalizing Decorated Programs
  • Syntax
  • Extracting Verification Conditions
  • Examples

Smallstep: Small-step Operational Semantics

• A Toy Language
  • Values
  • Normal Forms
  • Exercises
• Multi-Step Reduction
  • Multi-Step Reduction
  • Normal Forms Again
  • Equivalence of Big-Step and Small-Step Reduction
  • Additional exercises
• Small-Step Imp
• Concurrent Imp

Stlc: The Simply Typed Lambda-Calculus

• More Automation
  • The auto and eauto Tactics
  • The Proof with Tactic
  • The solve by inversion Tactic
  • The try solve Tactic
  • The normalize Tactic
• Typed Arithmetic Expressions
  • Syntax
  • Small-step reduction
  • Normal Forms and Values
  • Typing
  • Progress
  • Type Preservation
  • Type Soundness
  • Additional exercises
• The Simply Typed Lambda-Calculus
  • Syntax and Operational Semantics
  • Typing
  • Properties
  • Additional exercises
• Exercise: STLC with Arithmetic
  • Syntax and operational semantics

MoreStlc: More on the Simply Typed Lambda-Calculus

• Typechecking for STLC
  • Comparing Types
  • The Typechecker
  • Properties
• Simple Extensions to STLC
• Formalizing the Extensions
  • Examples
  • Properties of Typing

References: Typing Mutable References

• Mutable References
  • Syntax
  • Pragmatics
  • Operational Semantics
  • Typing
  • Safety
• References and Nontermination
• Additional Exercises

Subtyping: Subtyping

• Concepts
  • A Motivating Example
  • Subtyping and Object-Oriented Languages
  • The Subsumption Rule
  • The Subtype Relation
• Core definitions
  • Definition
  • Subtyping Examples and Exercises
• Typing
  • Typing examples
• Properties
  • Inversion Lemmas for Subtyping
  • Progress
  • Inversion Lemmas for Typing
  • Context Invariance
  • Substitution
  • Preservation
  • Exercises on typing

Records

• Simple Extensions to STLC
• Formalizing the extensions
  • Examples
  • Properties of typing
• Subtyping: Subtyping
• Subtyping
• Core definitions
• Subtyping
  • Definition
  • Subtyping examples and exercises
  • Properties of subtyping
• Typing
  • Typing examples
  • Properties of typing
  • Exercises on typing