Termination check on local recursive function

[amigalemming]

This function definition does not satisfy the termination checker:

powerAssociative :: (a -> a -> a) -> a -> a -> Integer -> a
powerAssociative op =
   let go acc _ 0 = acc
       go acc a n = go (if even n then acc else op acc a) (op a a) (div n 2)
   in  go

Liquid error is:

    Termination Error
go
No decreasing parameter
   |
51 |        go acc _ 0 = acc
   |        ^^

But this definition passes the termination checker:

powerAssociative :: (a -> a -> a) -> a -> a -> Integer -> a
powerAssociative _op acc _ 0 = acc
powerAssociative op acc a n =
   powerAssociative op (if even n then acc else op acc a) (op a a) (div n 2)

I prefer the first version in order to reduce the parameters that are carried through the recursion. I think the first version is also more comprehensible because it is obvious that op stays the same throughout the recursion.

Unfortunately, I cannot add a Liquid type signature to go in order to mark the decreasing parameter, because that type signature would be too general in the type variable a. I tried:

{-@ go :: a -> a -> n : Integer -> a / [n] @-}

[facundominguez]

Hello @amigalemming. It looks to me like Liquid Haskell should have rejected all flavors of powerAssociative. If n is -1, then div n 2 doesn't decrease, nor does it go towards 0. A smaller reproducer:

iterateTo0 :: Int -> Int
iterateTo0 0 = 0
iterateTo0 n = iterateTo0 (div n 2)

main :: IO ()
main = print $ iterateTo0 (-1)

This program doesn't terminate, and yet, it passes verification.

[amigalemming]

You are so right! So, it's a bug, but a different one. I tried to replace Integer by {m : Integer | m>=0}. However, Liquid Haskell still sees non-termination in the first implementation, but accepts the second implementation of powerAssociative.

[facundominguez]

I created #2285 to deal with negative dividends.

Regarding this issue, looks like it could be addressed by either documenting why the termination checker fails to verify go, or fixing it if possible. If I were to do any of these, I'd have to dive into the code to learn what's happening.

[facundominguez]

This is likely a duplicate of #2200.

I cannot reproduce this error but I can reproduce the one in #2200.

@amigalemming, what version of liquidhaskell are you using? And if possible, could you share the whole source file which is failing for you?

[amigalemming]

The original module is here: https://hackage.haskell.org/package/utility-ht-0.0.17.1/docs/Data-Function-HT.html I used latest liquidhaskell-0.9.8.1.