无法验证 F* (FStar) 中的简单程序

Question

我正在使用 F* 0.9.6.0，但我无法让这个简单的程序通过子类型检查：

module Test

open FStar.String

let minlen s n = strlen s >= n
let maxlen s n = strlen s <= n

let isLanguageValid s = (minlen s 2) && (maxlen s 8)
type language = s : string { isLanguageValid s }

let english : language = "en"
let invalid : language = "abcdefghi"

我希望 english 通过，但 invalid 失败。我尝试过的一切要么导致他们都被拒绝，要么都被接受。我究竟做错了什么？我只想接受这种类型的特定长度的字符串。

Answer 1

关于 F* 中字符串的推理非常有限。大多数证明需要将 strlen 之类的函数视为未解释的函数，或者触发对规范化的一些明智使用。

备注

[@@expect_failure]
let test = assert (strlen "English" == 7)
let test = assert_norm (strlen "English" == 7)

也就是说第一个断言在 F* 中是不可证明的——它没有通过验证者。

然而，第二个断言通过要求 F* 使用归一化而不是 SMT 来证明它而成功。

为了验证你的程序，我修改了它：



let minlen s n = strlen s >= n
let maxlen s n = strlen s <= n

let isLanguageValid s = (minlen s 2) && (maxlen s 8)
type language = s : string { normalize_term #bool (isLanguageValid s) }

let english : language = "en"

[@@expect_failure]
let invalid : language = "abcdefghi"

注意在 language 的定义中使用 normalize_term。

您可以在这里阅读一些关于规范化等的内容：https://github.com/FStarLang/FStar/wiki/Using-SMT-fuel-and-the-normalizer

仅供参考，我的示例是关于最新版本的 F*。最近的二进制版本可以在这里找到 https://github.com/FStarLang/binaries/tree/master/weekly

无法验证 F* (FStar) 中的简单程序

Trouble verifying simple programs in F* (FStar)

verification

formal-languages

fstar