Status of matita port of CompCert 1.6 C semantics
=================================================
Last seen working with matita svn r10890.
- Most of the memory model has been ported (common/Mem.v -> Mem.ma).
The main exception is minor arithmetic results than were proven with
omega, which we hope to prove using matita's automation at some
point.
- The memory model is executable; some small tests can be found in
test/memorymodel.ma. Note that the handling of integer values is
axiomatised, so conversions are not yet evaluated.
- The C syntax has been ported, minus a few lemmas that are not used by
the semantics.
- Most of the small-step C semantics has been ported, although much of the
underlying arithmetic and environment functions are only present as axioms,
including the type of identifiers.
- Nonetheless, this is sufficient to show the semantics of a trivial C program
in test/trivial.ma.
- A collection of definitions and lemmas that probably ought to be in
matita's standard library can be found in extralib.ma.
- Some of the machine integers (i.e., integers modulo) results are
given as axioms in Integers.ma. Implementing them should be routine now that
we have a binary representation of integers. The CompCert version is given
as a functor on the word size - we don't have an equivalent of this yet.
* Some experimental work on an executable semantics has been started in
Cexec.ma. At present only a small subset of expressions and statements
are handled.
* The patch in compcert-1.7.1-matita.patch adds a -dmatita option to
output a matita file containing a definition for the C program.
Note that there must be a "main" function. (This was made against
1.7.1 for convenience - the Clight syntax is the same as 1.6.)
There is a more recent version of compcert available with a revised memory
model that may be more closely suited to our needs.
matita issues and workarounds
-----------------------------
No unfold tactic yet; use reduction or rewriting instead.
Normalization of term containing large definitions (such as some of the
Integers library) can be prohibitive. This is a particular problem because
ndestruct currently normalizes the goal and every hypothesis that is rewritten.
For ndestruct, getting rid of irrelevant information (e.g., replacing the goal
with False) sometimes helps, an extra lemma can be used, or the definitions
can make careful use of 'nlet rec' to prevent reduction.
Some of the pattern matching in the C syntax has had to be unfolded in
a rather unpleasant way (where matching on pairs was used in the original).
The use of records in place of modules is a little delicate: large records
tend to use a lot of memory and processor at the moment, and the names of the
fields tend to clash a lot.
The lack of sections has been replaced by duplicating the variables in some
places, and adding a record in others.
The meminj_no_overlap definition in Mem.ma uses the logical Or explicitly
rather than the ∨ notation to regain reasonable performance. (This is
presumably due to disambiguation - the notation is also used for booleans.)
There are a couple of places in Mem.ma where rewriting had to be done carefully
to avoid assertions during unification; I'm not really sure what the problem
is.
Detail per-file
---------------
AST.ma
Program transformation sections left alone.
Coqlib.ma
Only essential parts:
- align
- some 2^n lemmas (which could go into the binary libraries)
- option_map
- parts of list disjointness and non-repetition
Csem.ma
The small step semantics have been ported. None of the big step semantics or
the equivalence proof has been ported.
Csyntax.ma
Everything except for a few minor definitions / lemmas that are not required
by the semantics.
Errors.ma
Only a basic definition without error messages.
Events.ma
Most of the definitions; haven't needed many of the lemmas yet.
Floats.ma
Axiomatised, but so was the original!
Globalenvs.ma
Basic definition only.
Integers.ma
Most of the operations have been ported, although some have been left as
axioms because the underlying operation is not present. The use of the
Coq module system to abstract over the word size has been left out for
now.
Maps.ma
Only a basic definition.
Mem.ma
Everything except for omega in proofs.
Smallstep.ma
Ported definitions for multiple steps and program behaviour; left
alternative definitions, some lemmas, plus simulations sections for later.
Values.ma
The definitions about values which don't rely on arithmetics operations that
haven't been ported yet are done. The other definitions and most of the
lemmas still remain to be done.