Skip to content

Subtype axioms #275

Open
Open

Description

@chdoc

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.

Activity

  1. strub commented on Oct 12, 2022

    @strub
    Member

    You might be interested by this:

    theory T.
    axiom [trusted] A : false.
    end T.
    
    clone T as U
      proof *[-trusted].
    
  2. ghost
    self-assigned this
    on Oct 12, 2022
  3. Repository owner unassigned on Oct 12, 2022
  4. ghost
    self-assigned this
    on Oct 12, 2022
  5. ghost added this to the Release 2022.07 milestone on Oct 12, 2022
  6. chdoc commented on Oct 21, 2022

    @chdoc
    ContributorAuthor

    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?

  7. bgregoir commented on Oct 28, 2022

    @bgregoir
    Contributor

    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).

  8. chdoc commented on Oct 28, 2022

    @chdoc
    ContributorAuthor

    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.

  9. chdoc commented on May 2, 2023

    @chdoc
    ContributorAuthor

    @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).

  10. dominique-unruh commented on May 14, 2023

    @dominique-unruh
    Contributor

    @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.)

    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)

  11. strub commented on May 14, 2023

    @strub
    Member

    Hi @dominique-unruh. Could you create a PR so that we see what breaks in the standard library?

  12. fdupress commented on May 14, 2023

    @fdupress
    Member

    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.

  13. dominique-unruh commented on May 14, 2023

    @dominique-unruh
    Contributor

    @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.

  14. dominique-unruh commented on May 14, 2023

    @dominique-unruh
    Contributor

    @fdupress

    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.

  15. 1 remaining item

  16. fdupress commented on May 14, 2023

    @fdupress
    Member

    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.

  17. alleystoughton commented on May 14, 2023

    @alleystoughton
    Member

    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).

  18. dominique-unruh commented on May 14, 2023

    @dominique-unruh
    Contributor

    @strub I made a pull request. Minor fixes were needed, see my comment in the PR.

  19. dominique-unruh commented on May 14, 2023

    @dominique-unruh
    Contributor

    @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.

  20. strub commented on May 14, 2023

    @strub
    Member

    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.

  21. strub commented on May 14, 2023

    @strub
    Member

    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.

  22. ghost closed this as completedin #377on May 17, 2023
  23. ghost reopened this on Jul 17, 2024
  24. strub commented on Jul 17, 2024

    @strub
    Member

    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.

  25. oskgo commented on Jan 9, 2025

    @oskgo
    Contributor

    @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.

  26. oskgo commented on Jan 21, 2025

    @oskgo
    Contributor

    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.
    
  27. fdupress commented on Jan 21, 2025

    @fdupress
    Member

    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.

  28. strub commented on Jan 21, 2025

    @strub
    Member

    Some remarks:

    • Your example works regardless of the subtype mechanism and is unrelated to revert subtype theory + syntactic sugar for cloning it #691
    • 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 Require Import 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.
  29. oskgo commented on Jan 21, 2025

    @oskgo
    Contributor

    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.

  30. oskgo commented on Jan 31, 2025

    @oskgo
    Contributor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions