Implementing the combinator calculus

Question

Concept

I am implementing an interpreter that allows a user to define arbitrary combinators and apply them to arbitrary terms. For example, a user may define the Church encoding for pairs by inputting the following combinator definitions:

pair a b c → c a b
true a b → a
first a → a true

The user may then input first (pair a b), which is reduced step-by-step according to the previously defined rules:

first (pair a b)
→ pair a b true
→ true a b
→ a

Other combinators may also be defined, such as those used in the SKI combinator calculus:

S x y z → x z (y z)
K x y → x
I x → x

The identity combinator could also be defined in terms of the first two combinators by I → S S K K or I → S K (K K) or I = S K x. The universal iota combinator could then be defined by:

ι x → x S K

These examples hopefully illustrate what I am trying to do.

Implementation

I am attempting to implement this using graph reduction and a graph rewriting system. Let tree be a data type defined recursively by

tree = leaf | (tree tree)

This is a binary tree, where nodes may be either leafs (terminal nodes) or branches (internal nodes) consisting of a pair of subtrees. The branches represent the application of a term to another term, while leaves represent combinators and arguments. Let rule be a data type defined by

rule = (tree tree)

This corresponds to a reduction rule that transforms the left tree into the right tree (a → b). The list of rules may then be defined by

rules = rule | (rule rules)

Effectively, when evaluating an expression such as pair a b c → c a b, the interpreter constructs a tree of the form (((pair a) b) c) corresponding to the left hand side, a tree of the form ((c a) b) corresponding to the right hand side, constructs a pair of both trees corresponding to a rule (where a,b,c are somehow specified to be arbitrary parameters and not necessarily combinators or terminal symbols), and appends this pair to the list rules. When reducing an expression of the form first (pair a b), the interpreter constructs the corresponding tree (first ((pair a) b)) and applies the reduction rules as follows:

(first ((pair a) b))
→ (((pair a) b) true)
→ ((true a) b)
→ a

To do this, the interpreter must perform pattern matching on the tree and its subtrees, "moving around" the combinators and arbitrary parameters to construct a new tree corresponding to the right hand side of the rule. An example implementation of the tree structure in C is given by

struct tree_t {
    bool is_leaf;
    union {
        char* symbol;
        struct {
            tree_t* left;
            tree_t* right;
        };
    };
};

A pattern matching function could be implemented as

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.
}

However, I am unsure of how to implement important details of this process, including:

1. Matching an input tree with the LHS tree of a reduction rule.
2. Transforming the input tree into the RHS tree of the reduction rule, preserving parameters (which may be leaves or branches) and "moving them around" around to their appropriate places.

I believe pattern-matching on a node would involve examining the left child and right child of the node and so on, until terminal nodes are reached. Does anyone know of a program or tutorial online that has implemented a similar concept in C and that I could learn from? Am I even on the right track in approaching the problem through this method, or is there a simpler way?

Answer 1

You need to take it in two separate steps. A pattern matcher matches a pattern against a tree, and builds a dictionary mapping variables in the pattern to values in the tree.

Then you pass that dictionary to a separate function that fills in the replacement, by replacing variables with their values from the dictionary.

The pattern matching approach described in SICP will work just fine in C, though you may find it easier to use a mutable data structure for the dictionary. See https://mitpress.mit.edu/sicp/full-text/sicp/book/node99.html