Dafny中标准库Math.Max为何比自定义Max验证速度快？

核心原因是Dafny标准库的Math.Max并非普通函数，它自带验证器能直接利用的预定义公理和优化标记，而你的自定义函数没有这些加持，导致验证器需要反复从头推导逻辑，最终超时。

具体来说有两点关键差异：

• 标准库函数附带预定义公理：
  Dafny官方给Math.Max内置了一系列已证明的核心性质（比如Max(a,b) ≥ a、Max(a,b) ≥ b、Max(a,b)必然等于a或b）。当验证器处理使用Math.Max的代码时，会直接调用这些现成的公理，无需展开函数的分支逻辑重新推导。而你的自定义Max函数，验证器每次遇到它都得拆解if a < b then b else a这个分支，在复杂验证场景下，反复做这种推导会大幅消耗时间，最终触发超时。

• 标准库函数有验证器级别的优化：
  Math.Max可能被标记为{:builtin}属性，Dafny验证器会将其直接映射到SMT求解器（如Z3）的原生max操作。求解器对原生操作的处理是高度优化的，速度远快于处理用户自定义的分支函数。

优化自定义Max的方法 #

如果需要保留自定义Max并提升验证速度，可以给它补充必要的公理，让验证器直接复用这些逻辑：

function Max(a: int, b: int): int
{
  if a < b then b else a
}

// 补充Max的核心性质公理
axiom MaxGreaterOrEqualA(a: int, b: int): Max(a, b) >= a
axiom MaxGreaterOrEqualB(a: int, b: int): Max(a, b) >= b
axiom MaxIsEitherAorB(a: int, b: int): Max(a, b) == a || Max(a, b) == b

内容的提问来源于stack exchange，提问作者Carl