实现组合子演算

Question

概念

我正在实现一个解释器,允许用户定义任意组合器并将它们应用于任意术语.例如,用户可以通过输入以下组合子定义来定义对的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 K或I ? 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.
}

但是,我不确定如何实施此过程的重要细节,包括:

1. 将输入树与缩减规则的LHS树匹配.
2. 将输入树转换为缩减规则的RHS树,保留参数(可以是叶子或分支)并"将它们四处移动"到适当的位置.

我相信节点上的模式匹配将涉及检查节点的左子节点和右子节点,等等,直到到达终端节点.有没有人知道在C中实现了类似概念的在线程序或教程,我可以从中学到什么？我是否正在通过这种方法解决问题的正确轨道,还是有更简单的方法？

Answer 1

您需要分两个单独的步骤进行。模式匹配器将模式与树进行匹配，并构建将模式中的变量映射到树中的值的字典。

然后，将该字典传递给一个单独的函数，该函数通过用字典中的值替换变量来填充替换。

SICP 中描述的模式匹配方法在 C 中可以很好地工作，尽管您可能会发现使用字典的可变数据结构更容易。请参阅https://mitpress.mit.edu/sicp/full-text/sicp/book/node99.html