Dependency Injection mit der Reader-Monade

Schon wieder nehme ich das böse M-Wort in den Mund! Dabei ist die Reader-Monade kaum mehr als eine einfache Function. Aber eins nach dem anderen.

Zuerst einmal das Datenmodell mit einem Fake-Service:

public class User {
    public long id;
    public String name;

    public User(String name, long id) {
        this.id = id;
        this.name = name;
    }
}

public interface UserService {
    User getUser(long id);

    List<User> findAll();
}

public class UserServiceImpl implements UserService {
    @Override
    public User getUser(long id) {
        return new User("user" + id,id);
    }

    @Override
    public List<User> findAll() {
        return IntStream.of(1,2,5,42).
               mapToObj(this::getUser).
               collect(Collectors.toList());
    }
}

Nun das Grundgerüst der Komponente, die diesen Service gern benutzen würde:

public class UserComponent {
    public User getUser(long id) { ??? }
    public String greet(User user) { ???  }
    public List<User> getAllUsers() { ??? }
    public String greetAll() { ??? }
}

Ohne den UserService läuft natürlich nichts, und wir wollen ihn auch nicht mit gewöhnlichen DI-Frameworks hineinzaubern. Welche Möglichkeiten haben wir dann?

Am naheliegendsten ist sicher, den Service im Konstruktor mitzugeben und in einer Instanzvariable zu speichern. Das Problem dabei ist, dass dann nur dort Objekte konstruiert werden können, wo der „richtige“ Service bekannt ist. Andere benötigte Klassen, die ebenfalls den Service benötigen, müssen als weitere Parameter übergeben werden (was die Initialisierung verkompliziert), oder im Konstruktor initialisiert werden (was zu unschönen Abhängigkeiten führt).

Weiterhin könnte man einfach jeder Methode den Service als Parameter mitgeben, also UserComponent.getUser(long id, UserService service). Das funktioniert, wird aber schnell ziemlich unschön, da dieser Parameter bei jedem einzelnen Aufruf „mitgeschleift“ werden muss.

Wir haben auch eine weitere Möglichkeit, nämlich keinen Wert, sondern eine Funktion zurückzuliefern, als wenn wir sagen wollten: Wenn du uns einen UserService gibst, können wir dir den Wert berechnen: Function getUser(long id).

Mit etwas „Verfeinerung“ ist das die Idee der Reader-Monade. Als erstes stellt sich die Frage, was ist, wenn wir mehr Services oder andere Daten (etwa aus einer Property-Datei) brauchen. Deshalb bündeln wir das Ganze gleich in ein Config-Interface:

public interface Config {
    public UserService userService();
    //später mehr...
}

Dann fällt uns auf, dass alle Methoden den Typ Function<Config, Irgendwas> zurückgeben würden. Da sollten wir uns Schreibarbeit sparen, und diesem neuen Typ gleichzeitig ein paar nützliche Methoden (von denen zwei, nämlich pure und flatMap, das Ding auch formal zu einer Monade machen) verpassen:

//R wie "Reader"
public interface R<A> extends Function<Config, A> {

    @Override
    A apply(Config c);

    static <A> R<A>; pure(A a) {
        return s -> a;
    }

    default <B> R<B> map(Function<A, B> fn) {
        return s -> fn.apply(apply(s));
    }

    default <B> R<B> flatMap(Function<A, R<B>> fn) {
        return s -> fn.apply(apply(s)).apply(s);
    }
}

Damit würde unsere UserComponent so aussehen:

public class UserComponent {

    public R<User> getUser(long id) {
        return config -> config.userService().getUser(id);
    }

    public R<String> greet(User user) {
        return R.pure("Hello " + user.name + "!");
    }

    public R<List<User>> getAllUsers() {
        return config -> config.userService().findAll();
    }

    public R<String> greetAll() {
        return getAllUsers().map(list ->
                list.stream().map(user ->
                        "Hello " + user.name + "!\n").
                        reduce("", String::concat));
    }

}

