Agda Issue: Records With Equal Levels Not Recognized

Hey guys! Today, we're diving deep into a peculiar issue encountered in Agda, a dependently typed programming language. Specifically, we're going to explore a scenario where Agda fails to recognize records as being the same, even when they seemingly have equal levels. This can be quite frustrating, especially when you're dealing with complex type-level computations. So, let's break it down and see what's going on.

The Problematic Scenario

Imagine you're working with records in Agda, and you define a record at a type l ⊔ m, where l and m are levels. Now, in one case (let's call it Case 1), you instantiate l to x ⊔ y and m to x ⊔ y. In another case (Case 2), you instantiate l to x and m to y. Logically, (x ⊔ y) ⊔ (x ⊔ y) should be the same as x ⊔ y, right? Agda should be able to figure this out, but sometimes it just doesn't. This is the core of the issue we're tackling.

Diving Deeper into the Code

To illustrate this, let's look at the code snippet provided. We have two modules, Part1 and Part2:

Part1

open import Agda.Primitive using (Set; Level; _⊔_)
module Part1 (l m : Level) where

record T : Set (l ⊔ m) where

In Part1, we define a record T that lives in the universe Set (l ⊔ m), where l and m are parameters representing levels. This is a pretty standard setup for defining records that are polymorphic over universe levels. Understanding levels is crucial in Agda, as they govern the universe hierarchy and prevent logical inconsistencies.

Part2

open import Agda.Primitive using (Set; Level; _⊔_)
module Part2 (x y : Level) where
  open import Part1 (x ⊔ y) (x ⊔ y) as P1
  open import Part1 x y as P2

  data _≡_ {k} {A : Set k} (a : A) : A -> Set k where
    refl : a ≡ a

  T1 : Set (x ⊔ y)
  T1 = P1.T

  T2 : Set (x ⊔ y)
  T2 = P2.T

  thing : P1.T ≡ P2.T
  thing = refl

In Part2, we import Part1 twice, once with levels (x ⊔ y) (x ⊔ y) (aliased as P1) and another time with levels x y (aliased as P2). We then define T1 as P1.T and T2 as P2.T. Intuitively, T1 and T2 should be the same, since (x ⊔ y) ⊔ (x ⊔ y) should be equivalent to x ⊔ y. We even try to prove this by defining thing : P1.T ≡ P2.T and attempting to use refl (reflexivity) to show that they are equal. However, this is where things go south.

The Error Message

When you try to compile this code, Agda throws a rather cryptic error:

Set y is not less or equal than Set x
when checking that the expression refl has type P1.T ≡ P2.T

This error message is telling us that Agda can't unify the types P1.T and P2.T. Specifically, it's complaining about the levels not being compatible. It seems like Agda isn't able to figure out that Set (x ⊔ y) is the same as Set ((x ⊔ y) ⊔ (x ⊔ y)), which is quite puzzling.

Why Does This Happen?

The root cause of this issue lies in how Agda handles level unification. While Agda has sophisticated mechanisms for type checking and unification, it's not always able to simplify level expressions automatically. In this case, the simplification of (x ⊔ y) ⊔ (x ⊔ y) to x ⊔ y isn't happening under the hood, leading to the type checking failure.

Level Unification in Agda

Agda's level system is designed to ensure that the universe hierarchy is well-founded, preventing paradoxes like Russell's paradox. Levels are organized in a hierarchy, with Set 0 being the smallest universe, Set 1 being the next, and so on. The _⊔_ operator takes two levels and returns their supremum (the smallest level that is greater than or equal to both). While Agda can handle simple level equalities, more complex simplifications sometimes require manual intervention.

The Role of refl

The refl constructor of the _≡_ data type represents reflexivity, meaning that a value is equal to itself. When you use refl, Agda needs to ensure that the types on both sides of the equality are indeed the same. In our case, Agda fails to see that P1.T and P2.T have the same type, even though they should, leading to the error.

How to Fix It? (Workarounds and Solutions)

So, what can we do to work around this issue? There are a few approaches we can take:

1. Explicit Level Equality

One way to help Agda along is to provide explicit evidence that the levels are equal. We can do this by defining a function that proves the equality of the levels and then using that in our proof. Let's modify Part2 to include this:

