函数证明期间会发生什么

Question

我正在尝试证明 icmp6 校验和函数的属性（对 16 位整数求和，添加进位，反转 16 位整数）。

我在 isabelle 中定义了函数。（我知道我的证明很糟糕）

但出于某种原因，isabelle 无法证明有关 icmp_csum 函数的某些信息，它想要证明。当我用 done 替换粘贴中的 oops 时，它会产生数千行，只是说： "linarith_split_limit exceeded (current value is 9)"

theory Scratch
imports Main Int List
begin

fun norm_helper :: "nat ⇒ nat" where
  "norm_helper x = (let y = divide x 65536 in (y + x - y * 65536))"

lemma "x ≥ 65536 ⟹ norm_helper x < x" by simp
lemma h: "norm_helper x ≤ x" by simp

fun normalize :: "nat ⇒ nat" where
  "normalize x = (if x ≥ 65536
    then normalize (norm_helper x)
    else x)"

inductive norm_to :: "nat ⇒ nat ⇒ bool" where
  "(x < 65536) ⟹ norm_to x x"
| "norm_to y z ⟹ y = norm_helper x ⟹ norm_to x z"

lemma ne: "norm_to x y ⟹ y = normalize x"
  apply (induct x y rule: norm_to.induct) by simp+

lemma i: "norm_to x y ⟹ x ≥ y"
  apply (induct x y rule: norm_to.induct) by simp+
lemma l: "norm_to x y ⟹ y < 65536"
  apply (induct x y rule: norm_to.induct) by simp+

lemma en: "y = normalize x ⟹ norm_to x y"
  apply (induct x rule: normalize.induct)
proof -
  fix x :: nat
  assume 1: "(x ≥ 65536 ⟹ y = Scratch.normalize (norm_helper x) ⟹ norm_to (norm_helper x) y)"
  assume 2: "y = Scratch.normalize x"  
  show "norm_to x y"
  proof (cases "x ≥ 65536")
    show "¬ 65536 ≤ x ⟹ norm_to x y"
      using norm_to.intros(1)[of x] 2 by simp
    {
      assume s: "65536 ≤ x"
      have d: "y = normalize (norm_helper x)" using 2 s by simp
      show "65536 ≤ x ⟹ norm_to x y"
        using 1 d norm_to.intros(2)[of "norm_helper x" y x]
        by blast
    }
  qed
qed

lemma "normalize x ≤ x" using en i by simp
lemma n[simp]: "normalize x < 65536" using en l by blast

fun sum :: "nat list ⇒ nat" where
  "sum [] = 0"
| "sum (x#xs) = x + sum xs"

fun csum :: "nat list ⇒ nat" where
  "csum xs = normalize (sum xs)"

fun invert :: "nat ⇒ nat" where
  "invert x = 65535 - x"

lemma c: "csum xs ≤ 65535" using n[of "sum xs"] by simp
lemma ic: "invert (csum xs) ≥ 0" using c[of xs] by blast

lemma asdf:
  assumes "xs = ys"
  shows "invert (csum xs) = invert (csum ys)"
  using  HOL.arg_cong[of "csum xs" "csum ys" invert,
                      OF HOL.arg_cong[of xs ys csum]] assms(1)
  by blast

function icmp_csum :: "nat list ⇒ nat" where
  "icmp_csum xs = invert (csum xs)"
apply simp
apply (rule asdf)
apply simp
oops

end

Answer 1

我不知道为什么会有 linarith 的跟踪输出，但是考虑到你的定义既不是递归的，也不是执行模式匹配的，你可以把它写成 definition:

definition icmp_csum :: "nat list ⇒ nat" where
  "icmp_csum xs = invert (csum xs)"

另一种可能性是将 invert 更改为 definition 而不是 fun。（一般来说，如果它既不递归也不执行模式匹配，definition 更可取，因为它的开销比 fun 少得多。）

注意，只导入 Main，而不是 Main Int List。

编辑： Tobias Nipkow 在 the mailing list 上的解释：

This is a known issue. In the outdated LNCS 2283 you can find a discussion what to do about it in Section 3.5.3 Simplification and Recursive Functions. The gist: don't use "if", use pattern matching or "case". Or disable if_split.

函数证明期间会发生什么

What happens during function proofs

isabelle