highJ: Haskell-Typklassen in Java


Heute will ich ein wenig über mein neuestes Projekt namens highJ schreiben. Eigentlich steht das „high“ für „higher kinded types“ (Typen höherer Ordnung), aber die Assoziation zu „highjack“ ist durchaus gewollt. Zum Thema Typen höherer Ordnung und Typklassen habe ich ja schon etwas geschrieben, deshalb soll es hier auch mehr um die Realisierung in Java gehen.

Ausgangspunkt meiner Reise war die Frustration, dass man nicht mal ein gescheites Funktor-Interface in Java schreiben kann, denn die dort vorgestellte Lösung funktioniert zwar, ist aber ziemlich „sperrig“, wie ich schon damals schrieb. Schon bei der nächsten Abstraktionsstufe, einem applikativen Funktor, versagte meine damalige Methode völlig. Im Rückblick verwundert es schon, dass ich zwar den Grund des Scheiterns verstand, aber lange nicht auf eine Lösung kam – wahrscheinlich weil ich einfach nicht akzeptieren wollte, dass in Java etwas wie List<T> in dieser Form niemals als Typ höherer Ordnung durchgehen würde. Der Trick ist, dass man die Liste nett verpacken muss.

Eigentlich ist es ganz logisch: In Java ist es kein Problem, wenn der Parametertyp T einer Liste nicht bekannt ist – das ist der allseits bekannte Typ-Polymorphismus erster Ordnung. Ein Funktor besteht aber im Kern aus einer Methode fmap, die ein X<A> nimmt und mit Hilfe einer übergebenen Funktion A -> B in ein X<B> umwandelt, wobei X eine Art Container (wie etwas List) ist. A und B sollen natürlich frei wählbar sein, also gehören sie als Typparameter zur fmap-Methode, und nicht zum Funktor selbst, sonst verliert das Konstrukt jegliche Flexibilität (wie bei meiner ursprünglichen Implementierung schön zu sehen ist). Und wer will schon für jede Kombination von A und B einen neuen Funktor erstellen müssen?

Gut, aber was passiert nun mit dem X? Dieses X muss natürlich ein Typparameter des Funktors werden, aber wie soll das gehen? Zu X gehört ja selbst ein Typparameter, und bei dem wollen wir uns nicht festlegen, denn er soll ja in der fmap-Methode einmal mit A und einmal mit B belegt werden. Aber betrachten wir das Problem einmal andersherum: Was ist, wenn X keinen Typparameter hätte? Versuchen wir einfach mal, einen Funktor zu schreiben:

//Pseudocode
public interface Functor<X>  {
    public <A, B> X?B fmap(F<A, B> fn,  X?A xa);
}

F ist hier natürlich einfach ein Funktions-Objekt, wie z.B. in der Bibliothek functionaljava. Die Frage ist, wie können wir X jeweils mit A oder B irgendwie verbinden? Die Antwort ist geradezu peinlich trivial: Wie brauchen ein Objekt, das sowohl X wie auch seinen Typparameter selbst als Typparameter hat. In highJ habe ich dieser Klasse einen etwas ungewöhnlichen Namen verpasst, nämlich nichts weiter als den Unterstrich. Der Grund wird schnell klar, wenn man viel Code lesen muss, der solche Signaturen enthält: Bereits ein Buchstabe wäre schon zuviel gewesen. Hier unsere neue Definition:

public interface Functor<X>  {
    public <A, B> _<X, B> fmap(F<A, B> fn,  _<X, A> xa);
}

Was ist nun im Unterstrich-Objekt gespeichert? Natürlich der „echte“ Typ, der durch X repräsentiert wird. Da das Unterstrich-Objekt aber zu allen möglichen X-Typen passen soll, bleibt uns nichts anderes übrig, als einfach ein Object zu verwenden:

//vereinfacht
public final class _<X,T> {
     private final Object data;

     public _(Object data) {
        this.data = data;
     }

     public Object read() {
        return data;
     }     
}    

Keine Angst, so unsicher habe ich es in highJ nicht implementiert, aber es geht hier ja nur um’s Prinzip. Wie würde nun eine Funktor-Implementierung für List aussehen? Zuerst brauchen wir unser X, dass wir ListOf nennen:

//vereinfacht
public final class ListOf  {
    public static <T> _<ListOf, T> wrap(List<T> list) {
        return new _<ListOf, T>(list);
    }
    
    public static <T> List<T> unwrap(_<ListOf, T> listWrapper) {
        return (List<T>) listWrapper.read();
    }
}

Die Klasse macht nicht mehr, als eine Liste ein- und wieder auszupacken. Beim Auspacken gibt es einen hässlichen Cast, aber in highJ ist dieser relativ sicher, denn ich habe einige Vorkehrungen getroffen, damit jedes X für seinen „eigenen“ Typen _<X,T> verantwortlich ist, und niemand anders ihn einpacken und auspacken darf. Wenn ListOf sicher sein kann, dass es seinem _<X,T> bei der Erzeugung eigenhändig eine List<T> mitgegeben hat, ist es auch „sicher“, dass beim Auspacken wieder eine List<T> drin ist. Wer natürlich hier mit Raw-Types oder Reflection zu tricksen versucht, ist selber schuld, wenn er auf die Nase fällt.

Nun als krönender Abschluss unsere Funktor-Implementierung für Listen:

public class ListFunctor implements Functor<ListOf>  {
    public <A, B> _<ListOf, B> fmap(F<A, B> fn,  _<ListOf, A> listA) {
        List<B> listB = new ArrayList<B>();
        for(A a : ListOf.unwrap(listA)) {
           listB.add(fn.f(a));
        }
        return ListOf.wrap(listB);
    }
}

Das ist der ganze Zauber, auf diesem Konzept beruht meine ganze Bibliothek. Nun könnte man einwenden, dass der ganze Aufwand mit dem Ein- und Auspacken die Sache unpraktikabel macht – und das habe ich anfangs auch gedacht. Der Clou ist aber, dass sich mit diesem Konzept Haskells Typklassen fast eins zu eins übersetzen lassen. Und das wiederum bedeutet, dass ein ganzes Arsenal an nützlichen Maschinen bereitsteht, mit dem so ein verpackter Wert bearbeitet werden kann – und dazu muss man ihn nur einmal am Anfang einpacken, und erst ganz am Ende wieder auspacken. Ich habe auch versucht, „Übersetzungsklassen“ wie ListOf komfortabler zu gestalten, was das Handling zumindest erträglich macht.

Neben dem bescheidenen Funktor gibt es inzwischen Bifunktoren, Monaden, Foldables, Arrows und vieles mehr. Als Datentypen verwende ich Klassen von functionaljava, und auch dort gibt es einige „Übersetzer“: ListOf, OptionOf, EitherOf, FunctionOf, PairOf. Ich bin übrigens selbst erstaunt, wie schnell die Bibliothek wächst. Das Ganze kommt mir manchmal fast etwas magisch vor: Ich brauche bloß den oft ziemlich unverständlichen Haskell-Code rein mechanisch nach Java zu übersetzten, und selbst so verrückte Sachen wie Kleisli-Arrows „funktioneren“ dann einfach. Und das wiederum gibt mir die Hoffnung, dass vielleicht am Ende doch etwas Nützliches bei der Sache herauskommen könnte. Ich habe jedenfalls meinen Spaß daran und lerne einige Ecken von Haskell kennen, die mir bisher völlig fremd waren.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s