Doppel-Switch in Java

Ich hasse es, wenn ich geschachtelte switch-Blöcke sehe. Es ist einfach unübersichtlich, und während man Fälle zusammenfassen kann, wo einem der zweite, „innere“ Wert egal ist, geht das für den ersten, „äußeren“ Wert nicht.

Nehmen wir als Anwendungsfall einmal ein boolesches TriState-Enum, das auch „und“- und „oder“-Operationen unterstützt. Eine mögliche Implementierung könnte so aussehen:

public enum TriState {
    TRUE, FALSE, UNKNOWN;

    private static TriState and(TriState a, TriState b) {
        switch(a) {
            case FALSE: return FALSE;
            case TRUE: return b;
            case UNKNOWN: switch(b) {
                case FALSE: return FALSE;
                default: return UNKNOWN;
            }
        }
        throw new AssertionError();
    }

    private static TriState or(TriState a, TriState b) {
        switch(a) {
            case TRUE: return TRUE;
            case FALSE: return b;
            case UNKNOWN: switch(b) {
                case TRUE: return TRUE;
                default: return UNKNOWN;
            }
        }
        throw new AssertionError();
    }
}

Man kann sich leicht vorstellen, wie bei mehr Werten die switches schnell unübersichtlich werden. Hier ein Beispiel, wie es mit DSL aussehen könnte:

public enum TriState {TRUE, FALSE, UNKNOWN;

    private static TriState and(TriState a, TriState b) {
        return switch2(a, b,
                case2(TRUE, TRUE, () -> TRUE),
                case2(FALSE, any(), () -> FALSE),
                case2(any(), FALSE, () -> FALSE),
                default2(() -> UNKNOWN)
        );
    }

    private static TriState or(TriState a, TriState b) {
            return switch2(a, b,
                    case2(FALSE, FALSE, () -> FALSE),
                    case2(TRUE, any(), () -> TRUE),
                    case2(any(), TRUE, () -> TRUE),
                    default2(() -> UNKNOWN)
            );
    }
}

Ich habe mich entschlossen, die „Leerstellen“ über einen speziellen Wert any() zu kennzeichnen. Wenn beide Werte egal sind, habe ich analog zum normalen switch als Synonym auch die Methode default2 bereitgestellt. Ich hoffe, dass das die Bedienung intuitiver macht. Hier die Implementierung des DSLs:

import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Supplier;

public final class Switch {
    private Switch(){ /*do not instantiate*/ }

    enum Any {any}

    public static Any any() {
        return Any.any;
    }

