language-agnostic - 使用关联和交换运算符进行模式匹配

Question

模式匹配(如在 Prolog、ML 系列语言和各种专家系统外壳中发现的)通常通过以严格的顺序逐个元素地匹配查询与数据来进行操作。

然而，在诸如自动定理证明之类的领域中，需要考虑一些运算符是关联的和可交换的。假设我们有数据

A or B or C

并查询

C or $X

按照表面语法，这不匹配，但从逻辑上讲，它应该与 $X 匹配绑定(bind)到 A or B因为 or是关联的和可交换的。

有没有任何语言的现有系统可以做这种事情？

Answer 1

关联交换模式匹配自 1981 and earlier 以来一直存在，仍然是热门话题today .

有很多系统实现了这个想法并使其有用。这意味着当可以使用关联性或交换性来进行模式匹配时，您可以避免编写复杂的模式匹配。是的，它可能很昂贵；模式匹配器自动执行此操作比您手动执行此操作要好。

您可以在 rewrite system for algebra and simple calculus 中查看示例使用我们的程序转换系统实现。在这个例子中，要处理的符号语言由语法规则定义，那些具有 A-C 属性的规则被标记。通过解析符号语言产生的对树的重写会自动扩展为匹配。