agda / agda

Agda is a dependently typed programming language / interactive theorem prover.
https://wiki.portal.chalmers.se/agda/pmwiki.php
Other
2.39k stars 337 forks source link

TBT: do not count rhs `j : Size< i` towards `j < i` in termination #7277

Open andreasabel opened 2 weeks ago

andreasabel commented 2 weeks ago

The syntax-based termination checker forbids T because it makes Agda loop.

{-# OPTIONS --type-based-termination #-}
{-# OPTIONS --sized-types #-}

module TypeBasedTermination.BoundedSizeNoMatch where

open import Agda.Builtin.Size
open import Agda.Builtin.Equality

-- The following should not termination check,
-- otherwise eta expansion can loop
T : Size → Set
T i = (j : Size< i) → T j

-- This loops:
loops : (i : Size) (x y : T i) → x ≡ y
loops i x y = refl

TBT currently accepts T which sends the type-checker into infinite eta-expansion for loops.