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

Cubical Agda: Program rejected by termination checker due to moved dot pattern #4725

Closed
nad opened this issue Jun 4, 2020 · 7 comments · Fixed by #5958
Closed

Cubical Agda: Program rejected by termination checker due to moved dot pattern #4725

nad opened this issue Jun 4, 2020 · 7 comments · Fixed by #5958
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

@nad
Copy link
Contributor

nad commented Jun 4, 2020

This code is not accepted:

{-# OPTIONS --cubical #-}

open import Agda.Builtin.Sigma

mutual

  data D : Set where
    d : S  D

  S : Set
  S = Σ D λ x  R x

  fst′ : S  D
  fst′ s = fst s

  data R : D  Set where
    r :  x  R (fst′ x)  R (d x)

module _
  (P : D  Set)
  (Q :  x  P x  R x  Set)
  (p :  s (p : P (fst s))  Q (fst s) p (snd s)  P (d s))
  (q :  s rs (ps : P (fst s)) (qs : Q (fst s) ps (snd s)) 
       Q (fst s) ps rs  Q (d s) (p s ps qs) (r s rs))
  where

  mutual

    f : (x : D)  P x
    f (d (x , r₁)) = p (x , r₁) (f x) (g x r₁)

    g : (x : D) (x⊑y : R x)  Q x (f x) x⊑y
    g (d (x , r₁)) (r .(x , r₁) r₂) =
      q (x , r₁) r₂ (f x) (g x r₁) (g _ r₂)

Agda seems to move the dot pattern from the r constructor to the d constructor, and because the underscore on the last line is inferred to be fst′ (x , r₁) rather than x the code is rejected (after @Saizan's fix of #4606).

Can we do better?

  • Moving the dot patterns in this way could be confusing to the programmer. If an explicit dot pattern is moved, then it makes sense to emit a warning.
  • If the dot pattern was not moved, then the code would presumably be accepted. Do we have to move it?
@nad nad added termination Issues relating to the termination checker dot patterns "Forced" (.x) patterns, wirtten by the user or generated by case splitting cubical Cubical Agda paraphernalia: Paths, Glue, partial elements, hcomp, transp labels Jun 4, 2020
@nad nad added this to the 2.6.2 milestone Jun 4, 2020
@jespercockx
Copy link
Member

jespercockx commented Jun 4, 2020

Moving the dot patterns in this way could be confusing to the programmer. If an explicit dot pattern is moved, then it makes sense to emit a warning.

The dot patterns are not actually moved, instead Agda tries to reconstruct the LHS from scratch using iterated case splitting. If after this case splitting there is still some discrepancy, these are registered in the origin of the internal patterns by the code in https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Rules/LHS.hs#L443-L462. One could conceivably emit a warning here if the patOrig p returns something other than PatODot in the case of a DotP.

If the dot pattern was not moved, then the code would presumably be accepted. Do we have to move it?

The dots are computed by the pattern unifier. It already has a system for priorities that it uses to decide which variable to instantiate: https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Rules/LHS/Problem.hs#L113-L123. So it already prefers to instantiate variables that correspond to a dot pattern written by the user. I'll investigate further why that mechanism doesn't kick in in your test case.

@jespercockx
Copy link
Member

Ah, I understand what's the problem now. When Agda does the case split on the constructor r, it has not yet performed the case split on the pair in the argument of d, so the argument of d is still just a variable. Since the unifier sees a variable being compared to a non-variable, the priorities are not taken into account and the variable is just solved. We could instead try to eta-expand the variable when comparing it to an expression of record type, but this could potentially cause unwanted eta-expansion (something that caused performance problems in the past).

@nad
Copy link
Contributor Author

nad commented Jun 4, 2020

I encountered this problem (but without any explicit dot patterns) in my code, and once I had understood its cause it was easy to fix it. However, the output of -vterm:20 is not very easy to read, and it is not easy to discover this option.

@fredrikNordvallForsberg
Copy link
Member

I think I am running into the same kind of problem, but with perhaps a simpler example, and I don't see any eta getting in the way here. Reporting partly in the hope that this will shed new light, and partly hoping to be told about a workaround.

{-# OPTIONS --cubical #-}

mutual
  data Ord : Set
  data _≤_ : Ord -> Ord -> Set

  data Ord where
    succ  : Ord -> Ord
    limit : (x y : Ord) -> (x<y : succ x ≤ y)  Ord

  data _≤_ where
    ≤-limiting  :  x y x<y z -> (limit x y x<y) ≤ z

≤-ind : (P : {x y : Ord}  x ≤ y  Set) 
        ( x y x<y z  P x<y  P (≤-limiting x y x<y z)) 
        (x y : Ord)  (x≤y : x ≤ y)  P x≤y
≤-ind P l .(limit x y x<y) .z (≤-limiting x y x<y z) = l x y x<y z (≤-ind P l (succ x) y x<y)

This gives the error

Termination checking failed for the following functions:
  ≤-ind
Problematic calls:
  ≤-ind P l (succ x) y x<y

because the dot pattern has been "moved" from limit x y x<y to x<y in ≤-limiting, hence x<y is not seen as structurally smaller when dot patterns are not taken into account under --cubical.

@jespercockx
Copy link
Member

It seems that the dots are moved because of forced constructor arguments. A workaround is to enable the flag --no-forcing. Perhaps this should be turned on by default for --cubical? (since we're currently not compiling cubical, turning off forcing doesn't actually hurt.)

@UlfNorell
Copy link
Member

Note that --no-forcing doesn't make a difference for the OP.

@jespercockx
Copy link
Member

Perhaps this could be fixed by relaxing @Saizan 's fix of #4606 to still allow the termination checker to look into dot patterns if they are variables or record constructors.

@UlfNorell UlfNorell modified the milestones: 2.6.2, 2.6.3 Feb 17, 2021
jespercockx added a commit to jespercockx/agda that referenced this issue Feb 17, 2021
…bles and record constructors even with --cubical
@andreasabel andreasabel added the regression in 2.6.2 Regression that first appeared in Agda 2.6.2 label Jun 14, 2022
@andreasabel andreasabel self-assigned this 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 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.)
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.)
@andreasabel andreasabel changed the title Program rejected due to moved dot pattern Cubical Agda: Program rejected by termination checker due to moved dot pattern Oct 25, 2022
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.

5 participants