prolog - 复杂抽象语法树的术语顺序

Question

我有一个关于抽象语法树的问题。
特别是我想用特定的术语顺序对几棵树进行排序。

如何为具有以下属性的 AST 定义术语顺序：

1. 对于几乎所有术语，顺序的行为与标准的内置术语顺序完全相同。
2. 深深嵌套在 AST 中的是仿函数 pos/6 的术语，它们表示源位置。这些函子应该在项顺序中被忽略，即函子 pos 的所有项应该比较相等。

是否可以使用 'pos' 的特殊情况来扩展内置术语顺序？

什么是最有效的解决方案，什么是最易读的解决方案？

也许我还应该提到我们的 AST 可能非常大，我只是对一个 AST 进行了基准测试，它有 217479 个适当的函子（忽略零原子）

Answer 1

我将定义一个关系ast_without_pos/2 ，它将 ASTA0与一个术语A相关联，A0除了所有 pos/6 子术语都被相同的术语替换，比如 atom t，然后在这些结果术语上使用标准术语顺序。我认为这是非常易读的，而且效率也相当高。

Answer 2

你可以看看 AST 上的 Zippers 吗？

这是列表的示例：

http://blog.logtalk.org/2013/04/zipper-lists-in-prolog/

如果你得到 Termite 的源代码，我想你会发现一个比树更通用的实现。

http://www.complang.tuwien.ac.at/adrian/termite/Manual/Contents.html

对你有什么帮助吗？