Skip to content
A Coq library to embed Impure OCaml oracles in certified Coq code
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
BasicImpExample
CanonNatExample
FibExample
coq_src
.gitignore
LICENSE
Makefile
README.md

README.md

ImpureDemo: importing OCaml functions as non-deterministic ones.

This repository contains a few demonstrations of using Impure library located here at coq_src/Impure/ as a git-subrepo.

The principle of the Impure library is to encode the type A -> B of an OCaml function as a type A -> ?? B in Coq, where ?? B is the type of an axiomatized monad that can be interpreted as B -> Prop. In other word, this encoding abstracts an OCaml function as a function returning a postcondition on its possible results (ie a relation between its parameter and its result). Side-effects are simply ignored. And reasoning on such a function is only possible in partial correctness.

A major feature of this cooperation between Coq and OCaml typechecker is to provide very simple parametric proofs about polymorphic OCaml functions. They correspond here to prove, by reasoning only on their type, that these functions preserve some invariants. As an example, we prove the partial correctness of a generic memoizing fixpoint operator: see rec_correct lemma at the end of ImpLoops. This lemma is applied in FibExample to prove the partial correctness of a memoized version of the naive Fibonacci function. However, currently, the soundness of these parametric proofs is still a conjecture.

A more significant use case of Impure is provided by satans-cert -- a certified checker of (Boolean) sat-solver answers. The ancester of Impure is also present in the Verified Polyhedra Library.

Credits

Sylvain Boulmé.

Installation

Requirements

  1. ocaml. Tested with versions >= 4.05 and <= 4.07.0. (But other versions should work too).

  2. ocamlbuild. Tested with version 0.12.0. (But other versions should work too).

  3. coq. Tested with versions >= 8.7.2 and <= 8.8.2. Here, other versions are likely to not work !

Compilation

After cloning, just change directory for a building directory (see below), and run make.

Code Overview

coq_src/ contains the Coq sources. Other directories aims to build examples of binaries.

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.