FStar 函数异常行为

Question

接受以下简单函数作为终止函数似乎不正确：

val fnc : (nw: nat) -> (ni: nat) -> (ni_max: nat) -> bool
let rec fnc nw ni ni_max =
  match ni with 
  | ni_max -> false
  | _      -> fnc nw (nw + ni) ni_max

令人惊讶的是，该函数确实在评估它时终止，例如，fnc 0 0 1 和 returns false。我错过了什么？

Answer 1

模式第一个分支中的ni_max是一个新的活页夹，与函数的参数ni_max无关。您的代码相当于：

let rec fnc nw ni ni_max =
  match ni with 
  | _ -> false
  | _      -> fnc nw (nw + ni) ni_max

这是一个总是 returns false 的函数。

您可能打算写

let rec fnc nw ni ni_max =
  if ni = ni_max then false
  else fnc nw (nw + ni) ni_max

现在终止检查器应该抱怨了。

FStar 函数异常行为

FStar function strange behavior

fstar