Der Rete Algorithmus (2)

“Look, that’s why there’s rules, understand? So that you think before you break ’em.”

Terry Pratchett

Nachdem im ersten Beitrag zum Rete Algorithmus die grundlegende Arbeitsweise beleuchtet wurde, geht es in diesem Beitrag um die Implementierung. Nicht um einen vollständigen OPS 5 Interpreter, sondern um die Bausteine, aus denen ein funktionsfähiges Rete Netz erstellt werden kann.

Dieser Beitrag splittet sich in eine erste Hälfte, in der eine Implementierung vorgenommen wird, die sich dicht an der Beschreibung aus dem ersten Beitrag hält. Im zweiten Teil werden dann einige der Implementierungen durch bessere Konstrukte ersetzt. Frei nach Kent Becks “Make it work, Make it right, Make it fast”.

Der Speicher

Die Elemente des Alpha- und Betaspeichers arbeiten der Einfachheit halber auf Map<String, Object> Instanzen, und entsprechen damit mehr oder weniger den OPS 5 Fakten. Die jeweiligen Typen AlphaHandle und BetaHandle besitzen beide eine ID zum direkten Zugriff und ein deleted Flag für den Einsatz beim Löschen.

public interface BetaHandle {

  List<Map<String, Object>> getValue();

  default boolean isDeleted() {
    return false;
  }

  Long getId();
}

Die Instanzen des BetaHandle arbeiten auf Listen von Map<String, Object> Instanzen, die den Kombinationen entsprechen, die in den Betaknoten erzeugt werden. Die Instanzen des AlphaHandle besitzen zusätzlich ein Typ-Attribute um sie schneller in den richtigen Teil des Rete Netzes zu bugsieren.

public interface AlphaHandle {
  Map<String, Object> getValue();

  Long getId();

  String getType();
  
  default boolean isDeleted() {
    return false;
  }
}

Beide Interfaces haben eine Default Methode isDeleted mit dem Rückgabewert false. Die Implementierungen scheren sich nicht um dieses Flag. Zum Löschen einer AlphaHandle oder BetaHandle Instanz wird die betreffende Instanz in einen Wrapper gesteckt.

public class DeletedAlphaHandle implements AlphaHandle {
  private final AlphaHandle wrapped;
  ...
  @Override
  public boolean isDeleted() {
    return true;
  }
}

Das Alpha Netz

Im Alpha Netz befinden sich die Alpha Knoten und der Alpha Memory. Außerdem werden hier die Fakten in das Netzwerk geschoben. Fangen wir also am besten am Ende der Netzes an.

Die Instanzen der Klasse AlphaMemory empfängt als AlphaNodeAccessor Werte vom Typ AlphaHandle und speichert sie in einer internen Map ab. Danach wird der AlphaHandle an alle angeschlossenen AlphaNodeAccessor weitergeleitet.

 public class AlphaMemory implements AlphaNode {
  private final Map<Long, AlphaHandle> values = new HashMap<>();
  private final List<AlphaNodeAccessor> accessors = new ArrayList<>();

  @Override
  public void handle(AlphaHandle value, MemoryContext context) {
    if (value.isDeleted()) {
      values.remove(value.getId());
    } else {
      values.put(value.getId(), value);
    }
    accessors.forEach(x -> x.handle(value, context));
  }

  @Override
  public <T extends AlphaNodeAccessor> T add(T node) {
    accessors.add(node);
    return node;
  }
}

Für den Fall, dass ein AlphaHandle mit einem deleted Flag erscheint, wird das AlphaHandle nicht hinzugefügt, sondern aus der Map entfernt

Der nächste Insasse des Alpha Netzes ist die Klasse AlphaNodeImpl. Sie ähnelt der Klasse AlphaMemory, speichert jedoch die AlphaHandle nicht. Stattdessen prüft sie, ob der AlphaHandle ein spezielles Predicate erfüllt oder nicht. Nur wenn das Predicate erfüllt ist, wird der AlphaHandle weitergereicht. Diese Knoten dienen als Filter im Alpha Netz.

public class AlphaNodeImpl implements AlphaNode {
  private final Predicate<Map<String, Object>> predicate;
  private final List<AlphaNodeAccessor> successors;

  public AlphaNodeImpl(Predicate<Map<String, Object>> predicate) {
    this.predicate = predicate;
    this.successors = new ArrayList<>();
  }

  @Override
  public void handle(AlphaHandle value, MemoryContext context) {
    if (predicate.test(value.getValue())) {
      successors.forEach(x -> x.handle(value, context));
    }
  }

  @Override
  public <T extends AlphaNodeAccessor> T add(T successor) {
    successors.add(successor);
    return successor;
  }
}

Mit Hilfe des Predicate können beliebige Tests auf den Werten der AlphaHandle Instanz durchgeführt werden.

    AlphaNode rectangle = new AlphaNodeImpl(x -> "red".equals(x.get("color"))));
    AlphaNode square = rectangle.add(new AlphaNodeImpl(x -> x.get("width").equals(x.get("height"))));

