查找 Alloy 谓词执行的实例

Question

是否可以搜索从给定状态到另一个约束状态的谓词执行（谓词应用程序序列）的实例？

一个有点相关的问题：有没有办法将谓词作为参数传递给另一个谓词？

Answer 1

您并不完全清楚您在寻找什么，至少对于像我这样的 reader 来说，我认为谓词是评估的东西，而不是执行.

Is it possible to search for instances of predicate executions ... ?

听起来好像您正在寻找 Jackson 的 Software Abstractions 第 2.4 节 "Execution traces" 和其他地方讨论的那种东西（参见 "trace"在索引中）。基本思路是

定义一个描述初始状态的谓词（Jackson 的示例称之为 init）
定义一组谓词，描述从一个状态到另一个状态的可能转换
对状态进行总排序

定义一个谓词来检查大致采用

形式的执行跟踪

pred traces {
  init [first] /* 'first' is defined by util/ordering[State] */
  all s : State - last 
    | let s' = next[s]
    | Possible_Transition[s, s']
}

许多变化当然是可能的。

is there a way to pass a predicate as argument to another predicate?

否，是。

否，因为Alloy使用一阶逻辑；谓词的所有参数都是原子集，扩展定义。

是的，因为我们当然可以通过制作一个将 1:1 映射到一组谓词的签名来具体化谓词，并在任何时候想要传递谓词时传递该签名的原子。鉴于人们想要以这种方式具体化的谓词数量有限，这总是可能的。（如果这一点和下面的解释对你来说非常明显，请原谅；我记得有一段时间它们对我来说不是非常明显，我希望 Stack Overflow 有一些 reader 对他们来说它们并不明显.)

假设我们有两个谓词 P 和 Q，每个谓词都有一个类型为 Atom 的原子参数 a。我们希望定义一个元谓词 M，它接受一个原子 x 和一个谓词 Y 和 returns Y[x].[=23 的值=]

// First some scaffolding 
sig Atom {}
pred P [a : Atom] { ... // whatever you like }
pred Q [a : Atom] { ... // whatever ... }

// Now the heart of the matter
abstract sig reification {}
one sig p, q extends reification {}

pred M [x : Atom, Y : reification] {
  (Y = p) implies P[x]
  else (Y = q) implies Q[x]
  else x != x
}

根据您希望将谓词作为参数传递的原因，您可能会合理地将此作为这样做的一种方式，或者作为您可能不想以这种方式进行的原因的证明。如果高阶谓词是您想考虑的关键部分，那么像 Alloy 这样的一阶系统可能不是最佳匹配。

但与其他一阶系统一样，Alloy 可以通过一些谨慎和努力来支持高阶参数。当我们应用 Alloy 来表明给定设计具有属性 P 时，我们在最常见的情况下支持这样一种说法，即设计的所有正确实现也将具有属性 P，在 Alloy 中的声明可能采用 all i : Implementation | correctly_implements_design[i] implies has_property_P[i] 的形式。但是实现是（稍微简化）输入和输出之间的关系。因此，任何关于实现的陈述都是二阶声明。因此，在概括给定设计的所有实现时，我们正在制作一阶参数（在 Alloy 模型中表示）来支持二阶声明。

如果您对使用 Alloy 对二阶命题进行论证有浓厚的兴趣，您将需要查阅 Jackson 书中的第 3.2.3、5.2.2 和 5.3 节。

查找 Alloy 谓词执行的实例

Finding instances of Alloy predicate executions

alloy