    @SafeVarargs
    public static <A,B,R> R switch2(A a, B b, BiFunction<A, B, Optional<R>>... cases) {
        return Arrays.stream(cases)
            .map(biFunction -> biFunction.apply(a,b))
            .flatMap(opt -> opt.map(Stream::of).orElseGet(Stream::empty))
            .findFirst()
            .orElseThrow(() -> new RuntimeException("no match found"));
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(A a, B b, Supplier<R> result) {
        return (_a, _b) -> a.equals(_a) && b.equals(_b) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(A a, Any any, Supplier<R> result) {
        return (_a, _b) -> a.equals(_a) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(Any any, B b, Supplier<R> result) {
        return (_a, _b) -> b.equals(_b) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(Any any1, Any any2, Supplier<R> result) {
        return default2(result);
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> default2(Supplier<R> result) {
        return (_a, _b) -> Optional.of(result.get());
    }
}

Auch wenn man in anderen Sprachen noch viel „natürlichere“ DSLs schreiben kann, ist es doch immer wieder schön zu sehen, wie „erweiterbar“ Java inzwischen geworden ist, und das ohne größeren Aufwand. Ich glaube aber, dass bei vielen Java-Entwicklern das Bewusstsein fehlt, welche Möglichkeiten sie inzwischen haben. Das ist schade, aber ich hoffe sehr, dass sich das langsam ändert.

Advertisements

Eine Builder-Variante mit Initialisierungsblöcken

Eines der weniger oft genutzen Java-Features sind Initialisierungsblöcke. Aber wenn sie dann einmal gebraucht werden, können sie ziemlich nützlich sein. Vielleicht auch, um Builder zu schachteln? Und wie könnte das aussehen?

Nehmen wir an, wir müssten eine einfache hierarchische Struktur aufbauen: Eine Menü-Leiste, darin Menüs, und in diesen wiederum Menüpunkte. Mit Initialisierungsblöcken könnte der Aufruf dann so aussehen:

MenuBarBuilder menuBarBuilder = new MenuBarBuilder() {{
    new Menu("menu1") {{
        new Item("item1.1");
        new Item("item1.2");
    }};
    new Menu("menu2") {{
        new Item("item2.1");
        new Item("item2.2");
        new Item("item2.3");
    }};
}};

System.out.println(menuBarBuilder);

Der Einfachheit halber bauen wir hier das Menü nicht zusammen (was ja nicht schwer ist, wenn man die Builder-Struktur erst einmal hat), sondern geben einfach nur eine String-Repräsentation aus. Hier wäre das Ergebnis:

menubar[
  menu 'menu1'[item 'item1.1', item 'item1.2'], 
  menu 'menu2'[item 'item2.1', item 'item2.2', item 'item2.3']]

Okay, bis auf die geschweiften Doppel-Klammern sieht die Verwendungsseite eigentlich gar nicht so schlimm aus. Aber welche Scheußlichkeiten müssen wir bei der Implementierung begehen, damit das funktioniert? Ich finde, auch die Implementierung ist recht erträglich, denn wir benutzen einen einfachen Trick: Menu ist eine innere Klasse von MenuBarBuilder, und kann sich somit bei der Objekterzeugung bei „seiner“ äußeren Instanz „registrieren“ (in diesem Fall einfach in eine vorgegebene Liste eintragen). Genauso ist Item eine innere Klasse von Menu und registriert sich dort. Dieser Aufbau löst eine Menge Probleme – und es wird nicht einmal ein statischer Import benötigt. Hier ist der Code:

import java.util.ArrayList;
import java.util.List;

public class MenuBarBuilder {

    private List<Menu> menus = new ArrayList<>();

    public String toString() {
        return "menubar" + menus.toString();
    }

    public class Menu {
        private final String menuName;
        private List<Item> items = new ArrayList<>();

        public Menu(String name) {
            this.menuName = name;
            MenuBarBuilder.this.menus.add(this);
        }

        public String toString() {
            return "\n  menu '" + menuName + "'" + items;
        }

        public class Item {
            private final String itemName;

            public Item(String name) {
                this.itemName = name;
                Menu.this.items.add(this);
            }

            public String toString() {
                return "item '" + itemName + "'";
            }

        }
    }

}

Ja, das ist alles was man braucht, damit der Aufruf oben funktioniert. Im Endeffekt ergibt sich die Einfachheit daraus, dass wir die Builder genau so ineinanderschachteln, wie auch unsere Struktur später aussehen soll.

Wie ist diese Builder-Variante nun einzuschätzen? Der größte Nachteil ist wohl, dass sie durch die Verwendung von Initialisierungsblöcken einfach ungewohnt ist. Weiterhin skaliert dieser Ansatz nicht so gut: Bei tiefen Hierarchien wird die Builder-Klasse immer länger, weil immer neue innere Klassen dazukommen, die man nicht auslagern kann. Außerdem wird für jeden verwendeten Initialisierungsblock eine anonyme Klassen erzeugt und eine entsprechende class-Datei angelegt, was bei viel geschachteltem „Inhalt“ ebenfalls problematisch sein kann (allerdings würde in diesem Fall auch das „normale“ Builder-Pattern unbequem werden). Auf der Haben-Seite dieses Konstrukts steht ein recht einfacher Aufbau und eine hohe Flexibilität.

Ehrlich gesagt bin ich mir nicht sicher, ob die vorgestellte Builder-Variante eine gute Idee ist, aber es war auf jeden Fall spannend, damit herumzuspielen, und überraschend, wie gut sie funktioniert.

Pattern-Matching in Java 8

In Scala ist Pattern-Matching ein beliebtes Feature mit fast unbegrenzten Anwendungsmöglichkeiten. Nicht umsonst wird es oft als „switch auf Steroiden“ bezeichnet. Im Rahmen eines kleinen Projekts habe ich überlegt, ob man das nicht auch in Java 8 nachbauen kann.

Man kann, mit einigen Einschränkungen. Hier einmal ein kleines Anwendungsbeispiel:

String string = ...
String s = match(string,
   StartsWith("foo", () -> "found foo..."),
   EndsWith("bar", () -> "found ...bar"),
   Contains("baz", () -> "found ...baz..."),
   EqualsIgnoreCase("blubb", () -> "found blubb"),
   Default(() -> "nix gefunden")
);
System.out.println(s);

Wie funktioniert das? Zuerst braucht man für die einzelnen Fälle ein Interface:

import java.util.Optional;

public interface Case<T,R> {
    Optional<R> accept(T value);
}

Es ist im Prinzip eine Art Funktion, die für einem Ausgangswert ein Resultat liefert, allerdings in einem Optional. Wir haben also eine Art Funktion, die eventuell etwas zurückliefert – genau dann, wenn der zu überprüfende Wert „passt“. Hier eine der verwendeten Case-Implementierungen (man verzeihe mir bitte die an Scala angelehnte Großschreibung der Methodennamen):

public static <R> Case<String, R> StartsWith(String prefix, Supplier<R> supplier) {
    return t -> t.startsWith(prefix)
            ? Optional.of(supplier.get())
            : Optional.<R>empty();
}

Wir liefern also den durch den Supplier vorgegebenen Wert (in ein Optional verpackt) zurück, aber nur, wenn der zu testende String den richtigen Präfix hat.

Die match-Methode ist auch recht unspektakulär (MatchException ist eine gewöhnliche Laufzeit-Exception):

@SafeVarargs
public static <T,R> R match(T value, Case<T,R> ... cases) throws MatchException {
    for(Case<T,R> c : cases) {
        Optional<R> result = c.accept(value);
        if (result.isPresent()) {
            return result.get();
        }
    }
    throw new MatchException();
}

Interessanterweise kann dieser Mechanismus auch die Arbeit mit Optional vereinfachen. Wenn wir einmal so tun, als hätte Optional wie in Scala die Unterklassen Some (die einen Wert enthält) und None (die „leer“ ist), könnte uns das zu dieser Verwendung anregen:

Optional<Integer> opt = ...
String s = match(opt,
        None(() -> "leer"),
        Some(42, () -> "die Antwort!"),
        SomeIf(a -> "gerade", a -> a % 2 == 0),
        Default(() -> "nix gefunden")
);

Selbst „geschachteltes“ Pattern-Matching ist möglich:

Optional<Optional<Integer>> opt = ...
String s = match(opt,
        None(() -> "leer"),
        Some(None(() -> "leer eingetütet")),
        Some(SomeIf(a -> "gerade", a -> a % 2 == 0)),
        Default(() -> "nix gefunden")
);

Hier die verwendeten Case-Implementierungen:

import static java.util.Optional.*;
...

public static <T,R> Case<Optional<T>,R> None(Supplier<? extends R> supplier) {
    return t -> t.isPresent()
            ? Optional.<R>empty()
            : of(supplier.get());
}

public static <T,R> Case<Optional<T>,R> Some(T value, Supplier<? extends R> supplier) {
    return t -> t.isPresent() && t.get().equals(value)
            ? of(supplier.get())
             : Optional.<R>empty();
}

public static <T,R> Case<Optional<T>,R> Some(Case<T,R> caseT) {
    return t -> t.isPresent()
            ? caseT.accept(t.get())
            : Optional.<R>empty();
}

public static <T,R> Case<Optional<T>,R> Some(Function<? super T, ? extends R> fn) {
    return t -> t.isPresent()
            ? of(fn.apply(t.get()))
            : Optional.<R>empty();
}

public static <T,R> Case<Optional<T>,R> SomeIf(Function<? super T, ? extends R> fn, Predicate<T> predicate) {
    return t -> t.isPresent() && predicate.test(t.get())
            ? of(fn.apply(t.get()))
            : Optional.<R>empty();
}

public static <T,R> Case<T,R> Default(Supplier<R> supplier) {
    return value -> of(supplier.get());
}

Ich will nicht verhehlen, dass wir hier haarscharf an den Grenzen von Javas Typ-Inferenz operieren, und auch leicht Eindeutigkeitsprobleme bei gleichnamigen statischen Methoden mit Lambda-Argumenten auftreten können. Ob diese kleine DSL wirklich „brauchbar“ ist, muss sich erst noch zeigen. Spaß macht es auf jeden Fall.

Java 8 und der Y-Kombinator

So schön Lambda-Ausdrücke auch sind, sie haben wenigstens eine Achillesferse: Rekursion. Betrachten wir folgendes Beispiel, das schon seit Java 5 funktionieren würde (ein entsprechendes Function-Interface einmal vorausgesetzt):

...
Function<Integer, Long> fac = new Function<Integer, Long>() {
    @Override
    public Long apply(Integer n) {
        return n == 0 ? 1L : n * apply(n-1);
    }
};

System.out.println(fac.apply(10)); //--> 3628800
...

So weit, so gut und auch so langweilig: Die gute alte Fakultät. Aber wie lässt sich die Definition der anonymen Klasse durch einen Lambda-Ausdruck ersetzen? Hier zwei Beispiele dafür, wie es schon einmal nicht geht:

//Compiler-Fehler: "Variable fac might not have been initialized"
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * fac.apply(n-1);  

//this verweist hier auf die umgebende Klasse, nicht auf den Lambda-Ausdruck selbst
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * this.apply(n-1);  

Wir müssen also tiefer in die Trickkiste greifen. Man bräuchte einen Weg, um die Rekursion sozusagen „explizit“ zu machen. Erfreulicherweise ist dieses Problem schon lange gelöst und gehört zur Folklore der funktionalen Sprachen: Man verwendet einen Fixpunkt-Kombinator wie den Y-Kombinator. Ich will an dieser Stelle nicht genauer auf die Funktionsweise eingehen, hauptsächlich um zu verhindern, dass mein Gehirn schmilzt, aber auch, weil man unter Magiern keine Tricks verrät. Deshalb hier eine sehr direkte Umsetzung dieses Konzepts (z.B. ohne weitere Vorkehrungen, um einen Stacküberlauf zu verhindern):

...
public static <X,Y> Function<X,Y> yCombinator(Function<Function<X,Y>,Function<X,Y>> f) {
   return x -> f.apply(yCombinator(f)).apply(x);
}
...

Function<Integer,Long> fac = yCombinator(f -> n -> n == 0 ? 1L : n * f.apply(n-1));

System.out.println(fac.apply(10)); //--> 3628800

Wer mehr dazu erfahren will, sollte sich den Wikibook-Eintrag zu Haskell’s fix-Funktion anschauen. Aber selbst wenn man die „Magie“ nicht im Detail nachvollziehen kann oder will, ist es nützlich zu wissen, dass es diesen Trick gibt. Es ist auch ein schönes Beispiel dafür, dass es sich lohnen kann, einmal über den objektorientierten Tellerrand zu schauen, um die tollen neuen Features von Java 8 auch wirklich ausnutzen zu können.

Update

Vielleicht ist folgende Schreibweise mit BiFunction lesbarer:


public static <X,Y> Function<X,Y> yCombinator(BiFunction<X,Function<X,Y>,Y> f) {
    return x -> f.apply(x, yCombinator(f));
}
...
//Anwendung
Function<Integer,Long> fac = yCombinator((n,f) -> n == 0 ? 1L : n * f.apply(n-1));
System.out.println(fac.apply(10));

Kann Java abstrakte Typ-Member simulieren?

Scala kennt von Anfang an abstrakte Typ-Member als Alternative zu Generics. Eine Übersicht findet sich hier, und ich habe auch schon damit herumgespielt. Die Kurzfassung: Während generische Klassen ihre Parameter nach außen bekanntmachen, und diese überall mit „durchgeschleift“ werden (müssen), werden abstrakte Typ-Member eher als eine Art Implementierungsdetail angesehen und somit sozusagen als „innere Angelegenheit“ behandelt.

Und gestern abend dämmerte mir, das Java zumindest prinzipiell etwas Ähnliches erlaubt – und nicht erst seit Java 8. Ich habe keine Ahnung, wie weit diese „Technik“ trägt – und ganz sicher ist sie nicht so flexibel wie Scalas Ansatz, der ja „dafür gebaut“ worden ist. Aber ich werde gleich zwei Instanzen mit unterschiedlichen Member-Typen in ein und dieselbe Liste packen – ohne Wildcards, Raw-Types, Casts oder Compiler-Warnungen. Sozusagen „innen generisch, außen nicht“ – ähnlich wie bei abstrakten Typ-Membern:

public class Outer<T> {

    public class Inner {
        public final T t;

        public Inner(T t) {
            this.t = t;
        }
    }

    public static void main(String[] args) {
        List<Outer.Inner> list = new ArrayList<>();
        list.add(new Outer<String>().new Inner("blubb"));
        list.add(new Outer<Integer>().new Inner(42));
        for(Outer.Inner inner : list) {
            System.out.println(inner.t);
        }
    }
}

Tadaaaaa! Das ist also der Trick: Innere Klassen, die die Generics von ihren äußeren Klassen „benutzen“. Übrigens: Wer solche seltsamen Konstruktoraufrufe wie im Beispielcode noch nicht gesehen hat, ist nicht allein – ich kannte die Syntax auch nicht, bis ich für die „Java Programmer“-Zertifizierung von Oracle lernen musste (daher auch die „Inspiration“ für diesen etwas kranken Code). Ich muss erst einmal sehen, in wie weit dieses Konstrukt überhaupt sinnvoll ist, und wie groß die Beschränkung durch die erzwungene „Innerklassigkeit“ in der Praxis ist. Falls ihr auch damit herumspielt, würden mich natürlich die Ergebnisse eurer Experimente brennend interessieren.

[Update]
Ich bin darauf hingeweisen worden, dass der „volle“ Typ meiner Liste eigentlich etwas wie List<Outer<String>.Inner> sein müsste, ich hier also doch mit Raw-Types arbeite (auch wenn ich keine Warnung sehe). Das macht das Ganze natürlich hinsichtlich der Typsicherheit obsolet, weil damit kein Unterschied zu einer normalen generischen Top-Level-Klasse, die als Raw-Typ verwendet wird, besteht. Schade…

Continuations in Java 8

Mit Java 8 in den Startlöchern bietet sich an, mal zum Vergleich ältere Blog-Beiträge zu „lambdafizieren“. Hier ist der aktualisierte Code zu Continuations in Java, der deutlich die Mächtigkeit der Lambdas und Default-Methoden zeigt:

import java.util.function.Function;

public interface Cont<R,A> {

    R runCont(Function<A,R> fn);

    public default <B> Cont<R,B> bind(final Function<A,Cont<R,B>> f){
        return k -> Cont.this.runCont(a -> f.apply(a).runCont(k));
    }

    public static <R,T> Cont<R,T> Return(final T t) {
        return fn -> fn.apply(t);
    }
}

Und das Beispiel:

import java.util.function.BiFunction;

public class PythExample {

    public static <R> BiFunction<Integer, Integer, Cont<R, Integer>> pythCont() {
        return (x, y) -> Cont.<R, Integer>Return(x * x).bind(
                a -> Cont.<R, Integer>Return(y * y).bind(
                        b -> Cont.<R, Integer>Return(a + b)));
    }

    public static void main(String... args) {
        PythExample.<Void>pythCont().apply(3, 4).runCont(
                r -> { System.out.println(r);  return null; });
    }
}

Aus der abstrakten Klasse ist (dank Default-Methode) ein Interface geworden, um die Lambda-Syntax nutzen zu können. Auch das Anwendungsbeispiel wurde deutlich gestrafft. Wie man schön sehen kann, sind die einstigen Monstrositäten jetzt tatsächlich „benutzbar“, auch wenn man sich sicher erst an die Syntax gewöhnen muss.

Top Ten „Was man an Java verbessern könnte“

Kurz vor dem langersehnten Java 8-Release drängt sich mir die Frage auf, was mich an Java am meisten stört, oder anders gesagt, was man (auch mit den modernen Sprachmitteln) unbedingt besser machen sollte, wenn man nicht auf Kompatibilität achten müsste. Dabei will ich gar nicht von gravierenden Neuerungen reden, die den Charakter der Sprache komplett ändern würden, sondern von den kleinen, vermeidbaren Hässlichkeiten. Natürlich ist das ein ziemlich kontroverses Thema, und jeder wird da seine eigene Liste haben…

  1. Unnötige Schlüsselwörter vermeiden: volatile, transient und strictfp könnten Annotationen sein, instanceof könnte zu einer Methode von Object werden
  2. Arrays keine Extrawurst mehr braten: Ein Array könnte sich syntaktisch an den Collections orientieren (auch wenn es vom Compiler „hintenherum“ anders behandelt wird) und müsste bei Zuweisungen invariant sein, um ArrayStoreExceptions zu vermeiden.
  3. Einen „Selbsttyp“ einführen: So wie this für das aktuelle Objekt steht, müsste ein generischer Typ This für die aktuelle Klasse stehen. Damit sind Tricksereien wie z.B. in der Typsignatur der Enum-Klasse nicht mehr nötig. Elternklassen und Interfaces können so problemlos Methoden definieren, die die konkrete Klasse als Rückgabewert besitzen.
  4. Primitive als generische Typen erlauben: Entsprechender Code kann automatisch generiert werden, ähnlich wie in Scala mit @specialized.
  5. Mehr Sicherheit gegen Nullpointer-Exceptions: Verbindliche, geprüfte Annotationen für Argumente, die null sein können.
  6. Object entrümpeln: Was soll die clone()-Methode in Object? Muss jedes Object als Lock dienen können, wozu soll man notify() und wait() mitschleppen? Wieso equals(), wenn nicht jede Klasse wirklich „vergleichbar“ ist? Wieso hashCode(), wenn viele Klassen nicht als Schlüssel einer Map taugen? Weg damit, in eigene Interfaces.
  7. Vernüftiges Serializable: Ein bisschen mehr Unterstützung wäre nicht schlecht, etwa über Annotationen (z.B. um einen „Konverter“ anzugeben, der eigentlich nicht-serialisierbare Member doch serialisieren kann).
  8. Unveränderliche Collections: Nein, nicht das, was Collections.unmodifiableList und so liefern, sondern immutable Collections, die ein neues Objekt liefern, wenn z.B. ein Element hinzugefügt oder gelöscht wird.
  9. String zu einem Iterable machen: Es ist völlig unverständlich, warum man nicht mit einer erweiterten For-Schleife über einen String iterieren kann.
  10. Vergleiche verbessern: Comparable streichen, Comparator.compare() ein Enum zurückgeben lassen, statt dafür int zu missbrauchen.

Wie sieht eure Liste aus?

Monoide in Java

Eine Abstraktion aus Haskell, die problemlos in Java abgebildet werden kann, sind Monoide. Keine Angst, die Idee dahinter ist so simpel, dass der bombastische Name schon fast ein wenig peinlich ist.

Zuerst einmal haben wir eine assoziative binäre Operation, die uns eine Halbgruppe beschert.

public interface Semigroup<T> {
    //a binary associative operation
    public T o(T t1, T t2);
}

Zu einem richtigen Monoid fehlt dann nur noch ein neutrales Element:

public interface Monoid<T> extends Semigroup<T> {
    //the neutral element regarding o
    public T empty(); 
}

Es gibt nützliche Klassen, die Halbgruppen, aber keine Monoide sind (ein Beispiel aus Haskell wäre der Typ „NonEmpty“ für nicht-leere Listen), deshalb haben ich die zwei Interfaces nicht zusammengefasst.

Wenn wir diese Interfaces implementieren, sollten wir darauf achten, dass wir die Gesetze einhalten, nämlich die Assoziativität: o(x,o(y,z)) = o(o(x,y),z) und die „Neutralität“ des neutralen Elements: o(empty,x) = o(x,empty) = x.

Welche Monoide fallen uns nun ein? Wie wäre es mit Zahlen und Booleans:

public enum IntMonoid implements Monoid<Integer> {
    Sum(){
        @Override
        public Integer empty() {
            return 0;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return t1 + t2;
        }
    },
    Product(){
        @Override
        public Integer empty() {
            return 1;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return t1 * t2;
        }
    },
    Min(){
        @Override
        public Integer empty() {
            return Integer.MAX_VALUE;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return Math.min(t1, t2);
        }
    },
    Max(){
        @Override
        public Integer empty() {
            return Integer.MIN_VALUE;
        }

        @Override
        public Integer o(Integer t1, Integer t2) {
            return Math.min(t1,t2);
        }
    }
}

public enum BoolMonoid implements Monoid<Boolean> {
    And(){
        @Override
        public Boolean empty() {
            return Boolean.TRUE;
        }

        @Override
        public Boolean o(Boolean t1, Boolean t2) {
            return t1 && t2;
        }
    },
    Or(){
        @Override
        public Boolean empty() {
            return Boolean.FALSE;
        }

        @Override
        public Boolean o(Boolean t1, Boolean t2) {
            return t1 || t2;
        }
    }
}

Oder auch Strings:

public enum StringMonoid implements Monoid<String> {
    Append(){
        @Override
        public String empty() {
            return "";
        }

        @Override
        public String o(String t1, String t2) {
            return t1 + t2;
        }
    }
}

Analoges könnte man für Listen oder Sets definieren. Nun fragt man sich sicher langsam, was man alles damit anstellen kann. Eine der Hauptanwendungen ist das „Falten“, also das Zusammenfassen aller Werte eines Container-Typs:

public enum Fold {
    ;

    public static <T> T fold(Semigroup<T> semigroup, T start, T... ts) {
        T result = start;
        for(T t : ts) {
            result = semigroup.o(result, t);
        }
        return result;
    }

    public static <T> T fold1(Monoid<T> monoid, T... ts) {
        return fold(monoid, monoid.empty(), ts);
    }

    public static <T> T fold(Semigroup<T> semigroup, T start, Iterable<T> ts) {
        T result = start;
        for(T t : ts) {
            result = semigroup.o(result, t);
        }
        return result;
    }

    public static <T> T fold1(Monoid<T> monoid, Iterable<T> ts) {
        return fold(monoid, monoid.empty(), ts);
    }
}

Das sieht dann so aus:

import static rummage.monoid.Fold.*;
import static rummage.monoid.StringMonoid.*;

System.out.println(fold1(Append,"Eins","Zwei","Drei","Vier"));
//EinsZweiDreiVier

Leider ist hier die Stringverkettung nicht so effizient wie mit einem StringBuilder, also sollte man aufpassen, dass man nicht zuviele Teilstrings auf diese Weise verkettet. Im „richtigen Leben“ würde ich deshalb eine spezialisierte Methode für Append in Fold bereitstellen.

Man kann auch neue Monoide aus vorhandenen basteln:

public enum DualMonoid {
    ;
    public static <T> Monoid<T> dual(final Monoid<T> monoid) {
       return new Monoid<T>() {
           @Override
           public T empty() {
               return monoid.empty();
           }

           @Override
           public T o(T t1, T t2) {
               return monoid.o(t2,t1);
           }
       };
    }

    public static <T> Semigroup<T> dual(final Semigroup<T> semigroup) {
        return new Semigroup<T>() {
            @Override
            public T o(T t1, T t2) {
                return semigroup.o(t2,t1);
            }
        };
    }

}

Damit funktioniert dann folgender Trick:

import static rummage.monoid.Fold.*;
import static rummage.monoid.StringMonoid.*;
import static rummage.monoid.DualMonoid.*;
...
System.out.println(fold1(dual(Append),"Eins","Zwei","Drei","Vier"));
//VierDreiZweiEins

In Haskell hat man noch wesentlich mehr Monoide, z.B. für Funktionen („Endo“) oder für algebraische Datentypen wie Maybe, Either und Tupel, und mehr Möglichkeiten, diese zu kombinieren. In Java sind die „bequemen“ Anwendungsmöglichkeiten insbesondere durch fehlende Closures etwas eingeschränkt, weshalb auch unser Fold im Vergleich zu Haskells Typklasse „Foldable“ bescheiden ausfällt.

Trotzdem finde ich es interessant, solche Abstraktionsmöglichkeiten einmal näher zu untersuchen, als immer die gleichen stupiden Schleifen zu schreiben. Und auch wenn die Schleifenlösung einfacher erscheint, gibt es Tücken: Wer noch nie bei der Minimumsuche den Startwert einmal fälschlich mit Integer.MIN_VALUE belegt hat, werfe das erste Bit… Gerade kompliziertere Operationen sind in einem Monoid sicher aufgehoben – hat man das einmal richtig hinbekommen, kann nichts mehr schiefgehen.

Continuations in Java

Continuations sind eine nützliche Sache, ob nun beim Compilerbau oder für Webanwendungen. Kein Wunder, dass Scala Continuations (genauer gesagt „Delimited Continuations“) schon „eingebaut“ hat, und dass auch für Java entsprechende Bibliotheken wie javaflow oder RIFE existieren (hier ein kleines Beispiel für die Anwendung). Übrigens bin ich alles andere als ein Experte auf diesem Gebiet, ich verstehe so ungefähr die Idee dahinter, aber praktische Erfahrungen damit habe ich nicht.

Allerdings hat mich diese Haskell-Wiki-Seite neugierig gemacht, wo die Arbeitsweise der Cont-Monade in Haskell erklärt wird. Der Code auf dieser Seite lässt sich fast eins zu eins nach Java übertragen, wenn man von fehlenden Closures (a.k.a. Lambdas) einmal absieht, und irrwitzige Typ-Signaturen in Kauf nimmt. Zuerst helfen wir Java mit ein paar Pseudo-Closures auf die Sprünge:

public interface F1<A,B> {
    public B $(A a);
}

//nur zur Bequemlichkeit
public abstract class F2<A,B,C> implements F1<A,F1<B,C>> {

    public abstract C $(A a, B b);

    @Override
    public F1<B,C> $(final A a) {
        return new F1<B,C>() {
            @Override public C $(B b) {
                return F2.this.$(a,b);
            }
        };
    }
}

Man verzeihe mir den etwas ungewöhnlichen (aber völlig „legalen“) Methodennamen $, bei dem es sich um einen kleinen Pun auf Haskells $ handelt, das auch nichts anderes tut, als eine Funktion mit ihrem Argument aufzurufen. Nun die Cont-Monade in Minimalausstattung, nämlich der return-Funktion (die mit Javas return überhaupt nichts zu tun hat) und bind (in Haskell wäre das der (>>=)-Operator):

public abstract class Cont<R,A> {

    public abstract R runCont(F1<A,R> fn);

    public static <R,T> Cont<R,T> Return(final T t) {
        return new Cont<R,T>() {
            @Override public R runCont(F1<T,R> fn) {
                return fn.$(t);
            }
        };
    }

    public <B> Cont<R,B> bind(final F1<A,Cont<R,B>> f){
        return new Cont<R,B>() {
            @Override public R runCont(final F1<B, R> k) {
                return Cont.this.runCont(new F1<A,R>(){
                    @Override public R $(A a) {
                        return f.$(a).runCont(k);
                    }
                });
            }
        };
    }
}

Diese Definition ist direkt aus dem Haskell-Wiki abgeschrieben, wobei ich natürlich Cont und seine Monaden-Typklassen-Instanz zusammengefasst habe (sonst wäre die Verwendung noch umständlicher geworden). Ich habe einmal das dortige Pythagoras-Beispiel implementiert, um zu zeigen, dass der Code wirklich funktioniert.

public class PythExample {

    public static <R> Cont<R, Integer> addCont(Integer a, Integer b) {
        return Cont.Return(a + b);
    }

    public static <R> Cont<R, Integer> squareCont(Integer x) {
        return Cont.Return(x * x);
    }

    public static <R> F2<Integer, Integer, Cont<R, Integer>> pythCont() {
        return new F2<Integer, Integer, Cont<R, Integer>>() {
            @Override public Cont<R, Integer> $(final Integer x, final Integer y) {
                return PythExample.<R>squareCont(x).bind(new F1<Integer, Cont<R, Integer>>() {
                    @Override public Cont<R, Integer> $(final Integer a) {
                        return PythExample.<R>squareCont(y).bind(new F1<Integer,Cont<R,Integer>>() {
                            @Override public Cont<R, Integer> $(final Integer b) {
                                return PythExample.<R>addCont(a, b);
                            }
                        });
                    }
                });
            }
        };
    }

    public static <R> F1<R, Void> print() {
        return new F1<R, Void>() {
            @Override public Void $(R r) {
                System.out.println(r);
                return null;
            }
        };
    }

    public static void main(String... args) {
        PythExample.<Void>pythCont().$(3, 4).runCont(PythExample.<Integer>print());
    }
}

Wie erwartet gibt dieses Monster 25 aus. Ich weiß, das Beispiel ist nicht besonders cool, aber es funktioniert, und viel mehr will ich mir bei der aktuellen Syntax auch nicht antun – an pythCont() habe ich eine ganze Weile gebastelt. Natürlich habe ich mir die Frage gestellt, wie das ganze mit besseren Lambdas laufen würde, und sowohl lambdaj– wie auch Approval Test-Closures getestet, beide ohne Erfolg: Erstere hatten keine geeignete Typsignatur, letztere führten den Code schon beim Erstellen (und dann natürlich nochmal beim eigentlichen Aufruf) aus, beides absolute Show-Stopper.

Es spricht nichts dagegen, den vorhandenen Code weiter aufzubohren (z.B. callCC, mehr Monaden-Funktionen, Simulation von do-Blöcken, sinnvollere Beispiele), auch wenn das schnell haarig werden kann. Das sieht natürlich anders aus, sobald Java „echte“ Closures unterstützt. Trotzdem ist es cool, dass sich Continuations ohne Bytecode-Manipulation, Reflection o.ä. in Java implementieren lassen.

Update:
Hier die gleiche Funktionalität in Java 8: Continuations in Java 8

Diamanten in Java

Java verfügt weder über Mehrfach- noch über Mixin-Vererbung. Insofern erscheint eine Diskussion des Diamant-Problems reichlich müßig. Trotzdem bin ich gerade darüber gestolpert, und habe einen Ansatz entwickelt, der – allerdings auf Kosten der Übersichtlichkeit – Code-Duplizierung vermeidet. Nehmen wir an, folgende Interfaces seien gegeben:

public interface Base {
    public void base();
    public void useBase();
}

public interface Foo extends Base {
    public void foo();
    public void useFoo();
}

public interface Bar extends Foo {
    public void bar();
    public void useBar();
}

public interface FooBar extends Foo, Bar {
    public void useFooAndBar();
}

Die useXYZ-Methoden können allgemein unter Rückgriff auf die anderen Methoden des Interfaces oder der Super-Interfaces implementiert werden, und sollten deshalb in abstrakte Klassen ausgelagert werden. Natürlich kann die abstrakte Klasse für FooBar nur von einer der beiden in Frage kommenden abstrakten Klassen erben, sagen wir von der zu Foo. Dann haben wir folgendes Szenario:

public abstract class BaseAbstract implements Base {
    public abstract void base();
    public void useBase() {
        System.out.println("using Base.base()");
        base();
    }
}

public abstract class FooAbstract extends BaseAbstract implements Foo {
    public abstract void foo();
    public void useFoo() {
        System.out.println("using Foo.foo() and Base.base()");
        foo();
        base();
    }
}

public abstract class BarAbstract extends BaseAbstract implements Bar {
    public abstract void bar();
    public void useBar() {
        System.out.println("using Bar.bar() and Base.base()");
        bar();
        base();
    }
}

public abstract class FooBarAbstract extends FooAbstract implements FooBar {
    public abstract void bar();
    //DUPLICATED
    public void useBar() {
        System.out.println("using Bar.bar() and Base.base()");
        bar();
        base();
    }
    public void useFooAndBar() {
        System.out.println("using everything");
        base();
        foo();
        bar();
    }
}

Wie man sieht, bleibt bei dieser Version nichts anderes übrig, als in FooBarAbstract den Inhalt von Bar zu wiederholen.

Mein Vorschlag, das Problem zu lösen, verletzt so einige OO-Prinzipien und wird dadurch unflexibel gegenüber nachträglichen Änderungen. Ich würde ihn nur empfehlen, wenn die Hierarchie wirklich feststeht und man sich damit erhebliche Code-Duplizierungen erspart (also wenn Anzahl und Umfang der useFoo()- und useBar()-Methoden recht groß ist. Der Trick beruht darauf, die Implementierung von useBar() schon in BaseAbstract zu erledigen. Dazu wird eine Hilfsmethode _bar() benötigt, die dort wo vorhanden (also in Bar und FooBar) einfach zum „echten“ bar(), das ja vom Nutzer der abstrakten Klasse bereitgestellt werden muss, weiterleitet:

public abstract class BaseAbstract implements Base {
    public abstract void base();

    public void useBase() {
        System.out.println("using Base.base()");
        base();
    }
    
    //Ersatz-Methode für bar()
    protected void _bar() {
       throw new UnsupportedOperationException(); 
    }
    
    //Code, der eigentlich in BarAbstract gehört
    public void useBar() {
        System.out.println("using Bar.bar() and Base.base()");
        _bar(); //benutzt die Ersatz-Methode
        base();
    }
}

public abstract class FooAbstract extends BaseAbstract implements Foo {
    public abstract void foo();
    public void useFoo() {
        System.out.println("using Foo.foo() and Base.base()");
        foo();
        base();
    }
}

public abstract class BarAbstract extends BaseAbstract implements Bar {
    public abstract void bar();

    //Delegation, sonst funktioniert useBar() nicht
    @Override protected void _bar() { bar(); }
}

public abstract class FooBarAbstract extends FooAbstract implements FooBar {
    public abstract void bar();

    //Delegation, sonst funktioniert useBar() nicht
    @Override protected void _bar() { bar(); }
    
    public void useFooAndBar() {
        System.out.println("using everything");
        base();
        foo();
        bar();
    }
}

Wie so oft wird mein Code keinen Schönheitspreis gewinnen, weil er mit den Beschränkungen von Java kämpft. Es ist ein Kompromiss, der zur Wahrung des DRY-Prinzips andere Konventionen verletzt. Man sollte sich sehr genau überlegen, ob diese Technik an einer bestimmten Stelle wirklich sinnvoll ist, aber wenn sie es ist, kann sie einige Arbeit sparen.

Wie immer bin ich natürlich neugierig, ob jemand eine bessere Idee hat.