functional-programming - 实现组合器演算

Question

概念
我正在实现一个解释器，允许用户定义任意 combinators并将它们应用于任意术语。例如，用户可以定义 Church encoding for pairs通过输入以下组合子定义:

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 combinator calculus 中使用的组合器。 :

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 combinator然后可以定义为:

ι x → x S K

这些示例有望说明我正在尝试做的事情。
执行
我正在尝试使用 graph reduction 来实现这一点和一个 graph rewriting系统。让 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) 的树对应于右手边，构造一对对应于 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 树，保留参数(可能是叶子或 Twig )并将它们“四处移动”到适当的位置。

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

Answer 1

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

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

SICP 中描述的模式匹配方法在 C 中也能正常工作，但您可能会发现对字典使用可变数据结构更容易。见 https://mitpress.mit.edu/sicp/full-text/sicp/book/node99.html