artificial intelligence - ¿Cómo puedo implementar el algoritmo de unificación en un lenguaje como Java o C#?

artificial-intelligence predicate

Question

Estoy trabajando en el libro de texto de AI que obtuve y he llegado al último problema de tarea para mi sección:

"Implemente el algoritmo de unificación descrito en la página 69 en cualquier idioma de su elección".

En la página 69, tiene el siguiente pseudocódigo para el algoritmo de unificación:

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

Ahora, entiendo el concepto general de unificación, pero no tengo la menor idea de cómo podría comenzar a implementar esto en un lenguaje como Java o C #.

Ni siquiera estoy seguro de cómo sería la firma del método. ¿Qué tipo de variables tomaría? Estoy bastante seguro de que necesito devolver listas para representar construcciones de cálculo de predicados, pero eso es una suposición.

Por ejemplo, cuando dice "E1 es una variable", bueno, si lo estoy pasando al método Unify, ¿cómo podría ser otra cosa? Podría verificar que no haya ningún problema, pero ¿sería diferente a "lista vacía"?

¿Puede alguien ayudarme o indicarme la dirección correcta para implementar el algoritmo Unificaiton en C # o Java?

Answer 1

El "... es una variable" significa verificar el tipo de la variable. Si el tipo de E1 es un valor variable (es decir, no es de la lista de tipos y no es un valor constante), entonces haga algo.

Answer 2

La mejor manera de representar variantes de tipo es con herencia. Por ejemplo, una secuencia de expresiones es solo una expresión. Una lista vacía estaría representada por un contenedor de longitud cero en el objeto de secuencia. Por lo tanto, devolver el valor nulo es aceptable para el fallo, que indico con ''?''. No estoy seguro de si C # realmente tiene un ''?'', Pero debería obtener la deriva.

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

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

EDITAR: La lista es covariante. Ver here Mi dialecto Vala de C # admite esto (por ahora), pero no creo que .net lo haga.

Answer 3

Las variables que utilizará cuando implemente el algoritmo son quizás lo que podría llamar metavariables. Son variables en su programa que describen una variable (o constante, o lista, etc.) en algún otro programa. Como tal, debe usar una variable que le indique el tipo de objeto (por ejemplo, variable, constante) y el valor del objeto. Puede hacerlo a través de la herencia, como lo ha sugerido Samuel Danielson, o mediante algún tipo de objeto Variant si su idioma proporciona uno, o una clase de variante manual que puede describir cualquier tipo de variable (por ejemplo, a través de una enumeración que describe el tipo y una variedad de campos escritos, de los cuales solo uno es válido, dependiendo del tipo).

Answer 4

Para cualquier persona interesada, encontré el mismo algoritmo en http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html con un poco más de contexto.

Veamos la primera línea:

function unify(E1, E2)

E1 y E2 son expresiones: listas, variables o constantes. En el estilo tradicional de POO, normalmente crearíamos una Expression clase base abstracta y derivaríamos otras clases como List , Variable o Constant . Sin embargo, en mi opinión, esto es una exageración. Implementé esto en C # usando la palabra clave dynamic .

La siguiente pregunta es ¿qué devuelve? Una lista de enlaces que se pueden implementar como un Dictionary<string, Object> .

A continuación se muestra un fragmento de la implementación en C # de una implementación de una biblioteca llamada Jigsaw que estoy desarrollando para enseñar cómo implementar los lenguajes 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;
}

Puede encontrar el resto del código de algoritmo en línea en http://code.google.com/p/jigsaw-library/source/browse/trunk/Unifier.cs . No es que en este ejemplo, la clase List sea ​​en realidad una lista estilo Lisp que implementé para la biblioteca.