search

idris-lang / Idris2

A purely functional programming language with first class types
https://idris-lang.org/
Other
2.52k stars 375 forks source link

total Omega : ⊥ #1988

Open yallop opened 3 years ago

yallop commented 3 years ago

While trying to understand the differences between Agda's and Idris's positivity checkers, I came across Andreas Abel's message from 2012, which passes the totality checker when translated to Idris:

data D : Type where Abs : (D = e) -> (e -> Void) -> D

lam : (D -> Void) -> D
lam f = Abs Refl f

app : D -> D -> Void
app (Abs Refl f) d = f d

omega : D
omega = lam (\x => app x x)

total
Omega : Void
Omega = app omega omega
$ idris2 omega.idr 
     ____    __     _         ___                                           
    /  _/___/ /____(_)____   |__ \                                          
    / // __  / ___/ / ___/   __/ /     Version 0.4.0-5126600fa
  _/ // /_/ / /  / (__  )   / __/      https://www.idris-lang.org           
 /___/\__,_/_/  /_/____/   /____/      Type :? for help                     

Welcome to Idris 2.  Enjoy yourself!
1/1: Building omega (omega.idr)
Main> :total Omega
Main.Omega is total
Main>
yallop commented 3 years ago

In fact, the following simpler program suffers from the same issue:

data D : Type where Abs : (D -> Void) -> D

app : D -> D -> Void
app (Abs f) d = f d

omega : D
omega = Abs (\x => app x x)

total
Omega : Void
Omega = app omega omega
gallais commented 3 years ago

That last one is properly rejected if you use %default total.

The totality checker somehow forgets to check that D is positive despite being in Omega's dependency graph. I've tried to track down this issue in the past but haven't found where the problem is.

balint99 commented 2 years ago

In Agda, this piece of code is rejected because the universe of the type of the constructor Abs is Set_1, which is higher than Set_0, the universe of the data type itself. Therefore, I think that adding universe levels to Idris might solve this problem, provided that data type definitions like this are rejected.

andrevidela commented 7 months ago 
data D : Type where Abs : (D = e) -> (e -> Void) -> D

lam : (D -> Void) -> D
lam f = Abs Refl f

app : D -> D -> Void
app (Abs Refl f) d = f d

omega : D
omega = lam (\x => app x x)

total
Omega : Void
Omega = app omega omega

still causes problems