-
Notifications
You must be signed in to change notification settings - Fork 364
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Proposal: new flag --cubical-compatible
replacing --without-K
#5843
Comments
It may be sound to have both the cubical operators (but not Glue) and K, though I don't know the details, see A Cubical Language for Bishop Sets. |
See #3750. |
I think we should think very carefully and perhaps do a poll before making a change to the default behaviour of Agda such as making |
I don't think we should change the default, that might break a lot of code for little benefit. |
In what sense is {-# OPTIONS --without-K #-}
open import Agda.Builtin.Bool using (Bool; true; false)
open import Agda.Builtin.Equality using (_≡_; refl)
open import Agda.Builtin.IO using (IO)
open import Agda.Builtin.Sigma using (Σ; _,_; fst)
open import Agda.Builtin.Unit using (⊤)
open import Agda.Primitive using (Level; _⊔_)
private
variable
a b : Level
A B : Set a
eq p x y z : A
P : A → Set p
------------------------------------------------------------------------
-- Some lemmas related to equality
-- Standard lemmas.
trans : x ≡ y → y ≡ z → x ≡ z
trans refl refl = refl
cong : (f : A → B) → x ≡ y → f x ≡ f y
cong _ refl = refl
-- This variant of subst is accepted by Agda 2.6.2, but not by the
-- current development version.
subst : (@0 P : A → Set p) → x ≡ y → P x → P y
subst _ refl p = p
------------------------------------------------------------------------
-- Erased
-- The type constructor Erased.
record Erased (@0 A : Set a) : Set a where
constructor [_]
field
@0 erased : A
-- Some standard properties of modalities. These two lemmas can be
-- proved if we assume function extensionality. They can also be
-- proved if we turn on --with-K.
postulate
[]-cong : Erased (x ≡ y) → [ x ] ≡ [ y ]
[]-cong-refl : []-cong [ refl {x = x} ] ≡ refl {x = [ x ]}
------------------------------------------------------------------------
-- Univalence
-- Equivalences.
_≃_ : Set a → Set b → Set (a ⊔ b)
A ≃ B =
Σ (A → B) λ f →
Σ (B → A) λ f⁻¹ →
Σ (∀ x → f (f⁻¹ x) ≡ x) λ f-f⁻¹ →
Σ (∀ x → f⁻¹ (f x) ≡ x) λ f⁻¹-f →
∀ x → cong f (f⁻¹-f x) ≡ f-f⁻¹ (f x)
-- Erased univalence.
postulate
@0 univ : A ≃ B → A ≡ B
@0 subst-id-univ : subst (λ A → A) (univ eq) x ≡ eq .fst x
-- Some definitions combining subst and univ.
subst-univ : (@0 P : Set a → Set p) → @0 A ≃ B → P A → P B
subst-univ P eq p = subst (λ ([ x ]) → P x) ([]-cong [ univ eq ]) p
@0 subst-univ-subst :
{eq : A ≃ B} →
subst-univ P eq p ≡ subst P (univ eq) p
subst-univ-subst {B = B} {eq = eq}
rewrite univ eq | []-cong-refl {x = B} = refl
@0 subst-univ-id : subst-univ (λ A → A) eq x ≡ eq .fst x
subst-univ-id = trans subst-univ-subst subst-id-univ
------------------------------------------------------------------------
-- A concrete example of something "bad"
-- The not function.
not : Bool → Bool
not true = false
not false = true
-- An equivalence defined using not.
--
-- The proof is omitted in order to save space.
@0 swap : Bool ≃ Bool
swap = not , omitted
where
postulate
omitted : _
-- A boolean that should be false.
should-be-false : Bool
should-be-false = subst-univ (λ A → A) swap true
-- We can prove that should-be-false is false.
@0 is-false : should-be-false ≡ false
is-false = subst-univ-id
-- However, if we run the following code, then "True" is printed.
postulate
print : Bool → IO ⊤
{-# COMPILE GHC print = print #-}
main : IO ⊤
main = print should-be-false I don't think the code above should be accepted, and if Agda 2.6.3-0a9a5dd is used, then we get the following error message:
The code is accepted by Agda 2.6.2. You might argue that the code uses some postulates related to |
Revised proposal:
Rationale: |
As an aside the following code that does not make use of {-# OPTIONS --without-K #-}
open import Agda.Builtin.Bool using (Bool; true; false)
open import Agda.Builtin.Equality using (_≡_; refl)
open import Agda.Builtin.IO using (IO)
open import Agda.Builtin.Sigma using (Σ; _,_; fst)
open import Agda.Builtin.Unit using (⊤)
open import Agda.Primitive using (Level; _⊔_)
private
variable
a b p : Level
A B : Set a
eq x y : A
------------------------------------------------------------------------
-- Some lemmas related to equality
-- Standard lemmas.
cong : (f : A → B) → x ≡ y → f x ≡ f y
cong _ refl = refl
subst : (P : A → Set p) → x ≡ y → P x → P y
subst _ refl p = p
------------------------------------------------------------------------
-- Univalence
-- Equivalences.
_≃_ : Set a → Set b → Set (a ⊔ b)
A ≃ B =
Σ (A → B) λ f →
Σ (B → A) λ f⁻¹ →
Σ (∀ x → f (f⁻¹ x) ≡ x) λ f-f⁻¹ →
Σ (∀ x → f⁻¹ (f x) ≡ x) λ f⁻¹-f →
∀ x → cong f (f⁻¹-f x) ≡ f-f⁻¹ (f x)
-- Univalence.
postulate
univ : A ≃ B → A ≡ B
subst-id-univ : subst (λ A → A) (univ eq) x ≡ eq .fst x
------------------------------------------------------------------------
-- A concrete example of something "bad"
-- The not function.
not : Bool → Bool
not true = false
not false = true
-- An equivalence defined using not.
--
-- The proof is omitted in order to save space.
swap : Bool ≃ Bool
swap = not , omitted
where
postulate
omitted : _
-- A boolean that should be false.
should-be-false : Bool
should-be-false = subst (λ A → A) (univ swap) true
-- We can prove that should-be-false is false.
is-false : should-be-false ≡ false
is-false = subst-id-univ
-- However, if we run the following code, then "True" is printed.
postulate
print : Bool → IO ⊤
{-# COMPILE GHC print = print #-}
main : IO ⊤
main = print should-be-false I don't think this is a problem: The GHC backend erases equality proofs for |
I don't know exactly what this means, but I guess there should be no change: one can currently import code that uses |
The only change (PR: #5862) is adding the flag |
I'd like to note that I find the name a little strange, given that code that uses |
Code using |
I import modules that use |
What's your point? Do you think it should be explicit in the name of the option that it doesn't break compatibility with |
--cubical-compatible
; make --without-K
default--cubical-compatible
replacing --without-K
If we have to include something like |
Maybe Imo, we haven't gained much really by renaming the option and may just create churn for the customers. In the end, it is down to RTFM in any case... |
OK. So I am not using cubical and I still need --without-K for formalizing univalent mathematics. Will I be forced to write the misleading |
Yeah, this is a problem. For the moment,
Actually, 2. and 3. are also strictly more than "without K", but maybe this could be tolerated. |
Doesn't I don't really understand (2), by the way. |
Maybe a good entry point for digging: |
Perhaps a better name would be |
As noted above this does not suffice to ensure compatibility with univalence. |
I am still not happy with renaming |
People were doing HoTT/UF in Lean and then this became impossible in the new versions of Lean. I really hope this doesn't happen with Agda as well. |
@martinescardo : A new proposal is at #6049 (comment). |
Marking this |
Agda dev discussion on 2022-03-23 (@UlfNorell @nad @MatthewDaggitt @jespercockx).
Problem we address:
--without-K
.New semantics:
--cubical-compatible
is the current--without-K
: implies the new--without-K
, triggers code that prepares stuff for--cubical
(hcomps etc.)--without-K
just ensures compatibility with univalence?
--without-K
will be on by defaultCode that breaks because
--without-K
is now silently on should give informative error to user with a suggestions to maybe turn on--with-K
. This affects:--with-K
and report this to the userK
, suggest to user--with-K
(do we have this already?)--without-K
is supplied as option where it does have no effect (i.e., unless--with-K
is globally on), alert the user of the new flag--cubical-compatible
(because they might have wanted this instead).Also, when a
--cubical
or--cubical-compatible
module imports a module that is not--cubical-compatible
, should this be an error? We could also lazily throw errors when hcomps etc. are missing, but then we need to point back to the module which fails to define them due to lack of--cubical-compatible
(s/le/ility/).The text was updated successfully, but these errors were encountered: