Porting to HB
This Pull Request is about porting the hierarchy of hand declared algebraic structures to the language of hierarchy-builder .
Rules for contributing to this PR:
- Tick the boxes down here when:
- the file is taken by you to work on,
- then when it works (modules depending on it can be ported),
- when it is complete (doc included).
- Add your commits here (no force push)
- All commits you push must compile. You can comment the remaining part of the the file to push a partial commit, but in that case you don't tick the :white_check_mark: box
Tasks:
- Use the graph of MC files with live info about this PR in order to pick your next task (the dependency graph is generated by this branch which is slightly broken to maximize parallelization from where we stand)
- blue nodes are taken by someone :construction:
- green nodes are ported
- solid green background means finished
- yellow background mean compiles :white_check_mark:
- A file containing no Structure and no Canonical should just work and requires no doc update.
- A file with Canonical but no Structure requires using HB.instance instead but no doc update.
- A file containing Structure require complete porting and doc update. Note that only structures with carriers of type
Typeshould be ported in this pass.
Progress:
- [ ] countalg.v finished (9 Structure, 153 Canonical)
- [ ] :construction: countalg.v taken
- [x] :white_check_mark: countalg.v compiles but needs more work
- [ ] finalg.v finished (11 Structure, 358 Canonical)
- [ ] :construction: finalg.v taken
- [x] :white_check_mark: finalg.v compiles but needs more work
- [x] fraction.v finished (0 Structure, 52 Canonical)
- [ ] :construction: fraction.v taken
- [ ] :white_check_mark: fraction.v compiles but needs more work
- [x] intdiv.v finished (0 Structure, 4 Canonical)
- [ ] :construction: intdiv.v taken
- [ ] :white_check_mark: intdiv.v compiles but needs more work
- [ ] interval.v finished (1 Structure, 26 Canonical)
- [ ] :construction: interval.v taken
- [x] :white_check_mark: interval.v compiles but needs more work
- [ ] matrix.v finished (0 Structure, 96 Canonical)
- [ ] :construction: matrix.v taken
- [x] :white_check_mark: matrix.v compiles but needs more work
- [ ] mxalgebra.v finished (2 Structure, 17 Canonical)
- [ ] :construction: mxalgebra.v taken
- [x] :white_check_mark: mxalgebra.v compiles but needs more work
- [x] mxpoly.v finished (0 Structure, 8 Canonical)
- [ ] :construction: mxpoly.v taken
- [ ] :white_check_mark: mxpoly.v compiles but needs more work
- [x] polydiv.v finished (0 Structure, 2 Canonical)
- [ ] :construction: polydiv.v taken
- [ ] :white_check_mark: polydiv.v compiles but needs more work
- [x] poly.v finished (0 Structure, 89 Canonical)
- [ ] :construction: poly.v taken
- [ ] :white_check_mark: poly.v compiles but needs more work
- [x] polyXY.v finished (0 Structure, 5 Canonical)
- [ ] :construction: polyXY.v taken
- [ ] :white_check_mark: polyXY.v compiles but needs more work
- [x] rat.v finished (0 Structure, 44 Canonical)
- [ ] :construction: rat.v taken
- [ ] :white_check_mark: rat.v compiles but needs more work
- [ ] ring_quotient.v finished (6 Structure, 55 Canonical)
- [ ] :construction: ring_quotient.v taken
- [x] :white_check_mark: ring_quotient.v compiles but needs more work
- [ ] ssralg.v finished (27 Structure, 149 Canonical)
- [ ] :construction: ssralg.v taken
- [x] :white_check_mark: ssralg.v compiles but needs more work
- [ ] ssrint.v finished (0 Structure, 29 Canonical)
- [ ] :construction: ssrint.v taken
- [x] :white_check_mark: ssrint.v compiles but needs more work
- [ ] ssrnum.v finished (8 Structure, 201 Canonical)
- [ ] :construction: ssrnum.v taken
- [x] :white_check_mark: ssrnum.v compiles but needs more work
- [ ] vector.v finished (3 Structure, 56 Canonical)
- [ ] :construction: vector.v taken
- [x] :white_check_mark: vector.v compiles but needs more work
- [ ] zmodp.v finished (0 Structure, 27 Canonical)
- [ ] :construction: zmodp.v taken
- [x] :white_check_mark: zmodp.v compiles but needs more work
- [ ] character.v finished (2 Structure, 13 Canonical)
- [ ] :construction: character.v taken
- [x] :white_check_mark: character.v compiles but needs more work
- [ ] classfun.v finished (0 Structure, 58 Canonical)
- [ ] :construction: classfun.v taken
- [x] :white_check_mark: classfun.v compiles but needs more work
- [ ] inertia.v finished (0 Structure, 5 Canonical)
- [ ] :construction: inertia.v taken
- [x] :white_check_mark: inertia.v compiles but needs more work
- [ ] integral_char.v finished (0 Structure, 1 Canonical)
- [ ] :construction: integral_char.v taken
- [x] :white_check_mark: integral_char.v compiles but needs more work
- [ ] mxabelem.v finished (2 Structure, 11 Canonical)
- [ ] :construction: mxabelem.v taken
- [x] :white_check_mark: mxabelem.v compiles but needs more work
- [ ] mxrepresentation.v finished (3 Structure, 85 Canonical)
- [ ] :construction: mxrepresentation.v taken
- [x] :white_check_mark: mxrepresentation.v compiles but needs more work
- [ ] vcharacter.v finished (0 Structure, 10 Canonical)
- [ ] :construction: vcharacter.v taken
- [x] :white_check_mark: vcharacter.v compiles but needs more work
- [ ] algC.v finished (0 Structure, 89 Canonical)
- [ ] :construction: algC.v taken
- [x] :white_check_mark: algC.v compiles but needs more work
- [ ] algebraics_fundamentals.v finished (0 Structure, 0 Canonical)
- [ ] :construction: algebraics_fundamentals.v taken
- [x] :white_check_mark: algebraics_fundamentals.v compiles but needs more work
- [x] algnum.v finished (0 Structure, 21 Canonical)
- [ ] :construction: algnum.v taken
- [ ] :white_check_mark: algnum.v compiles but needs more work
- [ ] closed_field.v finished (0 Structure, 0 Canonical)
- [ ] :construction: closed_field.v taken
- [x] :white_check_mark: closed_field.v compiles but needs more work
- [x] cyclotomic.v finished (0 Structure, 0 Canonical)
- [ ] :construction: cyclotomic.v taken
- [ ] :white_check_mark: cyclotomic.v compiles but needs more work
- [ ] falgebra.v finished (3 Structure, 61 Canonical)
- [ ] :construction: falgebra.v taken
- [x] :white_check_mark: falgebra.v compiles but needs more work
- [ ] fieldext.v finished (1 Structure, 138 Canonical)
- [ ] :construction: fieldext.v taken
- [x] :white_check_mark: fieldext.v compiles but needs more work
- [ ] finfield.v finished (0 Structure, 39 Canonical)
- [ ] :construction: finfield.v taken
- [x] :white_check_mark: finfield.v compiles but needs more work
- [ ] galois.v finished (1 Structure, 40 Canonical)
- [ ] :construction: galois.v taken
- [x] :white_check_mark: galois.v compiles but needs more work
- [x] separable.v finished (0 Structure, 0 Canonical)
- [ ] :construction: separable.v taken
- [ ] :white_check_mark: separable.v compiles but needs more work
- [ ] action.v finished (1 Structure, 29 Canonical)
- [ ] :construction: action.v taken
- [x] :white_check_mark: action.v compiles but needs more work
- [x] automorphism.v finished (0 Structure, 5 Canonical)
- [ ] :construction: automorphism.v taken
- [ ] :white_check_mark: automorphism.v compiles but needs more work
- [ ] fingroup.v finished (1 Structure, 16 Canonical)
- [ ] :construction: fingroup.v taken
- [x] :white_check_mark: fingroup.v compiles but needs more work
- [ ] gproduct.v finished (0 Structure, 28 Canonical)
- [ ] :construction: gproduct.v taken
- [x] :white_check_mark: gproduct.v compiles but needs more work
- [x] morphism.v finished (3 Structure, 14 Canonical)
- [ ] :construction: morphism.v taken
- [x] :white_check_mark: morphism.v compiles but needs more work
- [ ] perm.v finished (0 Structure, 23 Canonical)
- [ ] :construction: perm.v taken
- [x] :white_check_mark: perm.v compiles but needs more work
- [x] presentation.v finished (0 Structure, 0 Canonical)
- [ ] :construction: presentation.v taken
- [x] :white_check_mark: presentation.v compiles but needs more work
- [x] quotient.v finished (0 Structure, 14 Canonical)
- [ ] :construction: quotient.v taken
- [ ] :white_check_mark: quotient.v compiles but needs more work
- [x] abelian.v finished (2 Structure, 8 Canonical)
- [ ] :construction: abelian.v taken
- [ ] :white_check_mark: abelian.v compiles but needs more work
- [x] alt.v finished (0 Structure, 6 Canonical)
- [ ] :construction: alt.v taken
- [ ] :white_check_mark: alt.v compiles but needs more work
- [x] burnside_app.v finished (0 Structure, 24 Canonical)
- [ ] :construction: burnside_app.v taken
- [ ] :white_check_mark: burnside_app.v compiles but needs more work
- [ ] center.v finished (0 Structure, 7 Canonical)
- [ ] :construction: center.v taken
- [x] :white_check_mark: center.v compiles but needs more work
- [x] commutator.v finished (0 Structure, 4 Canonical)
- [ ] :construction: commutator.v taken
- [x] :white_check_mark: commutator.v compiles but needs more work
- [ ] cyclic.v finished (0 Structure, 4 Canonical)
- [ ] :construction: cyclic.v taken
- [x] :white_check_mark: cyclic.v compiles but needs more work
- [x] extraspecial.v finished (0 Structure, 1 Canonical)
- [ ] :construction: extraspecial.v taken
- [ ] :white_check_mark: extraspecial.v compiles but needs more work
- [x] extremal.v finished (2 Structure, 4 Canonical)
- [ ] :construction: extremal.v taken
- [ ] :white_check_mark: extremal.v compiles but needs more work
- [ ] finmodule.v finished (0 Structure, 27 Canonical)
- [ ] :construction: finmodule.v taken
- [x] :white_check_mark: finmodule.v compiles but needs more work
- [x] frobenius.v finished (0 Structure, 0 Canonical)
- [ ] :construction: frobenius.v taken
- [ ] :white_check_mark: frobenius.v compiles but needs more work
- [ ] gfunctor.v finished (4 Structure, 14 Canonical)
- [ ] :construction: gfunctor.v taken
- [x] :white_check_mark: gfunctor.v compiles but needs more work
- [ ] gseries.v finished (0 Structure, 0 Canonical)
- [ ] :construction: gseries.v taken
- [x] :white_check_mark: gseries.v compiles but needs more work
- [x] hall.v finished (0 Structure, 0 Canonical)
- [ ] :construction: hall.v taken
- [ ] :white_check_mark: hall.v compiles but needs more work
- [ ] jordanholder.v finished (0 Structure, 8 Canonical)
- [ ] :construction: jordanholder.v taken
- [x] :white_check_mark: jordanholder.v compiles but needs more work
- [x] maximal.v finished (2 Structure, 7 Canonical)
- [ ] :construction: maximal.v taken
- [ ] :white_check_mark: maximal.v compiles but needs more work
- [ ] nilpotent.v finished (0 Structure, 8 Canonical)
- [ ] :construction: nilpotent.v taken
- [x] :white_check_mark: nilpotent.v compiles but needs more work
- [ ] pgroup.v finished (0 Structure, 9 Canonical)
- [ ] :construction: pgroup.v taken
- [x] :white_check_mark: pgroup.v compiles but needs more work
- [x] primitive_action.v finished (0 Structure, 1 Canonical)
- [ ] :construction: primitive_action.v taken
- [ ] :white_check_mark: primitive_action.v compiles but needs more work
- [x] sylow.v finished (0 Structure, 0 Canonical)
- [ ] :construction: sylow.v taken
- [ ] :white_check_mark: sylow.v compiles but needs more work
- [ ] bigop.v finished (4 Structure, 35 Canonical)
- [ ] :construction: bigop.v taken
- [x] :white_check_mark: bigop.v compiles but needs more work
- [x] binomial.v finished (0 Structure, 0 Canonical)
- [ ] :construction: binomial.v taken
- [x] :white_check_mark: binomial.v compiles but needs more work
- [ ] choice.v finished (1 Structure, 5 Canonical)
- [ ] :construction: choice.v taken
- [x] :white_check_mark: choice.v compiles but needs more work
- [x] div.v finished (0 Structure, 0 Canonical)
- [ ] :construction: div.v taken
- [x] :white_check_mark: div.v compiles but needs more work
- [ ] eqtype.v finished (0 Structure, 5 Canonical)
- [ ] :construction: eqtype.v taken
- [x] :white_check_mark: eqtype.v compiles but needs more work
- [ ] finfun.v finished (2 Structure, 1 Canonical)
- [ ] :construction: finfun.v taken
- [x] :white_check_mark: finfun.v compiles but needs more work
- [x] fingraph.v finished (0 Structure, 2 Canonical)
- [ ] :construction: fingraph.v taken
- [x] :white_check_mark: fingraph.v compiles but needs more work
- [x] finset.v finished (0 Structure, 13 Canonical)
- [ ] :construction: finset.v taken
- [x] :white_check_mark: finset.v compiles but needs more work
- [ ] fintype.v finished (0 Structure, 6 Canonical)
- [ ] :construction: fintype.v taken
- [x] :white_check_mark: fintype.v compiles but needs more work
- [ ] generic_quotient.v finished (3 Structure, 26 Canonical)
- [ ] :construction: generic_quotient.v taken
- [x] :white_check_mark: generic_quotient.v compiles but needs more work
- [ ] order.v finished (9 Structure, 501 Canonical)
- [ ] :construction: order.v taken
- [x] :white_check_mark: order.v compiles but needs more work
- [x] path.v finished (0 Structure, 0 Canonical)
- [ ] :construction: path.v taken
- [x] :white_check_mark: path.v compiles but needs more work
- [x] prime.v finished (0 Structure, 1 Canonical)
- [ ] :construction: prime.v taken
- [x] :white_check_mark: prime.v compiles but needs more work
- [x] seq.v finished (0 Structure, 4 Canonical)
- [ ] :construction: seq.v taken
- [x] :white_check_mark: seq.v compiles but needs more work
- [x] ssrAC.v finished (0 Structure, 1 Canonical)
- [ ] :construction: ssrAC.v taken
- [x] :white_check_mark: ssrAC.v compiles but needs more work
- [x] ssrbool.v finished (0 Structure, 0 Canonical)
- [ ] :construction: ssrbool.v taken
- [x] :white_check_mark: ssrbool.v compiles but needs more work
- [x] ssreflect.v finished (4 Structure, 6 Canonical)
- [ ] :construction: ssreflect.v taken
- [x] :white_check_mark: ssreflect.v compiles but needs more work
- [x] ssrfun.v finished (0 Structure, 0 Canonical)
- [ ] :construction: ssrfun.v taken
- [x] :white_check_mark: ssrfun.v compiles but needs more work
- [x] ssrmatching.v finished (0 Structure, 0 Canonical)
- [ ] :construction: ssrmatching.v taken
- [x] :white_check_mark: ssrmatching.v compiles but needs more work
- [x] ssrnat.v finished (0 Structure, 4 Canonical)
- [ ] :construction: ssrnat.v taken
- [x] :white_check_mark: ssrnat.v compiles but needs more work
- [x] ssrnotations.v finished (0 Structure, 0 Canonical)
- [ ] :construction: ssrnotations.v taken
- [x] :white_check_mark: ssrnotations.v compiles but needs more work
- [ ] tuple.v finished (1 Structure, 25 Canonical)
- [ ] :construction: tuple.v taken
- [x] :white_check_mark: tuple.v compiles but needs more work
- [x] all_ssreflect.v finished
- [ ] :construction: all_ssreflect.v taken
- [ ] :white_check_mark: all_ssreflect.v compiles but needs more work
- [x] all_fingroup.v finished
- [ ] :construction: tuple.v taken
- [ ] :white_check_mark: all_fingroup.v compiles but needs more work
- [x] all_algebra.v finished
- [ ] :construction: all_algebra.v taken
- [ ] :white_check_mark: all_algebra.v compiles but needs more work
- [x] all_solvable.v finished
- [ ] :construction: all_solvable.v taken
- [ ] :white_check_mark: all_solvable.v compiles but needs more work
- [x] all_field.v finished
- [ ] :construction: all_field.v taken
- [ ] :white_check_mark: all_field.v compiles but needs more work
- [x] all_character.v finished
- [ ] :construction: all_character.v taken
- [ ] :white_check_mark: all_character.v compiles but needs more work
- [x] all.v finished
- [ ] :construction: all_character.v taken
- [ ] :white_check_mark: all_character.v compiles but needs more work
Overlays
- https://github.com/math-comp/Abel/pull/75
- https://github.com/coq-community/coqeal/pull/57
- https://github.com/proux01/coquelicot
- https://github.com/coq-community/bits/pull/20
- https://github.com/math-comp/finmap/pull/84
- https://github.com/coq-community/fourcolor/pull/44
- https://github.com/coq-community/gaia/pull/11
- https://github.com/coq-community/graph-theory/pull/25
- https://gitlab.inria.fr/coqinterval/interval/-/tree/hierarchy-builder
- https://github.com/math-comp/mczify/pull/39
- https://github.com/math-comp/multinomials/pull/42
- https://github.com/math-comp/odd-order/pull/37
- https://github.com/math-comp/real-closed/pull/38
- https://github.com/coq-community/reglang/pull/46
- [x] foo.v finished
- [ ] :construction: foo.v taken
- [ ] :white_check_mark: foo.v compiles but needs more work
Nix CI is broken:
error: value is a list while a set was expected, at /home/runner/work/math-comp/math-comp/default.nix:13:1
@CohenCyril is this gitlab CI pipeline a new thing?
@CohenCyril @pi8027 can you check if the recent locking in rat helps this example: https://github.com/math-comp/math-comp/pull/733/commits/5e84326f5a6759b1d227f066088988e39e8538ff I suspect it just gets slowed in this branch, but that it is already problematic.
Here is a squashed and rebase branch: https://github.com/math-comp/math-comp/tree/hierarchy-builder-rebased (but I cannot force push here)
Rebase force pushed, the previous state (before squashing everything) is saved in https://github.com/math-comp/math-comp/tree/hierarchy-builder-before-rebase_2022_05_04
So, here is the state of the CI:
- I dropped planB
- coq-dev is borken on Nix CI (I understand that https://github.com/NixOS/nixpkgs/pull/161977 should fix it)
- unfortunately coq-dev is also broken on Docker CI since the lower bound for OCaml was bumped without coordinating with the maintainer of Docker images (https://coq.zulipchat.com/#narrow/stream/237656-Coq-devs-.26-plugin-devs/topic/.3E.3D.204.2E09.20and.20opam/near/280985366) hopefully, this will be fixed soon
- reverse dependencies not ported yet
- analysis
- deriving
- extructures
- other reverse dependencies are working out of the box or with an overlay (c.f. list of overlays at bottom of top PR description):
- abel
- addition-chains
- autosubst
- bigenough
- category-theory
- coqeal
- coq-bits
- coquelicot
- finmap
- fourcolor
- gaia
- graph-theory
- interval
- mczify
- multinomials
- odd-order
- QuickChick
- real-closed
- reglang
- verdi
Out of curiosity, how are compilation times affected?
Last figure I remember was nearly a factor two but @gares would know better.
So, here is the state of the CI:
- Coq master seems fine thanks to @CohenCyril 's branch (https://github.com/NixOS/nixpkgs/pull/173112)
- only remaining broken reverse dependencies are:
- analysis
- deriving which uses universe polymorphism (c.f. https://github.com/proux01/deriving/blob/48f613b98bfe8d130431c00bac4fefa1e54576be/theories/base.v#L980-L982 ) not yet implemented in coq-elpi
- extructures which requires deriving
Last figure I remember was nearly a factor two but @gares would know better.
A 2x increase in compilation time seems a bit surprising (and maybe worrying) . In particular, the amount of time spent in HB code should be just a small fraction of the compilation time.
Isn't that suspicious? What is the main bottleneck here.
I think that Coq really needs something like HB, but if users are gonna get a 2x slowdown from it I'm not sure it is ready until it is more optimized.
The difference is that structures are more regular than before, and less manual tweaks. The time spent in HB commands is negligible, or close to so. The code generated is more likely to trigger bad behavior in conversion heuristics. But so far every time I did investigate a little change here or there would change the cost of a few lines of 100x, so I'm not scared, it is just about spending time on it. And for now the (little) energy is in cover the whole ssrnum (not far, but not there yet).
@CohenCyril you can now delete yout hb-ssrnum branch as it is integrated here
As a consequence, we had to drop support for Coq 8.13 and 8.14, this now only works with:
- Coq 8.15 with HB
masterbranch - Coq 8.16+rc1 with HB
masterbranch - Coq master with HB
coq-masterbranch
can we give planB another try? (I'm too bad at nix to bring it back)
can we give planB another try? (I'm too bad at nix to bring it back)
@CohenCyril do you remember how to set this up in Nix CI? (I probably won't have time to look at it anytime soon)
@CohenCyril no hurry, but I may need your Nix expertise with the CI here:
-
reglangfails in the CI but I'm not able to reproduce the failure locally, when I type the CI command
NIXPKGS_ALLOW_UNFREE=1 nix-build --no-out-link --argstr bundle "coq-8.15" --argstr job "reglang"
on my machine the thing compiles flawlessly
-
mathcomp-classicalandmathcomp-analysis: this works on Analysis CI (https://github.com/math-comp/analysis/pull/698) but not here, in that case I'm able to reproduce locally and it seems Nix is downloading the source of mathcomp (and not mathcomp-analysis) for mathcomp-classical and I don't understand why (I tried adding an overlay formathcomp-classicalbut without success)
@CohenCyril timings to compile OddOrder (make -j1 on my laptop):
- without semirings: 2074.59user 18.59system 35:21.32elapsed
- with semirings: 2209.54user 13.78system 37:09.35elapsed
So, that's about 6% slower.
(Note: I had to add a dozen pattern selections: https://github.com/proux01/odd-order/commit/bcca2577f882cb85830dd2816f6d80a21cac558c )
@pi8027 we did review some FIXME in order.v and left some comments, please look at them and decide what to do.
@pi8027 we did review some FIXME in order.v and left some comments, please look at them and decide what to do.
All of these are problems that should be fixed in HB, not mathcomp.
I did a last rebase to squash a few things and check that all commits do compile. From now on, we only cherry-pick from master (or push directly here for HB changes).
Manual merge in master in progress