The Coq mailing list

[Matthieu Sozeau <matthieu.sozeau AT inria.fr>]

Dear Coq-clubbers,

  We are pleased to announce release 1.0 of the Equations package. Equations is available through sources on github and through opam (package coq-equations.1.0for Coq 8.6 and coq-equations.1.0+8.7 for 8.7 and 8.7.1).

  Equations is a function definition plugin for Coq, that allows the definition of functions by dependent pattern-matching and well-founded, mutual or nested structural recursion and compiles them into core terms. It automatically derives the clauses equations, the graph of the function and its associated elimination principle.

  This version of Equations is based on a new simplification engine for the dependent equalities appearing in dependent eliminations that is also usable as a separate tactic, providing an axiom-free variant of dependent destruction. The main features of Equations include:

• Dependent pattern-matching in the style of Agda/Epigram, with inaccessible patterns, with and where clauses. The use of the K/UIP axiom or a user-provided proof of K is configurable, through the  Equations WithKoption.

• Support for well-founded recursion using by rec annotations, and automatic derivation of the subterm relation for inductive families.

• Support for mutual and nested structural recursion using with and where auxilliary definitions, allowing to factor multiple uses of the same nested fixpoint definition. It proves the expected elimination principles for mutual and nested definitions.

• Automatic generation of the defining equations as rewrite rules for every definition.

• Automatic generation of the unfolding lemma for well-founded definitions (requiring only functional extensionality).

• Automatic derivation of the graph of the function and its elimination principle. In case the automation fails to prove these principles, the user is asked to provide a proof.

• A new dependent elimination tactic based on the same splitting tree compilation scheme that can advantageously replace dependent destruction and sometimes inversion as well. The as clause of dependent elimination allows to specify exactly the patterns and naming of new variables needed for an elimination. The tactic is still a work-in-progress.

• A set of Derive commands for automatic derivation of constructions from an inductive type: its signature, no-confusion property, well-founded subterm relation and decidable equality proof, if applicable.

The current system is usable for developping non-toy programs and proofs (see examples). Documentation is available on the website, including a reference manual with an introduction to the features of the plugin. We are seeking and welcoming feedback from you on the usage of these tools!

– Matthieu Sozeau and Cyprien Mangin