Liquid Haskell：来自内联递归函数的 "Cyclic type alias definition" 错误

Question

我在 Haskell 中编写了一些代码来执行 ordinal arithmetic，现在正尝试使用 Liquid Haskell 来验证某些属性。但是，我遇到了 "reflecting" 递归函数的问题。我在下面的 "less than" 函数中发现了一个问题：

-- (Ord a n b) = a^n + b
{-@ data Ordinal [size] = Ord { a :: Ordinal, n :: Nat,  b :: Ordinal }
                        | Zero {} @-}
data Ordinal = Ord Ordinal Integer Ordinal
             | Zero
             deriving (Eq, Show)

{-@ measure size @-}
{-@ size :: Ordinal -> Nat @-}
size :: Ordinal -> Integer
size Zero = 1
size (Ord a n b) = (size a) + 1 + (size b)

{-@ inline ordLT @-}
ordLT :: Ordinal -> Ordinal -> Bool
ordLT _ Zero = False
ordLT Zero _ = True
ordLT (Ord a0 n0 b0) (Ord a1 n1 b1) =
    (ordLT a0 a1) || 
    (a0 == a1 && n0 < n1) || 
    (a0 == a1 && n0 == n1 && ordLT b0 b1)

one = (Ord Zero 1 Zero)     -- 1
w   = (Ord one 1 Zero)      -- omega
main = print w              -- Ord (Ord Zero 1 Zero) 1 Zero

仅使用上述方法执行 liquid ordinals.hs 会出现以下错误：

Error: Cyclic type alias definition for `Main.ordLT`
14 |     {-@ inline ordLT @-}
                     ^^^^^
The following alias definitions form a cycle:
* `Main.ordLT`

那么体现递归函数的正确方式是什么？我读过 liquid haskell tutorial 但我无法弄清楚它的例子有什么不同。

Answer 1

在没有更多上下文的情况下很难确定你想做什么，但 inline 确实不适用于递归函数：inline 允许你在类型 通过在编译时扩展它（在创建发送给求解器的验证条件之前），所以需要能够用一些特定的逻辑公式（这是不可能的，因为它是递归的）。

如果您需要能够在逻辑中使用任意 Haskell 函数，您可以考虑使用 Refinement Reflection。您的示例使用 {-@ reflect ordLT @-} 和 {-@ LIQUID "--exact-data-cons" @-} 进行编译。但是，细化反射创建的函数符号不会在逻辑中自动完全解释。 this paper, and more approachable examples/explanation are present in these slides and this blog post 中讨论了具体细节。要记住的要点是，由反射创建的 ordLT 符号最初将被视为逻辑中完全未解释的函数：LH 唯一知道的是 a0 == a1 ==> b0 == b1 ==> ordLT a0 b0 == ordLT a1 b1 之类的东西（如果你调用它在相同的输入上，结果是相同的）。

为了在逻辑中使用 ordLT 做一些有用的事情，您需要在范围内某处的值级别调用 ordLT，这将揭示该特定调用的值，因为 ordLT 的 return 类型（值级函数）在这些输入上断言了 ordLT （逻辑级未解释函数）的输出。示例在上面链接的幻灯片和论文中给出。我希望这足以让您入门！

Liquid Haskell：来自内联递归函数的 "Cyclic type alias definition" 错误

Liquid Haskell: "Cyclic type alias definition" error from an inlined recursive function

haskell

refinement-type

liquid-haskell