我如何能实现像Java或C＃语言的统一算法？(How can I implement the uni

我通过我的AI教科书工作的我，我是来为我部分的最后功课问题：

“实现统一算法在你选择的任何语言69页的概述。”

在69页，你有统一的算法如下伪代码：

function unify(E1, E2);
    begin
        case
            both E1 and E2 are constants or the empty list:
                if E1 = E2 then return {}
                else return FAIL;
            E1 is a variable:
                if E1 occurs in E2 then return FAIL
                 else return {E2/E1}
            E2 is a variable
                if E2 occurs in E1 then FAIL
                    else return {E1/E2}
            either E1 or E2 are empty then return FAIL
            otherwise:
                begin
                    HE1 := first element of E1;
                    HE2 := first element of E2;
                    SUBS1 := unify(HE1, HE2);
                    if SUBS1 := FAIL then return FAIL;
                    TE1 := apply(SUBS1, rest of E1);
                    TE2 := apply(SUBS1, rest of E2);
                    SUBS2 := unify(TE1, TE2);
                    if SUBS2 = FAIL then return FAIL;
                         else return composition(SUBS1, SUBS2)
                end
            end
        end

现在，我明白了统一的通用概念，但我完全不知道我会如何甚至开始像Java或C＃语言来实现这一点。

我甚至不能确定方法签名将是什么样子。它会采取什么样的变数？我敢肯定我需要回到列表来表示谓词演算结构，但是这是一个猜测。

例如，当它说“E1是一个变量”，好吧，如果我通过它进入相结合的方法，怎么会是什么，但？我可以检查空，但是那会是不是“空单”有什么不同？

谁能帮我或点我实现在C＃或Java的Unificaiton算法正确的方向？

Answer 1:

任何有兴趣，我发现在相同的算法http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html带着几分更多的上下文。

让我们看一下第一行：

function unify(E1, E2)

E1和E2都是表达式：对于列，变量或常量。在传统的面向对象编程风格通常，我们将创建一个抽象基类Expression ，并从中获得像其他类List ， Variable或Constant 。然而，在我看来这是矫枉过正。我使用实现了这个在C＃中dynamic关键字。

接下来的问题是什么呢返回？这可以被实现为一个绑定的列表Dictionary<string, Object> 。

下面是从C＃实现从库调用实现的一个片段拼图，我教如何实现语言C＃开发。

public static Dictionary<string, object> Unify(dynamic e1, dynamic e2)
{
    if ((IsConstant(e1) && IsConstant(e2)))
    {
        if (e1 == e2)
            return new Dictionary<string,object>();
        throw new Exception("Unification failed");
    }

    if (e1 is string)
    {
        if (e2 is List && Occurs(e1, e2))
            throw new Exception("Cyclical binding");
        return new Dictionary<string, object>() { { e1, e2 } };
    }

    if (e2 is string)
    {
        if (e1 is List && Occurs(e2, e1))
            throw new Exception("Cyclical binding");
        return new Dictionary<string, object>() { { e2, e1 } };
    }

    if (!(e1 is List) || !(e2 is List))
        throw new Exception("Expected either list, string, or constant arguments");

    if (e1.IsEmpty || e2.IsEmpty)
    {
        if (!e1.IsEmpty || !e2.IsEmpty)
            throw new Exception("Lists are not the same length");

        return new Dictionary<string, object>(); 
    }

    var b1 = Unify(e1.Head, e2.Head);
    var b2 = Unify(Substitute(b1, e1.Tail), Substitute(b1, e2.Tail));

    foreach (var kv in b2)
        b1.Add(kv.Key, kv.Value);
    return b1;
}

你可以在网上找到的算法代码的其余部分http://code.google.com/p/jigsaw-library/source/browse/trunk/Unifier.cs 。这并不是说在这个例子中， List类实际上是我的库中实现一个Lisp风格列表。

Answer 2:

代表型变异的最佳方式是与继承。例如，表达式序列仍然只是一个表达式。空列表将通过在序列对象零长度容器来表示。返回null因此，对于失败，我与表示可以接受“？”。我不知道如果C＃其实有一个“？”，而应该得到的漂移。

abstract class Expression { ... }
class Atom : Expression { ... }
class Variable : Expression { ... }
class Sequence : Expression { List <Expression> ... }

Expression? unify (Expression e1, Expression e2) { ... }

编辑：这份名单是协变的。见这里。 C＃的我的方言瓦拉支持这一（现在），但我不相信.NET一样。

Answer 3:

实现算法时，你将使用的变量，你可以打电话或者什么的元变量。他们是在你的程序，描述一些其他程序中的变量（或常量或列表等）的变量。这样就需要使用一个变量，告诉您的对象（例如，变量，常量）和该对象的值的类型。你可以通过继承来做到这一点塞缪尔·丹尼尔森曾建议，或者通过某种Variant对象，如果你的语言通过描述该类型的枚举和提供一个或手卷变种类，它可以描述任何类型的变量（例如。多种类型的字段，其中只有一个是有效的，依赖于类型）的。