OK, das sieht erst einmal ziemlich gewöhnungsbedürftig aus. getUser und getAllUsers sind einfach zu verstehen, sie reichen nur die Aufrufe an den Service weiter. Die Methode greet könnte eigentlich ohne Service auskommen, aber jeder weiß, wie schnell sich das ändern kann, und wer will sich schon merken, welche Methode jetzt eine Config braucht und welche nicht? Deshalb wird mit pure einfach ein R erzeugt, das einen Wert zurückliefert und dabei die Config völlig ignoriert. In greetAll sieht man, wie die Methoden aufeinander aufbauen können, in dem man sie mit map- (oder auch flatMap-) Aufrufen miteinander verknüppert. Interessant ist, dass hier überhaupt keine Spur mehr von einem Service oder einem Config-Objekt zu sehen ist, außer dem R-Rückgabetyp.

Wie wird das Ganze nun benutzt? Zuerst einmal braucht man natürlich eine Implementierung von Config. In unserem Mini-Beispiel reicht eine anonyme Klasse:

Config config = new Config() {
    @Override
    public UserService userService() {
        return new UserServiceImpl();
    }
};
...

Dann kann man Methoden wie gewohnt aufrufen, nur muss man überall ein .apply(config) dranhängen:

...
UserComponent userComp = new UserComponent();
System.out.println(userComp.greetAll().apply(config));
...

Natürlich können auch hier einzelne Methoden miteinander verknüpft werden:

...
System.out.println(userComp.getUser(42).
                   flatMap(userComp::greet).apply(config));
...

Das war das Grundprinzip der Reader-Monade als DI-Ersatz. Ich gebe zu, der entstehende Code sieht erst einmal ziemlich ungewöhnlich aus, und ich bin skeptisch, wie gut das Ganze in größeren Systemen funktionieren würde. Trotzdem ist es interessant zu sehen, wie man sich mit „Bordmitteln“ behelfen kann, wenn man kein DI-Framework einsetzen will.

Advertisements

Frege – funktionale Programmierung auf der JVM

Gottlob Frege war ein deutscher Mathematiker und Logiker, der lange vor Alonzo Church über Funktionen mit Funktionen als Argumente nachdachte. Ein schöner Name für eine funktionale Programmiersprache.

Die Sprache Frege lehnt sich stark an Haskell an, nutzt aber nach Möglichkeit die Gegebenheiten der JVM aus. Interessanterweise folgt Frege nicht dem üblichen Ansatz, direkt zu Bytecode zu compilieren, es erstellt stattdessen erst Java-Klassen (die allerdings weniger zur Abendlektüre geeignet sind) und ruft für diese den Java-Compiler auf.

Die auffälligsten Unterschiede zu Haskell sind die Übernahme des Package-Prinzips und von Private-Modifiern (statt Exportlisten) sowie die Nutzung nativer Strings und Primitive. Einige syntaktische Seltsamkeiten von Haskell wurden gestrichen, aber insgesamt fallen die Unterschiede gering aus.

Die Auswahl an Bibliotheken ist überschaubar und auch das Prelude (das Analogon zum Package java.lang) weist noch einige Lücken auf. Trotzdem macht das Vorhandene einen recht soliden Eindruck, es ist genug Dokumentation zum Loslegen vorhanden und es macht Spaß, ein wenig mit Frege herumzuspielen. Wenn die Kernsprache erst einmal stabil ist, sollte es kein Problem sein, geeignete Haskell-Bibliotheken mit geringen Anpassungen zu übernehmen. Außerdem ist auch der Zugriff auf Java-Bibliotheken ebenfalls recht unkompliziert möglich.

Die vorhandenen Ansätze lassen einen umsichtigen Umgang mit Typklassen erkennen (z.B. werden Funktionen wie null oder length verallgemeinert, so dass sie nicht nur auf Listen arbeiten). Das lässt darauf hoffen, dass bei künftigen Erweiterungen der Typklassen-Hierarchie einige von Haskells Fehlern vermieden werden.

Frege ist eine interessante Alternative zu den anderen JVM-Sprachen, deshalb hoffe ich sehr, dass dieses ambitionierte Projekt vorankommt und sich eine Community herausbildet.

Nochmal die Damen

Die berühmten 8 Damen hatte ich schon mal abgehandelt, aber das folgende Stückchen Haskell hat es mir angetan:

--http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Das sieht ein ganzes Stück besser aus als mein eigener Versuch, und die Logik dahinter ist bestechend einfach: safe testet, ob zwei Positionen „sicher“ sind (sich also nicht in der gleichen Reihe, Spalte oder Diagonale befinden). qu nimmt eine Liste mit allen Teillösungen für die Reihen kleiner als k, und prüft dann für jede Liste qs, welche Spalten j in der Reihe k „sicher“ sind, und sammelt alle entsprechenden Listen mit den neuen Positionen. Nun wird qu für 1 bis n aufgerufen, und dabei jeweils die Teillösung des letzten Aufrufs übergeben, was man mit foldr realisieren kann.

Und hier meine Scala-Übersetzung, die sich wieder möglichst nah ans Original halten soll:

object queens {

   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) = 
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }

   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

Zuerst importiere ich die abs-Methode und definiere den Typ (Int,Int) als Pos, weil ich ihn häufiger benötige. Lokale Hilfsfunktionen schreibt man in Scala besser zuerst, so dass man im Beispiel die umgekehrte Reihenfolge wie in Haskell hat. Bei safe gibt es kaum eine Änderung, wenn man davon absieht, dass in Scala leider kein Pattern Matching in der Argumentliste funktioniert. Die Methode qu wird im Prinzip unverändert übernommen, auch wenn die Syntax deutlich abweicht. Ich denke man sieht hier gut, wie stark Haskell den Entwurf von Scala beeinflusst hat, auch wenn man das Scala nicht unbedingt auf den ersten Blick ansieht. Zu guter Letzt kommt der Aufruf von qu über foldRight. In Scala ist foldLeft üblicher und auch performanter (da Haskell „lazy“ ist, scheint es dort umgekehrt zu sein), aber ich will ja dicht am Original bleiben. Da die Argumente für qu in der richtigen Reihenfolge geliefert werden, läßt sich das (k,l) => qu(k,l) wahlweise mit qu(_,_) oder schlicht mit qu abkürzen. Die main-Methode testet den klassischen 8×8-Fall.

Wie ich schon im oben genannten Artikel erwähnt habe, kann man mit Scala normalerweise sehr dicht an einer Vorlage in einer funktionalen Sprache wie Haskell, Clean oder ML bleiben. Natürlich wird durch die unvollständige Typinferenz und ausführlichere „Zeichensetzung“ in Scala alles ein wenig länglicher, aber strukturell ähneln sich die beiden Programme sehr stark. Auch die „Werkzeugkisten“ der beiden Sprachen haben viel gemeinsam, während Dinge wie Tupel, foldRight, Pattern Matching und List Comprehensions in Java fehlen.

So, in Zukunft werde ich die Damen in Ruhe lassen, zumindest hier im Blog… Hatte ich eigentlich schon erwähnt, dass ich Single bin? 😛

OO-Funktionales Gipfeltreffen: Scala und Bla

Wie bringt man einem objektorientierten System Funktionen bei? Scalas Antwort darauf ist, eine Funktion als ein Objekt aufzufassen und viel syntaktischen Zucker draufzustreuen. Mehr dazu hatte ich schon in diesem Artikel geschrieben. Wie sieht es andersherum aus, wie bringt man einem funktionalen System Objekte bei? Es gab und gibt viele Versuche, aber richtig überzeugen konnte mich bisher keiner: Alle Ansätze wirkten irgendwie aufgesetzt und künstlich. Aber ich bin über eine ziemlich unbekannte Sprache gestolpert, bei der sich Objektorientierung sozusagen ganz natürlich ergibt: Bla. Mir ist wirklich schleierhaft, wie so ein elegantes und überzeugendes Konzept so wenig Beachtung finden konnte. Neu ist Bla nun wirklich nicht, es wurde 1996 von Wouter van Oortmerssen geschrieben, der nicht nur andere unkonventionelle Sprachen wie false und Aardapple, sondern auch die 3D-Engines Cube und Cube 2 a.k.a. Sauerbraten entwickelt hat.

Bla fügt dem „üblichen“ funktionalen Mix ein einziges neues Element hinzu: Eine Funktion kann ihre aktelle Umgebung explizit zurückliefern. Tatsächlich lässt sich das self von Bla mit dem this vergleichen, das eine Scala-Funktion als echtes Objekt besitzt. Man muss schon genauer hinsehen, um überhaupt einen Unterschied zu anderen funktionalen Sprachen wie Haskell, OCaml oder Erlang zu bemerken:

