Как реализовать алгоритм унификации на языке Java или С#?

Я работаю через свой учебник по искусству, который я получил, и я пришел к последней проблеме домашних заданий для моего раздела:

"Внедрите алгоритм унификации, описанный на стр. 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 или С#.

Я даже не знаю, как будет выглядеть подпись метода. Какие переменные могли бы потребоваться? Я совершенно уверен, что мне нужно возвращать списки для представления предикатных вычислений, но это предположение.

Например, когда он говорит: "E1 - это переменная", ну, если я передаю его в метод Unify, как это может быть ничего? Я могу проверить значение null, но это будет отличаться от "пустого списка"?

Может ли кто-нибудь помочь мне или указать мне в правильном направлении для реализации алгоритма Unificaiton на С# или Java?

Ответ 1

Для всех, кого это интересует, я нашел тот же алгоритм в http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html с немного большим контекстом.

Давайте посмотрим на первую строку:

function unify(E1, E2)

E1 и E2 - выражения: списки, переменные или константы. Обычно в традиционном стиле ООП мы создадим абстрактный базовый класс Expression и выводим из него другие классы, такие как List, Variable или Constant. Однако, на мой взгляд, это излишне. Я реализовал это на С#, используя ключевое слово dynamic.

Следующий вопрос - что он возвращает? Список привязок, которые могут быть реализованы как Dictionary<string, Object>.

Ниже приведен фрагмент из реализации С# реализации из библиотеки под названием Jigsaw, которую я разрабатываю для обучения тому, как внедрять языки С#.

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, который я реализовал для библиотеки.

Ответ 2

Лучший способ представления вариантов типов - с наследованием. Например, последовательность выражений остается только выражением. Пустой список будет представлен контейнером с нулевой длиной в объекте последовательности. Таким образом, возвращаемое значение null допустимо для отказа, которое я указываю с помощью??. Я не уверен, что на С# есть "?", Но должен получить дрейф.

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

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

EDIT: список ковариантен. См. здесь. Мой диалоги Vala С# поддерживает это (пока), но я не верю, что .net делает.

Ответ 3

Переменные, которые вы будете использовать при реализации алгоритма, возможно, вы можете назвать метапеременными. Это переменные в вашей программе, которые описывают переменную (или константу, или список и т.д.) В какой-либо другой программе. Таким образом, вам нужно использовать переменную, которая сообщает вам тип объекта (например, переменную, константу) и значение объекта. Вы можете сделать это через наследование, предложенное Самуэлем Дэниелсоном, или через какой-то объект Variant, если ваш язык предоставляет один, или ручной класс вариантов, который может описывать любой тип переменной (например, через перечисление, описывающее тип и множество типизированных полей, из которых только один действителен, зависит от типа).

Ответ 4

"... является переменной" означает проверку типа переменной. Если тип E1 является значением переменной (т.е. Не списка типов, а не постоянным значением), тогда сделайте что-то.