17

入手した 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 をチェックすることはできますが、それは「空のリスト」とは異なりますか?

Unificaiton アルゴリズムを C# または Java で実装するために、誰かが私を助けたり、正しい方向に向けたりすることはできますか?

4

4 に答える 4

10

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

Lets look at the first line: 

function unify(E1, E2)

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.

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

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;
}

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.

于 2011-09-11T02:59:33.523 に答える
1

型のバリアントを表す最良の方法は、継承を使用することです。たとえば、一連の式は依然として単なる式です。空のリストは、シーケンス オブジェクト内の長さ 0 のコンテナーによって表されます。したがって、null を返すことは失敗として許容されます。これは「?」で示します。C# に実際に '?' があるかどうかはわかりませんが、ドリフトを取得する必要があります。

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

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

編集: リストは共変です。ここを参照してください。私の C# の Vala 方言はこれをサポートしていますが (今のところ)、.net がサポートしているとは思えません。

于 2009-09-08T23:46:35.273 に答える
1

アルゴリズムを実装するときに使用する変数は、おそらくメタ変数と呼ばれるものです。これらは、他のプログラムの変数 (または定数、またはリストなど) を記述するプログラム内の変数です。そのため、オブジェクトのタイプ (変数、定数など) とオブジェクトの値を示す変数を使用する必要があります。サミュエル・ダニエルソンが提案したように継承を介して、または言語が提供する場合はある種の Variant オブジェクトを介して、または任意の型の変数を記述できる手巻きのバリアントクラスを介してこれを行うことができます (たとえば、型を記述する列挙型とタイプに応じて、そのうちの 1 つだけが有効です)。

于 2009-09-10T15:04:55.033 に答える
0

「... は変数です」は、変数の型をチェックすることを意味します。E1 の型が変数値の場合 (つまり、型リストでも定数値でもない場合)、何かを行います。

于 2010-01-22T09:29:28.490 に答える