Suche
Funktionale Programmierung mit Java 9: Memoizing

Checkpoint Java: Was bitte ist Memoizing?

Sven Ruppert

© Shutterstock/Suttha Burawonk

Wenn man sich mit den funktionalen Aspekten der Programmierung auseinandersetzt, kommt man irgendwann mit dem Begriff des Memoizing in Kontakt. Was genau das sein soll und wie man das in Core Java abbilden kann, erklärt Sven Ruppert in diesem Teil seiner Kolumne Checkpoint Java.

In der Funktionalen Programmierung spricht man davon, das eine Funktion zu einem bestimmten Eingangswert immer denselben Ausgangswert liefert. Genau denselben? Ja, genau denselben soll die Funktion liefern. Wenn der Rückgabewert vom Typ int ist, ist das kein Problem. Wie aber sieht es aus, wenn der Rückgabewert eine Instanz vom Typ Gummibärchen ist? Hier ist also darauf zu achten, was der Unterschied zwischen dem selben Wert und dem gleichen Wert ist.

Wir werden für diese Artikelreihe von Beginn an mit JDK 9 arbeiten, auch wenn es zum Zeitpunkt der Veröffentlichung noch nicht final verfügbar ist. Das OpenJDK kann hier gefunden werden. Zuzüglich zu den Quelltextbeispielen in diesem Artikel verwende ich auch die Sourcen des Open-Source-Projekts Functional-Reactive. Die Sourcen liegen auf GitHub.

Beginnen wir mit einem einfachen Beispiel und verwenden folgende Funktion:

private static Function<Integer, Integer> squareFunction = x -> {
    System.out.println("In function");
    return x * x;
  };

In diesem Beispiel verwende ich System.out, um zu zeigen, wie oft die Funktion aufgerufen worden ist. Selbstverständlich ist das nichts für den produktiven Einsatz.

Wenn nun diese Funktion zweimal aufgerufen wird, kann man das auf der Konsole sehen. Es erscheint zweimal In action.

final Integer a = squareFunction.apply(2);
    final Integer b = squareFunction.apply(2);

Definieren wir uns nun eine Methode, um das Memoizing auf eine Funktion anzuwenden.

Function<Integer, Integer> memoizationFunction =  
                           Memoizer.memoize(squareFunction);

Ziel dieser Methode ist es, dass nach deren Anwendung die gelieferte Funktion bei zweimaligem Aufruf mit demselben Wert nur einmal als Meldung auf der Konsole zu sehen ist. Oder besser gesagt, das ein Ergebnis nur einmalig berechnet wird. Die Funktion soll sich also merken, dass sie dieses Ergebnis schon einmal produziert hat.

ConcurrentHashMap

Um sich Werte zu merken, kann man sich einer Map bedienen. Hier werden zu den jeweiligen Eingangswerten die berechneten Ausgangswerte gehalten. Wird wieder ein Ergebnis angefordert,  wird erst in der Map nachgesehen, ob es dazu schon ein Ergebnis gibt. Wenn dem so ist, wird dieses Ergebnis verwendet, ansonsten wird es berechnet und ebenfalls in der Map abgelegt. Als Implementierung der Map empfiehlt sich die ConcurrentHashMap, da wir nicht ausschließen können, dass multiple Zugriffe zur selben Zeit erfolgen.

Seit Java 8 gibt es die Methode computeIfAbsent, mit der zum einen der Schlüssel und zum anderen die Berechnung des Wertes als Funktion übergeben werden kann. Die Implementierung der Funktionalität Memoizing ist nun nichts anderes als eine Ummantelung der Funktion.

private static Function<Integer, Integer> squareFunction = x -> {
    System.out.println("In function");
    return x * x;
  };

  public static class Memoizer<T,U> {
    private final Map<T,U> memoizationCache 
                           = new ConcurrentHashMap<>();

    private Function<T, U> doMemoize(final Function<T,U> function) {
      return input -> memoizationCache
                          .computeIfAbsent(input, function);
    }
    public static <T, U> Function<T, U> 
           memoize(final Function<T, U> function) {
      return new Memoizer<T, U>().doMemoize(function);
    }

  }


  public static void main(String[] args) {
    final Function<Integer, Integer> f = 
          Memoizer.memoize(squareFunction);
    final Integer a = f.apply(2);
    final Integer b = f.apply(2);
  }

Wenn man nun die Funktion verwendet, die einem von dem Aufruf der Methode memoize(…) zurückgeliefert worden ist,  stellt man fest, dass bei mehrfacher Verwendung desselben Eingangswertes nur einmal die Meldung auf der Konsole erscheint. Nun sind wir in der Lage, eine Function<A,B> mit der Eigenschaft des Memoizing auszustatten. Wie aber sieht es nun bei einer BiFunction<A,B,R> aus?

