source: C-semantics/README @ 226

Status of matita port of CompCert 1.6 C semantics
=================================================

Last seen working with matita svn r10998.

- 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.

- The Clight syntax file has been ported, minus a few lemmas that are not used
  by the semantics.

- The small-step inductively defined Clight semantics has been ported.

- 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 theory about machine integers (i.e., integers modulo) are
  given as axioms in Integers.ma.  Proving 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.

* The executable semantics can be found in CexecIO.ma, which uses the
  resumption monad defined in IOMonad.ma.

* The patch in acc-0.1.spaces.patch adds a -ma option to the prototype
  compiler which outputs a matita file containing the Clight program as
  a definition usable by the semantics.  It also adds parsing support for
  the memory space extensions (__data and friends).

* 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.)
  This is an older version of the prototype compiler patch, and lacks the
  memory extensions.

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 mostly 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!  Likely to be removed because we do
  not intend to support floating point.

Globalenvs.ma

  Basic definition only; sufficient for animating the semantics.

Integers.ma

  The operations have been ported, although the results about them generally
  have not.  The equality results have been left axiomatised because they
  require proof irrelevance because each integer carries a proof that it is
  in range.  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 most of the simulations sections
  for later.

Values.ma

  The definitions about operations relevant to the Clight semantics have been
  ported.  The other definitions and most of the lemmas still remain to be done.