如何高效计算含“空洞”的两棵树的meet运算？

核心规则回顾 #

先明确meet运算的定义：

• meet(ty, ?) = ty，直接保留非空洞树
• meet(?, ty) = ty，同上
• meet(Int, Int) = Int、meet(Bool, Bool) = Bool，同类型叶子节点直接匹配
• 函数类型：meet(ty1 -> ty2, ty1' -> ty2') = meet(ty1,ty1') -> meet(ty2,ty2')，递归处理参数与返回值
• 乘积类型：meet(ty1 * ty2, ty1' * ty2') = meet(ty1,ty1') * meet(ty2,ty2')，递归处理左右成员
• 其余情况（如Int与Bool、函数与乘积类型不匹配）直接抛出错误

当前实现的优化方向 #

你当前采用的DFS同步遍历+三指针思路是可行的，但可以从以下几个点优化效率：

1. 避免不必要的内存复制

如果类型树是不可变的，遇到空洞时无需复制整个子树，直接复用原树的指针即可，大幅减少内存分配与拷贝开销：

if (tree1->tag == TAG_HOLE) return tree2;
if (tree2->tag == TAG_HOLE) return tree1;

若树是可变结构，再考虑深拷贝子树，避免原树修改影响结果。

2. 提前错误检测

在递归遍历前先检查节点类型是否匹配，不匹配直接抛出错误，避免无效递归：

if (tree1->tag != tree2->tag) {
    // 排除其中一个是空洞的情况后，类型不匹配
    if (tree1->tag != TAG_HOLE && tree2->tag != TAG_HOLE) {
        fprintf(stderr, "Meet运算未定义：类型标签%d与%d不匹配\n", tree1->tag, tree2->tag);
        exit(EXIT_FAILURE);
    }
}

3. 标记联合的高效访问

用C标记联合实现类型树时，直接通过标签访问对应成员，避免冗余指针运算。示例结构定义：

typedef enum {
    TAG_INT,
    TAG_BOOL,
    TAG_FUN,
    TAG_PROD,
    TAG_HOLE
} TypeTag;

typedef struct TypeTree TypeTree;

struct TypeTree {
    TypeTag tag;
    union {
        // 函数类型：参数+返回值
        struct { TypeTree* param; TypeTree* ret; } fun;
        // 乘积类型：左+右成员
        struct { TypeTree* left; TypeTree* right; } prod;
    } data;
};

访问时直接根据标签取union成员，比如处理函数类型：

case TAG_FUN: {
    TypeTree* param_meet = meet(tree1->data.fun.param, tree2->data.fun.param);
    TypeTree* ret_meet = meet(tree1->data.fun.ret, tree2->data.fun.ret);
    TypeTree* res = malloc(sizeof(TypeTree));
    res->tag = TAG_FUN;
    res->data.fun.param = param_meet;
    res->data.fun.ret = ret_meet;
    return res;
}

4. 内存池优化分配

如果频繁创建类型树节点，用内存池替代malloc/free，减少内存碎片与分配开销。比如预先分配一块连续内存，按需取用，最后统一释放。

完整实现示例 #

#include <stdio.h>
#include <stdlib.h>

typedef enum {
    TAG_INT,
    TAG_BOOL,
    TAG_FUN,
    TAG_PROD,
    TAG_HOLE
} TypeTag;

typedef struct TypeTree TypeTree;

struct TypeTree {
    TypeTag tag;
    union {
        struct { TypeTree* param; TypeTree* ret; } fun;
        struct { TypeTree* left; TypeTree* right; } prod;
    } data;
};

// 创建叶子节点
TypeTree* create_leaf(TypeTag tag) {
    TypeTree* t = malloc(sizeof(TypeTree));
    t->tag = tag;
    return t;
}

// 创建函数类型节点
TypeTree* create_fun(TypeTree* param, TypeTree* ret) {
    TypeTree* t = malloc(sizeof(TypeTree));
    t->tag = TAG_FUN;
    t->data.fun.param = param;
    t->data.fun.ret = ret;
    return t;
}

// 创建乘积类型节点
TypeTree* create_prod(TypeTree* left, TypeTree* right) {
    TypeTree* t = malloc(sizeof(TypeTree));
    t->tag = TAG_PROD;
    t->data.prod.left = left;
    t->data.prod.right = right;
    return t;
}

// 创建空洞节点
TypeTree* create_hole() {
    return create_leaf(TAG_HOLE);
}

// 错误处理
void meet_error(TypeTree* t1, TypeTree* t2) {
    fprintf(stderr, "Meet运算未定义：类型标签%d与%d不匹配\n", t1->tag, t2->tag);
    exit(EXIT_FAILURE);
}

// Meet运算核心实现
TypeTree* meet(TypeTree* t1, TypeTree* t2) {
    // 处理空洞情况
    if (t1->tag == TAG_HOLE) return t2;
    if (t2->tag == TAG_HOLE) return t1;

    // 类型不匹配，抛出错误
    if (t1->tag != t2->tag) {
        meet_error(t1, t2);
    }

    switch (t1->tag) {
        case TAG_INT:
        case TAG_BOOL:
            // 同类型叶子直接复用原节点（不可变前提下）
            return t1;
        case TAG_FUN: {
            TypeTree* param = meet(t1->data.fun.param, t2->data.fun.param);
            TypeTree* ret = meet(t1->data.fun.ret, t2->data.fun.ret);
            return create_fun(param, ret);
        }
        case TAG_PROD: {
            TypeTree* left = meet(t1->data.prod.left, t2->data.prod.left);
            TypeTree* right = meet(t1->data.prod.right, t2->data.prod.right);
            return create_prod(left, right);
        }
        default:
            meet_error(t1, t2);
            return NULL; // 永远不会执行到这里
    }
}

// 辅助打印类型树
void print_type(TypeTree* t) {
    switch (t->tag) {
        case TAG_INT: printf("Int"); break;
        case TAG_BOOL: printf("Bool"); break;
        case TAG_FUN:
            printf("(");
            print_type(t->data.fun.param);
            printf(" -> ");
            print_type(t->data.fun.ret);
            printf(")");
            break;
        case TAG_PROD:
            printf("(");
            print_type(t->data.prod.left);
            printf(" * ");
            print_type(t->data.prod.right);
            printf(")");
            break;
        case TAG_HOLE: printf("?"); break;
    }
}

int main() {
    // 测试用例：meet((Int->Bool), (?->Bool)) = Int->Bool
    TypeTree* t1 = create_fun(create_leaf(TAG_INT), create_leaf(TAG_BOOL));
    TypeTree* t2 = create_fun(create_hole(), create_leaf(TAG_BOOL));
    TypeTree* res = meet(t1, t2);
    print_type(res); // 输出 (Int -> Bool)
    printf("\n");
    return 0;
}

额外注意事项 #

• 若类型树需支持修改，遇到空洞时必须深拷贝子树，避免原树被修改影响结果。
• 可添加引用计数机制管理节点内存，避免内存泄漏。
• 对于大型类型树，可缓存已计算的meet结果（记忆化），避免重复递归计算相同树对。

内容的提问来源于stack exchange，提问作者José Romero