I use company-coq in Emacs. Some symbols will
display differently in your setup. At the
bottom of this file there is a list of
Example: An optimized arithmetic evaluator
Idea: have a syntactic representation of
arithmetic operations so we can write a sound
- The type of arithmetic expressions [ aexp ].
- An evaluator: [ ⟦a⟧ₙ ]
- An optimizer: [ optimize a ]
- A proof of soundness: [ ⟦optimize a⟧ₙ = ⟦a⟧ₙ ]
We can evaluate an arithmetic expression
The following function takes an arithmetic
expression and slightly simplifies it, changing
every occurrence of [0 `+ e] into just [e].
(Note: there are two pattern-matches here!) To make sure our optimization is doing the
right thing we can test it on some examples
and see if the output looks OK.
But if we want to be sure the optimization is
correct -- i.e., that evaluating an optimized
expression gives the same result as the
original -- we should prove it.
Proofs can be written in a variety of forms. Vanilla Coq of An Inexperience User
- repeats a lot of similar operations.
- it resorts to arbitrary named variables.
- The proof breaks at any change in the context
or in the naming conventions in Coq.
- What if we add...? [Let a1 := `1.]
Proof without naming usign ssreflect.
Better, but still has a lot of repetition. A shorter proof with some automation.
If we remove the comments, we see that the
whole proof is only a few lines long now: (I
am inlining the first case)
We avoided the repetition in the proof and the
explicit use of generated names. However, there
is still a big issue here: we need to remember
the exact positions of variables and hypotheses
(the [?] and [->])! Writing custom tactics Let's write an alternative formulation,
without having to remember positions. The idea is
to pick from the context the right hypotheses to
do rewrite. We write a tactic using Ltac, the tactic
language of Coq.
Simplify and move everything in the list of
Adapting proofs to changes in definitions
We now perform a reasonable change and see how
that affects our proof. Instead of having one case
for each binary operator, we squish them in one
This is exactly the same
The optimizer is a bit different
We introduced the change; let's replay now the
proof and see how it breaks.
The actual proof
Idea: specify the type of the element to
perform elimination or case analysis so we always
know before hand why the proof breaks.
Let's do a tactic to check the type of the first
variable in the goal.
Add some nice notation because why not
If we have used the check in the original
proof, we would have gotten a much better error
Specifying the exact cases There is one last annoyence: we have no
guarantee that the case we're solving is actually
the case we want to solve: what is [first] or
[last]? When should [try] succeed?
We change the optimizer to do one more thing:
If we replay the same proof as for [optimize],
We have more cases!
We'd like to write a tactic to select specific
cases in an elim/case, something of the sort
✓ binop; case; except OPlus, OMult do
Unfortunately, Ltac won't help us here: there is
no support for this, or at least no simple way to
solve it without resorting to ugly hacks.
We need to bring another tactic language.
This is not the only limitation of Ltac: another
limitation is present already in the [✓] tactic,
as it doesn't work properly for polymorphic types:
We will make little use of its __typed__
nature, which is crucial in certain types of
tactics (see [Kaiser et al., ICFP 2018] for this
kind of use).
The point we make here is to show features that
are useful to code proofs and must therefore be
incorporated into tactic languages.
We start by re-doing the tactics we wrote so far,
but now in Mtac2.
Here we are just "importing" other tactics:
the ones from ssreflect and the tactic
[solve_rewriting] tactic we did above.
We re-create [check_arg] because of Ltac's
issue. We define a specific exception for it.
[check_arg] is almost the same as the Ltac
Note: It is a Coq definition! We can write a
standard Coq notation for it:
We can write the proof almost as we did before.
[|1>] is [first] and [l>] is [last]
So far, we gain little to what we had. The
interesting bit comes when we can specify exactly
what are the cases we expect will remain in the
proof. For this we use the tactical included in
Mtac2 to specify the specific cases a tactic must
When we use the same proof for [optimize_more]
we see the error we get:
The error message could be improved. Good
news: we can do it easily! The Mtac2 tactics are
all written in Gallina, so we can simply rewrite
them at will for our project (of course, we can
and should also push to Mtac2's repo!).
Let's define an exception to show the
constructor of the failing case.
Yes, I love notations!
[apply_except] takes a list of constructors
[l] and a tactic [t]
We try the same proof again.
When applied to a real proof (also from SF) we
get... (demo PE.V)
Before concluding: One liners An alternative to the full-control style of
proving advocated here is to use heavy
proof-search. Let's bring THE HAMMER!
- It often takes way too long to solve or fail.
- When it fails you don't know why and how to fix it.
We will now move to a different kind of
tactics: we will take a natural number and convert
it to a
We can add a proof that the result evaluates
to the same.
It is too typed: it fails because we do not
have a proof for every nat.