diff options
Diffstat (limited to 'dev/doc')
| -rw-r--r-- | dev/doc/MERGING.md | 80 | ||||
| -rw-r--r-- | dev/doc/changes.md | 76 | ||||
| -rw-r--r-- | dev/doc/coq-src-description.txt | 6 | ||||
| -rw-r--r-- | dev/doc/debugging.md | 2 | ||||
| -rw-r--r-- | dev/doc/primproj.md | 41 | ||||
| -rw-r--r-- | dev/doc/release-process.md | 100 | ||||
| -rw-r--r-- | dev/doc/universes.md (renamed from dev/doc/univpoly.txt) | 191 | ||||
| -rw-r--r-- | dev/doc/universes.txt | 26 |
8 files changed, 356 insertions, 166 deletions
diff --git a/dev/doc/MERGING.md b/dev/doc/MERGING.md index 71fc396088..c0cd9c8cdd 100644 --- a/dev/doc/MERGING.md +++ b/dev/doc/MERGING.md @@ -1,16 +1,17 @@ # Merging changes in Coq -This document describes how patches (submitted as Pull Requests) should be -merged into the main repository (https://github.com/coq/coq). +This document describes how patches, submitted as pull requests (PRs) on the +`master` branch, should be merged into the main repository +(https://github.com/coq/coq). ## Code owners -The [CODEOWNERS](/.github/CODEOWNERS) file describes, for each part of the +The [CODEOWNERS](../../.github/CODEOWNERS) file describes, for each part of the system, two owners. One is the principal maintainer of the component, the other is the secondary maintainer. -When a pull request is submitted, GitHub will automatically ask the principal -maintainer for a review. If the pull request touches several parts, all the +When a PR is submitted, GitHub will automatically ask the principal +maintainer for a review. If the PR touches several parts, all the corresponding principal maintainers will be asked for a review. Maintainers are never assigned as reviewer on their own PRs. @@ -42,17 +43,48 @@ A maintainer is expected to be reasonably reactive, but no specific timeframe is given for reviewing. (*) In case a component is touched in a trivial way (adding/removing one file in -a `Makefile`, etc), or by applying a systematic process (global renaming, -deprecationg propagation, etc) that has been reviewed globally, the assignee can +a `Makefile`, etc), or by applying a systematic refactoring process (global +renaming for instance) that has been reviewed globally, the assignee can say in a comment they think a review is not required and proceed with the merge. +### Breaking changes + +If the PR breaks compatibility of some external projects in CI, then fixes to +those external projects should have been prepared (cf. the relevant sub-section +in the [CI README](../ci/README.md#Breaking-changes) and the PR can be tested +with these fixes thanks to ["overlays"](../ci/user-overlays/README.md). + +Moreover the PR must absolutely update the [`CHANGES`](../../CHANGES) file. + +If overlays are missing, ask the author to prepare them and label the PR with +the [needs: overlay](https://github.com/coq/coq/labels/needs%3A%20overlay) label. + +When fixes are ready, there are two cases to consider: + +- For patches that are backward compatible (best scenario), you should get the + external project maintainers to integrate them before merging the PR. +- For patches that are not backward compatible (which is often the case when + patching plugins after an update to the Coq API), you can proceed to merge + the PR and then notify the external project maintainers they can merge the + patch. + ## Merging Once all reviewers approved the PR, the assignee is expected to check that CI completed without relevant failures, and that the PR comes with appropriate documentation and test cases. If not, they should leave a comment on the PR and put the approriate label. Otherwise, they are expected to merge the PR using the -[merge script](/dev/tools/merge-pr.sh). +[merge script](../tools/merge-pr.sh). + +When CI has a few failures which look spurious, restarting the corresponding +jobs is a good way of ensuring this was indeed the case. +To restart a job on Travis, you should connect using your GitHub account; +being part of the Coq organization on GitHub should give you the permission +to do so. +To restart a job on GitLab CI, you should sign into GitLab (this can be done +using a GitHub account); if you are part of the +[Coq organization on GitLab](https://gitlab.com/coq), you should see a "Retry" +button; otherwise, send a request to join the organization. When the PR has conflicts, the assignee can either: - ask the author to rebase the branch, fixing the conflicts @@ -65,14 +97,40 @@ In some rare cases (e.g. the conflicts are in the CHANGES file), it is ok to fix the conflicts in the merge commit (following the same steps as below), and push to `master` directly. Don't use the GitHub interface to fix these conflicts. -The command to be used is: +To merge the PR proceed in the following way ``` -$ dev/tools/merge-pr XXXX +$ git checkout master +$ git pull +$ dev/tools/merge-pr.sh XXXX +$ git push upstream ``` -where `XXXX` is the number of the PR to be merged. This operation should be followed by a push. +where `XXXX` is the number of the PR to be merged and `upstream` is the name +of your remote pointing to `git@github.com:coq/coq.git`. +Note that you are only supposed to merge PRs into `master`. PRs should rarely +target the stable branch, but when it is the case they are the responsibility +of the release manager. + +This script conducts various checks before proceeding to merge. Don't bypass them +without a good reason to, and in that case, write a comment in the PR thread to +explain the reason. Maintainers MUST NOT merge their own patches. DON'T USE the GitHub interface for merging, since it will prevent the automated backport script from operating properly, generates bad commit messages, and a messy history when there are conflicts. + +### Merge script dependencies + +The merge script passes option `-S` to `git merge` to ensure merge commits +are signed. Consequently, it depends on the GnuPG command utility being +installed and a GPG key being available. Here is a short documentation on +how to use GPG, git & GitHub: https://help.github.com/articles/signing-commits-with-gpg/. + +The script depends on a few other utilities. If you are a Nix user, the +simplest way of getting them is to run `nix-shell` first. + +**Note for homebrew (MacOS) users:** it has been reported that installing GnuPG +is not out of the box. Installing explicitly "pinentry-mac" seems important for +typing of passphrase to work correctly (see also this +[Stack Overflow Q-and-A](https://stackoverflow.com/questions/39494631/gpg-failed-to-sign-the-data-fatal-failed-to-write-commit-object-git-2-10-0)). diff --git a/dev/doc/changes.md b/dev/doc/changes.md index ab78b0956f..bb8189efc7 100644 --- a/dev/doc/changes.md +++ b/dev/doc/changes.md @@ -1,3 +1,74 @@ +## Changes between Coq 8.8 and Coq 8.9 + +### ML API + +Misctypes + +- Syntax for universe sorts and kinds has been moved from `Misctypes` + to `Glob_term`, as these are turned into kernel terms by + `Pretyping`. + +Proof engine + +- More functions have been changed to use `EConstr`, notably the + functions in `Evd`, and in particular `Evd.define`. + + Note that the core function `EConstr.to_constr` now _enforces_ by + default that the resulting term is ground, that is to say, free of + Evars. This is usually what you want, as open terms should be of + type `EConstr.t` to benefit from the invariants the `EConstr` API is + meant to guarantee. + + In case you'd like to violate this API invariant, you can use the + `abort_on_undefined_evars` flag to `EConstr.to_constr`, but note + that setting this flag to false is deprecated so it is only meant to + be used as to help port pre-EConstr code. + +- A few type alias have been deprecated, in all cases the message + should indicate what the canonical form is. An important change is + the move of `Globnames.global_reference` to `Names.GlobRef.t`. + +- Unification API returns `evar_map option` instead of `bool * evar_map` + with the guarantee that the `evar_map` was unchanged if the boolean + was false. + +ML Libraries used by Coq + +- Introduction of a "Smart" module for collecting "smart*" functions, e.g. + Array.Smart.map. +- Uniformization of some names, e.g. Array.Smart.fold_left_map instead + of Array.smartfoldmap. + +Printer.ml API + +- The mechanism in Printer that allowed dynamically overriding pr_subgoals, + pr_subgoal and pr_goal was removed to simplify the code. It was + earlierly used by PCoq. + +Source code organization + +- We have eliminated / fused some redundant modules and relocated a + few interfaces files. The `intf` folder is gone, and now for example + `Constrexpr` is located in `interp/`, `Vernacexpr` in `vernac/` and + so on. Changes should be compatible, but in a few cases stricter + layering requirements may mean that functions have moved. In all + cases adapting is a matter of changing the module name. + +Vernacular commands + +- The implementation of vernacular commands has been refactored so it + is self-contained now, including the parsing and extension + mechanisms. This involves a couple of non-backward compatible + changes due to layering issues, where some functions have been moved + from `Pcoq` to `Pvernac` and from `Vernacexpr` to modules in + `tactics/`. In all cases adapting is a matter of changing the module + name. + +### Unit testing + + The test suite now allows writing unit tests against OCaml code in the Coq + code base. Those unit tests create a dependency on the OUnit test framework. + ## Changes between Coq 8.7 and Coq 8.8 ### Bug tracker @@ -74,6 +145,11 @@ Declaration of printers for arguments used only in vernac command happen. An alternative is to register the corresponding argument as a value, using "Geninterp.register_val0 wit None". +Types Alias deprecation and type relocation. + +- A few type alias have been deprecated, in all cases the message + should indicate what the canonical form is. + ### STM API The STM API has seen a general overhaul. The main change is the diff --git a/dev/doc/coq-src-description.txt b/dev/doc/coq-src-description.txt index b3d49b7e56..764d482957 100644 --- a/dev/doc/coq-src-description.txt +++ b/dev/doc/coq-src-description.txt @@ -17,12 +17,6 @@ toplevel Special components ------------------ -intf : - - Contains mli-only interfaces, many of them providing a.s.t. - used for dialog bewteen coq components. Ex: Constrexpr.constr_expr - produced by parsing and transformed by interp. - grammar : Camlp5 syntax extensions. The file grammar/grammar.cma is used diff --git a/dev/doc/debugging.md b/dev/doc/debugging.md index fd3cbd1bc3..14a1cc693c 100644 --- a/dev/doc/debugging.md +++ b/dev/doc/debugging.md @@ -47,7 +47,7 @@ Debugging with ocamldebug from Emacs 7. some hints: - To debug a failure/error/anomaly, add a breakpoint in - Vernac.vernac_com at the with clause of the "try ... interp com + `Vernac.interp_vernac` (in `toplevel/vernac.ml`) at the with clause of the "try ... interp com with ..." block, then go "back" a few steps to find where the failure/error/anomaly has been raised - Alternatively, for an error or an anomaly, add breakpoints in the middle diff --git a/dev/doc/primproj.md b/dev/doc/primproj.md new file mode 100644 index 0000000000..ea76aeeab5 --- /dev/null +++ b/dev/doc/primproj.md @@ -0,0 +1,41 @@ +Primitive Projections +--------------------- + + | Proj of Projection.t * constr + +Projections are always applied to a term, which must be of a record +type (i.e. reducible to an inductive type `I params`). Type-checking, +reduction and conversion are fast (not as fast as they could be yet) +because we don't keep parameters around. As you can see, it's +currently a `constant` that is used here to refer to the projection, +that will change to an abstract `projection` type in the future. +Basically a projection constant records which inductive it is a +projection for, the number of params and the actual position in the +constructor that must be projected. For compatibility reason, we also +define an eta-expanded form (accessible from user syntax `@f`). The +constant_entry of a projection has both informations. Declaring a +record (under `Set Primitive Projections`) will generate such +definitions. The API to declare them is not stable at the moment, but +the inductive type declaration also knows about the projections, i.e. +a record inductive type decl contains an array of terms representing +the projections. This is used to implement eta-conversion for record +types (with at least one field and having all projections definable). +The canonical value being `Build_R (pn x) ... (pn x)`. Unification and +conversion work up to this eta rule. The records can also be universe +polymorphic of course, and we don't need to keep track of the universe +instance for the projections either. Projections are reduced _eagerly_ +everywhere, and introduce a new `Zproj` constructor in the abstract +machines that obeys both the delta (for the constant opacity) and iota +laws (for the actual reduction). Refolding works as well (afaict), but +there is a slight hack there related to universes (not projections). + +For the ML programmer, the biggest change is that pattern-matchings on +kind_of_term require an additional case, that is handled usually +exactly like an `App (Const p) arg`. + +There are slight hacks related to hints is well, to use the primitive +projection form of f when one does `Hint Resolve f`. Usually hint +resolve will typecheck the term, resulting in a partially applied +projection (disallowed), so we allow it to take +`constr_or_global_reference` arguments instead and special-case on +projections. Other tactic extensions might need similar treatment. diff --git a/dev/doc/release-process.md b/dev/doc/release-process.md new file mode 100644 index 0000000000..1821a181f1 --- /dev/null +++ b/dev/doc/release-process.md @@ -0,0 +1,100 @@ +# Release process # + +## As soon as the previous version branched off master ## + +- [ ] Create a new issue to track the release process where you can copy-paste + the present checklist. +- [ ] Change the version name to the next major version and the magic numbers + (see [#7008](https://github.com/coq/coq/pull/7008/files)). +- [ ] Put the corresponding alpha tag using `git tag -s`. + The `VX.X+alpha` tag marks the first commit to be in `master` and not in the + branch of the previous version. +- [ ] Create the `X.X+beta1` milestone if it did not already exist. +- [ ] Decide the release calendar with the team (freeze date, beta date, final + release date) and put this information in the milestone (using the + description and due date fields). + +## About one month before the beta ## + +- [ ] Create the `X.X.0` milestone and set its due date. +- [ ] Send an announcement of the upcoming freeze on Coqdev and ask people to + remove from the beta milestone what they already know won't be ready on time + (possibly postponing to the `X.X.0` milestone for minor bug fixes, + infrastructure and documentation updates). +- [ ] Determine which issues should / must be fixed before the beta, add them + to the beta milestone, possibly with a + ["priority: blocker"](https://github.com/coq/coq/labels/priority%3A%20blocker) + label. Make sure that all these issues are assigned (and that the assignee + provides an ETA). +- [ ] Ping the development coordinator (**@mattam82**) to get him started on + the update to the Credits chapter of the reference manual. + See also [#7058](https://github.com/coq/coq/issues/7058). + The command to get the list of contributors for this version is + `git shortlog -s -n VX.X+alpha..master | cut -f2 | sort -k 2` + (the ordering is approximative as it will misplace people with middle names). + +## On the date of the feature freeze ## + +- [ ] Create the new version branch `vX.X` and + [protect it](https://github.com/coq/coq/settings/branches) + (activate the "Protect this branch", "Require pull request reviews before + merging" and "Restrict who can push to this branch" guards). +- [ ] Remove all remaining unmerged feature PRs from the beta milestone. +- [ ] Start a new project to track PR backporting. The proposed model is to + have a "X.X-only PRs" column for the rare PRs on the stable branch, a + "Request X.X inclusion" column for the PRs that were merged in `master` that + are to be considered for backporting, a "Waiting for CI" column to put the + PRs in the process of being backported, and "Shipped in ..." columns to put + what was backported. (The release manager is the person responsible for + merging PRs that target the version branch and backporting appropriate PRs + that are merged into `master`). + A message to **@coqbot** in the milestone description tells it to + automatically add merged PRs to the "Request X.X inclusion" column. +- [ ] Delay non-blocking issues to the appropriate milestone and ensure + blocking issues are solved. If required to solve some blocking issues, + it is possible to revert some feature PRs in the version branch only. + +## Before the beta release date ## + +- [ ] Ensure the Credits chapter has been updated. +- [ ] Ensure an empty `CompatXX.v` file has been created. +- [ ] Ensure that an appropriate version of the plugins we will distribute with + Coq has been tagged. +- [ ] Have some people test the recently auto-generated Windows and MacOS + packages. +- [ ] Change the version name from alpha to beta1 (see + [#7009](https://github.com/coq/coq/pull/7009/files)). + We generally do not update the magic numbers at this point. +- [ ] Put the `VX.X+beta1` tag using `git tag -s`. + +### These steps are the same for all releases (beta, final, patch-level) ### + +- [ ] Send an e-mail on Coqdev announcing that the tag has been put so that + package managers can start preparing package updates. +- [ ] Draft a release on GitHub. +- [ ] Get **@maximedenes** to sign the Windows and MacOS packages and + upload them on GitHub. +- [ ] Prepare a page of news on the website with the link to the GitHub release + (see [coq/www#63](https://github.com/coq/www/pull/63)). +- [ ] Upload the new version of the reference manual to the website. + *TODO: setup some continuous deployment for this.* +- [ ] Merge the website update, publish the release + and send annoucement e-mails. +- [ ] Ping **@Zimmi48** to publish a new version on Zenodo. + *TODO: automate this.* +- [ ] Close the milestone + +## At the final release time ## + +- [ ] Change the version name to X.X.0 and the magic numbers (see + [#7271](https://github.com/coq/coq/pull/7271/files)). +- [ ] Put the `VX.X.0` tag. + +Repeat the generic process documented above for all releases. + +- [ ] Switch the default version of the reference manual on the website. + +## At the patch-level release time ## + +We generally do not update the magic numbers at this point (see +[`2881a18`](https://github.com/coq/coq/commit/2881a18)). diff --git a/dev/doc/univpoly.txt b/dev/doc/universes.md index ca3d520c70..c276603ed2 100644 --- a/dev/doc/univpoly.txt +++ b/dev/doc/universes.md @@ -1,11 +1,11 @@ -Notes on universe polymorphism and primitive projections, M. Sozeau -=================================================================== +Notes on universe polymorphism +------------------------------ -The new implementation of universe polymorphism and primitive -projections introduces a few changes to the API of Coq. First and -foremost, the term language changes, as global references now carry a -universe level substitution: +The implementation of universe polymorphism introduces a few changes +to the API of Coq. First and foremost, the term language changes, as +global references now carry a universe level substitution: +~~~ocaml type 'a puniverses = 'a * Univ.Instance.t type pconstant = constant puniverses type pinductive = inductive puniverses @@ -15,30 +15,31 @@ type constr = ... | Const of puniverses | Ind of pinductive | Constr of pconstructor - | Proj of constant * constr - +~~~ Universes -========= +--------- - Universe instances (an array of levels) gets substituted when +Universe instances (an array of levels) gets substituted when unfolding definitions, are used to typecheck and are unified according -to the rules in the ITP'14 paper on universe polymorphism in Coq. +to the rules in the ITP'14 paper on universe polymorphism in Coq. +~~~ocaml type Level.t = Set | Prop | Level of int * dirpath (* hashconsed *) type Instance.t = Level.t array type Universe.t = Level.t list (* hashconsed *) +~~~ The universe module defines modules and abstract types for levels, universes etc.. Structures are hashconsed (with a hack to take care -of the fact that deserialization breaks sharing). +of the fact that deserialization breaks sharing). - Definitions (constants, inductives) now carry around not only + Definitions (constants, inductives) now carry around not only constraints but also the universes they introduced (a Univ.UContext.t). -There is another kind of contexts [Univ.ContextSet.t], the latter has +There is another kind of contexts `Univ.ContextSet.t`, the latter has a set of universes, while the former has serialized the levels in an -array, and is used for polymorphic objects. Both have "reified" -constraints depending on global and local universes. +array, and is used for polymorphic objects. Both have "reified" +constraints depending on global and local universes. A polymorphic definition is abstract w.r.t. the variables in this context, while a monomorphic one (or template polymorphic) just adds the @@ -46,18 +47,18 @@ universes and constraints to the global universe context when it is put in the environment. No other universes than the global ones and the declared local ones are needed to check a declaration, hence the kernel does not produce any constraints anymore, apart from module -subtyping.... There are hence two conversion functions now: [check_conv] -and [infer_conv]: the former just checks the definition in the current env +subtyping.... There are hence two conversion functions now: `check_conv` +and `infer_conv`: the former just checks the definition in the current env (in which we usually push_universe_context of the associated context), -and [infer_conv] which produces constraints that were not implied by the +and `infer_conv` which produces constraints that were not implied by the ambient constraints. Ideally, that one could be put out of the kernel, -but currently module subtyping needs it. +but currently module subtyping needs it. Inference of universes is now done during refinement, and the evar_map carries the incrementally built universe context, starting from the -global universe constraints (see [Evd.from_env]). [Evd.conversion] is a -wrapper around [infer_conv] that will do the bookkeeping for you, it -uses [evar_conv_x]. There is a universe substitution being built +global universe constraints (see `Evd.from_env`). `Evd.conversion` is a +wrapper around `infer_conv` that will do the bookkeeping for you, it +uses `evar_conv_x`. There is a universe substitution being built incrementally according to the constraints, so one should normalize at the end of a proof (or during a proof) with that substitution just like we normalize evars. There are some nf_* functions in @@ -67,16 +68,16 @@ the universe constraints used in the term. It is heuristic but validity-preserving. No user-introduced universe (i.e. coming from a user-written anonymous Type) gets touched by this, only the fresh universes generated for each global application. Using - +~~~ocaml val pf_constr_of_global : Globnames.global_reference -> (constr -> tactic) -> tactic - +~~~ Is the way to make a constr out of a global reference in the new API. If they constr is polymorphic, it will add the necessary constraints to the evar_map. Even if a constr is not polymorphic, we have to take care of keeping track of its universes. Typically, using: - - mkApp (coq_id_function, [| A; a |]) - +~~~ocaml + mkApp (coq_id_function, [| A; a |]) +~~~ and putting it in a proof term is not enough now. One has to somehow show that A's type is in cumululativity relation with id's type argument, incurring a universe constraint. To do this, one can simply @@ -84,19 +85,19 @@ call Typing.resolve_evars env evdref c which will do some infer_conv to produce the right constraints and put them in the evar_map. Of course in some cases you might know from an invariant that no new constraint would be produced and get rid of it. Anyway the kernel will tell you if you -forgot some. As a temporary way out, [Universes.constr_of_global] allows +forgot some. As a temporary way out, `Universes.constr_of_global` allows you to make a constr from any non-polymorphic constant, but it will fail on polymorphic ones. Other than that, unification (w_unify and evarconv) now take account of universes and produce only well-typed evar_maps. -Some syntactic comparisons like the one used in [change] have to be -adapted to allow identification up-to-universes (when dealing with -polymorphic references), [make_eq_univs_test] is there to help. +Some syntactic comparisons like the one used in `change` have to be +adapted to allow identification up-to-universes (when dealing with +polymorphic references), `make_eq_univs_test` is there to help. In constr, there are actually many new comparison functions to deal with that: - +~~~ocaml (** [equal a b] is true if [a] equals [b] modulo alpha, casts, and application grouping *) val equal : constr -> constr -> bool @@ -105,7 +106,7 @@ val equal : constr -> constr -> bool application grouping and the universe equalities in [u]. *) val eq_constr_univs : constr Univ.check_function -(** [leq_constr_univs u a b] is [true] if [a] is convertible to [b] modulo +(** [leq_constr_univs u a b] is [true] if [a] is convertible to [b] modulo alpha, casts, application grouping and the universe inequalities in [u]. *) val leq_constr_univs : constr Univ.check_function @@ -120,47 +121,47 @@ val leq_constr_universes : constr -> constr -> bool Univ.universe_constrained (** [eq_constr_univs a b] [true, c] if [a] equals [b] modulo alpha, casts, application grouping and ignoring universe instances. *) val eq_constr_nounivs : constr -> constr -> bool - -The [_univs] versions are doing checking of universe constraints -according to a graph, while the [_universes] are producing (non-atomic) +~~~ +The `_univs` versions are doing checking of universe constraints +according to a graph, while the `_universes` are producing (non-atomic) universe constraints. The non-atomic universe constraints include the -[ULub] constructor: when comparing [f (* u1 u2 *) c] and [f (* u1' u2' -*) c] we add ULub constraints on [u1, u1'] and [u2, u2']. These are -treated specially: as unfolding [f] might not result in these +`ULub` constructor: when comparing `f (* u1 u2 *) c` and `f (* u1' u2' +*) c` we add ULub constraints on `u1, u1'` and `u2, u2'`. These are +treated specially: as unfolding `f` might not result in these unifications, we need to keep track of the fact that failure to satisfy them does not mean that the term are actually equal. This is used in -unification but probably not necessary to the average programmer. +unification but probably not necessary to the average programmer. Another issue for ML programmers is that tables of constrs now usually -need to take a [constr Univ.in_universe_context_set] instead, and -properly refresh the universes context when using the constr, e.g. using -Clenv.refresh_undefined_univs clenv or: - +need to take a `constr Univ.in_universe_context_set` instead, and +properly refresh the universes context when using the constr, e.g. using +Clenv.refresh_undefined_univs clenv or: +~~~ocaml (** Get fresh variables for the universe context. Useful to make tactics that manipulate constrs in universe contexts polymorphic. *) -val fresh_universe_context_set_instance : universe_context_set -> +val fresh_universe_context_set_instance : universe_context_set -> universe_level_subst * universe_context_set - -The substitution should be applied to the constr(s) under consideration, +~~~ +The substitution should be applied to the constr(s) under consideration, and the context_set merged with the current evar_map with: - +~~~ocaml val merge_context_set : rigid -> evar_map -> Univ.universe_context_set -> evar_map - -The [rigid] flag here should be [Evd.univ_flexible] most of the +~~~ +The `rigid` flag here should be `Evd.univ_flexible` most of the time. This means the universe levels of polymorphic objects in the -constr might get instantiated instead of generating equality constraints +constr might get instantiated instead of generating equality constraints (Evd.univ_rigid does that). -On this issue, I recommend forcing commands to take [global_reference]s +On this issue, I recommend forcing commands to take `global_reference`s only, the user can declare his specialized terms used as hints as constants and this is cleaner. Alas, backward-compatibility-wise, this is the only solution I found. In the case of global_references -only, it's just a matter of using [Evd.fresh_global] / -[pf_constr_of_global] to let the system take care of universes. +only, it's just a matter of using `Evd.fresh_global` / +`pf_constr_of_global` to let the system take care of universes. The universe graph -================== +------------------ To accomodate universe polymorphic definitions, the graph structure in kernel/univ.ml was modified. The new API forces every universe to be @@ -176,68 +177,14 @@ no universe i can be set lower than Set, so the chain of universes always bottoms down at Prop < Set. Modules -======= +------- One has to think of universes in modules as being globally declared, so when including a module (type) which declares a type i (e.g. through a parameter), we get back a copy of i and not some fresh universe. -Projections -=========== - - | Proj of constant * constr - -Projections are always applied to a term, which must be of a record type -(i.e. reducible to an inductive type [I params]). Type-checking, -reduction and conversion are fast (not as fast as they could be yet) -because we don't keep parameters around. As you can see, it's currently -a [constant] that is used here to refer to the projection, that will -change to an abstract [projection] type in the future. Basically a -projection constant records which inductive it is a projection for, the -number of params and the actual position in the constructor that must be -projected. For compatibility reason, we also define an eta-expanded form -(accessible from user syntax @f). The constant_entry of a projection has -both informations. Declaring a record (under [Set Primitive -Projections]) will generate such definitions. The API to declare them is -not stable at the moment, but the inductive type declaration also knows -about the projections, i.e. a record inductive type decl contains an -array of terms representing the projections. This is used to implement -eta-conversion for record types (with at least one field and having all -projections definable). The canonical value being [Build_R (pn x) -... (pn x)]. Unification and conversion work up to this eta rule. The -records can also be universe polymorphic of course, and we don't need to -keep track of the universe instance for the projections either. -Projections are reduced _eagerly_ everywhere, and introduce a new Zproj -constructor in the abstract machines that obeys both the delta (for the -constant opacity) and iota laws (for the actual reduction). Refolding -works as well (afaict), but there is a slight hack there related to -universes (not projections). - -For the ML programmer, the biggest change is that pattern-matchings on -kind_of_term require an additional case, that is handled usually exactly -like an [App (Const p) arg]. - -There are slight hacks related to hints is well, to use the primitive -projection form of f when one does [Hint Resolve f]. Usually hint -resolve will typecheck the term, resulting in a partially applied -projection (disallowed), so we allow it to take -[constr_or_global_reference] arguments instead and special-case on -projections. Other tactic extensions might need similar treatment. - -WIP -=== - -- [vm_compute] does not deal with universes and projections correctly, -except when it goes to a normal form with no projections or polymorphic -constants left (the most common case). E.g. Ring with Set Universe -Polymorphism and Set Primitive Projections work (at least it did at some -point, I didn't recheck yet). - -- [native_compute] works with universes and projections. - - Incompatibilities -================= +----------------- Old-style universe polymorphic definitions were implemented by taking advantage of the fact that elaboration (i.e., pretyping and unification) @@ -247,33 +194,33 @@ possible, as unification ensures that the substitution is built is entirely well-typed, even w.r.t universes. This means that some terms that type-checked before no longer do, especially projections of the pair: - +~~~coq @fst ?x ?y : prod ?x ?y : Type (max(Datatypes.i, Datatypes.j)). - +~~~ The "template universe polymorphic" variables i and j appear during typing without being refreshed, meaning that they can be lowered (have upper constraints) with user-introduced universes. In most cases this won't work, so ?x and ?y have to be instantiated earlier, either from the type of the actual projected pair term (some t : prod A B) or the -typing constraint. Adding the correct type annotations will always fix +typing constraint. Adding the correct type annotations will always fix this. Unification semantics -===================== +--------------------- In Ltac, matching with: -- a universe polymorphic constant [c] matches any instance of the +- a universe polymorphic constant `c` matches any instance of the constant. -- a variable ?x already bound to a term [t] (non-linear pattern) uses +- a variable ?x already bound to a term `t` (non-linear pattern) uses strict equality of universes (e.g., Type@{i} and Type@{j} are not equal). In tactics: -- [change foo with bar], [pattern foo] will unify all instances of [foo] - (and convert them with [bar]). This might incur unifications of - universes. [change] uses conversion while [pattern] only does +- `change foo with bar`, `pattern foo` will unify all instances of `foo` + (and convert them with `bar`). This might incur unifications of + universes. `change` uses conversion while `pattern` only does syntactic matching up-to unification of universes. -- [apply], [refine] use unification up to universes. +- `apply`, `refine` use unification up to universes. diff --git a/dev/doc/universes.txt b/dev/doc/universes.txt deleted file mode 100644 index a40706e996..0000000000 --- a/dev/doc/universes.txt +++ /dev/null @@ -1,26 +0,0 @@ -How to debug universes? - -1. There is a command Print Universes in Coq toplevel - - Print Universes. - prints the graph of universes in the form of constraints - - Print Universes "file". - produces the "file" containing universe constraints in the form - univ1 # univ2 ; - where # can be either > >= or = - - If "file" ends with .gv or .dot, the resulting file will be in - dot format. - - - *) for dot see http://www.research.att.com/sw/tools/graphviz/ - - -2. There is a printing option - - {Set,Unset} Printing Universes. - - which, when set, makes all pretty-printed Type's annotated with the - name of the universe. - |