Archive 2019
Program requirementsprojet
TeacherPierre Letouzey
Weekly hours 2 h CM , 2 h TP
Years Master Logique et Fondements de l'Informatique

Syllabus

The course take place during the last 6 weeks of the 1st semester and the first 6 weeks of the 2nd semester.

One half of this module will consist of course work, the other half will consist of practical work on a machine. The course will finish with a project to be carried out in Coq. The first part of this course is a prerequisite for the Homotopy Type Theory course.

Contents

Functional programming in Coq

  • Lambda-calculus, recursivity (and its limitations in Coq), ML style typing
  • Common data structures (Boolean, integers, lists, options, trees, etc.)
  • Generic programming: polymorphism, modules, type classes
  • Dependent types
  • Connections with other languages such as OCaml, presentation of the "absent" from Coq (exceptions, imperative traits, input-output,...), how to make the link between OCaml and Coq

Formal proofs in Coq

  • Specification language, basic logical rules
  • Arithmetic, calculation, rewriting, recurrence
  • Proof of properties of the usual data structures
  • Inductive predicates
  • Automation
  • Possibly: a quick overview of other proof assistants and comparison with Coq

Bibliography