BiFunction

Bei einer BiFunction handelt es sich um eine Funktion mit zwei Eingangswerten. Das bedeutet, dass ein Ergebniswert nun von zwei Werten abhängt. Soweit ist alles recht einfach. Nur wie werden wir uns die Funktion des Memoizing aufbauen? Hierzu spielen wir ein wenig mit der BiFunction an sich herum und versuchen diese umzuformen. Dazu verwenden wir folgende Beispielfunktion:

BiFunction<Integer,Integer,Integer> biFunctionA = (x,y) -> x * y;

Diese Funktion kann man auch in eine Funktion umformen, die zweistufig aufgebaut ist.

Function<Integer, Function<Integer, Integer>> biFunctionB 
         = x -> y -> x * y;

Den Vorgang an sich nennt man Currying. Wer ein wenig mehr Theorie dazu lesen möchte, der kann bei Wikipedia beginnen.

Um das Memoizing zu realisieren, kann man mit der vorher gezeigten Variante auf der jeweiligen Stufe ansetzen.

Function<Integer, Function<Integer,Integer>> memoizationFunction
        = Memoizer.memoize(x -> Memoizer.memoize(y -> x * y));

Die Verwendung ist aber noch alles andere als komfortabel. Das Ziel sollte sein, dass eine BiFunction übergeben wird und eine BiFunction mit der Eigenschaft des Memoizing wieder zurückgeliefert werden wird. Aber eines nach dem anderen.

create

Der erste Schritt ist die Umformung der BiFunction<A,B,R> in eine Function<A, Fuction<B,R>>. Hierzu definieren wir eine Methode, die uns genau diese Transformation abbildet.

private static final BiFunction<Integer, Integer, Integer> biFunctionA = (x , y) -> x * y;

  public static Function<Integer, Function<Integer, Integer>> create(
      BiFunction<Integer, Integer, Integer> biFunction) {
    return Memoizer.memoize(x -> Memoizer.memoize(y -> biFunction.apply(x , y)));
  }

  public static void main(String[] args) {
    final Function<Integer, Function<Integer, Integer>> function = create(biFunctionA);
    System.out.println("memoizationFunction = " + function.apply(2).apply(3));
    System.out.println("memoizationFunction = " + function.apply(2).apply(3));
  }

transform

Der erste Schritt ist vollbracht, fehlt jetzt noch die Rücktransformation auf eine BiFunction. Auch hier kann man recht einfach den Aufruf delegieren.

public static BiFunction<Integer, Integer, Integer> transform(
      Function<Integer, Function<Integer, Integer>> function) {
    return (a,b) -> function.apply(a).apply(b);
  }

Beides zusammen ergibt dann folgende Methode.

public static Function<Integer, Function<Integer, Integer>> create(
      BiFunction<Integer, Integer, Integer> biFunction) {
    return Memoizer.memoize(x -> Memoizer.memoize(y -> biFunction.apply(x , y)));
  }

  public static BiFunction<Integer, Integer, Integer> transform(
      Function<Integer, Function<Integer, Integer>> function) {
    return (a,b) -> function.apply(a).apply(b);
  }

  public static BiFunction<Integer, Integer, Integer> memoize(
                BiFunction<Integer, Integer, Integer> f){
    return transform(create(biFunctionA));
  }

Oder, wenn man beides ineinander überführt:

public static BiFunction<Integer, Integer, Integer> memoize(
                BiFunction<Integer, Integer, Integer> f){
    Function<Integer, Function<Integer, Integer>> cf
        = Memoizer.memoize(x -> Memoizer.memoize(y -> f.apply(x , y)));
    return (a,b) -> cf.apply(a).apply(b);
  }

Bisher haben wir alles auf eine bestimmte Funktion bezogen. Das kann man dank Generics allerdings allgemeiner formulieren.

Hierfür definieren wir die Typen A, B und R.

public static <A,B,R> BiFunction<A, B, R> memoize(BiFunction<A, B, R> f) {
    Function<A, Function<B, R>> cf
        = Memoizer.memoize(x -> Memoizer.memoize(y -> f.apply(x , y)));
    return (a , b) -> cf.apply(a).apply(b);
  }
  
  public static void main(String[] args) {
    Main.<Integer,Integer,Integer>memoize((x , y) -> x * y).apply(2 , 3);
    Main.<String, String, Integer>memoize((x,y) -> Integer.valueOf(a) * Integer.valueOf(b));
  }

