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

Agda 2.6.4 RC2 type checking error #6856

Closed
martinescardo opened this issue Sep 15, 2023 · 7 comments · Fixed by #6886
Closed

Agda 2.6.4 RC2 type checking error #6856

martinescardo opened this issue Sep 15, 2023 · 7 comments · Fixed by #6886
Assignees
Labels
constraints Constraints (postponed type checking problems, postponed unification problems, instance constraints) regression on master Unreleased regression in development version (Change to "regression in ..." should it be released!)
Milestone

Comments

@martinescardo
Copy link

martinescardo commented Sep 15, 2023

The following type checks in Agda 2.6.3.

data _=_ {X : Set} : X  X  Set where
 refl : {x : X}  x = x

record Σ {X : Set} (Y : X  Set) : Set  where
 constructor
  _,_
 field
  pr₁ : X
  pr₂ : Y pr₁

_×_ : Set  Set  Set
X × Y = Σ λ (_ : X)  Y

id : {X : Set}  X  X
id x = x

_∘_ : {X : Set} {Y : Set} {Z : Y  Set}
     ((y : Y)  Z y)
     (f : X  Y) (x : X)  Z (f x)
g ∘ f = λ x  g (f x)

_∼_ : {X : Set} {A : X  Set}  ((x : X)  A x)  ((x : X)  A x)  Set
f ∼ g =  x  f x = g x

_≅_ : Set  Set  Set
X ≅ Y = Σ λ (f : X  Y)  Σ λ (g : Y  X)  (g ∘ f ∼ id) × (f ∘ g ∼ id)


module _ (X Y : Set)
         (A : X  Set)
         (B : Y  Set)
       where

 fact :λ (x : X)  Σ λ (y : Y)  A x × B y)
      ≅ ((Σ λ (x : X)  A x) × (Σ λ (y : Y)  B y))
 fact = f , g , gf , fg
  where
   f : _
   f (x , y , a , b) = ((x , a) , (y , b))
   g : _
   g ((x , a) , (y , b)) = x , y , a , b
   fg : f ∘ g ∼ id
   fg _ = refl
   gf : g ∘ f ∼ id
   gf _ = refl

infixr 50 _,_
infixl 5 _∘_
infix  4 _∼_
infixr 2 _×_

In Agda 2.6.4 RC2 it gives the following error:

f (g x) != x of type Σ (λ _ → Σ (λ y → B y))
when checking that the expression id has type
(x : Σ (λ x₁ → A x₁) × Σ (λ y → B y)) →
Σ (λ x₁ → A x₁) × Σ (λ y → B y)

If you make the refls into holes, the definition type checks with no unsolved constraints.

If you replace the last four lines by

   fg : f ∘ g ∼ id
   fg ((x , a) , (y , b)) = ?
   gf : g ∘ f ∼ id
   gf (x , y , a , b) = ?

then this again type checks, and you can fill the holes with refl. But then this doesn't type check after ctrl-c-ctrl-l.

In practice, this occurs in line 121 of TypeTopology/source/Circle/Integers-SymmetricInduction.lagda. The above is an abridged version.

@martinescardo
Copy link
Author

This modification type checks in Agda 2.6.4 RC2.

 S = Σ λ (x : X) → Σ λ (y : Y) → A x × B y
 T = (Σ λ (x : X) → A x) × (Σ λ (y : Y) → B y)

 fact : S ≅ T
 fact = f , g , gf , fg
  where
   f : S → T
   f (x , y , a , b) = ((x , a) , (y , b))
   g : _
   g ((x , a) , (y , b)) = x , y , a , b
   fg : f ∘ g ∼ id
   fg _ = refl
   gf : g ∘ f ∼ id
   gf _ = refl

So it seems to be a type inference problem. But instead of giving unsolved constraints it is giving an error as discussed in the previous comment (and Agda 2.6.3 can solve the constraints and doesn't give an error).

@martinescardo
Copy link
Author

I "fixed" TypeTopology so that it now type checks with Agda 2.6.4 RC2. However, the above example shows that Agda 2.6.4 type-checks / type-infers fewer Agda files than 2.6.3.

@andreasabel andreasabel added the status: bisecting A git bisect has been started to find the cause of the issue label Sep 24, 2023
@andreasabel andreasabel added this to the 2.6.4 milestone Sep 24, 2023
@andreasabel
Copy link
Member

andreasabel commented Sep 24, 2023

Bisection run v2.6.3 - master reports:

Succeeds at:

  • b86dd2b [ releases notes ] Removed mention to -fprof-auto.
  • dc845d0 Also apply the change to getDefinition and add documentation
  • 32599bc [ Release Agda 2.6.3 #6055, CHANGELOG ] Updated list of closed issues.
  • dd60c64 [ workflows ] add cabal sdist to whitespace.yml CI

Internal error at:

This bisect run only found the point where the result went from "good" to "internal error".

@andreasabel
Copy link
Member

Looks like the OP went from accepted to rejected somewhere invisible due to a cover of "internal error" introduced by 536b73f.
@jespercockx , could you have a look please?

@andreasabel andreasabel added constraints Constraints (postponed type checking problems, postponed unification problems, instance constraints) regression on master Unreleased regression in development version (Change to "regression in ..." should it be released!) and removed status: bisecting A git bisect has been started to find the cause of the issue labels Sep 24, 2023
@andreasabel
Copy link
Member

Turning on -v tc.lhs.top:10 triggers the following impossible:

[ "delta =" <+> do escapeContext impossible (size delta) $ prettyTCM delta

Maybe this points to a violated invariant?

@andreasabel
Copy link
Member

I did a manual bisect now, patching away the __IMPOSSIBLE__ at each step. Result is:
f271f44 is the first bad commit (ping @jespercockx)

Date: Sun Sep 3 19:07:22 2023 +0200
[ fix #6758 ] Instantiate defBlocked in case of blocked definition

@jespercockx jespercockx self-assigned this Sep 27, 2023
@jespercockx
Copy link
Member

Here's my idea of what is going on during the type checking of the where block:

  • First, Agda tries to type check the definitions of f and g, but is blocked by the metas in their type signatures.
  • Then it tries to check the definitions of fg and gf. Checking refl at type f (g x) = x is blocked as well because the definitions of f and g are not yet known. Importantly, Agda blocks this problem on the meta it gets from the defBlocked fields of f and g, which point to the same metas that the definitions of f and g themselves are blocked on.
  • Next, Agda checks the body of fact itself, which succeeds. In the process, it also learns about the types of f and g, instantiating the two metas from their types.
  • This unblocks both the checking of the definitions of f and g, and the checking of both refls. Agda (arbitrarily) decides to check the refl first.
  • Agda again tries to reduce f (g x) to whnf, which still doesn't work (as we still don't have a definition for f and g) but now there is also no longer any meta blocking the problem! Since nothing is blocking the problem, Agda assumes that f (g x) is the final whnf and throws an error because it is not equal to x.

To fix this problem, it seems like we should instead block the checking of the refl until the definitions of f and g have actually been checked and added to the signature. It seems we already have a constructor for this in the Blocker type for this: UnblockOnDef, but we are not using it here which is causing the problem.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
constraints Constraints (postponed type checking problems, postponed unification problems, instance constraints) regression on master Unreleased regression in development version (Change to "regression in ..." should it be released!)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants