Proof leaking in Coq extraction?

Question

In order to understand how general recursive Function definitions works, and how they comply with Coq's structural recursion constraint, I tried to reimplement it on the Peano natural numbers. I want to define recursive nat -> nat functions that can use any previous values, not just the predecessor. Here is what I did :

  Definition nat_strong_induction_set
             (* erased at extraction, type specification *)
             (P : nat -> Set)
             (* The strong induction step. To build the P n it can, but does not have to, 
                recursively query the construction of any previous P k's. *)
             (ind_step : forall n : nat, (forall k : nat, (lt k n -> P k)) -> P n)
             (n : nat)
    : P n.
  Proof.
    (* Force the hypothesis of ind_step as a standard induction hypothesis *)
    assert (forall m k : nat, lt k m -> P k) as partial_build.
    { induction m.
      - intros k H0. destruct k; inversion H0.
      - intros k H0. apply ind_step. intros k0 H1. apply IHm. apply (lt_transitive k0 k).
        assumption. apply le_lt_equiv. assumption. }
    apply (partial_build (S n) n). apply succ_lt.
  Defined.

I used some custom lemmas on nats that I didn't paste here. It works, I managed to define the euclidean division div a b with it, which recursively uses div (a-b) b. The extraction is almost what I expected :

let nat_strong_induction_set ind_step n =
  let m = S n in
  let rec f n0 k =
    match n0 with
    | O -> assert false (* absurd case *)
    | S n1 -> ind_step k (fun k0 _ -> f n1 k0)
  in f m n

Except for the n0 parameter. We see that the only effect of this parameter is to stop the recursion at the S n-nth step. The extraction also mentions that this assert false should not happen. So why is it extracted ? This seems better

let nat_strong_induction_set ind_step n =
  let rec f k = ind_step k (fun k0 _ -> f k0)
  in f n

It looks like a glitch of Coq's structural recursion constraint, to ensure the termination of all recursions. The Coq definition of nat_strong_induction_set writes lt k n, so Coq knows only previous P k's will be queried. This makes a decreasing chain in the nats, which is forced to terminate in less than S n steps. This allows a structural recursive definition on an additional fuel parameter n0 starting at S n, it won't affect the result. So if it is only a part of the termination proof, why is it not erased by the extraction ?

Arthur Azevedo De Amorim Arthur Azevedo De Amorim · Accepted Answer · 2018-08-14T15:58:09

Your match is not erased because your definition mixes two things: the termination argument, where the match is needed, and the computationally relevant recursive call, where it isn't.

To force erasure, you need to convince Coq that the match is computationally irrelevant. You can do so by making the termination argument -- that is, the induction on m -- produce the proof of a proposition instead of a function of type forall m k, lt k m -> P k. Luckily, the standard library provides an easy way of doing so, with the Fix combinator:

Require Import Coq.Arith.Wf_nat.

Definition nat_strong_induction_set
             (P : nat -> Set)
             (ind_step : forall n : nat, (forall k : nat, (lt k n -> P k)) -> P n)
             (n : nat)
    : P n :=
  Fix lt_wf P ind_step n.

Here, lt_wf is a proof that lt is well-founded. When you extract this function, you get

let rec nat_strong_induction_set ind_step n =
  ind_step n (fun y _ -> nat_strong_induction_set ind_step y)

which is exactly what you wanted.

(As an aside, note that you don't need well-founded recursion to define division -- check for instance how it is defined in the Mathematical Components library.)

Proof leaking in Coq extraction?

1 Answers