[Agda] Termination checker change?
Pierre Hyvernat
pierre.hyvernat at univ-savoie.fr
Thu Jun 5 16:09:14 CEST 2014
Hi...
I've noticed that the termination checker of Agda 2.3.3 (and 2.4.1)
doesn't accept a rather innocent function...
(Agda 2.3.2 does accept it.)
Basically, a structurally recursive function on a W-type isn't seen as
terminating when the argument is "hidden" inside a pair whose second
projection is a function.
Here is the problematic definition, simplified for the occasion
(<_,_> is the constructor for pairs, and Empty and Branch are
constructors for W types)
test : (W × (One -> One)) -> One
test < Empty , _ > = *
test < Branch a t , _ > = test < t (br a) , (λ _ -> *) >
and the unproblematic one (without pairs)
test2 : W -> (One -> One) -> One
test2 Empty r = ⋆
test2 (Branch a t) _ = test2 (t (br a)) (λ _ -> *)
test is tagged as non-terminating while test2 is tagged as
terminating...
(Note that replacing "One -> One" by "One" in the type of test doesn't
show the problem!)
Is there an explanation, or is that a bug?
===== 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
-- non-terminating!!!
test : (W × (One -> One)) -> One
test < Empty , _ > = *
test < Branch a t , _ > = test < t (br a) , (λ _ -> *) >
-- terminating
test2 : W -> (One -> One) -> One
test2 Empty r = *
test2 (Branch a t) _ = test2 (t (br a)) (λ _ -> *)
--terminating
test3 : (W × One) -> One
test3 < Empty , _ > = *
test3 < Branch a t , _ > = test3 < t (br a) , * >
==========
Pierre
--
We biologists have a special word for stable.
It is "dead".
More information about the Agda
mailing list