Skip to content

Instantly share code, notes, and snippets.

@elefthei
Created July 18, 2021 00:27
Show Gist options
  • Save elefthei/9b8e9cb943ca4e3dc548e5404b29cec5 to your computer and use it in GitHub Desktop.
Save elefthei/9b8e9cb943ca4e3dc548e5404b29cec5 to your computer and use it in GitHub Desktop.
Coq getting equality out of `Program Fixpoint`
From Coq Require Import Vectors.VectorDef.
From Coq Require Import micromega.Lia.
From Coq Require Import Program.Basics Program.Equality.
From Coq Require Import Arith.PeanoNat.
Import VectorNotations.
Open Scope program_scope.
Definition vec := t.
Program Definition double{n}(v: vec unit n): vec unit (n*2) :=
v ++ v.
Next Obligation. lia. Defined.
Program Fixpoint exp(n: nat): vec unit (2^n) :=
match n with
| 0 => [tt]
| S n' => double (exp n') (** I want this equality *)
end.
Next Obligation. lia. Defined.
(** First, define the body of the lemma as a definition *)
Program Definition exp_Sn'_body(n: nat) := exp (S n) = double (exp n).
Next Obligation. exact (exp_obligation_1 n). Defined. (** Provide the same proof as `exp` *)
Lemma exp_Sn: forall n,
exp_Sn'_body n.
Proof.
unfold exp_Sn'_body.
simpl_eq. (* Ltac from Program.Equality *)
unfold exp_Sn'_body_obligation_1.
reflexivity.
Defined.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment