Typechecker loops
- Dominant language
- Java
- Stars
- 756
- Forks
- 31
- PR merge metrics
- No merged PRs in 30d
Description
Impredicativity in Arend allows encoding the Girard-Hurken paradox in an inconsistent context;
In the following code:
```arend
\import HLevel
\import Logic
\import Paths.Meta
\class Girard (all-prop : \Pi (A : \Set) -> isProp A) {
\data V
| set (A : \Prop) (f : A -> V)
\where
\use \level Vprop : isProp V => all-prop V
\func \infix 4 in (x y : V) : \Prop \elim y
| set A f => \Sigma (i : A) (f i = x)
\func foundation (x : V) (p : x in x) : Empty \elim x, p
| set A f, (i , p) => foundation (f i) (rewrite p (i , p))
\func V' : V => set V (\lam x => x)
\func VinV : V' in V' => (V', idp)
\func loopy : Empty => foundation V' VinV
}
```
Attempting to normalize `loopy` causes the typechecker to go in an infinite loop.
This is inspired by the 1lab which also has [similar issues](https://gist.github.com/ncfavier/41993e24d6d118e9162d2f92585dc155) due to impredicativity.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the Arend code in the issue and attempt to normalize `loopy`, confirming that the typechecker loops. Compare the behavior with the linked 1lab example and trace the typechecker’s handling of the impredicative `Girard` construction. Done means the reproducer no longer causes an infinite loop while preserving the reported typechecking behavior.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100