Coq中push/pop求值器产生异常证明义务的问题

Great question! Let's break down why you're hitting these issues with your dependent-type stack language, and how to fix the evaluation function properly.

Why the Original Fixpoint Fails #

Your original Fixpoint worked for push and pop because their index relationships were straightforward:

• push takes a Prog n and produces a Prog (S n) (stack size increases by 1)
• pop takes a Prog (S n) and produces a Prog n (stack size decreases by 1)

When you added pop'—which requires the stack to have at least 2 elements before execution—its constructor has a more complex index dependency: forall n, Prog (S (S n)) -> Prog (S n). The original Fixpoint fails because Coq can't automatically infer the link between the current program's index n and the subprogram's index S (S n0) (where n = S n0). Without explicit hints, the type checker can't verify that the vector returned by evaluating the subprogram matches the expected size for the pop' case.

Why Program Fixpoint Generates Weird Obligations #

Program Fixpoint tries to automatically handle recursive definitions with dependent types, but it relies on inferring a termination metric and index relationships. For your pop' constructor, the subprogram's index (S (S n0)) is larger than the current program's index (S n0), which confuses Program's default termination checker. Instead of recognizing that we're recursing on a structural subterm of the program, it generates spurious obligations to link unrelated index variables (like k and n0) because it can't leverage the inductive invariants of your Prog type.

Correct Solutions #

Let's walk through three reliable ways to implement the evaluation function correctly.

1. Explicit Dependent Pattern Matching #

By explicitly binding the index parameters of your Prog constructors (using @), you give Coq clear hints about how indices relate. This lets the type checker verify the vector size matches in each case.

First, make sure you have the Vector library imported:

Require Import Vector.

Define your updated Prog type:

Inductive Prog : nat -> Type :=
| Push : forall {n}, nat -> Prog n -> Prog (S n)
| Pop : forall {n}, Prog (S n) -> Prog n
| Pop' : forall {n}, Prog (S (S n)) -> Prog (S n).

Now write the eval function with explicit constructor parameters:

Fixpoint eval {n} (p : Prog n) : Vector.t nat n :=
match p with
| @Push n0 v p' => Vector.cons _ v (eval p')
| @Pop n0 p' => 
    let s := eval p' in
    match s with @Vector.cons _ _ _ s' => s' end
| @Pop' n0 p' => 
    let s := eval p' in
    match s with @Vector.cons _ _ _ (@Vector.cons _ _ _ s') => Vector.cons _ _ s' end
end.

The @ syntax forces Coq to use the explicit index parameter n0 for each constructor, making the relationship between n (the current program's result stack size) and the subprogram's index unambiguous.

2. Fixpoint with a Size Measure #

Another approach is to use a termination measure based on the size of the program. This bypasses tricky dependent matching by letting Coq verify recursion terminates because each recursive call uses a smaller subprogram.

First, define a size function for Prog:

Fixpoint size {n} (p : Prog n) : nat :=
match p with
| Push _ p' => 1 + size p'
| Pop p' => 1 + size p'
| Pop' p' => 1 + size p'
end.

Then write eval with the measure annotation:

Fixpoint eval {n} (p : Prog n) {measure (size p)} : Vector.t nat n :=
match p with
| Push v p' => Vector.cons _ v (eval p')
| Pop p' => 
    let s := eval p' in
    match s with Vector.cons _ _ s' => s' end
| Pop' p' => 
    let s := eval p' in
    match s with Vector.cons _ _ (Vector.cons _ _ s') => Vector.cons _ _ s' end
end.

Coq will automatically verify that size p' < size p for each recursive call, so it accepts the definition without extra proof obligations.

3. Program Fixpoint with Manual Proof Obligations #

If you prefer using Program Fixpoint, you can resolve the generated obligations by explicitly proving the index relationships.

Start with the Program Fixpoint definition:

Program Fixpoint eval {n} (p : Prog n) : Vector.t nat n :=
match p with
| Push v p' => Vector.cons _ v (eval p')
| Pop p' => 
    let s := eval p' in
    match s with Vector.cons _ _ s' => s' end
| Pop' p' => 
    let s := eval p' in
    match s with Vector.cons _ _ (Vector.cons _ _ s') => Vector.cons _ _ s' end
end.

Coq will generate proof obligations (check with Print Obligations.). To resolve them:

1. For obligations related to index equality (e.g., proving S (S n0) = S (S (pred (S n)))), use eq_refl since the indices are definitionally equal.
2. For termination obligations, use simpl; assumption since the subprogram is a structural subterm of the original program.

You can discharge the obligations with:

Next Obligation. reflexivity. Qed.
Next Obligation. simpl; assumption. Qed.
(* Repeat for any remaining obligations *)

Final Notes #

All three approaches work, but the explicit dependent matching or size measure methods are usually cleaner for this kind of dependent stack language. The key is to make sure Coq can see the invariant that your Prog type enforces: every program is well-formed, so evaluation will never hit a stack underflow.

内容的提问来源于stack exchange，提问作者user1544337