Coq-std++
This project contains an extended "Standard Library" for Coq called coq-std++. The key features of this library are as follows:
- It provides a great number of definitions and lemmas for common data structures such as lists, finite maps, finite sets, and finite multisets.
- It uses type classes for common notations (like
∅
,∪
, and Haskell-style monad notations) so that these can be overloaded for different data structures. - It uses type classes to keep track of common properties of types, like it having decidable equality or being countable or finite.
- Most data structures are represented in canonical ways so that Leibniz
equality can be used as much as possible (for example, for maps we have
m1 = m2
iff∀ i, m1 !! i = m2 !! i
). On top of that, the library provides setoid instances for most types and operations. - It provides various tactics for common tasks, like an ssreflect inspired
done
tactic for finishing trivial goals, a simple breadth-first solvernaive_solver
, an equality simplifiersimplify_eq
, a solversolve_proper
for proving compatibility of functions with respect to relations, and a solverset_solver
for goals involving set operations. - It is entirely dependency- and axiom-free.
Side-effects
Importing std++ has some side effects as the library sets some global options. Notably:
-
Generalizable All Variables
: This option enables implicit generalization in arguments of the form`{...}
(i.e., anonymous arguments). Unfortunately, it also enables implicit generalization inInstance
. We think that the fact that both behaviors are coupled together is a bug in Coq. - The behavior of
Program
is tweaked:Unset Transparent Obligations
,Obligation Tactic := idtac
,Add Search Blacklist "_obligation_"
. Seebase.v
for further details.
Prerequisites
This version is known to compile with:
- Coq version 8.6.0 / 8.6.1 / 8.7.0 / 8.7.1
Installing via opam
To obtain the latest stable release via opam (1.2.2 or newer), you have to add the Coq opam repository:
opam repo add coq-released https://coq.inria.fr/opam/released
Then you can do opam install coq-stdpp
.
To obtain a development version, add the Iris opam repository:
opam repo add iris-dev https://gitlab.mpi-sws.org/FP/opam-dev.git
Building from source
Run make -jN
in this directory to build the library, where N
is the number
of your CPU cores. Then run make install
to install the library.