Opaque definitions

Opaque definitions are a mechanism for controlling unfolding of Agda definitions, to help with both goal readability and performance. Like abstract definitions, opaque definitions will not unfold in general, but unlike abstract definitions, opacity can be selectively controlled at use-sites.

Our implementation of unfolding control is based on the theory introduced by Gratzer et. al. in Controlling unfolding in type theory, but handled entirely at the elaborator level, without a dependency on our (cubical) extension types.

Overview

  • Functions (and primitive functions) can be marked opaque. Outside of opaque blocks, these behave like postulates.

  • Opaque blocks, even in unrelated modules, can have unfolding clauses, which allow the user to list their choice of names that should be locally treated as transparent.

  • Opaque definitions do not reduce in type signatures, even inside opaque blocks where they would otherwise be unfolded.

Unfolding opaque definitions

Consider an implementation of the integers as an abstract setoid: The underlying representation is given by pairs of natural numbers, representing a difference, but day-to-day, we would like to treat as its own type.

Our core module might define these operations:

  1. module Integer where
  2. opaque
  3. : Set
  4. = Nat × Nat
  5. _≡ℤ_ : (x y : ℤ) Set
  6. (p , n) ≡ℤ (p' , n') = (p + n') ≡ (p' + n)
  7. infix 10 _≡ℤ_
  8. 0 :
  9. 0 = 0 , 0
  10. 1 :
  11. 1 = 1 , 0
  12. _+ℤ_ : (x y : ℤ)
  13. (p , n) +ℤ (p' , n') = (p + p') , (n + n')
  14. _*ℤ_ : (x y : ℤ)
  15. (a , b) *ℤ (c , d) = ((a * c) + (b * d)) , ((a * d) + (b * c))
  16. infixl 20 _+ℤ_
  17. infixl 30 _*ℤ_
  18. -ℤ_ :
  19. -ℤ (p , n) = (n , p)

We’d now like to prove that the integers form a ring, under the _≡ℤ_ notion of equality. Some of the equations on natural numbers involved are pretty nasty, though, so this would be very hard to do without a solver for semiring equations. However, such a solver would also depend on reflection machinery, bloating the dependency tree of the Integer module for people who do not care about it provably forming a ring.

Fortunately, since is opaque rather than abstract, a different module, say Integer-ring, can provide its own proofs, in an opaque block that unfolds the definition of :

  1. module Integer-ring where
  2. open Integer
  3. opaque
  4. unfolding
  5. distl : x y z x *ℤ (y +ℤ z) ≡ℤ x *ℤ y +ℤ x *ℤ z
  6. distl (a , b) (c , d) (e , f) = use-nat-solver where postulate
  7. use-nat-solver
  8. : a * (c + e) + b * (d + f) + (a * d + b * c + (a * f + b * e))
  9. a * c + b * d + (a * e + b * f) + (a * (d + f) + b * (c + e))

Since the definition of distlℤ is in an opaque block with an unfolding ℤ clause, it sees through the opacity of , and of all names unfolded by ’s opaque block (see below).

What actually unfolds?

When an opaque block is checked, Agda will compute ahead-of-time the set of names it is allowed to unfold. This set is per-block, not per-definition. An unfolding clause, if it mentions opaque names, will cause the unfolding sets associated with those names to be added to the current block.

The following illustrates the behaviour of these rules:

  • Unfolding any name in an opaque block will cause any of the other names in that block to be unfolded as well. Example:

    1. module _ where private
    2. opaque
    3. x : Nat
    4. y : Nat
    5. x = 3
    6. y = 4
    7. opaque
    8. unfolding x
    9. _ : y 4
    10. _ = refl

    Here, even though only x was asked for, y is also available for unfolding.

  • Since the unfolding sets brought in by clauses are associated with the block, unfolding is transitive:

    1. module _ where private
    2. opaque
    3. x : Nat
    4. x = 3
    5. opaque
    6. unfolding x
    7. y : Nat
    8. y = 4 + x
    9. opaque
    10. unfolding y
    11. _ : y 7
    12. _ = refl
  • Opaque blocks which are lexically nested can also unfold the names of their parent blocks, even if the name is not in scope when the child block is defined:

    1. module _ where private
    2. opaque
    3. x : Nat
    4. x = 3
    5. opaque
    6. y : Nat
    7. y = 4
    8. _ : x 3
    9. _ = refl
    10. z : Nat
    11. z = 5
    12. opaque
    13. unfolding y
    14. _ : z 5
    15. _ = refl

    This is because the x and z are direct children of the same opaque block: the opaque block that defines y does not “split” its parent block.

Multiple unfolding clauses are supported, as well as unfolding more than one name per clause. The syntax for the latter is simply a space-separated list of names, which must refer to unambiguous functions:

  1. module _ where private
  2. opaque
  3. x : Nat
  4. x = 3
  5. opaque
  6. y : Nat
  7. y = 4
  8. opaque
  9. z : Nat
  10. z = 5
  11. opaque
  12. unfolding x y
  13. unfolding z
  14. _ : x + y + z 12
  15. _ = refl

Finally, unfolding clauses do not introduce new layout context, so that the following is legal: note that y appears to the left of x, but is still attached to the same unfolding clause. This allows the user their preference for how to lay out their unfolding sets:

  1. opaque
  2. unfolding x
  3. y
  4. unfolding z
  5. _ : x + y + z 12
  6. _ = refl

Having an unfolding clause appear after other definitions, or outside of opaque blocks, is a syntax error.

Note that unlike abstract blocks, which are treated on a per-module basis, opaque blocks will only unfold names according to the rules above:

  1. module _ where private
  2. opaque
  3. x : Nat
  4. x = 3
  5. -- opaque
  6. -- _ : x 3
  7. -- _ = refl
  8. -- Fails with: x != 3 of type Nat

Unfolding in types

Note that unfolding clauses do not apply to the type signatures inside an opaque block. Much like for abstract blocks, this prevents leakage of implementation details, but it is also necessary to ensure that the types of names defined by the opaque block remain valid outside the opaque block. Consider:

  1. opaque
  2. S : Set
  3. S = Set
  4. foo : S
  5. foo = Nat
  6. opaque
  7. unfolding foo
  8. -- bar : foo
  9. -- bar = 123
  10. -- Error: S should be a sort, but it isn't

If the definition of bar′ were allowed, we would have bar′ : foo′ in the context. Outside of the relevant opaque blocks, foo′ is not a type, for foo′ : S, and S is not a sort. In cases like this, using an auxiliary definition whose type is a sort is required:

  1. -- Lift foo to a definition:
  2. ty : Set
  3. ty = foo
  4. bar : ty
  5. bar = 123

Since ty′ : Set is manifestly a well-formed type, even outside of this opaque block, there is no problem in adding bar′ : ty′ to the context.

Bibliography

Daniel Gratzer, Jonathan Sterling, Carlo Angiuli, Thierry Coquand, and Lars Birkedal; “Controlling unfolding in type theory”.