概念
我正在实现一个解释器，它允许用户定义任意组合器并将它们应用于任意术语。例如，用户可以通过输入以下组合子定义来定义对的Church 编码：
pair a b c → c a b
true a b → a
first a → a true
然后用户可以输入first (pair a b)，根据之前定义的规则逐步减少：
first (pair a b)
→ pair a b true
→ true a b
→ a
也可以定义其他组合子，例如在SKI 组合子演算中使用的那些：
S x y z → x z (y z)
K x y → x
I x → x
身份组合器也可以根据前两个组合器由I → S S K KorI → S K (K K)或来定义I = S K x。然后可以通过以下方式定义通用iota 组合器：
ι x → x S K
这些例子希望能说明我正在尝试做的事情。
执行
我正在尝试使用图形缩减和图形重写系统来实现这一点。让tree是递归定义的数据类型
tree = leaf | (tree tree)
这是一棵二叉树，其中节点可以是叶子（终端节点）或由一对子树组成的分支（内部节点）。分支代表一个术语对另一个术语的应用，而叶子代表组合子和参数。让我们rule定义一个数据类型
rule = (tree tree)
这对应于将左树转换为右树 (a → b) 的归约规则。的列表rules然后可以定义为
rules = rule | (rule rules)
有效地，当评估一个表达式时pair a b c → c a b，解释器构造一棵(((pair a) b) c)对应于左侧形式的树，一棵对应于右手边形式的树((c a) b)，构造一对对应于 a 的两棵树rule（其中a,b,c以某种方式指定是任意参数，不一定是组合符或终结符号），并将这对附加到列表中rules。当减少形式的表达时first (pair a b)，解释器构造相应的树(first ((pair a) b))并应用归约规则，如下所示：
(first ((pair a) b))
→ (((pair a) b) true)
→ ((true a) b)
→ a
为此，解释器必须对树及其子树执行模式匹配，“移动”组合子和任意参数以构造对应于规则右侧的新树。C中树结构的示例实现由下式给出
struct tree_t {
bool is_leaf;
union {
char* symbol;
struct {
tree_t* left;
tree_t* right;
};
};
};
模式匹配函数可以实现为
bool matches(tree_t* pattern, tree_t* replacement) {
if (pattern -> is_leaf && replacement -> is_leaf)
//do stuff, return a boolean
else if (pattern -> is_leaf && replacement -> is_branch)
//do stuff, return a boolean
else if (pattern -> is_branch && replacement -> is_leaf)
//do stuff, return a boolean
else if (pattern -> is_branch && replacement -> is_branch)
return matches(pattern -> left, replacement -> left) && matches(pattern -> right, replacement -> right);
//The above tests for equality recursively by testing for equality in each subtree.
}
但是，我不确定如何实施此过程的重要细节，包括：
- 将输入树与归约规则的 LHS 树匹配。
- 将输入树转换为归约规则的 RHS 树，保留参数（可能是树叶或树枝）并将它们“移动”到适当的位置。
我相信节点上的模式匹配将涉及检查节点的左孩子和右孩子等等，直到到达终端节点。有谁知道在 C 中实现了类似概念并且我可以从中学习的在线程序或教程？通过这种方法解决问题，我是否走在正确的轨道上，还是有更简单的方法？