TriFunction to n-Function

Wenn man an dieser Stelle angekommen ist, kann man darüber nachdenken, wie das mit einer TriFunction aussehen möge. Nur leider gibt es keine TriFunction im JDK. Wenn man diese jedoch benötigt, sollte man sich davon aber nicht abhalten lassen. Eine TriFunction ist schnell definiert. Wenn man dann noch die BiFunction aus dem JDK als Vorbild nimmt, ist es für die Entwickler, die diese verwenden, sehr intuitiv.

@FunctionalInterface
  public interface TriFunction<T1, T2,T3, R> {
    R apply(T1 t1, T2 t2, T3 t3);
    default <V> TriFunction<T1, T2,T3, V> andThen(Function<? super R, ? extends V> after) {
      Objects.requireNonNull(after);
      return (T1 t1, T2 t2, T3 t3) -> after.apply(apply(t1, t2, t3));
    }
  }

Auch hier kann man denselben Weg wie bei der BiFunction gehen.

public static <A, B, C, R> TriFunction<A, B, C, R> memoize(TriFunction<A, B, C, R> f) {
    Function<A, Function<B, Function<C,R>>> cf
        = Memoizer.memoize(
        x -> Memoizer.memoize(
            y -> Memoizer.memoize(
                z -> f.apply(x , y , z))));
    return (a , b, c) -> cf.apply(a).apply(b).apply(c);
  }

Hierbei sieht man deutlich, dass wir dieses bis zu einer beliebigen Größenordnung so weiter definieren können. Der Weg zur NFunction ist also frei.

…und da gab es noch legacy Code

Der ein oder andere Entwickler wird hin und wieder doch einmal mit etwas älterem Quelltext konfrontiert. Hier ist es meist so, dass der Umbau auf neue Interfaces meist nicht machbar ist. Was aber kann man machen, um zum Beispiel von dieser Art des partiellen Cachings zu profitieren? Stellen wir uns hier einmal ein klassisches Stück Java vor.

public static class MyLegacyClass {
    public Value doWorkA(int a, int b){
      return new Value();
    }
    public Value doWorkB(int a, int b){
      return new Value();
    }
  }

Um diese Methoden von einer Instanz der Klasse MyLegacyClass zu verwenden, gibt es unter anderem die folgende Möglichkeit: Es wird sich eine Methodenreferenz auf die Methode doWork von dieser Instanz geholt. Diese Methodenreferenz entspricht der Signatur einer BiFunction, da sie zwei Parameter und einen Rückgabewert hat.

final MyLegacyClass myLegacyClass = new MyLegacyClass();
    final BiFunction<Integer, Integer, Value> doWork = myLegacyClass::doWorkA;
    final BiFunction<Integer, Integer, Value> memoize = Memoizer.memoize(doWork);

Diese BiFunction kann mittels Memoizing mit der Eigenschaft des partiellen Cachings
ausgestattet werden. Die ursprüngliche Methode bleibt davon unberührt und kann weiterhin wie
zuvor verwendet werden. Bisweilen kommt es vor, das alter Quelltext auch Methoden mit mehr als zwei Parametern besitzt. Hier kann man dann mit den selbst definierten TriFunction arbeiten.

Checkpoint Java

In dieser Kolumne klopft der Autor Sven Ruppert (Vaadin) Java auf alltägliche Probleme ab. Er gibt hilfreiche Tipps und Tricks, wie Entwickler gängige Stolperfallen vermeiden und klareren Code schreiben können. Einen besonderen Blick wirft er auf die neuen Möglichkeiten von Funktionaler und Reaktiver Programmierung. Alle Teile der Kolumne Checkpoint Java finden sich hier.

Fazit

Wir haben gesehen, das es manchmal recht einfach ist, generische Muster in Java abzubilden. Eine Brücke zwischen altem und neuem Quelltext haben wir nun dank MethodHandles ebenfalls. Somit steht ein recht komfortabler Weg zur Verfügung, alten Quelltext ohne Bytecode-Manipulation oder größeres Refactoring mit unseren neuen Konzepten zu kombinieren. Den Quelltext findet ihr auf Github. Bei Fragen und Anregungen einfach melden unter sven@vaadin.com oder per Twitter @SvenRuppert.

Happy Coding!

Geschrieben von
Sven Ruppert
Sven Ruppert
Sven Ruppert arbeitet seit 1996 mit Java und ist Developer Advocate bei Vaadin. In seiner Freizeit spricht er auf internationalen und nationalen Konferenzen, schreibt für IT-Magazine und für Tech-Portale. Twitter: @SvenRuppert
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.