13

is there anything like the tactic simpl for Program Fixpoints?

In particular, how can one proof the following trivial statement? 

Program Fixpoint bla (n:nat) {measure n} :=
match n with
| 0 => 0
| S n' => S (bla n')
end.

Lemma obvious: forall n, bla n = n. 
induction n. reflexivity.
(* I'm stuck here. For a normal fixpoint, I could for instance use 
simpl. rewrite IHn. reflexivity. But here, I couldn't find a tactic 
transforming bla (S n) to S (bla n).*)

Obviously, there is no Program Fixpoint necessary for this toy example, but I'm facing the same problem in a more complicated setting where I need to prove termination of the Program Fixpoint manually.

Anton Trunov
  • 15,074
  • 2
  • 23
  • 43
ouler
  • 133
  • 6

1 Answers1

8

I'm not used to using Program so there's probably a better solution but this is what I came up with by unfolding bla, seeing that it was internally defined using Fix_sub and looking at the theorems about that function by using SearchAbout Fix_sub.

Lemma obvious: forall n, bla n = n.
Proof.
intro n ; induction n.
 reflexivity.
 unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
 rewrite IHn ; reflexivity.

(* This can probably be automated using Ltac *)
 intros x f g Heq.
  destruct x.
  reflexivity.
  f_equal ; apply Heq.
Qed.

In your real-life example, you'll probably want to introduce reduction lemmas so that you don't have to do the same work every time. E.g.:

Lemma blaS_red : forall n, bla (S n) = S (bla n).
Proof.
intro n.
 unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
 reflexivity.

(* This can probably be automated using Ltac *)
 intros x f g Heq.
  destruct x.
  reflexivity.
  f_equal ; apply Heq.
Qed.

This way, next time you have a bla (S _), you can simply rewrite blaS_red.

gallais
  • 11,823
  • 2
  • 30
  • 63
  • 2
    In the same idea, you can state the equation lemma for `bla`: `forall n, bla n = match n with | 0 => 0 | S n' => S (bla n') end.` – eponier Apr 01 '16 at 08:19
  • 3
    Is that really the best answer? Doesn’t that make `Program Fixpoint` relatively tedious for large functions, when you have to manually write a reduction lemma? – Joachim Breitner Oct 28 '17 at 23:09
  • 3
    More recent plugins like `Equations` generate reduction lemmas for you. – gallais Oct 29 '17 at 08:00