[Agda] Termination checking in cubical mode

Dr. ERDI Gergo gergo at erdi.hu
Fri Nov 9 02:08:23 CET 2018


Hi,

I've played around with Agda's --cubical mode, using 
https://github.com/agda/cubical (after being pointed to it on Stack 
Overflow). My current code typechecks, but trips up the termiation 
checker in the definition of a binary function over HITs.

1. The code that I initially wrote is here: 
https://gist.github.com/gergoerdi/f8e7d20fc45ee0f6dba52161df2c59c4

In this version, the termination checker complains about basically every 
occurrence of `_+_` in the internal point case (i.e. the fourth clause). I 
don't think this behaviour is justified: all the corner and edge cases[1] 
are covered by the previous three clauses of `_+_` which have no recursive 
calls.

Is there any valid reason why these `point + point` etc. cases are 
reported as "problematic", or is this just an implementation shortcoming?


2. If I inline the definition of `_+_` in `X + A` etc. as in
     X+A = (x +̂ a) - (y +̂ b)

then the only remaining problematic calls are the ones in the definition 
of `right`:

     right : qᵢ i1 ≡ q₁
     right i = comp
       (λ j → p j + A ≡ p j + A′)
       (λ { j (i = i0) → qᵢ j
          ; j (i = i1) → cong (λ ξ → quot {x} {y} {x′} {y′} eq₁ j + ξ) q
          })
       (inc (left i))

Here, again, the `p j + A` and the `p j + A′` case should be covered by 
previous clauses (since both are on edges). But the `_+_` in the `cong` 
call looks like a valid problem.

Supposing that all the other problems are resolved (either by fixing 
some bug in Agda's termination checker, or me manually inlining all 
corner- and edge-calls of `_+_`[2]), what is the general strategy for 
referring to the function being defined, when defining functions over 
HITs, without causing termination problems? In other words, what can I do 
with this last remaining `_+_` call in `cong`

FWIW, since my HIT is a quotient type, I think morally just defining it on 
the corners and edges should be sufficient, so no "real" information is 
being added in the inner point case.

Thanks,
 	Gergo


[1] I love how 'corner case' and 'edge case' are actual technical terms in 
CTT!

[2] I guess the latter is going to happen faster


More information about the Agda mailing list