问题标签 [implicit-state-passing]

我经常在 Prolog 中编写代码，其中涉及一些算术计算（或在整个程序中很重要的状态信息），首先获取存储在谓词中的值，然后重新计算值，最后使用存储值retractall，assert因为在 Prolog 中，我们不能使用两次为变量赋值is（因此几乎每个需要修改的变量都是全局的）。我开始知道这在 Prolog 中不是一个好习惯。对此我想问：

1. 为什么在 Prolog 中这是一种不好的做法（尽管我自己不喜欢通过上述步骤只是为了拥有一种灵活的（可修改的）变量）？

2. 有哪些一般方法可以避免这种做法？小例子将不胜感激。

PS我刚开始学习Prolog。我确实有 C 等语言的编程经验。

为进一步澄清而编辑

下面给出了我想说的一个不好的例子（在 win-prolog 中）：

然后我们可以像这样查询：

在这里，这是非常琐碎的，但在实际程序和应用中，上述全局变量的方法变得不可避免。有时，上面给出的列表如assert(value(0))... 会变得很长，其中包含更多用于定义更多变量的断言谓词。这样做是为了使不同函数之间的值通信成为可能，并在程序运行期间存储变量的状态。

最后，我还想知道一件事：尽管您提出了各种避免方法，但上述做法何时变得不可避免？

长序列和短序列之间的距离是短序列与长序列的任何与短序列长度相同的子序列之间的最小距离。

我使用的距离是我认为的曼哈顿距离。（但这应该不重要，因为我希望能够改变距离函数）。

第一个版本展示了一个简单的实现，没有提前放弃。我生成所有相同长度的子序列，映射它们以找到它们与短序列之间的距离，然后使用 aggregate/3 找到最小值。

示例查询：

这个下一个版本应该更有效，因为一旦距离超过已经找到的最小值，它将放弃计算长序列的子序列和短序列之间的距离。

询问：

但是在这里我使用了 assert 和 Retract，所以我想要一个执行相同算法但没有这些算法的版本。我认为我应该能够使用带有半上下文符号的 dcg 来做到这一点，但发现很难掌握......我如何跟踪我通过回溯生成的子序列以及最小距离的“状态”到目前为止找到了吗？

我遇到的问题.. seq_subseq/2 是通过回溯生成子序列。测试的第一个子序列需要设置为最小距离。然后我想循环，所以回溯生成另一个序列。但要回溯，我必须失败。但是我不能带回到目前为止的最小距离来检查下一个序列。

如果我不想使用回溯，我想我需要定义一个状态转换谓词来按顺序生成子序列。

眼下

所以我想我需要定义一个关系：

这将像：

和

但我需要以一种有效的方式做到这一点。

更新- 感谢 Mat 的回答，我现在有了这个，我认为这是一个很大的改进。谁能看到对此的进一步改进？我有一个双嵌套 -> 结构和一个！在 accumulate_dis/4 定义中，这两者看起来都很难看。我还让它返回长序列的子序列，它是距短序列最短的距离。

它需要使用非整数，所以我认为 clpfd 不合适。

询问：

这个问题从 Mat对算法改进的回答开始另一个是二进制节点的数量。

虽然我能够通过使用Listing/1和线程额外的状态变量来得出一个解决方案：

注意：请参阅下面的 Prolog 输出。

我对使用length/2作为约束不满意，因为它的使用并不明显，而且它没有使用 DCG。从以前对其他问题的其他尝试中，我知道使用数字作为约束会失败，例如

然而，在搜索时，我发现CLP(FD) 与 DCG 一起使用，并决定尝试一下。

但是，这会导致无限循环不返回任何结果。
注意：我了解 CLP(FD) 的概念，但我对它的实际使用几乎没有。

所以问题是：

1. CLP(FD) 可以与此解决方案一起使用吗？如果可以，如何使用？
2. 如何将非 DCG 解决方案转换回 DCG 版本？

补充

起始代码和清单

序言输出

答案列表

对于那些不熟悉 DCG 的人来说，Prolog 工具箱中的一个导入工具是 Listing /1，它将 DCG 转换为标准 Prolog。

例如