Die zwei hier abgebildeten Zeilen für geometrische Formen formulieren die Prüfung auf die Farbe Rot und einen identischen Wert für Breite und Höhe. Besteht ein Rechteck diese Prüfung, dann ist es ein rotes Quadrat.

Das Beta Netz

Im Beta Netz sieht alles ein wenig komplizierter aus, weil die Knoten zwei Eingänge besitzen. Sie bearbeiten also den Fall, dass entweder ein AlphaHandle oder ein BetaHandle hinzukommt. Im Beta Netz existieren die Klassen BetaMemory, AlphaBetaAdapter, BetaNodeImpl und Terminal. Die Klasse BetaMemory speichert, wir ihr Pendant im Alpha Netz, generierte BetaHandle und leitet sie an nachfolgende Knoten weiter. der AlphaBetaAdapter ist ein spezialisierter BetaMemory, der aus eingehenden AlphaHandle einelementige BetaHandle generiert.

Die Klasse Terminal am Ende des Netzwerkes liefert alle Kombinationen (BetaHandle) von Fakten, die zur Aktivierung einer Regel führen.

public class Terminal implements BetaNodeAccessor {
  private final Map<Long, BetaHandle> values = new HashMap<>();

  public Collection<BetaHandle> getValues() {
    return values.values();
  }

  @Override
  public void handle(BetaHandle value, MemoryContext context) {
    if (value.isDeleted()) {
      values.remove(value.getId());
    } else {
      values.put(value.getId(), value);
    }
  }
}

Über die getValues Methode kann die RuleEngine im Match-Resolve-Act Cycle erfragen, welche Regeln aktiviert werden können.

Die wichtigste Klasse im Beta Netz ist die BetaNodeImpl. Sie implementiert die Kombination von verschiedenen Fakten. Beispielsweise kann eine Regel für rote Kreise und rote Quadrate nur aktiviert werden, wenn ein Betaknoten für einen roten Kreis und ein rotes Quadrat eine Kombination erzeugen kann.

public class BetaNodeImpl implements BetaNode {
  private final Map<Long, BetaHandle> betaValues = new HashMap<>();
  private final Map<Long, AlphaHandle> alphaValues = new HashMap<>();
  private final Map<Cross, BetaHandle> values = new HashMap<>();

  private final List<BetaNodeAccessor> accessors = new ArrayList<>();
  private final BiPredicate<List<Map<String, Object>>, Map<String, Object>> predicate;

  public BetaNodeImpl(BiPredicate<List<Map<String, Object>>, Map<String, Object>> predicate) {
    this.predicate = predicate;
  }

  @Override
  public void handle(AlphaHandle alphaHandle, MemoryContext context) {
    List<BetaHandle> betaHandles;
    if (alphaHandle.isDeleted()) {
      alphaValues.remove(alphaHandle.getId());
      betaHandles = betaValues.values().stream()
          .map(betaHandle -> context.delete(values.remove(new Cross(alphaHandle, betaHandle))))
          .filter(Objects::nonNull).collect(toList());
    } else {
      alphaValues.put(alphaHandle.getId(), alphaHandle);
      betaHandles = betaValues.values().stream().filter(x -> predicate.test(x.getValue(), alphaHandle.getValue()))
          .map(betaHandle -> storeValue(betaHandle, context, alphaHandle)).collect(toList());
    }
    accessors.forEach(x -> betaHandles.forEach(y -> x.handle(y, context)));
  }

  @Override
  public void handle(BetaHandle betaHandle, MemoryContext context) {
    List<BetaHandle> betaHandles;
    if (betaHandle.isDeleted()) {
      betaValues.remove(betaHandle.getId());
      betaHandles = alphaValues.values().stream()
          .map(alphaHandle -> context.delete(values.remove(new Cross(alphaHandle, betaHandle))))
          .filter(Objects::nonNull)
          .collect(toList());
    } else {
      betaValues.put(betaHandle.getId(), betaHandle);
      betaHandles = alphaValues.values().stream().filter(x -> predicate.test(betaHandle.getValue(), x.getValue()))
          .map(alphaHandle -> storeValue(betaHandle, context, alphaHandle)).collect(toList());
    }
    accessors.forEach(x -> betaHandles.forEach(y -> x.handle(y, context)));
  }

  private BetaHandle storeValue(BetaHandle beta, MemoryContext context, AlphaHandle alpha) {
    BetaHandle betaHandle = context.create(beta, alpha);
    values.put(new Cross(alpha, beta), betaHandle);
    return betaHandle;
  }

  @Override
  public <T extends BetaNodeAccessor> T add(T node) {
    accessors.add(node);
    return node;
  }
}

