| Age | Commit message (Collapse) | Author |
|---|
|
univ_depends checks whether a universe variable appears or
is equal to a universe. In comparison with the previous hack
in inductiveops based on try...catching UniverseInconsistency,
this should be semantically equivalent, simplier, and more
robust in case we allow someday an unsafe mode where
merge_constraints would be a no-op.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@15013 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Let's gain a few % by not using Pervasive.compare on a structure containing
some universe_levels, but rather UniverseLevel.compare on them.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@15012 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Let's reintroduce the idea of stopping the graph traversal as
soon as a LE arc has been found, but this time we do so only
when we're not interested by the LT/LE distinction.
This way, we should remain correct but avoid largly the time penalty
induced by the last fix on univ.ml: the +30% on contrib Container
is almost gone, let's hope it'll be the same with Ssreflect.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@15007 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
The earlier version was a bit too quick to answer <= while strict
constraints could still appear from remaining universes to explore.
Typical situation: compare u v when u <= v and u <= w < v.
Encountering u <= v isn't enough to conclude yet...
This means that kernels from r13719 to now in trunk, and
from r13735 to now in 8.3 (including 8.3pl{1,2,3}) couldn't accurately
detect universe inconsistencies, leading to potential proofs of False!
Oups, sorry...
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14993 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Here Foo is Univ.constraints, Univ.universes, Evd.evar_map, Evd.Metamap
Ok, all these structures are currently ocaml's maps or similar,
with a unique empty value, and (=) can be used on them in this
particular case. But using Foo.is_empty is safer : it will work
even if the underlying representation changes. Example : for
spotting non-legitimate use of (=) we might embed a type into
a record with a functional field.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14614 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Inductive definitions aren't that big, but they may contain some
constr (in types, rel_context, etc), hence if we hash-cons the
constr in Definition but not these ones, we may loose some sharing.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14544 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- An inductive is hidden inside case_info.
(btw, maybe we could get rid of this ci_ind altogether,
since the information is already in the predicate of the match)
- Typical situation where user kn and canonical kn are initially (==)
was not preserved by hconsing of constant / mutual_inductive
- inductive = (mutual_inductive * int) and
constructor = inductive * int were not properly shared
This should fix the strange situation of Udine/PiCalc taking *more*
vo space after the last round of hcons tweaks.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14507 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Now that Yann has provided a better hashing mechanism for constr,
it might be interesting to (re-?)activate a global hash-consing of
constr. Earlier, specific hash-cons tables were created at each call
to hcons_constant_declaration. According to Hugo, this was meant to
avoid blow-up in at least contrib Pocklington. This contrib seems
to behave nicely now with global hashconsing (thanks Yann ;-).
We'll see tomorrow what impact this has on other contribs.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14487 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- When hash-consing, seeing ident as having string as sub-structure
induces a penalty: two searchs are done in two tables
(one for string, one for id).
We simply say now that the hcons function for ident is the one
for string
- use more == during hash-consing of Names.uniq_ident and
Names.module_path
- clarification concerning hash-cons of Names.constant and
Names.mutual_inductive: we only hash-cons the canonical part,
but == could be used nonetheless on the obtained pair. Simply
note that canonical_con of hash-consed constants will produce
kernel_names that may be (=) but not (==).
- Code cleanup : no direct use of string hash-consing apart in Names,
we hence simplify hcons_names
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14464 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Two issues were preventing the hcons1_univ function to properly work
- a launch of Names.hcons_names () at each hconsing of universe,
hence one separated hash-table for dir-path created at each time,
oups...
- Bad handling of the universe sub-structure universe_level
To check : is there an interest in making separate calls to
Names.hcons_names () in separate places (Univ, Term, Declare) ?
I think not. Btw the hconsing of Declare.hcons_constant_declaration
is also probably wrong. To be fixed in a forthcoming patch.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@14463 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
evar, and simultaneously make type inference with universes work better.
This only exports more functions from kernel/univ, to be able to work
with a set of universe variables during type inference. Universe
constraints are gradually added during type checking, adding information
necessary e.g. to lower the level of unknown Type variables to Prop or
Set. There does not seem to be a disastrous performance hit on the
stdlib, but might have one on some contribs (hence the "Tentative").
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13905 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
The whole standard library fits in 3 universes (instead of 22 with the
previous algorithm).
Very costy, time complexity: O(n^4) (if we assume map operations are
done in constant time), with n being the number of universe
variables. It takes ~35s for the whole stdlib.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13796 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
This is merely refactoring so that UniverseL{Map,Set} constructions
appear nicely.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13788 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13786 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13784 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Sometimes the same (repr g u) was done in different functions
after being passed u as argument. We rather try to compute
(repr g u) as soon as possible, and then pass it instead of u.
Beware of sync issues : if g changes, arcu might become obsolete
(cf. setlt, setleq, merge ...)
Typical code around occurences of declare_univ was doing up to 3
lookups:
- is u in g ?
- if not we descend again in g to add it
- and then later repr is called on the same u.
With my safe_repr, we do one lookup if u is in g, and a lookup and
an addition otherwise. Ok, declare_univ was rarely used, but it seems
nicer this way.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13726 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
No need to tell the world about the fact that constraints are
implemented via caml's Set. Other modules just need to know about
the empty and union functions (and addition functions "enforce_geq"
and "enforce_eq" that were already there).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13725 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
The gains on contribs are quite small, around 3% max, apart from
3 small contribs where it's about 10% (corresponding to 10s each).
With last patch, we add quicker lookup for universes in the graph
(up to 5 times less calls to cmp_univ_level on an example), but
probably more "administrative" work (i.e. addition of updated paths
in the graphs, handling pairs of updated graphs and results in
functions, etc), and some sharing might also have been lost since
graphs changed more.
Anyway, little gain and more complex code, let's remove this patch
for now ... until the next attempt to speed-up the universe layer.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13724 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
We'll see experimentally if this helps... A few more functions could
be adapted (e.g. between), and an occurence of compare just discard
the compacted graph (in compare_greater)
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13723 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- The "compare" function on universes (the one answering EQ|LT|LE|NLE)
was launching "collect" for creating the transitive upward closure
of u, and then checking if v is in it. We now proceed more lazily,
by stopping creating the transitive closure as soon as v is found.
- In univ_entry, the first arg u of Equiv(u,v) is removed. It can
indeed be retrieved from the key of the universe graph leading
to this Equiv.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13719 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13614 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Instead of formatting directly to an output channel, provide an output
function that handles formatting and I/O. This allows changing the
output format.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13610 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
In particular, the unused lib/tlm.ml and lib/gset.ml are removed
In addition, to simplify code, Libobject.record_object returning only the
('a->obj) function, which is enough almost all the time.
Use Libobject.record_object_full if you really need also the (obj->'a).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13460 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13323 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13119 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13005 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- Many of them were broken, some of them after Pierre B's rework
of mli for ocamldoc, but not only (many bad annotation, many files
with no svn property about Id, etc)
- Useless for those of us that work with git-svn (and a fortiori
in a forthcoming git-only setting)
- Even in svn, they seem to be of little interest
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12972 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
+ changed printing of universe Type(0) to Set, so not to show that the
implementation starts numbering with Set=Type(0) while documentation uses
Type(0) for the common type of Prop and Set.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12956 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12337 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
This commit concerns about the first half of the useless code
mentionned by Oug for coqtop (without plugins). For the moment,
Oug is used in a mode where any elements mentionned in a .mli
is considered to be precious. This already allows to detect and
remove about 600 lines, and more is still to come.
Among the interesting points, the type Entries.specification_entry
and its constructors SPExxx were never used. Large parts of cases.ml
(and hence subtac_cases.ml) were also useless.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@12069 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11595 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11593 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- compare the integer indexes first, in order to avoid
comparing the dirpath part if possible
- use an ad-hoc comparison function rather than Pervasives.compare
(slightly faster during my tests on the compcert contrib)
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11589 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
contraintes bornant par le haut le type de l'inductif (ce qui peut
arriver quand l'inductif est argument d'une constante) étaient
oubliées : on pouvait se retrouver avec des inductifs dont le type des
constructeurs, une fois instancié par des paramètres) n'était plus
typable (seul leur réduit, après expansion des constantes, était
typable). [kernel, test-suite]
+ Affichage des inductifs (via Print) en prenant la forme utilisateur des
constructeurs.
+ Correction warning dans compilation gallina.ml.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11266 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
les notations dans les alias de module.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11063 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
univers, suite à discussion avec Bruno : on franchit le cap et on
ajoute le sous-typage Prop <= Set. On n'a donc plus besoin d'utiliser
l'image de Prop dans la hiérarchie en dehors de la zone de calcul de
la sorte la plus basse d'un inductif polymorphe (au passage, nous
avons décidé de renommer Type -1 en Type 0-, pour bien indiquer qu'il
se trouve au même niveau que Type 0).
Coq se retrouve donc avec la hiérarchie Prop <= Set <= Type i et avec
une copie de Prop (Type 0-) et une copie de Set (Type 0) dans la
hiérarchie Type. En théorie, on pourrait donc supprimer "Prop Null" et
"Prop Pos" de l'implémentation et ne travailler qu'avec "Type".
L'ajout de Prop <= Set vaut à la fois dans le cas Set prédicatif et
dans le cas Set imprédicatif (Prop et Set étant en bas de la
hiérarchie, il n'y a pas d'incohérence connue). Dans le modéle
ensembliste, Prop et Type 0- sont interprétés par exemple comme
{{},{o}}, où "o" est un objet particulier interprétant les preuves, et
il n'y a pas de Set imprédicatif. Dans un modèle de réalisabilité,
Set imprédicatif est interprétable et Prop peut au choix s'interpréter
comme Set ou comme booléen (cf la thèse de Miquel). Le sous-typage du
côté ensembliste s'obtient en mettant au moins l'ensemble {{},{o}}
dans l'interprétation de Set (ce qu'on fait de la même manière que
Prop <= Type 1, avec conversion typée), et du côté réalisabilité en
mettant l'ensemble {Typ(vide),Typ(unit)} dans l'interprétation de Set
("Typ" étant la coercion faisant d'un ensemble un terme), ce qui est
fait dans la section 6.2.4 de la thèse d'Alexandre Miquel (modèle du
CC implicite sans types inductifs).
Il reste un problème pratique. Lorsqu'on donne
Inductive unit:Type := tt:unit.
Coq dit que unit est dans Prop. C'est correct parce qu'il n'y a pas de
contraintes d'univers mais un peu déroutant même si la coercion
"unit : Set" reste valide. Une suggestion est de ne rendre polymorphe
que les inductifs dont on ne donne pas la sorte explicitement, comme dans
Inductive unit := tt:unit.
mais alors, comment indiquer l'absence de sorte explicite si le type a
des paramètres réels (comme "vect") ??
PS: modification de sort_cmp dans checker/inductive.ml faite.
--This line, and those below, will be ignored--
M kernel/univ.ml
M kernel/univ.mli
M kernel/inductive.ml
M kernel/reduction.ml
M kernel/indtypes.ml
M checker/inductive.ml
M checker/reduction.ml
M pretyping/reductionops.ml
M pretyping/termops.ml
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10920 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
(i.e. "Inductive unit := tt." conduisait à "t:Prop" alors que le
principe de la hiérarchie d'univers est d'être cumulative -- et que
Set en soit le niveau 0).
Une solution aurait été de poser Prop <= Set mais on adopte une autre
solution. Pour éviter le côté contre-intuitif d'avoir unit dans Type
et Prop <= Set, on garde la représentation de Prop au sein de la
hiérarchie prédicative sous la forme "Type (max ([],[])" (le niveau
sans aucune contrainte inférieure, appelons Type -1) et on adapte les
fonctions de sous-typage et de typage pour qu'elle prenne en compte la
règle Type -1 <= Prop (cf reduction.ml, reductionops.ml, et effets
incidents dans Termops.refresh_universes et Univ.super).
Petite uniformisation des noms d'univers et de sortes au passage
(univ.ml, univ.mli, term.ml, term.mli et les autres fichiers).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10859 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10826 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
appels à type_of et get_type_of sont souvent utilisés pour construire
des termes à partir de types; on ne rajoute pas non plus de
contraintes inutiles parce que type_of et get_type_of ne changent pas
le graphe de contraintes; tout ce qu'on perd est une information
utilisateur sur le type en lui-même mais puisque pretty.ml n'appelle
ni type_of ni get_type_of, ces informations sur la représentation
interne des univers restent a priori accessibles pour l'utilisateur.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10674 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Variable, et plus de trucs useless qui traînaient par ma faute (y
compris dans le noyau, la honte).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10388 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
lib/option.ml(i) . J'en profite pour rajouter des primitives de lifting
des fonctions (à un ou deux arguments tous ou partie de type option).
Il reste quelques opérations dans Util à propos desquelles je ne suis
pas trop sûr, ou simplement que j'ai oublié, mais qui attendront demain
car il est tard (comme some_in qui devrait devenir Option.make je
suppose) . Elles s'expriment souvent facilement en fonction des
autres, par exemple "option_compare x y" est égal à "Option.lift2 compare x y"
. Le option_cons devrait faire son chemin dans le module parce qu'il est
assez primitif et qu'il n'y a pas de fonction "cons" dans OCaml.
J'en ai profité aussi pour remplacer les trop nombreux "failwith" par
des erreurs locales au module, donc plus robustes.
J'ai trouvé aussi une fonction qui était définie deux fois, et une
définie dans un module particulier.
Mon seul bémol (mais facile à traiter) c'est la proximité entre le
nom de module Option et l'ancien Options. J'ai pas de meilleure idée de
nom à l'heure qu'il est, ni pour l'un, ni pour l'autre.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10346 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Printing Universes est active.
Ajout de l'option "using" à la tactique non documentée "auto decomp".
Ajout de la base "extcore" pour étendre "auto decomp" avec des
principes élémentaires tels que le dépliage de "iff".
Quelques extensions/raffinements dans ChoiceFacts et ClassicalFacts.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@10156 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
details).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@9821 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
les interfaces de module (bug similaire à #1302 mais pour les
définitions -- au lieu des inductifs)
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@9505 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
Amélioration affichage des univers. Réparation de petits oublis du premier
commit. Essai d'une nouvelle stratégie : si le type d'une constante
est mentionné explicitement, la constante est monomorphe dans Type.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@9314 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
- prise en compte du niveau à la déclaration du type comme une fonction
des sortes des conclusions des paramètres uniformes
- suppression du retypage de chaque instance de type inductif (trop coûteux)
et donc abandon de l'idée de calculer une sorte minimale même dans
des cas comme Inductive t (b:bool) := c : (if b then Prop else Type) -> t.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@8845 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@8673 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@7352 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@6994 85f007b7-540e-0410-9357-904b9bb8a0f7
|
|
extensibilité aux contraintes numériques
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@6992 85f007b7-540e-0410-9357-904b9bb8a0f7
|
