Jean-Christophe Filliâtre and Pierre Letouzey
We present here the Coq extraction commands, used to build certified and relatively efficient functional programs, extracting them from the proofs of their specifications. The functional languages available as output are currently Objective Caml, Haskell and Scheme. In the following, “ML” will be used (abusively) to refer to any of the three.
The current extraction mechanism is new for version 7.0 of Coq. In particular, the F_{ω} toplevel used as an intermediate step between Coq and ML has been withdrawn. It is also not possible any more to import ML objects in this F_{ω} toplevel. The current mechanism also differs from the one in previous versions of Coq: there is no more an explicit toplevel for the language (formerly called Fml).
The next two commands are meant to be used for rapid preview of extraction. They both display extracted term(s) inside Coq.
Extracts one constant or module in the Coq toplevel.
Recursive extraction of all the globals (or modules) qualid_{1} … qualid_{n} and all their dependencies in the Coq toplevel.
All the following commands produce real ML files. User can choose to produce one monolithic file or one file per Coq library.
Recursive extraction of all the globals (or modules) qualid_{1} … qualid_{n} and all their dependencies in one monolithic file file. Global and local identifiers are renamed according to the choosen ML language to fullfill its syntactic conventions, keeping original names as much as possible.
Extraction of the whole Coq library ident.v to an ML module
ident.ml. In case of name clash, identifiers are here renamed
using prefixes coq_
or Coq_
to ensure a
session-independent renaming.
Extraction of the Coq library ident.v and all other modules ident.v depends on.
The list of globals qualid_{i} does not need to be exhaustive: it is automatically completed into a complete and minimal environment.
The ability to fix target language is the first and more important of the extraction options. Default is Ocaml. Besides Haskell and Scheme, another language called Toplevel is provided. It is a pseudo-Ocaml, with no renaming on global names: so names are printed as in Coq. This third language is available only at the Coq Toplevel.
Since Objective Caml is a strict language, the extracted code has to be optimized in order to be efficient (for instance, when using induction principles we do not want to compute all the recursive calls but only the needed ones). So the extraction mechanism provides an automatic optimization routine that will be called each time the user want to generate Ocaml programs. Essentially, it performs constants inlining and reductions. Therefore some constants may not appear in resulting monolithic Ocaml program (a warning is printed for each such constant). In the case of modular extraction, even if some inlining is done, the inlined constant are nevertheless printed, to ensure session-independent programs.
Concerning Haskell, such optimizations are less useful because of lazyness. We still make some optimizations, for example in order to produce more readable code.
All these optimizations are controled by the following Coq options:
Default is Set. This control all optimizations made on the ML terms (mostly reduction of dummy beta/iota redexes, but also simplications on Cases, etc). Put this option to Unset if you want a ML term as close as possible to the Coq term.
Default is Set, so by default, the extraction mechanism feels free to inline the bodies of some defined constants, according to some heuristics like size of bodies, useness of some arguments, etc. Those heuristics are not always perfect, you may want to disable this feature, do it by Unset.
In addition to the automatic inline feature, you can now tell precisely to inline some more constants by the Extraction Inline command. Conversely, you can forbid the automatic inlining of some specific constants by the Extraction NoInline command. Those two commands enable a precise control of what is inlined and what is not.
Prints the current state of the table recording the custom inlinings declared by the two previous commands.
Puts the table recording the custom inlinings back to empty.
A user can explicitely asks a constant to be extracted by two means:
In both cases, the declaration of this constant will be present in the produced file. But this same constant may or may not be inlined in the following terms, depending on the automatic/custom inlining mechanism.
For the constants non-explicitely required but needed for dependancy reasons, there are two cases:
Extraction will fail if it encounters an informative axiom not realized (see section 18.2.3). A warning will be issued if it encounters an logical axiom, to remind user that inconsistant logical axioms may lead to incorrect or non-terminating extracted terms.
It is possible to assume some axioms while developing a proof. Since these axioms can be any kind of proposition or object or type, they may perfectly well have some computational content. But a program must be a closed term, and of course the system cannot guess the program which realizes an axiom. Therefore, it is possible to tell the system what ML term corresponds to a given axiom.
Give an ML extraction for the given constant. The string may be an identifier or a quoted string.
Same as the previous one, except that the given ML terms will be inlined everywhere instead of being declared via a let.
Note that the Extract Inlined Constant command is sugar for an Extract Constant followed by a Extraction Inline. Hence a Reset Extraction Inline will have an effect on the realized and inlined xaxiom.
Of course, it is the responsability of the user to ensure that the ML terms given to realize the axioms do have the expected types. In fact, the strings containing realizing code are just copied in the extracted files. The extraction recognize whether the realized axiom should become a ML type constant or a ML object declaration.
Example:
Notice that in the case of type scheme axiom (i.e. whose type is an arity, that is a sequence of product finished by a sort), then some type variables has to be given. The syntax is then:
The number of type variable given is checked by the system.
Example:
Realizing an axiom via Extract Constant is only useful in the case of an informative axiom (of sort Type or Set). A logical axiom have no computational content and hence will not appears in extracted terms. But a warning is nonetheless issued if extraction encounters a logical axiom. This warning reminds user that inconsistant logical axioms may lead to incorrect or non-terminating extracted terms.
If an informative axiom has not been realized before an extraction, a warning is also issued and the definition of the axiom is filled with an exception labelled AXIOM TO BE REALIZED. The user must then search these exceptions inside the extracted file and replace them by real code.
The system also provides a mechanism to specify ML terms for inductive types and constructors. For instance, the user may want to use the ML native boolean type instead of Coq one. The syntax is the following:
Give an ML extraction for the given inductive type. You must specify extractions for the type itself (first string) and all its constructors (between square brackets). The ML extraction must be an ML recursive datatype.
Example: Typical examples are the following:
Due to differences between Coq and ML type systems, some extracted programs are not directly typable in ML. We now solve this problem (at least in Ocaml) by adding when needed some unsafe casting Obj.magic, which give a generic type ’a to any term.
For example, Here are two kinds of problem that can occur:
Definition dp := fun (A B:Set)(x:A)(y:B)(f:forall C:Set, C->C) => (f A x, f B y).
In Ocaml, for instance, the direct extracted term would be:
let dp x y f = Pair((f () x),(f () y))
and would have type:
dp : 'a -> 'a -> (unit -> 'a -> 'b) -> ('b,'b) prod
which is not its original type, but a restriction.
We now produce the following correct version:
let dp x y f = Pair ((Obj.magic f () x), (Obj.magic f () y))
Inductive anything : Set := dummy : forall A:Set, A -> anything.
which corresponds to the definition of an ML dynamic type. In Ocaml, we must cast any argument of the constructor dummy.
Even with those unsafe castings, you should never get error like “segmentation fault”. In fact even if your program may seem ill-typed to the Ocaml type-checker, it can’t go wrong: it comes from a Coq well-typed terms, so for example inductives will always have the correct number of arguments, etc.
More details about the correctness of the extracted programs can be found in [86].
We have to say, though, that in most “realistic” programs, these problems do not occur. For example all the programs of Coq library are accepted by Caml type-checker without any Obj.magic (see examples below).
We present here two examples of extractions, taken from the Coq Standard Library. We choose Objective Caml as target language, but all can be done in the other dialects with slight modifications. We then indicate where to find other examples and tests of Extraction.
The file Euclid contains the proof of Euclidean division (theorem eucl_dev). The natural numbers defined in the example files are unary integers defined by two constructors O and S:
This module contains a theorem eucl_dev, and its extracted term is of type
forall b:nat, b > 0 -> forall a:nat, diveucl a b
where diveucl is a type for the pair of the quotient and the modulo. We can now extract this program to Objective Caml:
The inlining of gt_wf_rec and lt_wf_rec is not mandatory. It only enhances readability of extracted code. You can then copy-paste the output to a file euclid.ml or let Coq do it for you with the following command:
Let us play the resulting program:
# #use "euclid.ml";; type sumbool = Left | Right type nat = O | S of nat type diveucl = Divex of nat * nat val minus : nat -> nat -> nat = <fun> val le_lt_dec : nat -> nat -> sumbool = <fun> val le_gt_dec : nat -> nat -> sumbool = <fun> val eucl_dev : nat -> nat -> diveucl = <fun> # eucl_dev (S (S O)) (S (S (S (S (S O)))));; - : diveucl = Divex (S (S O), S O)
It is easier to test on Objective Caml integers:
# let rec i2n = function 0 -> O | n -> S (i2n (n-1));; val i2n : int -> nat = <fun> # let rec n2i = function O -> 0 | S p -> 1+(n2i p);; val n2i : nat -> int = <fun> # let div a b = let Divex (q,r) = eucl_dev (i2n b) (i2n a) in (n2i q, n2i r);; div : int -> int -> int * int = <fun> # div 173 15;; - : int * int = 11, 8
The file Heap.v contains the proof of an efficient list sorting algorithm described by Bjerner. Is is an adaptation of the well-known heapsort algorithm to functional languages. The main function is treesort, whose type is shown below:
Let’s now extract this function:
One more time, the Extraction Inline and NoInline directives are cosmetic. Without it, everything goes right, but the output is less readable. Here is the produced file heapsort.ml:
type nat = | O | S of nat type 'a sig2 = 'a (* singleton inductive, whose constructor was exist2 *) type sumbool = | Left | Right type 'a list = | Nil | Cons of 'a * 'a list type 'a multiset = 'a -> nat (* singleton inductive, whose constructor was Bag *) type 'a merge_lem = 'a list (* singleton inductive, whose constructor was merge_exist *) (** val merge : ('a1 -> 'a1 -> sumbool) -> ('a1 -> 'a1 -> sumbool) -> 'a1 list -> 'a1 list -> 'a1 merge_lem **) let rec merge leA_dec eqA_dec l1 l2 = match l1 with | Nil -> l2 | Cons (a, l) -> let rec f = function | Nil -> Cons (a, l) | Cons (a0, l3) -> (match leA_dec a a0 with | Left -> Cons (a, (merge leA_dec eqA_dec l (Cons (a0, l3)))) | Right -> Cons (a0, (f l3))) in f l2 type 'a tree = | Tree_Leaf | Tree_Node of 'a * 'a tree * 'a tree type 'a insert_spec = 'a tree (* singleton inductive, whose constructor was insert_exist *) (** val insert : ('a1 -> 'a1 -> sumbool) -> ('a1 -> 'a1 -> sumbool) -> 'a1 tree -> 'a1 -> 'a1 insert_spec **) let rec insert leA_dec eqA_dec t a = match t with | Tree_Leaf -> Tree_Node (a, Tree_Leaf, Tree_Leaf) | Tree_Node (a0, t0, t1) -> let h3 = fun x -> insert leA_dec eqA_dec t0 x in (match leA_dec a0 a with | Left -> Tree_Node (a0, t1, (h3 a)) | Right -> Tree_Node (a, t1, (h3 a0))) type 'a build_heap = 'a tree (* singleton inductive, whose constructor was heap_exist *) (** val list_to_heap : ('a1 -> 'a1 -> sumbool) -> ('a1 -> 'a1 -> sumbool) -> 'a1 list -> 'a1 build_heap **) let rec list_to_heap leA_dec eqA_dec = function | Nil -> Tree_Leaf | Cons (a, l0) -> insert leA_dec eqA_dec (list_to_heap leA_dec eqA_dec l0) a type 'a flat_spec = 'a list (* singleton inductive, whose constructor was flat_exist *) (** val heap_to_list : ('a1 -> 'a1 -> sumbool) -> ('a1 -> 'a1 -> sumbool) -> 'a1 tree -> 'a1 flat_spec **) let rec heap_to_list leA_dec eqA_dec = function | Tree_Leaf -> Nil | Tree_Node (a, t0, t1) -> Cons (a, (merge leA_dec eqA_dec (heap_to_list leA_dec eqA_dec t0) (heap_to_list leA_dec eqA_dec t1))) (** val treesort : ('a1 -> 'a1 -> sumbool) -> ('a1 -> 'a1 -> sumbool) -> 'a1 list -> 'a1 list sig2 **) let treesort leA_dec eqA_dec l = heap_to_list leA_dec eqA_dec (list_to_heap leA_dec eqA_dec l)
Let’s test it:
# #use "heapsort.ml";; type sumbool = Left | Right type nat = O | S of nat type 'a tree = Tree_Leaf | Tree_Node of 'a * 'a tree * 'a tree type 'a list = Nil | Cons of 'a * 'a list val merge : ('a -> 'a -> sumbool) -> 'b -> 'a list -> 'a list -> 'a list = <fun> val heap_to_list : ('a -> 'a -> sumbool) -> 'b -> 'a tree -> 'a list = <fun> val insert : ('a -> 'a -> sumbool) -> 'b -> 'a tree -> 'a -> 'a tree = <fun> val list_to_heap : ('a -> 'a -> sumbool) -> 'b -> 'a list -> 'a tree = <fun> val treesort : ('a -> 'a -> sumbool) -> 'b -> 'a list -> 'a list = <fun>
One can remark that the argument of treesort corresponding to eqAdec is never used in the informative part of the terms, only in the logical parts. So the extracted treesort never use it, hence this ’b argument. We will use () for this argument. Only remains the leAdec argument (of type ’a -> ’a -> sumbool) to really provide.
# let leAdec x y = if x <= y then Left else Right;; val leAdec : 'a -> 'a -> sumbool = <fun> # let rec listn = function 0 -> Nil | n -> Cons(Random.int 10000,listn (n-1));; val listn : int -> int list = <fun> # treesort leAdec () (listn 9);; - : int list = Cons (160, Cons (883, Cons (1874, Cons (3275, Cons (5392, Cons (7320, Cons (8512, Cons (9632, Cons (9876, Nil)))))))))
Some tests on longer lists (10000 elements) show that the program is quite efficient for Caml code.
As a test, we propose an automatic extraction of the Standard Library of Coq. In particular, we will find back the two previous examples, Euclid and Heapsort. Go to directory contrib/extraction/test of the sources of Coq, and run commands:
make tree; make
This will extract all Standard Library files and compile them. It is done via many Extraction Module, with some customization (see subdirectory custom).
This test works also with Haskell. In the same directory, run:
make tree; make -f Makefile.haskell
The haskell compiler currently used is hbc. Any other should also work, just adapt the Makefile.haskell. In particular ghc is known to work.
Some pathological examples of extraction are grouped in the file
contrib/extraction/test_extraction.v
of the sources of Coq.
Several of the Coq Users’ Contributions use extraction to produce certified programs. In particular the following ones have an automatic extraction test (just run make in those directories):
Lannion, Rocq/HIGMAN and Lyon/CIRCUITS are a bit particular. They are the only examples of developments where Obj.magic are needed. This is probably due to an heavy use of impredicativity. After compilation those two examples run nonetheless, thanks to the correction of the extraction [86].