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

Higher constructors can trick the productivity checker #6108

Closed
dolio opened this issue Sep 16, 2022 · 1 comment · Fixed by #6115
Closed

Higher constructors can trick the productivity checker #6108

dolio opened this issue Sep 16, 2022 · 1 comment · Fixed by #6115
Assignees
Labels
documented-in-changelog Issues already documented in the CHANGELOG guardedness Problems of the guardedness checker for coinduction. type: bug Issues and pull requests about actual bugs
Milestone

Comments

@dolio
Copy link

dolio commented Sep 16, 2022

Agda's productivity checker seems to be satisfied by a definition being guarded by higher constructors. However, higher constructors can reduce to non-constructors at their endpoints, allowing definitions like this to be accepted:

data C (A : Type) : Type

record P (A : Type) : Type where
  coinductive
  field
    force : C A

open P

data C A where
  now : A  C A
  later : P A  C A
  wait : force ≡ later

hmm : P A
hmm .force = wait i0 hmm

Normalizing force hmm is an infinite loop.

This example is wrong in an obvious way, because wait i0 = force, so the definition of hmm is actually equivalent to force hmm = force hmm. But, it'd be really nice if a proper understanding of how this should work also rules out P A being contractible:

: P A
∞ .force = later ∞
  
contr : (x : P A)  x ≡ ∞
contr x i .force = wait i (contr x i)

since this definition also contains, as a specialization:

contr x i0 .force = contr x i0 .force

Although in that case it evaluates like contr x i0 .force = x .force, so perhaps this is too much to hope for.

@dolio dolio changed the title Higher constructors can trick productivity checker Higher constructors can trick the productivity checker Sep 16, 2022
@nad nad added type: bug Issues and pull requests about actual bugs guardedness Problems of the guardedness checker for coinduction. labels Sep 16, 2022
@nad
Copy link
Contributor

nad commented Sep 16, 2022

Here is a self-contained test case:

{-# OPTIONS --safe --cubical --guardedness #-}

open import Agda.Builtin.Cubical.Path
open import Agda.Primitive.Cubical

mutual

  record R : Set where
    coinductive
    field
      force : D

  data D : Set where
    point  : R  D
    higher : R.force ≡ point

r : R
r .R.force = higher i0 r

loops : D
loops = r .R.force

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documented-in-changelog Issues already documented in the CHANGELOG guardedness Problems of the guardedness checker for coinduction. type: bug Issues and pull requests about actual bugs
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants