Skip to content
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

Recursor of inductive-inductive type does not pass termination check in Cubical Agda #5953

Closed
szumixie opened this issue Jun 11, 2022 · 7 comments · Fixed by #5958
Closed
Assignees
Labels
cubical Cubical Agda paraphernalia: Paths, Glue, partial elements, hcomp, transp dot patterns "Forced" (.x) patterns, wirtten by the user or generated by case splitting regression in 2.6.2 Regression that first appeared in Agda 2.6.2 termination Issues relating to the termination checker
Milestone

Comments

@szumixie
Copy link
Contributor

The following code typechecks without the --cubical flag, but does not pass the termination checker with the flag:

{-# OPTIONS --cubical #-}

data Con : Set
data Ty : Con  Set

data Con where
  nil : Con
  ext :: Con)  Ty Γ  Con

data Ty where
  univ :: Con)  Ty Γ
  pi :: Con) (A : Ty Γ)  Ty (ext Γ A)  Ty Γ

module _
  (A : Set)
  (B : A  Set)
  (n : A)
  (e : (a : A)  B a  A)
  (u : (a : A)  B a)
  (p : (a : A) (b : B a)  B (e a b)  B a)
  where
  recCon : Con  A
  recTy :: Con)  Ty Γ  B (recCon Γ)

  recCon nil = n
  recCon (ext Γ A) = e (recCon Γ) (recTy Γ A)

  recTy Γ (univ Γ) = u (recCon Γ)
  recTy Γ (pi Γ A B) = p (recCon Γ) (recTy Γ A) (recTy (ext Γ A) B)
@andreasabel andreasabel added termination Issues relating to the termination checker cubical Cubical Agda paraphernalia: Paths, Glue, partial elements, hcomp, transp regression in 2.6.2 Regression that first appeared in Agda 2.6.2 labels Jun 14, 2022
@andreasabel
Copy link
Member

If you switch from --cubical to --without-K, the definition is accepted, because then dot patterns are taken into consideration for termination certification.

andreasabel added a commit that referenced this issue Jun 14, 2022
…erns

With #4606, --cubical no longer considered dotted patterns as patterns
for termination certification.  This patch considers dotted variables
and dotted record patterns as benign and considers then as pattern
always in the termination checker, even in the first phase (no
dot-patterns) which is the only phase with --cubical.  (The other
modes have the dot-pattern termination phase as well.)
@andreasabel andreasabel added the dot patterns "Forced" (.x) patterns, wirtten by the user or generated by case splitting label Jun 14, 2022
@andreasabel andreasabel self-assigned this Jun 14, 2022
@andreasabel andreasabel added this to the 2.6.3 milestone Jun 14, 2022
andreasabel added a commit that referenced this issue Jun 14, 2022
…erns

With #4606, --cubical no longer considered dotted patterns as patterns
for termination certification.  This patch considers dotted variables
and dotted record patterns as benign and considers then as pattern
always in the termination checker, even in the first phase (no
dot-patterns) which is the only phase with --cubical.  (The other
modes have the dot-pattern termination phase as well.)
andreasabel added a commit that referenced this issue Jun 15, 2022
…erns

With #4606, --cubical no longer considered dotted patterns as patterns
for termination certification.  This patch considers dotted variables
and dotted record patterns as benign and considers then as pattern
always in the termination checker, even in the first phase (no
dot-patterns) which is the only phase with --cubical.  (The other
modes have the dot-pattern termination phase as well.)
@nad
Copy link
Contributor

nad commented Jun 15, 2022

If the program should be rejected when --cubical is used, then it should also be rejected when --without-K is used, right?

@andreasabel
Copy link
Member

andreasabel commented Jun 15, 2022

Turning off dot-pattern termination for --without-K would mean that we could not do the usual proof by pattern matching that the successor relation is well-founded:

{-# OPTIONS --without-K #-}

open import Agda.Builtin.Nat using (Nat; zero; suc)

data Acc {A : Set} (R : A  A  Set) (x : A) : Set where
  acc : ( y  R y x  Acc R y)  Acc R x

data _<_ (x : Nat) : Nat  Set where
  <S : x < suc x

iswf< :  x  Acc _<_ x
iswf< x = acc (h x)
  where
  h :  x y  y < x  Acc _<_ y
  h .(suc y) y <S = acc (h y)

@andreasabel
Copy link
Member

If the program should be rejected when --cubical is used, then it should also be rejected when --without-K is used, right?

After the fix, it is accepted in both modes. But see my previous comment for a violation of your principle. Likely, the termination checker rejects too many programs under --cubical, just to be on the safe side. But with termination checking being undecidable, we accept that it is incomplete, and may also violate your principle. (If you want your principle, we could e.g. have a check that --cubical is actually necessary, i.e. cubical features are positively used, because in this case, the type checker would already not succeed with just --without-K.)

andreasabel added a commit that referenced this issue Jun 15, 2022
…erns

With #4606, --cubical no longer considered dotted patterns as patterns
for termination certification.  This patch considers dotted variables
and dotted record patterns as benign and considers then as pattern
always in the termination checker, even in the first phase (no
dot-patterns) which is the only phase with --cubical.  (The other
modes have the dot-pattern termination phase as well.)
@nad
Copy link
Contributor

nad commented Jun 15, 2022

"My principle" is that code that is accepted when --without-K is used should be accepted also when --with-K, --erased-cubical or --cubical is used. Every extra check that is performed in Cubical Agda should also be performed when --without-K is used.

Turning off dot-pattern termination for --without-K would mean that we could not do the usual proof by pattern matching that the successor relation is well-founded:

The code is accepted (with --erased-cubical) if the dot is moved:

iswf< :  x  Acc _<_ x
iswf< x = acc (h x)
  where
  h :  x y  y < x  Acc _<_ y
  h (suc y) .y <S = acc (h y)

However, Agda emits a warning:

Could not generate equivalence when splitting on indexed family,
the function will not compute on transports by a path.
  Reason: UnsupportedYet Injectivity
                           position:    0
                           type:        Nat
                           datatype:    Nat
                           parameters: 
                           indices:    
                           constructor: suc
when checking the definition of h

@nad
Copy link
Contributor

nad commented Jun 16, 2022

"My principle" is that code that is accepted when --without-K is used should be accepted also when --with-K, --erased-cubical or --cubical is used. Every extra check that is performed in Cubical Agda should also be performed when --without-K is used.

I realised that my statement is too strong. One could make Cubical Agda checks unnecessarily strict without the risk of breaking anything, and that may be the case for the check under discussion. @Saizan wrote the following:

-- Andrea: 22/04/2020.
-- With cubical we will always have a clause where the dot
-- patterns are instead replaced with a variable, so they
-- cannot be relied on for termination.
-- See issue #4606 for a counterexample involving HITs.
--
-- Without the presence of HITs I conjecture that dot patterns
-- could be turned into actual splits, because no-confusion
-- would make the other cases impossible, so I do not disable
-- this for --without-K entirely.

I'm not sure exactly how to interpret this. Would it make sense to include dot patterns when checking termination for a Cubical Agda definition that does not involve matching for HITs?

@andreasabel
Copy link
Member

Would it make sense to include dot patterns when checking termination for a Cubical Agda definition that does not involve matching for HITs?

I suppose so.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cubical Cubical Agda paraphernalia: Paths, Glue, partial elements, hcomp, transp dot patterns "Forced" (.x) patterns, wirtten by the user or generated by case splitting regression in 2.6.2 Regression that first appeared in Agda 2.6.2 termination Issues relating to the termination checker
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants