[Agda] strange termination check

Sergei Meshveliani mechvel at botik.ru
Fri Oct 11 01:45:15 CEST 2013


On Thu, 2013-10-10 at 21:57 +0400, Sergei Meshveliani wrote:
> Please, why the below  powerToPos  is not checked as terminating ?
> 
> 
> {-# OPTIONS --termination-depth=3 #-}
> module Report where
> open import Level    using () renaming (zero to 0ℓ)
> open import Function using (case_of_)
> open import Relation.Binary 
>             using (module Setoid; module IsEquivalence;_Preserves_⟶_)
> open import Relation.Binary.PropositionalEquality using (_≡_)
> open import Algebra    using (Semigroup; module Semigroup)
> open import Data.Empty using (⊥)
> open import Data.List  using ([]; _∷_)
> open import Data.Fin   using (Fin) renaming (zero to 0b; suc to sucB)
> open import Data.Digit using (Bit)
> open import Data.Bin   using (Bin⁺)
>           
> 1b : Bit
> 1b = sucB 0b
> 
> postulate H : Semigroup 0ℓ 0ℓ
> 
> open Semigroup H using (setoid; _≈_; _∙_)
>                        renaming (Carrier to C; isEquivalence to ≈equiv)
> open IsEquivalence ≈equiv using ()
>                  renaming (refl to ≈refl; sym to ≈sym; trans to ≈trans)
> 
> HasLast1 : Bin⁺ → Set       -- "is the bit list of a non-zero binary"
> HasLast1 []           =  ⊥
> HasLast1 (b ∷ [])     =  b ≡ 1b
> HasLast1 (_ ∷ b ∷ bs) =  HasLast1 (b ∷ bs)
> 
> powerToPos : C → (bs : Bin⁺) → HasLast1 bs → C
>
> [..]

> The recursion     (b ∷ b' ∷ bs)  -->  (b' ∷ bs)  
> 
> by the second argument is well-founded. Why does not the checker see the
> termination proof? 


Sorry, the implementation needs to be

powerToPos _ []                    ()
powerToPos x (0b      ∷ [])        ()
powerToPos x (sucB 0b ∷ [])        _   =  x
powerToPos x (sucB (sucB ()) ∷ [])

powerToPos x (b ∷ b' ∷ bs)  last1-b:b':bs =
                           case b of \ { 0b              → p ∙ p
                                       ; (sucB 0b)       → x ∙ (p ∙ p)
                                       ; (sucB (sucB ()))
                                       }
                           where
                           hl1 : HasLast1 (b' ∷ bs)
                           hl1 = last1-b:b':bs

                           p = powerToPos x (b' ∷ bs) hl1
-----------------------------------------------------------------------

And again, I do not understand why is not it checked as terminating.

Thanks,

------
Sergei




More information about the Agda mailing list