我如何用Java或C#语言实现统一算法?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (14)

我正在通过我的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算法吗?

提问于
用户回答回答于

表示类型变体的最好方法是继承。例如,一系列表达式仍然只是一个表达式。一个空列表将由序列对象中的零长度容器表示。因此,返回null表示失败,我用'?'表示。我不确定C#实际上是否有'?',但应该得到漂移。

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

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

名单是covariant。看到这里。我的Vala方言C#支持这个(现在),但我不相信.net。

用户回答回答于

对于任何感兴趣的人,我都可以在http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html找到相同的算法, 并提供更多的上下文。

让我们看看第一行:

function unify(E1, E2)

E1和E2是表达式:列表,变量或常量。在传统的面向对象编程风格通常,我们将创建一个抽象基类Expression和派生其他类从中喜欢ListVariableConstant。但在我看来,这是过度杀伤力。我使用dynamic关键字在C#中实现了这一点。

接下来的问题是它返回了什么?一个可以作为a实现的绑定列表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风格的列表。

扫码关注云+社区