artificial-intelligence - 如何用 Java 或 C# 等语言实现统一算法？

Question

我正在阅读我得到的 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 是一个变量”时，如果我将它传递给 Unify 方法，它怎么可能不是呢？我可以检查 null 但这会与“空列表”不同吗？

谁能帮助我或指出正确的方向以在 C# 或 Java 中实现 Unificaiton 算法？

Answer 1

对于任何感兴趣的人，我在
http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html有更多的上下文。

让我们看看第一行:

function unify(E1, E2)

E1 和 E2 是表达式:列表、变量或常量。在传统的 OOP 风格中，我们通常会创建一个抽象基类 Expression并从中派生出其他类，如 List , Variable , 或 Constant .然而，在我看来，这是矫枉过正。我在 C# 中使用 dynamic 实现了这个。关键词。

下一个问题是它返回了什么？可以实现为 Dictionary<string, Object> 的绑定(bind)列表.

下面是来自名为 Jigsaw 的库的 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 class 实际上是我为库实现的 Lisp 样式列表。