You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
As discussed, it would be nice to tag operators and axioms in certain abstract theories as non-instantiable. For Subtype, this could look as follows:
type T.
pred P : T.
axiom P_nonempty : exists x, P x.
generate type sT.
generate op insub : T -> sT option.
generate op val : sT -> T.
generate axiom insubN (x : T): !P x => insub x = None.
generate axiom insubT (x : T): P x => omap val (insub x) = Some x.
generate axiom valP (x : sT): P (val x).
generate axiom valK: pcancel val insub.
(* rest of the Subtype theory ... *)
The idea is that one can check once (when writing the theory) that the generated collection of operators and axioms is consistent for all instances (that validate the non-generated axioms) and thereby facilitate the use of proof* everywhere else.
Of course, we could implement quotients using choice and subtypes, so this may be the only instance we ever need. IIUC, that's what HOL systems tend to do. So implementing the typedef from Isabelle/HOL is another option.
After a bit of thinking and reading about this, maybe it would be preferable (in particular safer) to implement something akin to the HOL typedef mechanism described for instance in Sect. 2.2 of From Types to Sets by Local Type Definition
in Higher-Order Logic.
My main issue with the "trusted axiom" approach is that there is no way to ensure that people won't clone subType with concrete instantiations for val and insub without ever seeing the (then inconsistent) trusted axioms. IIUC, one way or another, we need to be able to create theories with abstract operators that cannot be instantiated during cloning.
Also, I don't think we need more than a typedef. We generally assume a choice operator (aka Hilbert's epsilon-operator), so we can define quotient types as the subtype of (canonical) representatives for equivalence classes.
The aforementioned paper also proposes a variant of typedef that can be used inside proofs. I think this is something that we might want to consider at a later point.
@strub @bgregoir @gbarthe What are your thoughts on this?
My impression, is that the problem will be only for the subtype theory.
I think, we should provide a simple patch such that we can do a local clone of subtype without
problem.
Then, we should work on how to have a proper definition of subtype in EC (without need of that theory).
At the very least, if we tag some of the axioms in subType to not show up in proof*, we also need a way to tag the operators val and insub as uninstantiable. Otherwise, people can (accidentally) introduce (almost) impossible to detect inconsistencies.
@strub @fdupress @bgregoir This has been dormant for a while. If I recall correctly, tagging ops in a theory as uninstantiable was something that was asked for in Porto for some unrelated reason. If we ensure that val and insub are kept abstract, then suppressing the axioms should be fine.
Incidentally, I think that the current way to handle non-emptiness is suboptimal. This should actually always be proved by the user. But without knowing what the witness of the sT is it's hard to define its preimage as an op (without using choice).
@chdoc
I wrote a replacement for Subtype that alleviates the problem by using several tricks:
val and insub are not unspecified operators, but defined (via choiceb as "some suitable val and insub"). This makes sure that they cannot be overwritten.
The only axiom is that the predicate P is inhabited.
The type sT is also defined, and hence cannot be overwritten. It is defined as a thin wrapper around a type called do_not_use_this_type_or_you_get_unsoundness_admit. While it is technically possible to clone this subtype theory unsoundly (by specifying type do_not_use_this_type_or_you_get_unsoundness_admit = ... during clone), the name makes it unlikely that people do so.
The fact that there is a bijection between do_not_use_this_type_or_you_get_unsoundness_admit and P is axiomatized, but using lemma ... admit. qed. instead of axiom .... This ensures that clone ... proof * does not require us to prove the existence of this bijection.
Instead, there is an axiom inhabited saying that P is inhabited. It is not actually used but it ensures that one cannot accidentally instantiate an empty Subtype.
With these changes, one can create subtypes without getting unprovable proof obligations. (The existing mechanism makes it impossible to soundly instantiate many theories that internally use Subtype. E.g., clone ZModP.ZModRing ... proof * requires us to prove the unprovable Subtype axioms, but without proof *, we might not show the important p >= 2 axiom. This is proof of false waiting to happen...) At the same time, everything is sound as long as one follows the rule always to have a proof * when cloning in a non-abstract theory (imho, EasyCrypt should enforce that, or at least make it a strong default), and does not refer to do_not_use_this_type_or_you_get_unsoundness_admit directly while cloning.
With my Subtype replacement (SafeSubtype.eca.txt), one can declare subtypes as follows:
clone SafeSubtype as ST with
type T = int,
op P = fun x:int, 0 <= x
proof *.
realize inhabited.
exists 0. trivial.
qed.
The theory is designed to be a drop-in replacement for the existing Subtype. It exports the same ops, types, and lemmas.
Main disadvantage: The theory contains an admit. But I think if it's in the stdlib (instead of the existing Subtype), and the admit get a clear comment that it is ok because of the axioms inhabited, then that should be OK. (At least till a builtin subtype command comes along.)
One very minor thing to keep in mind (not to stop this change, but to enable it with minimal loss elsewhere) is that defining the injection and projection in all subtypes will likely cause issues like those that arose from doing the same in a specific one ('a distr) last year: the SMT lemma selection is going to suddenly pull in a whole lot more theory that was previously hidden by abstraction.
It might make sense, for now, to make sure that all subtype instantiations in the stdlib are marked as much as possible with nosmt. We can return to working on switching the default independently.
@strub I'm trying to make the PR (and see where the stdlib breaks) but I run into a mystery and am not sure whether it's intended or a bug.
pred x (c:bool) = true.
op y = x.
fails but
op x (c:bool) = true.
op y = x.
succeeds. In general, it seems that preds can never be part of ops. Is that intentional?
From looking at the reference manual, I don't see any difference between ops and preds (except that the type annotations are written a bit differently).
It's a problem because it means in my Subtype, P has to be an op. But if it's an op, then it will need to be instantiated with ops. But inductive ispoly in Poly.ec is a pred, and I don't see how to make it an op because inductive seems to produce preds.
It might make sense, for now, to make sure that all subtype instantiations in the stdlib are marked as much as possible with nosmt. We can return to working on switching the default independently.
How does one do that? I only know how to do it to lemmas, but not to theories as a whole. Ideally, we would like to add nosmt to the definitions of val and insub but I don't know if that's possible.
Yes-ish: you can't add a nosmt annotation when cloning, so the way you'd need to do it is to first define your op tagged as nosmt, then use it in cloning. Perhaps don't do it and let's see if anything blows up because of the size of SMT contexts.
As for the pred vs op issue, this will count as "something that breaks in the stdlib" and that we need to think hard about sorting out.
Easy and dirty fix is to make inductive define an op instead (after thinking about how that impacts a whole bunch of things), but doing this more systematically might also fit current code simplification efforts.
I remember P-Y explaining to me why getting rid of preds entirely would require some major refactoring, but I can't remember (and it must have been on slack).
@strub I'm trying to make the PR (and see where the stdlib breaks) but I run into a mystery and am not sure whether it's intended or a bug.
I got around this (it turns out in Poly.ec, the inductive predicate didn't really need to be an inductive one, since it used the inductive predicate in a degenerate case with only one case and no recursion). Stdlib and examples now work.
I remember P-Y explaining to me why getting rid of preds entirely would require some major refactoring, but I can't remember (and it must have been on slack).
This is because we have this (now artificial since expressions can contain non-executable constructions) distinction between expressions & formulas.
Now, last time I spoke about this with Benjamin, we realized that operators body could contain formula without having to do a heavy refactoring (having formulas in the RHS of the assignment instruction would be a totally different story). This is something that could be done once Cameron is done with the refactoring of substitutions.
Yes-ish: you can't add a nosmt annotation when cloning, so the way you'd need to do it is to first define your op tagged as nosmt, then use it in cloning. Perhaps don't do it and let's see if anything blows up because of the size of SMT contexts.
I think that this should be part of the reflexion around the new behavior of the smt/nosmt annotations.
Reopening the issue. The current subtype implementation is a nightmare w.r.t. pretty-printing: all subtypes are named sT and it is hard to understand. I propose to implement Christian ideas.
@strub You can still rename sT when cloning. The ergonomics of renaming and instantiating with another abstract type are about the same IMO.
I'm not against uninstantiable types/operators/axioms, but I don't think it helps with pretty printing of subtypes.
I do think it would be nice to make subtypes more solid. There are ways to prove false without instantiating do_not_instantiate_this_type directly, though all ways I could find either involve mangling its name through renaming or at least writing out the name of the type in the source somewhere. There's also the risk that future features make it possible to either create an alias for do_not_instantiate_this_type without explicitly mentioning it or allow getting rid of references to P from a cloned Subtype theory without mentioning do_not_instantiate_this_type. You can already get rid of lemmas using clear [Thy.*] and the P operator during instantiation, but I can't find a way to get rid of the other operators without mentioning do_not_instantiate_this_type yet.
Turns out subtypes are still unsound because sT (and do_not_instantiate_this_type) do not directly reference T. This causes problems when making the subtype parametric using sections and declare type. The sT ends up not being parametric, while the lemmas stay parametric from which it is easy to derive a contradiction by using parameters that end up with subtypes that should have different properties.
I've weaponized it by using the trivial subtype and the fact that the unit type only has one member, while the integers have distinct members:
require Subtype.
section.
declare type t.
clone include Subtype with
type T <- t,
op P <- predT
proof * by exists witness.
end section.
lemma sT_has_two: exists (v1 v2: sT), v1 <> v2.
proof.
exists (insubd 0) (insubd 1).
rewrite -negP => eq_insubd.
apply (congr1 val<:int>) in eq_insubd.
by do 2! (rewrite insubdK in eq_insubd => //).
qed.
lemma sT_is_unital (v1 v2: sT): v1 = v2.
proof. by apply val_inj<:unit>; elim (val v1); elim (val v2). qed.
lemma explosion: false.
proof. move: sT_has_two => [v0 v1] /=. apply sT_is_unital. qed. print Subtype.
It seems to me that the issue here is that the clone include leaks out of the section. Unlikely to be fixed by #691 unless subtype is forbidden from interacting with the section mechanism in this way.
Yes, you can use the renaming. But still, the current subtype theory does not prevent you from introducing inconsistent axioms (as you demonstrated) so I prefer to stick to the one that is simpler to read.
Your example is not an unsoundness per se. You have a proof of false under an inconsistent axiom. I still agree that there is a usability issue that we should work on. But here too, this is unrelated to revert subtype theory + syntactic sugar for cloning it #691. It is anyway very easy to introduce inconsistencies with section. See below for an example in Coq. (This is an example coming from a real project)
IMO, having a primitive subtype construction is the way to go.
From mathcomp RequireImport all_ssreflect.
Parameter P : pred nat.
Axiom A : forall n, prime n -> P n.
Section A.
Variable (n : nat).
Parameter n_is_prime : prime n.
Lemma LA : P n.
Proof. exact: (A _ n_is_prime). Qed.
End A.
Section B.
Variable (n : nat).
Variable n_is_prime : prime n.
Lemma LB : P n.
Proof. exact: (A _ n_is_prime). Qed.
End B.
Print n_is_prime.
Print LA.
Print LB.
I don't know if this is the case for your Coq example, but at least in EasyCrypt with the current subtype theory you end up with no remaining discoverable axioms in the resulting theory.
My litmus test for "do I have a full proof" is whether cloning the theory (meaning the entire file) with proof * shows any axioms, and in this case it does not. Doesn't that correspond to having the result in a closed environment?
I'm not sure if it's fair to say that the fault is with the interactions between clone include and sections alone. I don't think I'd be able to do something similar without the Subtype theory, which currently has the special permission of being allowed to use admitted in subtype_injection.
The issue here is that while cloning means that you get a unique sT for every operator since a new operator requires a new clone, it does not mean that you get a unique sT for every type parameter 'a.
I think that with the old theory, making the following modification fills in the hole while keeping it possible to make parametric subtypes;
type 'a do_not_instantiate_this_type.
type sT = T do_not_instantiate_this_type wrapped.
Also, all other occurrences of do_not_instantiate_this_type should be replaced with T do_not_instantiate_this_type.
I don't know how that translates to the new mechanism.
My proposed fix doesn't entirely work either. It's still possible to inject a type parameter into P without injecting it into T;
op unital ['a] = forall (x y: 'a), x = y.
section.
declare type t.
clone include Subtype with
type T <- bool,
op P <- if unital<:t> then predT else pred1 witness
proof * by (exists witness => /#).
end section.
lemma sT_has_two: exists (v1 v2: sT), v1 <> v2.
proof.
exists (insubd<:unit> false) (insubd<:unit> true).
rewrite -negP => eq_insubd.
apply (congr1 val<:unit>) in eq_insubd.
do 2! (rewrite insubdK // in eq_insubd).
qed.
lemma sT_is_unital: unital<:sT>.
proof.
rewrite /unital => x y.
rewrite -valKd<:bool> -(valKd<:bool> y).
congr.
have := valP<:bool> x.
have := valP<:bool> y.
by have -> /= -> ->: !unital<:bool> by smt().
qed.
lemma explosion: false.
proof. move: sT_has_two => [v0 v1] /=. apply sT_is_unital. qed.
Seems like a built in mechanism really is the only way to go forward without some kind of dependent types.
Activity
strub commentedon Oct 12, 2022
You might be interested by this:
chdoc commentedon Oct 21, 2022
After a bit of thinking and reading about this, maybe it would be preferable (in particular safer) to implement something akin to the HOL typedef mechanism described for instance in Sect. 2.2 of From Types to Sets by Local Type Definition
in Higher-Order Logic.
My main issue with the "trusted axiom" approach is that there is no way to ensure that people won't clone
subTypewith concrete instantiations forvalandinsubwithout ever seeing the (then inconsistent) trusted axioms. IIUC, one way or another, we need to be able to create theories with abstract operators that cannot be instantiated during cloning.Also, I don't think we need more than a
typedef. We generally assume a choice operator (aka Hilbert's epsilon-operator), so we can define quotient types as the subtype of (canonical) representatives for equivalence classes.The aforementioned paper also proposes a variant of
typedefthat can be used inside proofs. I think this is something that we might want to consider at a later point.@strub @bgregoir @gbarthe What are your thoughts on this?
bgregoir commentedon Oct 28, 2022
My impression, is that the problem will be only for the subtype theory.
I think, we should provide a simple patch such that we can do a local clone of subtype without
problem.
Then, we should work on how to have a proper definition of subtype in EC (without need of that theory).
chdoc commentedon Oct 28, 2022
At the very least, if we tag some of the axioms in
subTypeto not show up inproof*, we also need a way to tag the operatorsvalandinsubas uninstantiable. Otherwise, people can (accidentally) introduce (almost) impossible to detect inconsistencies.chdoc commentedon May 2, 2023
@strub @fdupress @bgregoir This has been dormant for a while. If I recall correctly, tagging ops in a theory as uninstantiable was something that was asked for in Porto for some unrelated reason. If we ensure that
valandinsubare kept abstract, then suppressing the axioms should be fine.Incidentally, I think that the current way to handle non-emptiness is suboptimal. This should actually always be proved by the user. But without knowing what the
witnessof thesTis it's hard to define its preimage as an op (without using choice).dominique-unruh commentedon May 14, 2023
@chdoc
I wrote a replacement for Subtype that alleviates the problem by using several tricks:
valandinsubare not unspecified operators, but defined (via choiceb as "some suitable val and insub"). This makes sure that they cannot be overwritten.Pis inhabited.sTis also defined, and hence cannot be overwritten. It is defined as a thin wrapper around a type calleddo_not_use_this_type_or_you_get_unsoundness_admit. While it is technically possible to clone this subtype theory unsoundly (by specifyingtype do_not_use_this_type_or_you_get_unsoundness_admit = ...during clone), the name makes it unlikely that people do so.do_not_use_this_type_or_you_get_unsoundness_admitandPis axiomatized, but usinglemma ... admit. qed.instead ofaxiom .... This ensures thatclone ... proof *does not require us to prove the existence of this bijection.inhabitedsaying thatPis inhabited. It is not actually used but it ensures that one cannot accidentally instantiate an empty Subtype.With these changes, one can create subtypes without getting unprovable proof obligations. (The existing mechanism makes it impossible to soundly instantiate many theories that internally use
Subtype. E.g.,clone ZModP.ZModRing ... proof *requires us to prove the unprovableSubtypeaxioms, but withoutproof *, we might not show the importantp >= 2axiom. This is proof of false waiting to happen...) At the same time, everything is sound as long as one follows the rule always to have aproof *when cloning in a non-abstract theory (imho, EasyCrypt should enforce that, or at least make it a strong default), and does not refer todo_not_use_this_type_or_you_get_unsoundness_admitdirectly while cloning.With my
Subtypereplacement (SafeSubtype.eca.txt), one can declare subtypes as follows:The theory is designed to be a drop-in replacement for the existing
Subtype. It exports the sameops,types, andlemmas.Main disadvantage: The theory contains an admit. But I think if it's in the stdlib (instead of the existing Subtype), and the admit get a clear comment that it is ok because of the axioms
inhabited, then that should be OK. (At least till a builtin subtype command comes along.)I strongly vote for including it (or something similar) so that we can finally have the rule that all axioms should always be proven. (See also https://github.com/EasyCrypt/easycrypt/issues/331#issuecomment-1411733326)
strub commentedon May 14, 2023
Hi @dominique-unruh. Could you create a PR so that we see what breaks in the standard library?
fdupress commentedon May 14, 2023
One very minor thing to keep in mind (not to stop this change, but to enable it with minimal loss elsewhere) is that defining the injection and projection in all subtypes will likely cause issues like those that arose from doing the same in a specific one (
'a distr) last year: the SMT lemma selection is going to suddenly pull in a whole lot more theory that was previously hidden by abstraction.It might make sense, for now, to make sure that all subtype instantiations in the stdlib are marked as much as possible with
nosmt. We can return to working on switching the default independently.dominique-unruh commentedon May 14, 2023
@strub I'm trying to make the PR (and see where the stdlib breaks) but I run into a mystery and am not sure whether it's intended or a bug.
fails but
succeeds. In general, it seems that
preds can never be part ofops. Is that intentional?From looking at the reference manual, I don't see any difference between ops and preds (except that the type annotations are written a bit differently).
It's a problem because it means in my Subtype,
Phas to be anop. But if it's anop, then it will need to be instantiated withops. Butinductive ispolyinPoly.ecis apred, and I don't see how to make it anopbecauseinductiveseems to producepreds.dominique-unruh commentedon May 14, 2023
@fdupress
How does one do that? I only know how to do it to lemmas, but not to theories as a whole. Ideally, we would like to add
nosmtto the definitions ofvalandinsubbut I don't know if that's possible.1 remaining item
fdupress commentedon May 14, 2023
Yes-ish: you can't add a
nosmtannotation when cloning, so the way you'd need to do it is to first define youroptagged asnosmt, then use it in cloning. Perhaps don't do it and let's see if anything blows up because of the size of SMT contexts.As for the
predvsopissue, this will count as "something that breaks in the stdlib" and that we need to think hard about sorting out.Easy and dirty fix is to make
inductivedefine anopinstead (after thinking about how that impacts a whole bunch of things), but doing this more systematically might also fit current code simplification efforts.alleystoughton commentedon May 14, 2023
I remember P-Y explaining to me why getting rid of preds entirely would require some major refactoring, but I can't remember (and it must have been on slack).
dominique-unruh commentedon May 14, 2023
@strub I made a pull request. Minor fixes were needed, see my comment in the PR.
dominique-unruh commentedon May 14, 2023
I got around this (it turns out in Poly.ec, the
inductivepredicate didn't really need to be an inductive one, since it used theinductivepredicate in a degenerate case with only one case and no recursion). Stdlib and examples now work.strub commentedon May 14, 2023
This is because we have this (now artificial since expressions can contain non-executable constructions) distinction between expressions & formulas.
Now, last time I spoke about this with Benjamin, we realized that operators body could contain formula without having to do a heavy refactoring (having formulas in the RHS of the assignment instruction would be a totally different story). This is something that could be done once Cameron is done with the refactoring of substitutions.
strub commentedon May 14, 2023
I think that this should be part of the reflexion around the new behavior of the
smt/nosmtannotations.strub commentedon Jul 17, 2024
Reopening the issue. The current subtype implementation is a nightmare w.r.t. pretty-printing: all subtypes are named
sTand it is hard to understand. I propose to implement Christian ideas.oskgo commentedon Jan 9, 2025
@strub You can still rename
sTwhen cloning. The ergonomics of renaming and instantiating with another abstract type are about the same IMO.I'm not against uninstantiable types/operators/axioms, but I don't think it helps with pretty printing of subtypes.
I do think it would be nice to make subtypes more solid. There are ways to prove false without instantiating
do_not_instantiate_this_typedirectly, though all ways I could find either involve mangling its name through renaming or at least writing out the name of the type in the source somewhere. There's also the risk that future features make it possible to either create an alias fordo_not_instantiate_this_typewithout explicitly mentioning it or allow getting rid of references toPfrom a clonedSubtypetheory without mentioningdo_not_instantiate_this_type. You can already get rid of lemmas usingclear [Thy.*]and thePoperator during instantiation, but I can't find a way to get rid of the other operators without mentioningdo_not_instantiate_this_typeyet.oskgo commentedon Jan 21, 2025
Turns out subtypes are still unsound because
sT(anddo_not_instantiate_this_type) do not directly referenceT. This causes problems when making the subtype parametric using sections anddeclare type. ThesTends up not being parametric, while the lemmas stay parametric from which it is easy to derive a contradiction by using parameters that end up with subtypes that should have different properties.I've weaponized it by using the trivial subtype and the fact that the unit type only has one member, while the integers have distinct members:
fdupress commentedon Jan 21, 2025
It seems to me that the issue here is that the
clone includeleaks out of the section. Unlikely to be fixed by #691 unlesssubtypeis forbidden from interacting with the section mechanism in this way.strub commentedon Jan 21, 2025
Some remarks:
falseunder an inconsistent axiom. I still agree that there is a usability issue that we should work on. But here too, this is unrelated to revert subtype theory + syntactic sugar for cloning it #691. It is anyway very easy to introduce inconsistencies with section. See below for an example in Coq. (This is an example coming from a real project)IMO, having a primitive subtype construction is the way to go.
oskgo commentedon Jan 21, 2025
I don't know if this is the case for your Coq example, but at least in EasyCrypt with the current subtype theory you end up with no remaining discoverable axioms in the resulting theory.
My litmus test for "do I have a full proof" is whether cloning the theory (meaning the entire file) with
proof *shows any axioms, and in this case it does not. Doesn't that correspond to having the result in a closed environment?I'm not sure if it's fair to say that the fault is with the interactions between
clone includeand sections alone. I don't think I'd be able to do something similar without theSubtypetheory, which currently has the special permission of being allowed to useadmittedinsubtype_injection.The issue here is that while cloning means that you get a unique
sTfor every operator since a new operator requires a new clone, it does not mean that you get a uniquesTfor every type parameter'a.I think that with the old theory, making the following modification fills in the hole while keeping it possible to make parametric subtypes;
Also, all other occurrences of
do_not_instantiate_this_typeshould be replaced withT do_not_instantiate_this_type.I don't know how that translates to the new mechanism.
oskgo commentedon Jan 31, 2025
My proposed fix doesn't entirely work either. It's still possible to inject a type parameter into
Pwithout injecting it intoT;Seems like a built in mechanism really is the only way to go forward without some kind of dependent types.