在 Stainless 中引入终止作为先决条件

Question

我正在尝试根据以下函数证明无类型 lambda 演算的计算：

 def eval(t: Term): Option[Term] = t match {
    case App(t1, t2) => eval(t1) match {
      case Some(Abs(x, body)) => eval(t2) match {
        case Some(v2) => eval(subst(x, v2, body))
        case None() => None[Term]()
      }
      case _ => None[Term]() // stuck
    }
    case _ => Some(t) // Abs or Var, already a value
  }

returns None 或一个值。然而，我被指出这个函数可能不会终止。我的问题是如何在 Leon/Stainless 中引入函数必须终止的先决条件？

Answer 1

我不知道有什么方法可以引入专门说明 "this function terminates (at the arguments given)" 的先决条件。您应该尝试找出一个与此等价的更高级别的谓词。在您的情况下，这是行不通的，因为您无法提供可计算的谓词来确定无类型 lambda 演算中的项是否具有范式。

但并非全部丢失：这里通常的方法是引入一个额外的 "fuel" 类型 BigInt 参数。它表示要执行的最大减少步骤数。在每一步中，您将燃料减一。如果燃料为零，则中止递归并 return None。这将使您的函数终止。

但是，您始终需要提供 "big enough" 燃料。通常燃料将是一个参数，引理有一个前提条件 eval(fuel, t) = Some(u).

在 Stainless 中引入终止作为先决条件

Introducing termination as a precondition in Stainless

formal-verification

scala

stainless