[Agda] Termination Checking in Development Agda
karim kanso
cskarim at swan.ac.uk
Fri Dec 18 19:07:03 CET 2009
Hello Agda Users,
Recently (about a week ago) I upgraded to the latest development version, I
have noticed
that a function that used to pass termination check now does not. To start
with, I am
exploring model checking from Agda as a platform. To this end, I require to
represent
infinite paths as codata.
Using these codata structures complicates matters (particularly with
dependant
pattern matching) so inductive data type of a lasso is defined, then a
translation
from the lasso to infinite paths. It is this translation that is causing
problems.
Below is a simplified version of the problem, instead of a lasso, loops are
used. I have
tested a simpler version that dont require the principle of transfer and
these pass the
termination check. To the best of my understanding the function loop2path
(below)
uses guarded recursion so should pass the check.
Could any one please explain why it applying the proof transfer principle
breaks
termination? Or is this some kind of bug?
Best,
Karim Kanso
module coterm where
open import Data.Nat using (ℕ;suc;zero)
open import Data.Fin using (Fin;suc;zero)
open import Relation.Binary.Core using (_≡_;refl)
transfer : {A : Set} →
(F : A → Set) →
(a b : A) →
(r : a ≡ b) →
(p : F a) →
F b
transfer F .b b refl p = p
postulate state : ℕ
postulate action : Fin state → ℕ
postulate transition : (s : Fin state) →
(a : Fin (action s)) →
Fin state
data Path : Fin state → Fin state → Set where
end : {s : Fin state} → Path s s
next : {s' : Fin state} →
(s : Fin state) →
(a : Fin (action s)) →
Path (transition s a) s' → Path s s'
codata Path' : Fin state → Set where
next : (s : Fin state) →
(a : Fin (action s)) →
Path' (transition s a) →
Path' s
data Loop (s : Fin state) : Set where
loop : {s' : Fin state} →
(l : Path s s') →
(a : Fin (action s')) →
(lp : s ≡ (transition s' a)) →
Loop s
loop2path : {s : Fin state} → Loop s → Path' s
loop2path {s} (loop {s'} l a lp) = aux l a lp
where
aux : {t t' : Fin state} → (l : Path t t') → (a : Fin (action t')) → (lp
: s ≡ transition t' a) → Path' t
aux {t} {.t} end a' lp' = next t a' (transfer Path' s (transition t a')
lp' (aux l a lp))
aux {t} (next .t a' y) a lp = next t a' (aux y a lp)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20091218/4b1ddc15/attachment.html
More information about the Agda
mailing list