-- The Bla Language, 4.2.2
-- http://strlen.com/files/lang/bla/Bla_paper_letter.pdf
stack[T]() = self where
    d = []
    isEmpty = d=[]
    push(x : T) = do d := [x|d]
    pop(): T = d | [] -> raise stack_empty
                 | [h|t] -> h do d := t

Die Funktion stack definiert – wie in funktionaler Sprachen inklusive Scala üblich – ein paar lokale Funktionen, darunter auch die Funktion d, die auf eine Liste mit unseren Daten zeigt. Zurückgegeben wird allerdings nicht irgendein Wert, sondern die „Umgebung“, die sich stack() geschaffen hat.

Das lässt sich nicht ganz nach Scala übersetzten. In Scala würde man vielleicht soetwas schreiben:

class Stack[T] () {
  var d = List[T]()
  def isEmpty = d == Nil
  def push(x : T) = d = x :: d
  def pop: T = d match {
      case Nil => error("stack_empty")
      case h :: t => d = t; h
  }      
}

object Stack {
  def apply[T]() = new Stack[T]()
  
  def main(args: Array[String]) {
    val stack = Stack[Int]()
    stack.push(42)
    stack.push(4711)
    println(stack.pop)
    println(stack.isEmpty)
    println(stack.pop)
    println(stack.isEmpty)
  }
}

Stack hier als Funktion zu definieren wäre nicht besonders sinnvoll. Trotzdem ähnelt die Struktur der Klasse Stack frappierend der Funktion stack[T]() in Bla – mit dem kleinen Unterschied, dass ich am Ende der Klasse kein this hinschreiben muss – die Rückgabe der von Stack erzeugten „Umgebung“ wird stillschweigend vom Konstruktor übernommen.

Das Konzept von Bla erscheint mir einfacher als das von Scala, da es ohne „Magie“ (wie es das Liften von Methoden zu Funktionen oder die apply-Methode ist) auskommt. Das Vererbungsproblem löst Bla sehr einfach: Es gibt ein Schlüsselwort implements, wobei man in der neuen Funktion die gleichen Member bereitstellen muss wie im Original, und ein Schlüsselwort extends, mit dem man zu einer vorhandenen Umgebung einer Funktion neue Member hinzufügen kann. Ein einfaches Modulsystem sorgt für die Datenkapselung.

Der Rest der Sprache ist wie bereits erwähnt recht konventionell, wenn man vom Zuweisungsoperator absieht, der natürlich für die Implementierung veränderlicher Objekte unverzichtbar ist.

Es war für mich als Nicht-C-ler nicht ganz einfach, die Sourcen zu kompilieren, aber da es jetzt läuft, werde ich auch ein wenig damit herumspielen.

Bla ist eine interessante, zu Unrecht fast vergessene Sprache, die ihrer Zeit wohl voraus war, und ich hoffe, dass sie wenigstens Impulse bei der Entwicklung neuer Sprachen geben kann.

Wie funktional ist Scala?

Nachdem ich ein wenig über die funktionale Sprache Clean gelesen hatte, wollte ich auch mal ein Beispiel selber programmieren. Das fiel mir erstaunlich leicht, denn Clean ähnelt der Sprache Haskell, mit dem ich auch schon ein wenig herumgespielt habe. Das Ergebnis ist sicher kein Meilenstein funktionaler Programmierung, aber das Programm läuft. Hier sind also meine acht Damen in Clean:

//Clean 2.2
module Queens
import StdEnv

Start = queens []

queens list 
    | length list == 8 = [list]
    | otherwise = flatten (map (\x = queens [x:list]) (filter (valid list) [1..8]))
    where 
    valid t h = not (isMember h t || diagonal (+) (h+1) t || diagonal (-) (h-1) t)
        where
        diagonal _ _ [] = False
        diagonal op n [h:t] = n == h || diagonal op (op n 1) t

