Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make a few sumbool lemmas of stdlib transparent #14353

Closed
wants to merge 1 commit into from

Conversation

eponier
Copy link
Contributor

@eponier eponier commented May 20, 2021

Kind: bug fix

Fixes coq/stdlib#25

  • Added / updated test-suite (do we need to check that computation is possible within Coq?)

@eponier eponier requested a review from a team as a code owner May 20, 2021 16:07
@eponier
Copy link
Contributor Author

eponier commented May 20, 2021

I searched for such lemmas using Search headconcl:sumbool.

Among the results, I did not changed the following lemmas:

  • lemmas about reals (e.g. Rle_lt_dec) that do not compute anyway as far as I can tell;
  • lemmas about excluded middle (e.g. constructive_definite_descr_excluded_middle) for the same reason;
  • lemma Zmin_le_prime_inf which is in a deprecated file.

@eponier
Copy link
Contributor Author

eponier commented May 20, 2021

Not sure what should be done w.r.t. test-suite/documentation/changelog.

@eponier
Copy link
Contributor Author

eponier commented May 27, 2021

Ping. The commit itself is fairly trivial, it is more a political question of deciding whether these lemmas must be made transparent. Not sure if this is acceptable for 8.14.

@ppedrot
Copy link
Member

ppedrot commented May 27, 2021

Regardless of what is implemented in this PR, I think we should have a more principled approach to the opacity problem, and in particular a set of systematic guidelines for the standard library. This issue has been popping regularly and we should tackle it once and for all instead of haphazardly making things defined.

I think that most of the issues can be summarized as a phase boundary between Prop and Type, so we should probably take singleton elimination as a guiding principle.

  • Falsity is fine because it does not matter for computation.
  • Equalities over decidable types can be made to compute by wrapping them in a transparent decider so there is not real point in making them transparent.
  • Generic equalities are more tricky, which is something that should be decided carefully.
  • Accessibility proofs block computations, but for practical purposes they can be eta-expanded by a huge factor through a combinator to not be problematic in practice. This is similar to equality canonization.

In this PR, the equality subproofs of the sumbool are indistinctively set transparent, while I believe that per the above verbiage, only the computational skeleton should be exposed, the (dis)equality subproofs should probably be Qed-opaque.

@eponier
Copy link
Contributor Author

eponier commented May 27, 2021

I tried to have a global approach, and that's why I dealt with all the sumbool lemmas instead of just NoDup_decand incl_dec, but I understand that you're speaking of an approach even more global.

As for the proofs, I considered that what was important was to compute the head constructor (regardless of the proposition inside the sumbool, which is somewhat arbitrary, but allows to use if then else effectively). From this point of view, only left and right in the proof should be exposed, the rest can be turned opaque. But since the proofs were small, I took the simpler approach of making the whole proof transparent. By the way, I wonder what is the typical way of making only some parts of a proof opaque. For me, the basic tool is abstract, but as I read that this tactics also has drawbacks, I am not sure if this is the recommended approach.

@github-actions github-actions bot added the needs: rebase Should be rebased on the latest master to solve conflicts or have a newer CI run. label May 25, 2022
@coqbot-app
Copy link
Contributor

coqbot-app bot commented Jun 24, 2022

The "needs: rebase" label was set more than 30 days ago. If the PR is not rebased in 30 days, it will be automatically closed.

@coqbot-app coqbot-app bot added the stale This PR will be closed unless it is rebased. label Jun 24, 2022
@Alizter
Copy link
Contributor

Alizter commented Jun 24, 2022

@coq/stdlib-maintainers should we resurrect and make progress on this PR?

@MSoegtropIMC
Copy link
Contributor

I agree with @ppedrot that while the need is there, the way it is done is not very agreeable. Besides the arguments he gave I would say that transparent definitions should be stable and not be defined with tactics like auto. Frequently proofs depend on the exact definition. This goes together with @ppedrot's recommendation to to split the definition in the purely computational part and opaque lemmas for the Prop part.

@Alizter Alizter added the needs: progress Work in progress: awaiting action from the author. label Jun 24, 2022
@coqbot-app
Copy link
Contributor

coqbot-app bot commented Jul 25, 2022

This PR was not rebased after 30 days despite the warning, it is now closed.

@coqbot-app coqbot-app bot closed this Jul 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
needs: progress Work in progress: awaiting action from the author. needs: rebase Should be rebased on the latest master to solve conflicts or have a newer CI run. stale This PR will be closed unless it is rebased.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

incl_dec and NoDup_dec should be Defined and not Qed
4 participants