JetBrains / JetBrains/Arend

Typechecker loops

Open
#352 1 comment 1 reaction 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.