3

我正在制作一个编译器（用于一种新语言），它通过模式匹配支持 AC 统一。匹配算法已经有效，但是我在函数的逻辑和数学方面以及它的属性方面遇到了麻烦，这将以很好的方式定义语言的设计。我有几个关于函数属性的问题：

关联和交换属性仅适用于二元函数？

例如，如果我声明一个函数 max(a,b)，这将是可交换的，因为 max(a,b) = max(b,a) 并且是关联的，因为 max(a,max(b,c)) = max(max （a，b），c），但我想不出任何具有两个以上满足该公理的参数的函数。例如，我可以定义 max(a,b,c) = max(a,max(b,c)) 这将是一个三元函数，但该语言将能够将它与符合它的二进制操作统一起来。

统一通过将诸如 max(a,max(b,c)) 之类的关联函数简化为可变和规范形式 max(a,b,c) 然后在此规范形式上执行模式匹配，所以所有（我认为) 具有超过 3 个参数的此属性的可能函数实际上是相同二元函数的复合

标识元素是否仅适用于二元函数？

解释：可以有一个可变函数 f(a,b,...)（超过 2 个参数），使得存在满足 f(a,b,c,e) = f(a,b,c) 的元素 e ) 对于没有直接二进制父级的函数（例如加法是二进制的，但编译器将加法管理为内部表示的可变函数）

诸如零之类的统一元素仅在语言中通过删除其对函数的 aparences 进行管理，例如 add(1,2,x,0) ，它表示表达式 1+2+x+0 减少为 1+2+x

这些问题对于在定义规则（例如 a+b = b+a）时自动识别函数的此属性的算法设计以及语言设计和将强加于函数声明的约束（可以是，如果这些问题中的任何一个为假，则不合逻辑

4

1 回答 1

1

查看 AC 和可变函数的一种方法是查看cons列表、袋子和集合的函数：

 cons(a, cons(b, nil)) // depicts a binary tree, a list or a set?
  • 如果cons没有公理，则它是二叉树
  • 如果 cons 是关联的，而不是可交换的，也不是幂等的，那么它就是一个列表。
  • 如果 cons 是关联的和可交换的，那么它是一个包
  • 如果 cons 是关联的、交换的和幂等的，那么它是一个集合。

现在，variadic 函数就像更好的符号一样cons：

  • set(1,2,3,4)cons是 ACI的“更好的符号” 。
  • list(1,2,3,4,1,2,3,4)为一个
  • bag(1,1,2,2,3,3,4,4)交流电

ELAN、Maude、Tom、ASF+SDF 等支持某种“匹配模”的系统在底层使用了这种同余性：它们将具有理论的二元运算符映射到内部数据结构，如列表、集合和包展平递归应用程序，排序和消除重复项等。

于 2013-12-30T11:44:17.073 回答