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

Question

estoy trabajando a través de mi libro de texto de AI llegué y he llegado al último problema de tarea para mi sección:

"Implementar el algoritmo de unificación se indica en la página 69 en cualquier idioma de su elección."

En la página 69, tiene las siguientes pseudo-có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 la unificación, pero no tengo ni idea de cómo iba a empezar a poner en práctica esta en un lenguaje como Java o C#.

Ni siquiera estoy seguro de cómo se verí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 paso al método Unify, ¿cómo podría ser algo más que eso? Podría verificar nulo pero ¿sería diferente a la "lista vacía"?

¿Alguien me puede ayudar o señalarme en la dirección correcta para implementar el algoritmo de Unificaiton en C# o Java?

Answer 1

La mejor manera de representar las variantes de tipo es con la herencia. Por ejemplo, una secuencia de expresiones sigue siendo 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, la devolución nula es aceptable por falla, que indico con '?'. No estoy seguro si C# en realidad tiene un '?', Pero debería entenderse.

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# lo admite (por ahora), pero no creo que .net lo haga.

Answer 2

Las variables que usará al implementar 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, necesita 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 sugirió Samuel Danielson, o mediante algún tipo de objeto Variant si su idioma lo proporciona, o una clase variante enrollada a mano que puede describir cualquier tipo de variable (por ejemplo, a través de una enumeración que describe el tipo y variedad de campos tipados, de los cuales solo uno es válido, depende del tipo).

Answer 3

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

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.

deja mirada en la primera línea:

function unify(E1, E2) 

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

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

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