Wie kann ich den Vereinigungsalgorithmus in einer Sprache wie Java oder C# implementieren?

Question

arbeite ich durch meine AI Lehrbuch Ich habe und ich habe für meinen Abschnitt zum letzten Hausaufgabe Problem kommen: „Implementieren des Unifikationsalgorithmus auf Seite skizzierte 69 in jeder Sprache Ihrer Wahl“

Auf Seite 69 haben Sie den folgenden Pseudo-Code für den Unifikationsalgorithmus:

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 

Jetzt verstehe ich das allgemeine Konzept der Vereinigung, aber ich habe absolut keine Ahnung, wie ich selbst, dies umzusetzen beginnen würde, in einer Sprache wie Java oder C#.

Ich bin nicht einmal sicher, wie die Methodensignatur aussehen würde. Welche Art von Variablen würde es brauchen? Ich bin mir ziemlich sicher, dass ich Listen zurückgeben muss, um Prädikat-Kalkül-Konstrukte darzustellen, aber das ist eine Vermutung.

Zum Beispiel, wenn es sagt "E1 ist eine Variable", nun, wenn ich es in die Unify-Methode übergebe, wie könnte es alles andere als sein? Ich könnte nach Null suchen, aber wäre das anders als "leere Liste"?

Kann mir jemand helfen oder in die richtige Richtung zeigen, um den Unificaiton-Algorithmus in C# oder Java zu implementieren?

Answer 1

Die beste Möglichkeit zur Darstellung von Typvarianten ist die Vererbung. Zum Beispiel ist eine Folge von Ausdrücken immer noch nur ein Ausdruck. Eine leere Liste würde durch einen Container mit der Länge Null im Sequenzobjekt dargestellt. Die Rückgabe von null ist daher akzeptabel für einen Fehler, den ich mit "?" Angeben kann. Ich bin mir nicht sicher, ob C# tatsächlich ein '?' Hat, aber sollte die Drift bekommen.

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

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

EDIT: Die Liste ist kovariant. Siehe here. Mein Vala-Dialekt von C# unterstützt dies (vorerst), aber ich glaube nicht, dass .net das tut.

Answer 2

Die Variablen, die Sie bei der Implementierung des Algorithmus verwenden, sind vielleicht die Metavariablen, die Sie nennen könnten. Sie sind Variablen in Ihrem Programm, die eine Variable (oder eine Konstante, eine Liste usw.) in einem anderen Programm beschreiben. Daher müssen Sie eine Variable verwenden, die den Typ des Objekts (z. B. Variable, Konstante) und den Wert des Objekts angibt. Sie können dies über die Vererbung tun, wie Samuel Danielson vorgeschlagen hat, oder über eine Art von Variant-Objekt, wenn Ihre Sprache eine bietet, oder eine handrollierte Variantenklasse, die jeden Typ von Variablen beschreiben kann (zB über eine enum, die den Typ und a beschreibt Vielzahl typisierter Felder, von denen je nach Typ nur eine gültig ist.

Answer 3

Das "... ist eine Variable" bedeutet, dass der Typ der Variablen überprüft wird. Wenn der Typ von E1 ein variabler Wert ist (d. H. Nicht von der Typenliste und nicht ein konstanter Wert), dann tue etwas.

Answer 4

Für alle Interessierten fand ich den gleichen Algorithmus bei http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html mit ein bisschen mehr Kontext.

Lets in der ersten Zeile sehen:

function unify(E1, E2) 

E1 und E2 sind Ausdrücke: entweder Listen, Variablen oder Konstanten. Im traditionellen OOP-Stil würden wir normalerweise eine abstrakte Basisklasse Expression erstellen und daraus andere Klassen wie List, Variable oder Constant ableiten. Meiner Meinung nach ist das Overkill. Ich habe dies in C# mit dem Schlüsselwort dynamic implementiert.

Die nächste Frage ist, was es zurückgibt? Eine Liste von Bindungen, die als Dictionary<string, Object> implementiert werden können.

Unten ist ein Ausschnitt aus der C# -Implementierung einer Implementierung aus einer Bibliothek namens Jigsaw, die ich entwickle, um zu lehren, wie man Sprachen C# implementiert.

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

Sie können den Rest des Algorithmus Code online unter http://code.google.com/p/jigsaw-library/source/browse/trunk/Unifier.cs finden. Nicht, dass in diesem Beispiel die Klasse List tatsächlich eine Liste im Lisp-Stil ist, die ich für die Bibliothek implementiert habe.