实施统一和跳过变量

Question

我正在以通常的方式实现通常的统一算法：通过表达式树递归下降，沿途将变量绑定添加到散列 table，进行发生检查。在 Java 中，碰巧使用覆盖函数来配合语言的粒度，因此实现中处理变量的部分是：

@Override
public boolean unify(Term a, Map<Var, Term> map) {
    if (this == a) {
        return true;
    }
    Term x = map.get(this);
    if (x != null) {
        return x.unify(a, map);
    }
    if (a instanceof Var) {
        x = map.get((Var) a);
        if (x != null) {
            return x.unify(this, map);
        }
    }
    if (a.occurs(this)) {
        return false;
    }
    map.put(this, a);
    return true;
}

这个版本是正确的，而且在很多情况下都非常快，但是它有一个问题，特别是在使用它进行类型推断时。当将大量变量统一到同一个目标时，它最终会得到一组基本上看起来像这样的绑定：

a=b
b=c
c=d
d=e

然后每次一个新的变量必须统一到同一个东西，它必须一步一步地遍历链才能找到它现在在哪里，这需要O(N)的时间，这意味着统一同一事物的变量集合需要总时间 O(N^2).

可能最好的解决方案是实现某种快捷方式，类似于更新 a 以直接指向当前的最终目标，无论它是什么。如何以一种在所有情况下都正确有效的方式执行此操作并不完全显而易见。

几十年来，统一已经广为人知并得到广泛使用，所以我想解决这个问题的方法也一定已经知道了几十年，但我看到的关于统一的几次讨论似乎都没有提到它。

修改算法的具体处理方式是什么？

Answer 1

我同意捷径是正确的方法。你应该可以改变这个：

    return x.unify(a, map);

对此：

    if (! x.unify(a, map)) {
        return false;
    }
    map.put(this, map.get(x));
    return true;

还有这个：

        return x.unify(this, map);

对此：

        if (! x.unify(this, map)) {
            return false;
        }
        map.put(a, map.get(x));
        return true;

(每个人 map.put 只切掉一层间接，但是因为你在递归调用之后立即这样做，这也将切掉任何不必要的间接，你知道只有一层到的间接寻址。)

这并不能完全防止链，因为可以将 a 与 b 和 then b 与 [=18= 统一起来] 等等;但每条链在随后再次遇到时都会得到充分处理，因此您仍然可以摊销固定时间。

Answer 2

这里有一个想法：所有由 = 连接的变量都是等价的 class。所以你可以制作地图

unify(Term a, Map<VarClass, Term> map) {...

其中 VarClass 是通过 classical union-find algorithm for disjoint sets 实现的。

当您发现以前添加到映射中的变量对 x=y 时，将 x 添加到包含 y 的 VarClass 中（创建一个并在 none 存在的情况下添加一个可变的空占位符映射）。

地图右侧的 Term 绝不是 Var。

联合查找操作出于所有实际目的均摊常数时间并且在实践中相当快。

实施统一和跳过变量

Implementing unification and skipping variables

java

algorithm

performance

unification