链接数据结构：限制 link 操作

Question

我有一个带有两个签名的模型（见下文）：Data 和 Node。我定义了一些表征 Node 居民的谓词，即：Orphan、Terminal 和 Isolated。

我想做的 - 但还没有实现 - 是定义一个谓词 Link 来模拟两个节点的 linking 使得一个节点成为后继者（succ) 的另一个。此外，我想限制操作，使得 links 只能对 Isolated 节点进行。此外，我希望限制——如果可能的话——以某种方式内部于Link谓词。

这是我最近的尝试：

sig Data {}

sig Node {
    data: Data,
    succ: lone Node
}

// Node characterisation
pred Isolated (n: Node) { Orphan[n] and Terminal[n] }

pred Orphan (n: Node) { no m: Node | m.succ = n }

pred Terminal (n: Node) { no n.succ }


/*
 * Link
 * 
 * May only Link n to an m, when:
 *  - n differs from m
 *  - m is an Isolated Node (DOES NOT WORK)
 *
 * After the operation: 
 *  - m is the succcessor of n
 */
pred Link (n,m: Node) {
    n != m
    Isolated[m] /* Not satisfiable */
    m = succ[n]
}

pred LinkFeasible { some n,m: Node | Link[n,m] }

run LinkFeasible

包含连词 Isolated[m] 会使模型无法满足。我想我明白为什么：不可能有 Node 既是 Isolated 又是的后继者。我把它包括在内只是希望它能揭示我的意图。

我的问题：如何将 Link 谓词定义为 link 两个节点，以便只有 Isolated 个节点可以 linked-to？

Answer 1

问题是您希望 Link 成为更改 succ 值的操作。为了在 Alloy 中模拟变化，您需要添加一个有序的签名来表示您系统的不同状态。所以你的签名看起来像这样：

open util/ordering[time]

sig Time {}
sig Data {}

sig Node {
    data: Data,
    succ: Node lone -> Time
}

但这也会改变你所有的谓词。你不能说一个节点是孤立的或终端的，你只能说一个节点在时间 T.

是孤立的

如果您有软件抽象，这将在第 6.1 节中介绍。我不熟悉那本书之外 Alloy 中关于建模时间的任何好的指南。

链接数据结构：限制 link 操作

Linked Data Structures: Restricting a link operation

alloy