Die Klasse besitzt für jeden der Eingange jeweils eine Map, in der die Elemente über ihre ID referenziert sind. Zusätzlich besitzt sie auch eine Map für die erzeugten BetaHandle Instanzen. Diese werden über einen Key referenziert, der aus den IDs der kombinieren AlphaHandle und BetaHandle besteht. Die Map ist notwendig, um beim Löschen der erzeugten BetaHandle, die richtigen Instanzen an die nachfolgenden Knoten zu senden.

Diese Klasse kann Kombinationen aus der Liste möglicher Kombinationen herausfiltern, indem ein BiPredicate auf die Werte der AlphaHandle und BetaHandle Instanzen aufgerufen wird.

Verwendung

Um die bisherige Implementierung zu testen, muss aus den einzelnen Komponenten ein Rete Netzwerk zusammengesteckt werden. Die Startknoten in Form von AlphaNodeImpl Instanzen werden über die add Methode der RuleEngine in eine Map geschrieben. Ihr Typ "rectangle" und "circle" dienen dabei als Key.

RuleEngine ruleEngine = new RuleEngine();
AlphaNode rectangle = ruleEngine.add("rectangle", new AlphaNodeImpl(x -> "red".equals(x.get("color"))));
AlphaNode square = rectangle.add(new AlphaNodeImpl(equals("width", "height")));
AlphaNode circle = ruleEngine.add("circle", new AlphaNodeImpl(x -> "1".equals(x.get("border"))));
AlphaNode circleSize = circle.add(new AlphaNodeImpl(equalsConstant("size", "15")));
AlphaBetaAdapter squares = square.add(new AlphaMemory()).add(new AlphaBetaAdapter());
BetaNodeImpl sameColor = new BetaNodeImpl((b, a) -> b.get(0).get("color").equals(a.get("color")));
squares.add(sameColor);
circleSize.add(sameColor);
ruleEngine.add(sameColor.add(new Terminal()));

Der erste AlphaNode testet hier Rechtecke auf die Farbe rot und der zweite AlphaNode ob die Rechtecke quadratisch sind. Die weiteren AlphaNode Instanzen prüfen Eigenschaften für Kreise. Alle werden an der Instanz von BetaNodeImpl zusammengeführt, von der die Farbe von Rechtecken im BetaHandle gegen die Farbe von Kreisen im AlphaHandle geprüft werden. Die RuleEngine kann später auf das Ergebnis zugreifen, indem eine abschließende Terminal Instanz an die RuleEngine übergeben wird.

Nun fehlen noch Fakten im Speicher der RuleEngine. Im folgenden Beispiel wird ein Rechteck und ein Kreis hinzugefügt und dann das Rechteck wieder entfernt.

    AlphaHandle rectangle = ruleEngine.add("rectangle", Map.of("color", "red", "width", "10", "height", "10"));
    ruleEngine.add("circle", Map.of("color", "red", "size", "15", "border", "1"));
    ruleEngine.remove(rectangle);

Die Logausgabe zu diesen drei Befehlen zeigt in den ersten drei Zeilen, wie das Rechteck durch das Alpha Netz läuft und vom Adapter an den Betaknoten weitergereicht wird. In Zeile 4 bis 6 läuft der Kreis durch das Netz und wird in Zeile 7 an den Betaknoten weitergereicht, der daraufhin seine Ausgabe an den Terminal weiterreicht. Die letzten vier Zeilen zeigen, wie das Rechteck aus dem Speicher gelöscht wird, indem es den gesamten Weg bis zum Terminal mit dem deleted Flag durchläuft.

alpha: AlphaHandle@+1[rectangle]{color=red, width=10, height=10}}
alpha: AlphaHandle@+1[rectangle]{color=red, width=10, height=10}}
adapter: AlphaHandle@+1[rectangle]{color=red, width=10, height=10}}
alpha: AlphaHandle@+3[circle]{color=red, border=1, size=15}}
alpha: AlphaHandle@+3[circle]{color=red, border=1, size=15}}
beta: AlphaHandle@+3[circle]{color=red, border=1, size=15}} BetaHandle@+2[{color=red, width=10, height=10}]}
terminal: BetaHandle@+4[{color=red, width=10, height=10}, {color=red, border=1, size=15}]}
alpha: AlphaHandle@-1{height=10, width=10, color=red}}
alpha: AlphaHandle@-1{height=10, width=10, color=red}}
adapter: AlphaHandle@-1{height=10, width=10, color=red}}
beta: BetaHandle@-4[{height=10, width=10, color=red}, {size=15, border=1, color=red}]}
terminal: BetaHandle@-4[{height=10, width=10, color=red}, {size=15, border=1, color=red}]}

Bevor das Rechteck gelöscht wurde, war die Regel instantisiert, weil im Terminal ein BetaHandle vorhanden war. an dieser Stelle hätte ein Regelinterpreter die Werte aus dem BetaHandle entnehmen können und die Aktion der Regel auf diesen Werten ausführen können.

Damit ist die erste Implementierung eines einfachen Rete Algorithmus fertiggestellt. Im nächsten Beitrag zum Rete Algorithmus wird diese Implementierung von einigen ihrer Schwächen befreit.