agda / agda

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

TBT: Bug in size preservation regarding postulates #7270

Open andreasabel opened 1 month ago

andreasabel commented 1 month ago

TBT accepts this, but this is questionable, since it seems to assume too much about postulates:

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

record U : Set where
  coinductive
  field force : U
open U

postulate d : U → U

-- f is classified as size preserving, but is not, since d is unknown
-- Counterexamples: d = id; d u = u .force
f : U → U
f u = d u .force

-- This should not pass:
u : U
u .force = f u

I failed to exploit this bug, because TBT does not accept the same if we replace d by a module parameter (which we later could instantiate to something evil). ATTN: @knisht