rocq-prover / rocq-prover/stdlib

Cannot pattern match on exist in program definitions

Open
#24 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rocq Prover
Stars
42
Forks
38
Avg merge
14h 6m
Merged PRs (30d)
3

Description

Version

Coq 8.13.2

Operating system

Red Hat Enterprise Linux Workstation 7.4

Description of the problem

It is not possible to pattern match on terms
belonging to the sig type family in the following Program Definitions,
because the witnesses seem to get projected out by some hidden coercion.
However, changing sig into sigT or Ssig will allow
implementing the inspect pattern just fine.

From Coq Require Import Lia Logic.StrictProp NArith.NArith.

Obligation Tactic := idtac.

Section Context.

Import N.

Local Open Scope N_scope.

Context (f : N -> N) (mono : forall (a b : N) (l : a < b), f a < f b).

Print Coercions.

Fail Program Definition f_inspect (n : N) : positive :=
  let m := f (succ n) - f n in
  match exist _ m (eq_refl m) with
  | exist _ N0 e => _
  | exist _ (Npos p) e => p
  end.

Fail Program Definition f_inspect (n : N) : positive :=
  let m := f (succ n) - f n in
  match exist _ m (eq_refl m) in sig _ return positive with
  | exist _ N0 e => _
  | exist _ (Npos p) e => p
  end.

Program Definition f_inspect (n : N) : positive :=
  let m := f (succ n) - f n in
  match existT _ m (eq_refl m) in sigT _ return positive with
  | existT _ N0 e => _
  | existT _ (Npos p) e => p
  end.
Next Obligation. intros n m _ _ e. pose proof mono n (succ n) as l. lia. Qed.

Program Definition f_inspect' (n : N) : positive :=
  let m := f (succ n) - f n in
  match Sexists (fun n : N => Squash (m = n)) m (squash (eq_refl m)) in
  Ssig _ return positive with
  | Sexists _ N0 e => _
  | Sexists _ (Npos p) e => p
  end.
Next Obligation.
  intros n m _ _ e'.
  exfalso. apply sEmpty_ind. induction e' as [e].
  pose proof mono n (succ n) as l. lia. Qed.

End Context.
The command has indeed failed with message:
Found a constructor of inductive type sig while a constructor of N is expected.
The command has indeed failed with message:
Wrong inductive type.
Notes

This may be related to coq/coq#4341 or coq/coq#10877.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Reproduce the provided Coq 8.13.2 example and compare the failing sig matches with the working sigT and Ssig versions. Read the related issues coq/coq#4341 and coq/coq#10877; done means the sig pattern matches in both shown Program Definitions without the reported errors.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.