“The hell with the rules. If it sounds right, then it is.”
Eddie Van Halen
Im zweiten Beitrag zum Rete Algorithmus wurde eine erste einfache Implementierung vorgestellt. Schon bei der Umsetzung zeigte sich jedoch, dass diverse Details anders gelöst werden sollten. Es passiert recht häufig, dass sich eine zu enge Anlehnung an eine Beschreibung eines Algorithmus den Weg zu einer guten Lösung erschwert oder sogar verbaut. Aus ähnlichen Gründen blieb mir viele Jahre der Zugang zu einer korrekten Double-Array-Trie Implementierung versperrt. Auch dort bedurfte es erst einen neuen Zugang zum Thema um die Blockade zu beenden.
Die bisherige Implementierung sah am Übergang zwischen dem Alpha und dem Beta Netz einen AlphaMemory vor, der die AlphaHandle aufsammelte, die erfolgreich die Prüfungen im Alpha Netz überstanden haben. Diese wurden dann über den AlphaBetaAdapter an den BetaNodeImpl oder Terminal übergeben. Der im letzten Beitrag erwähnte BetaMemory wurde im Beispiel Netz schon ausgelassen, da er die Ausgangswerte speichert, die BetaNodeImpl und Terminal als Eingangswerte speichern. Ähnlich überflüssig ist der AlphaMemory, dessen Ausgangswerte, die gespeicherten Eingangswerte des AlphaBetaAdapter sind.
Die Rete Netz aus dem ersten Beitrag vereinfacht sich, ohne die oben unnötige Klassen, auf das folgende.
Eine andere Vereinfachung ist die Aufsplittung der Eingangskanäle der Knoten. Die klassische Implementierung sieht für Alphaknoten einen Eingang vor, der entweder Daten zum Einfügen oder Daten zum Löschen transportierte. Die bisherige Implementierung besaß eine handle Methode im AlphaNodeAccessor Interface. Die neue besitzt eine insert und eine remove Methode.
public interface AlphaNodeAccessor {
default void insert(AlphaHandle value, MemoryContext context) {
throw new UnsupportedOperationException();
}
default void remove(AlphaHandle value, MemoryContext context) {
throw new UnsupportedOperationException();
}
}
Durch diese Veränderung verbessert sich nicht nur der Source Code der implementierenden Klassen, weil das hässliche If-Then-Else verschwindet. Die Wrapper für löschende AlphaHandle und die isDeleted Methode werden obsolet.
@Override
public void insert(AlphaHandle value, MemoryContext context) {
if (predicate.test(value.getValue())) {
successors.forEach(x -> x.insert(value, context));
}
}
@Override
public void remove(AlphaHandle value, MemoryContext context) {
if (predicate.test(value.getValue())) {
successors.forEach(x -> x.remove(value, context));
}
}
Für AlphaHandle Instanzen, die gelöscht werden sollten, wurde bislang das Alpha Netz mit allen Prüfungen durchlaufen. Das ist unökonomisch, wenn die Zahl der Prüfungen innerhalb des Alpha Netzes rechenintensiv ist im Vergleich zum Prüfen der Eingangswerte der AlphaBetaAdapter und BetaNodeImpl Instanzen.
Die neue Implementierung merkt sich alle Ausgänge aus dem Alpha Netz in einer Map. Das Einfügen im Alpha Netz erfolgt über die grünen Pfade, das Löschen über die roten Pfade.
public void addAlphaTerminal(String type, AlphaNodeAccessor accessor) {
alphaTerminals.computeIfAbsent(type, k -> new ArrayList<>()).add(accessor);
}
Gestartet wird das Löschen nun nicht mehr am Startknoten für einen Typen, sondern an den entsprechenden Ausgängen des Alpha Netzes.
public void remove(AlphaHandle alphaHandle) {
alphaTerminals.get(requireNonNull(alphaHandle).getType()).forEach(x -> x.remove(alphaHandle, this));
}
Dort wird geprüft, ob ein AlphaHandle mit entsprechender ID den Ausgang passiert hat. Im Zuge dieses Refactorings wurde auch die Map mit den Eingangswerten im AlphaBetaAdapter entfernt. Die dort enthaltenen Werte sind in der Map mit den Ausgangswerten zu finden.
@Override
public void insert(AlphaHandle value, MemoryContext context) {
BetaHandle betaHandle = context.create(value);
betaValues.put(value.getId(), betaHandle);
accessors.forEach(x -> x.insert(betaHandle, context));
}
@Override
public void remove(AlphaHandle value, MemoryContext context) {
BetaHandle betaHandle = betaValues.get(value.getId());
if (betaHandle == null) {
return;
}
accessors.forEach(x -> x.remove(betaHandle, context));
}
Das etwas erweiterte Beispiel für die Anwendung des Rete Algorithmus könnte in Pseudo OPS 5 wie folgt formuliert sein.
(rectangle ^border 2 ^width $width ^height = $width ^color $color) (circle ^size 15 ^border 1 ^color $color) => exit()
Die Regel soll auf Quadrate mit dicken Rand und Kreise mit der selben Farbe wie die Quadrate, dünnen Rand und einem Durchmesser von 15 reagieren.
RuleEngine ruleEngine = new RuleEngine();
AlphaNode rectangle = ruleEngine.addStart("rectangle", new AlphaNodeImpl(equalsConst("border", "2")));
AlphaNode square = rectangle.add(new AlphaNodeImpl(equals("width", "height")));
AlphaNode circle = ruleEngine.addStart("circle", new AlphaNodeImpl(equalsConst("border", "1")));
AlphaNode circleSize = circle.add(new AlphaNodeImpl(equalsConst("size", "15")));
AlphaBetaAdapter squares = ruleEngine.addAlphaTerminal("rectangle", square.add(new AlphaBetaAdapter()));
BetaNodeImpl sameColor = ruleEngine.addAlphaTerminal("circle", new BetaNodeImpl(compare("color", 0)));
squares.add(sameColor);
circleSize.add(sameColor);
ruleEngine.addTerminal(sameColor.add(new Terminal()));
ruleEngine.addStart("rectangle", Map.<em>of</em>("color", "red", "width", "10", "height", "10", "border", "2"));
ruleEngine.addStart("circle", Map.<em>of</em>("color", "red", "size", "15", "border", "1"));
ruleEngine.addStart("rectangle", Map.<em>of</em>("color", "green", "width", "5", "height", "5", "border", "2"));
ruleEngine.addStart("circle", Map.<em>of</em>("color", "green", "size", "15", "border", "1"));
In den letzten vier Zeilen des Beispiels werden ein rotes und ein grünes Rechteck und ein roter und ein grüner Kreis hinzugefügt. Am Terminal stehen nach dem Einfügen zwei BetaHandle Instanzen zur Verfügung.
terminal insert: BetaHandle@4[{color=red, border=2, width=10, height=10}, {color=red, border=1, size=15}]}
terminal insert: BetaHandle@8[{color=green, border=2, width=5, height=5}, {color=green, border=1, size=15}]}
act: BetaHandle@4[{color=red, border=2, width=10, height=10}, {color=red, border=1, size=15}]}
Die Regel wird also zwei mal aktiviert, einmal für die grünen und einmal für die roten Formen.
Obwohl die erste Implementierung funktional vollständig war, hat der zu starke Bezug auf die Beschreibung des Algorithmus die Implementierung unelegant und ineffizient werden lassen. Daher ist es immer ratsam eine erste Implementierung noch einmal zu überarbeiten.