对于以下清单，我还手动更改了变量的名称，以便更容易理解和理解。当 DCG 转换为标准 Prolog 时，两个额外的变量可能会作为谓词的最后两个参数出现。在这里，我改变了他们的名字。它们将从S0倒数第二个参数开始，然后按S1、S2等顺序进行，直到它们成为最后一个参数。此外，如果输入参数之一通过代码进行线程化，我已经更改了名称，例如UtoU0等等。我还添加了 clp(fd) 约束作为注释。

在部分答案中使用Listing/1 ：

对 SWI-Prolog 源代码的引用

如果您想查看将 clp(fd) 或 DCG 转换为标准 prolog 的源代码，请点击此处的链接。

• clp(fd)
• 直流电

笔记

将这些视为我的个人笔记，以防我将来必须回到这个问题。如果他们能帮助别人，把他们留给我自己是没有意义的。

关于

什么时候需要使用 length/2 来限制 DCG 结果的大小，什么时候可以使用 CLP(FD)？

在查看使用 clp(fd) 作为约束的代码列表后，我可以开始理解为什么要使用构建并行列表和使用length/2。我没想到代码会那么复杂。

关于 clp(fd) 如何避免导致错误

参数没有充分实例化 1=:=_2692

可以看出它检查变量是否被绑定

例如

代码的演变

根据@lurker 的回答，我能够将代码演变成这样，即能够在给定一元操作列表、二元操作列表和终端列表的情况下生成唯一一元二叉树的所有组合。虽然它可以生成表达式的组合，但它仍然需要一个中间步骤来重新排列三个列表中的项目的顺序，然后才能用于生成我需要的表达式。

这是我需要的部分

这是一个很好的快速方法，可以看出它们是独一无二的。

如果您一直在阅读评论，那么您就会知道可以仅将一个列表用作约束或不将列表用作约束。

如果您禁用列表作为约束使用

你得到

和

无论哪种方式都是有用的，出于与使用它们的项目相关的原因，我只是对从约束生成的那些有个人偏好。

下一个演变来自于参考 Mat 的答案。

我不会显示结果或详细解释这一点，因为此时它应该是微不足道的。值得注意的是，它会生成两种不同类型的结果，第一种是列表，第二种是复合词。

原创5题

原始问题有 5 个部分，但不是为该答案创建一个新问题，而是删除了该问题的部分内容，以便 lurker 给出的答案可以保留在这里。

1. CLP(FD) 可以与此解决方案一起使用吗？如果可以，如何使用？
2. 什么时候需要使用 length/2 来限制 DCG 结果的大小，什么时候可以使用 CLP(FD)？
3. 还有什么其他方法可以用 DCG 引起迭代深化？
4. 如何将非 DCG 解决方案转换回 DCG 版本？
5. 随着我的 DCG 变得越来越复杂，我将需要更多的约束变量。是否有关于如何处理此问题的标准做法，或者只是遵循冲洗和重复方法？

这是Mat 的回答中的一个较早问题的后续问题

从此开始

然后阅读

对于一个变量，使用一个包含仅包含该变量的单个元素的列表。如果要传递多个变量，请使用包含 f(...) 形式的单个项的列表，捕获所有要传递的变量。这也很值得提出自己的问题。

演变成这样

哪个有效，但要注意use a list that contains a single term of the form f(...)，这里f(...)不在列表中。

我是不是哪里出错了？

补充

参考

• Markus Triska在美国思考
• Markus Triska 的Prolog DCG 入门
• 立即学习 Prolog 的额外参数！

隐式状态传递的变量名称约定

通常在使用隐式状态传递时，变量被命名

S0→ S1→…→S

但是对于我的一元二叉树示例，我将它们命名为

S0→ S1→…→Sn

以Sn代替结尾S。

例如

标准

这里

原因是这个例子有一个相当罕见的属性，即每个 DCG 谓词的长度都在增加，

例如

所以结尾xn给了我对准确性的另一次检查。

参考：ISO/IEC DTR 13211–3:2006 定句语法规则

6.1.3 终端序列的变量名约定

此 TR 使用名为 S0、S1、...、S 的变量来表示在处理语法规则或将语法规则扩展为子句时用作参数的终端序列。在这种表示法中，变量 S0、S1、...、S 可以看作是一系列状态，其中 S0 代表初始状态，变量 S 代表最终状态。因此，如果变量 Si 表示给定状态下的终端序列，则变量 Si+1 将表示用语法规则解析 Si 后剩余的终端序列。