我该如何在Java或C#等语言中实现合一算法？

Question

我该如何在Java或C#等语言中实现合一算法？

artificial-intelligencepredicateunification

16

我正在阅读一本人工智能教材，现在来到了这节课最后一个作业题：

"用你所选的任何编程语言实现第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方法中，除了变量它还能是什么？我可以检查空值但与“空列表”有什么不同吗？

有人能帮助我或指点我在C#或Java中实现统一算法的正确方向吗？

- Mithrax

4个回答

1

用继承来表示类型变体是最好的方法。例如，表达式序列仍然只是一个表达式。在序列对象中，空列表将由零长度容器表示。因此，返回 null 表示失败是可以接受的，我用“？”来表示。我不确定 C# 是否实际上有“？”，但应该能理解我的意思。

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

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

编辑：这个列表是协变的。请看这里。我的 Vala 方言支持这个（现在），但我不相信 .net 支持。

- Samuel Danielson

1

在实现算法时，您将使用的变量可能是所谓的元变量。它们是程序中描述其他程序中的变量（或常量、列表等）的变量。因此，您需要使用一个变量来告诉您对象的类型（例如变量、常量）和对象的值。您可以通过继承来实现这一点，就像Samuel Danielson建议的那样，或者通过某种变体对象（如果您的语言提供了该对象），或者手动编写的变体类来描述任何类型的变量（例如，通过描述类型的枚举和各种类型的字段，其中只有一个字段是有效的，取决于类型）。

- Kylotan

0

"

\"...是一个变量\"的意思是检查变量的类型。如果E1的类型是一个变量值（即不是列表类型和常量值），那么就执行某些操作。

"

- user9903

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cdiggins · Accepted Answer

如果有人感兴趣，我在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#语言的Jigsaw库的实现的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风格列表。