Liquid 的表现力 Haskell

Question

根据最近的，我一直在思考以下问题：

我们可以在 LH 中创建一些新的惊人类型，特别是表达一些非平凡的整数子集。例如：

{-@ type Nat = {v:Int | v>=0 } @-}
{-@ type grtN N = {v:Int | v>N } @-}
{-@ type Even = {v:Int | v mod 2 == 0 } @-}

但是现在我可以用 LH 表达哪些其他非平凡的子集？

我可以在 LH 中创建一个只包含 2 的幂的类型吗？我上一个问题是关于什么的，答案似乎是否定的。

所以出现的一个自然问题是我可以表达什么样的（整数）子集？有好的人物刻画吗？

Answer 1

我相信LH会让你写任意算术约束。但是后端求解器只能确定线性整数算法的理论（通过 presburger 算法），因此一旦您开始编写非线性表达式，您就失去了求解器将实际验证您的代码的任何保证。此外，SMT 求解器仅支持一阶逻辑，因此您无法量化关系。

Expressive power of Liquid Haskell