open import Agda.Primitive using (Set; Level; _⊔_)
open import Agda.Builtin.Equality using (_≡_)
module Part2 (x y : Level) where
  open import Part1 (x ⊔ y) (x ⊔ y) as P1
  open import Part1 x y as P2

  level-equal : (x y : Level) -> (x ⊔ y) ⊔ (x ⊔ y) ≡ (x ⊔ y)
  level-equal x y = refl

  T1 : Set (x ⊔ y)
  T1 = P1.T

  T2 : Set (x ⊔ y)
  T2 = P2.T

  thing : P1.T ≡ P2.T
  thing = refl

Unfortunately, this doesn't directly solve the problem. Agda still struggles to use this equality automatically in the type checking process. We need to find a way to apply this equality to convince Agda that the types are indeed the same.

2. Using rewrite (with Agda.Builtin.Equality)

The rewrite construct in Agda allows us to use an equality proof to rewrite a type. To use rewrite, we need to import Agda.Builtin.Equality. Let's modify our code to use rewrite:

open import Agda.Primitive using (Set; Level; _⊔_)
open import Agda.Builtin.Equality using (_≡_; sym; rewrite)
module Part2 (x y : Level) where
  open import Part1 (x ⊔ y) (x ⊔ y) as P1
  open import Part1 x y as P2

  level-equal : (x y : Level) -> (x ⊔ y) ⊔ (x ⊔ y) ≡ (x ⊔ y)
  level-equal x y = refl

  T1 : Set ((x ⊔ y) ⊔ (x ⊔ y))
  T1 = P1.T

  T2 : Set (x ⊔ y)
  T2 = P2.T

  thing : T1 ≡ T2
  thing rewrite level-equal x y = refl

In this version, we've made a few key changes:

• We've imported Agda.Builtin.Equality and brought _≡_, sym, and rewrite into scope.
• We've explicitly typed T1 as Set ((x ⊔ y) ⊔ (x ⊔ y)) to match the definition in P1.
• We've used rewrite level-equal x y in the definition of thing. This tells Agda to use the level-equal proof to rewrite the type of T1 before checking the equality.

This approach often works because it gives Agda the explicit guidance it needs to perform the level simplification. The rewrite keyword is a powerful tool for dealing with type equalities in Agda.

3. Using a Helper Function

Another strategy is to define a helper function that explicitly converts between the two types. This can sometimes help Agda see the connection more clearly. Here's how we can do it:

open import Agda.Primitive using (Set; Level; _⊔_)
open import Agda.Builtin.Equality using (_≡_)
module Part2 (x y : Level) where
  open import Part1 (x ⊔ y) (x ⊔ y) as P1
  open import Part1 x y as P2

  level-equal : (x y : Level) -> (x ⊔ y) ⊔ (x ⊔ y) ≡ (x ⊔ y)
  level-equal x y = refl

  T1 : Set ((x ⊔ y) ⊔ (x ⊔ y))
  T1 = P1.T

  T2 : Set (x ⊔ y)
  T2 = P2.T

  -- Helper function to convert between the types
  convert : P1.T -> P2.T
  convert t = t

  thing : P1.T ≡ P2.T
  thing = refl -- This will still fail

Unfortunately, even with the helper function, the direct refl proof might still fail. However, the helper function can be useful in other contexts where you need to explicitly convert between the two types.

4. Pattern Matching (Sometimes)

In some cases, pattern matching can help Agda see the equality. However, this is more applicable when dealing with data types and their constructors, rather than level equalities directly. It's worth keeping in mind as a general technique.

Agda Version and Potential Bugs

The original poster mentioned using Agda version 2.8.0. It's worth noting that older versions of Agda might have bugs or limitations in their type checking and unification algorithms. If you're encountering issues like this, it's always a good idea to try the latest version of Agda to see if the problem has been resolved. Keeping your Agda version up to date can save you a lot of headaches.

Conclusion

This issue highlights some of the challenges in working with advanced type systems like Agda's. While Agda is incredibly powerful, its type checking and unification algorithms aren't perfect. Sometimes, we need to provide explicit guidance to help Agda along. By understanding the intricacies of level unification and using techniques like rewrite, we can overcome these challenges and write robust, type-safe code. Remember, understanding the error messages and experimenting with different approaches are key to mastering Agda.

So, next time you encounter a similar issue, don't despair! Try these workarounds, and you'll likely find a way to make Agda see what you see. Happy coding, everyone!