So sieht Code aus, mit dem man OO-Programmierer erschrecken kann. Aber mit ein paar zusätzlichen Informationen klärt sich das Bild: Ergebnis der Berechnung soll eine Liste von Int-Listen sein. Dabei hat jede Int-Liste acht Stellen und gibt eine Brettposition wieder (die n-te Zahl gibt dabei an, in welcher Spalte die Dame in der n-ten Reihe steht). Hat unsere Liste die gewünschte Länge 8, sind wir fertig. Andernfalls (otherwise) nehmen wir die Spaltenpositionen von 1 bis 8, behalten nur die, die nicht von den vorangegeangenen bedroht werden (filter(valid list)), fügen die jeweilige Position an die vorhandene Liste, rufen damit Queens rekursiv auf und liefern die Ergebnisse der einzelnen Aufrufe zusammengefügt (flatten) zurück. Die Unterfunktion valid hat drei Bedrohungsarten zu berücksichtigen: gleiche Spalte und gleiche Diagonale aufsteigend oder absteigend. Für die Diagonalen gibt es eine Unter-Unterfunktion diagonal, bei der auch der Operator mitgeliefert wird, der die Richtung der Diagonale bestimmt (also, ob zur vorhandenen Position +1 oder -1 in der nächsten Zeile gerechnet wird). Eigentlich ganz logisch, wenn man sich nicht von der Syntax erschrecken lässt.

Nun wird Scala oft als objektorientierte Sprache mit etwas funktionalem Flair beschrieben. Das ist auch wenig verwunderlich, schließlich läuft Scala auf der JVM, und die Kompatibilität zu Java wird (zu recht) immer wieder betont. Codeschnipsel, die Scala als „besseres Java“ propagieren sollen, tun ein übriges, um dieses Bild zu festigen. Dabei wird übersehen, dass Scala viel, viel weiter in Richtung funktionaler Programmierung geht als andere gebräuchliche OO-Sprachen, und damit meiner Meinung nach ziemlich genau in der Mitte zwischen den Paradigmen steht. Wie sieht nun mein Beispiel in Scala aus, wenn ich versuche, mich möglichst dicht ans Original zu halten?

object Queens {
  def main(args: Array[String]) { println(queens(Nil)) }
   
  def queens(list: List[Int]):List[List[Int]] = list match {
    case full if full.size == 8 => List(full)
    case _ => def valid(t:List[Int])(h:Int) = {
        def diagonal(op: (Int,Int)=>Int, n:Int, li:List[Int]): Boolean = li match {
          case Nil => false
          case h :: t => n == h || diagonal(op, op(n,1), t)
        }
        ! (t.contains(h) || diagonal(_+_, h+1, t) || diagonal(_-_, h-1, t))
      }
      (1 to 8 toList).filter(valid(list)).map(n => queens(n :: list)).flatten
  }
}

Ich finde, das sieht ziemlich ähnlich aus. Scala hat im Gegensatz zu Haskell und Clean nur eine partielle Typinferenz (der übliche Hindley-Milner-Algorithmus verträgt sich mit OO und vor allem Methodenüberladung nicht), so dass die Aufruftypen und bei rekursiven Funktionen auch die Rückgabetypen angegeben werden müssen. Lokale Funktionsdefinitionen funktionieren ähnlich wie das originale where, wobei man die lokale Funktion besser vor der Benutzung definiert. Der rekursive Aufruf von queens verwendet die gleichen Funktionen wie das Original. In diesem Fall finde ich, dass die objektorientierte Schreibweise vorteilhafter ist: Nimm die Positionsliste, filtere sie nach gültigen Positionen, rufe queens mit der um die jeweilige neue Position ergänzte Liste rekursiv auf, und füge die Ergebnisse zusammen. Man erhält also eine Abarbeitungsreihenfolge in Leserichtung, und nicht umgekehrt.

Der vorgestellte Code zeigt, wie weit man sich in Scala von Java wegbewegen kann, denn dort könnte man nicht einmal annähernd etwas ähnliches schreiben. Wenn man es will, ist mit Scala ein sehr funktionaler Stil möglich, nicht ganz wie in Haskell oder Clean, aber doch sehr dicht dran. Aber das Schöne ist, dass man dazu nicht gezwungen wird. Es ist immer gut, wenn man sich entscheiden kann. Funktionale Programmierung ist keine „Silver Bullet“, aber es lohnt, sich damit zu beschäftigen.

Nachtrag:
Martin Odersky hat gerade einen Artikel veröffentlicht, in dem er Scala als „postfunktionale Sprache“ bezeichnet, und auch auf andere Diskussionen um Scalas „Funktionalität“ verweist. Die neue Bezeichnung gefällt mir. Und Java könnte man dann unter den „dysfunktionalen Sprachen“ einordnen 😀