[Agda] Termination checker change?
Pierre Hyvernat
pierre.hyvernat at univ-savoie.fr
Fri Jun 6 10:15:16 CEST 2014
>Yes, indeed, the termination checker has changed, due to a soundness
>issue.
>
>Currently, it does not look through pairs anymore, so you have to
>curry your functions.
>
It looks a little subtler than that
test4 : (W × (One -> One)) -> One
test4 < Empty , f > = *
test4 < Branch a t , f > = test4 < t (br a) , (λ x → f x) >
is accepted, while
test3 : (W × (One -> One)) -> One
test3 < Empty , f > = *
test3 < Branch a t , f > = test3 < t (br a) , (λ x → x) >
is not...
(The only difference is the second component of the pair in the
recursive call...)
Does it mean it doesn't accept any kind of deep-pattern matching?
>I have an idea to bring uncurried functions back (in a sound way), but
>will need some time to implement it.
>
Is the actual termination checker of Agda described somewhere. Last time
I checked, the wiki
http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.TerminationChecker
wasn't accurate.
I once had understood that the termination checker used both a variant
of the size-change principle, together with some sized-typed principle.
If so, do the two notions interact in some non-trivial way?
A quick look at the source seems to indicate they do not...
Is that right?
===== file test.agda =====
module test where
record One : Set where constructor *
record _×_ (A : Set) (B : Set) : Set where
constructor <_,_>
field
fst : A
snd : B
module Problem (A : Set) (D : A -> Set) (br : (a : A) -> D a) where
data W : Set where
Empty : W
Branch : (a : A) -> (f : (d : D a) -> W) -> W
test3 : (W × (One -> One)) -> One
test3 < Empty , f > = *
test3 < Branch a t , f > = test3 < t (br a) , (λ x → x) >
test4 : (W × (One -> One)) -> One
test4 < Empty , f > = *
test4 < Branch a t , f > = test4 < t (br a) , (λ x → f x) >
==========
Pierre
--
Things are more like they are today than they ever
were before.
-- Dwight Eisenhower
More information about the Agda
mailing list