如何在 Dafny 3.1.0 中完成 let-such-that 表达式？

Question

表达式 let-such-that 在 Dafny 的早期版本中有效，但在 Dafny 3.1.0 中无效。例如，以下代码（也在 https://rise4fun.com/Dafny/ABZpf 中）引发错误：“要可编译，必须唯一确定 let-such-that 表达式的值”。

datatype NNF_Formula =   F 
                       | T
                       | V(prop:string) 
                       | NegV(prop:string) 
                       | EX(f:NNF_Formula) 
                       | AX(f:NNF_Formula) 
                       | EG(f:NNF_Formula) 
                       | AG(f:NNF_Formula) 
                       | ER(f1:NNF_Formula,f2:NNF_Formula) 
                       | AR(f1:NNF_Formula,f2:NNF_Formula) 
                       | EF(f:NNF_Formula)  
                       | AF(f:NNF_Formula) 
                       | EU(f1:NNF_Formula,f2:NNF_Formula) 
                       | AU(f1:NNF_Formula,f2:NNF_Formula) 
                       | EUsel(f1:NNF_Formula,f2:NNF_Formula) 
                       | AUsel(f1:NNF_Formula,f2:NNF_Formula) 
                       | Or(f1:NNF_Formula,f2:NNF_Formula)
                       | And(f1:NNF_Formula,f2:NNF_Formula) 

function method family(alpha: NNF_Formula): nat {
  match alpha
  case F => 0
  case T => 1
  case V(_) => 2
  case NegV(_) => 3
  case AX(_) => 4
  case EX(_) => 5
  case AG(_) => 6
  case EG(_) => 7
  case AR(_, _) => 8
  case ER(_, _) => 9
  case AF(_) => 10
  case EF(_) => 11
  case AU(_, _) => 12
  case EU(_, _) => 13
  case AUsel(_, _) => 14
  case EUsel(_, _) => 15
  case Or(_, _) => 16
  case And(_, _) => 17
}

// ORDER IN NNF FORMULAS

predicate method leq_string(s1:string,s2:string) { 
s1 == "" || (s2 != "" && s1[0] <= s2[0] && ( s1[0] == s2[0] ==> leq_string(s1[1..],s2[1..])))
}

lemma antisym_leq_string_Lemma (s1:string, s2:string)
requires leq_string(s1,s2)  && leq_string(s2,s1) 
ensures s1 == s2
{
if s1 != "" && s2 != "" { antisym_leq_string_Lemma(s1[1..],s2[1..]); }
}


predicate method leq_NNF_Formula (alpha:NNF_Formula, beta:NNF_Formula)
{
if family(alpha) < family(beta) then true
else if family(alpha) > family(beta) then false
else if family(alpha) <= 1 then true
else if 2 <= family(alpha) <= 3 then leq_string(alpha.prop,beta.prop) 
else if 4 <= family(alpha) <= 7 || 10 <= family(alpha) <= 11 then leq_NNF_Formula(alpha.f,beta.f) 
else leq_NNF_Formula(alpha.f1,beta.f1) && (alpha.f1 == beta.f1 ==> leq_NNF_Formula(alpha.f2,beta.f2)) 
}

lemma minimum_formula_Lemma (s:set<NNF_Formula>)
requires s != {}
ensures exists phi :: phi in s && forall psi :: psi in s-{phi}  ==> (leq_NNF_Formula(phi,psi) && psi != phi)

function method pick_minimum_formula(s: set<NNF_Formula>): NNF_Formula
requires s != {}
{
minimum_formula_Lemma(s); 
var phi :| phi in s && forall psi :: psi in s-{phi}  ==> (leq_NNF_Formula(phi,psi) && psi != phi);
phi
}

为清楚起见，我省略了引理的证明，但它是可以证明的。为了确保唯一性，我还稍微复杂了引理的保证。在以前的 Dafny 版本中，这也适用：确保存在 phi :: phi in s && forall psi :: psi in s ==> leq_NNF_Formula(phi,psi).

我需要对 NNF_Formula 的集合进行某种迭代，在 Dafny 3.1.0 上是否有不同的方法来执行此操作？

Answer 1

这个错误当然可以更清楚。

只有函数方法不允许这种情况。不过你可以写成普通的method就可以了

method pick_minimum_formula(s: set<NNF_Formula>) returns (nnf: NNF_Formula)
requires s != {}
{
minimum_formula_Lemma(s); 
var phi :| phi in s && forall psi :: psi in s-{phi}  ==> (leq_NNF_Formula(phi,psi) && psi != phi);
nnf := phi;
}

你也可以写成function，这样就可以了。

但是，function method 确实要求任何 let-such-that 表达式都是唯一的。原因是编译后的 let-such-that 表达式可能是不确定的；另一方面，任何函数都必须是确定性的。但是 function method 必须是一个输出与函数结果匹配的方法！如果该方法不确定，则无法保证这一点。

如何在 Dafny 3.1.0 中完成 let-such-that 表达式？

How let-such-that expressions could be done in Dafny 3.1.0?

dafny