如何用Java或C#等语言实现统一算法? [英] How can I implement the unification algorithm in a language like Java or C#?

问题描述

我正在阅读自己的AI教科书，并且本节中遇到了最后一个家庭作业问题:

I'm working through my AI textbook I got and I've come to the last homework problem for my section:

以您选择的任何一种语言来实现第69页上概述的统一算法."

"Implement the Unification Algorithm outlined on page 69 in any language of your choice."

在第69页上，您具有以下用于统一算法的伪代码:

On page 69, you have the following pseudo-code for the unification algorithm:

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#这样的语言来实现统一.

Now, I understand the general concept of unification but I have absolutely no idea how I would even begin to implement this in a language like Java or C#.

我什至不确定方法签名是什么样子.它需要哪种类型的变量?我相当确定我需要返回列表来表示谓词演算构造，但这只是一个猜测.

I'm not even sure what the method signature would look like. What type of variables would it take? I'm fairly certain I need to return lists to represent predicate calculus constructs but that is a guess.

例如，当它说"E1是一个变量"时，如果我将其传递给Unify方法，它怎么可能呢?我可以检查是否为null，但这是否与空列表"不同?

For example, when it says "E1 is a variable", well, if I'm passing it into the Unify method, how could it be anything but? I could check for null but would that be different than "empty list"?

有人可以帮助我或为我指出在C#或Java中实现Unificaiton算法的正确方向吗?

Can anyone help me or point me in the right direction for implementing the Unificaiton algorithm in C# or Java?

推荐答案

对于有兴趣的人，我在以下地方找到了相同的算法 http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html 和更多上下文.

For anyone interested I found the same algorithm at http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html with a bit more context.

让我们看一下第一行:

function unify(E1, E2)

E1和E2是表达式:列表，变量或常量.通常，在传统的OOP风格中，我们将创建一个抽象基类Expression并从中派生其他类，例如List，Variable或Constant.但是，我认为这太过分了.我使用dynamic关键字在C#中实现了这一点.

E1 and E2 are expressions: either lists, variables, or constants. In traditional OOP style typically we would create an abstract base class Expression and derive other classes from it like List, Variable, or Constant. However in my opinion this is overkill. I implemented this in C# using the dynamic keyword.

下一个问题是它返回什么? 绑定的列表，可以将其实现为Dictionary<string, Object>.

The next question is what does it return? A list of bindings which can be implemented as a Dictionary<string, Object>.

下面是C#实现中的摘录，该摘录来自名为拼图的库的实现我正在为教如何实现C#语言而开发.

Below is a snippet from the C# implementation of an implementation from a library called Jigsaw that I am developing for teaching how to implement languages 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样式列表.

You can find the rest of the algorithm code online at http://code.google.com/p/jigsaw-library/source/browse/trunk/Unifier.cs. Not that in this example the List class is actually a Lisp-style list that I implemented for the library.

这篇关于如何用Java或C#等语言实现统一算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！