Suche
Im Ozean der funktionalen Programmierung

Frege – das Haskell für die JVM: Eine Einführung [Pirates of the JVM]

Redaktion JAXenter

In der Serie Pirates of the JVM stellen wir die Programmiersprachen der Java-Plattform vor. Heute im Fokus: Frege – das Haskell für die JVM. Wir haben uns mit Frege-Erfinder Ingo Wechsung unterhalten, der uns im Gespräch die Vor- und Nachteile der Sprache und dessen Einsatzgebiete näher brachte. Abgerundet wird das Ganze durch ein kleines Anwendungsbeispiel und einige Informationen zur Entstehungsgeschichte.

Auf der Seekarte der JVM-Sprachen navigieren wir heute in den funktionalen Ozean. Neben den Platzhirschen Scala und Clojure sind hier einige kleinere Sprachen angesiedelt. Frege ist eine davon. Im Frege-Slogan „Haskell for the JVM“ wird schon deutlich, worauf die Sprache abzielt: Die komplette Implementierung von Haskell 2010 für die Java-Plattform.

Klick auf die Karte für die komplette Infografik.

Frege – der Hintergrund

JAXenter: Was hat dich dazu bewogen, Frege zu entwickeln? Welche Vorteile bietet Frege, die andere Programmiersprachen nicht haben?

Ingo Wechsung

Ingo Wechsung: Das Frege-Projekt hat sich eher zufällig entwickelt. Vor über zehn Jahren gab es einen Artikel in einem Perl-Blog, den ich damals regelmäßig las. Darin wurde die Sprache ML vorgestellt. Wobei der Fokus darauf lag, dass man ganze Programme ohne irgendwelche Typdeklarationen schreiben könne – wie in Perl – und das Programm dennoch typsicher ist – nicht wie in Perl. Das Zauberwort war Typ-Inferenz: Man muss nicht hinschreiben, was der Typ ist, denn der Compiler findet es selbst heraus und stellt sicher, dass alles seine Ordnung hat. Das hat mich absolut fasziniert, und ich wollte verstehen, wie so etwas geht. Damals gab es noch nicht so viele Informationen im Internet wie heute, aber nach einiger Zeit fand ich eine Arbeit von Simon Peyton Jones, einem der Väter von Haskell. Das war ein guter Einstieg in die Welt der Typen, und nebenbei in Haskell, denn die Beispielimplementierung lag natürlich in Haskell vor.

Das Zauberwort war Typ-Inferenz: Man muss nicht hinschreiben, was der Typ ist, denn der Compiler findet es selbst heraus.

Ich studierte also diese und einige andere Arbeiten, und versuchte, den Typchecker in Perl – damals mein Favorit – zu implementieren. Dies gelang auch und ich hatte unheimlich viel gelernt und verstanden. Vor allem war Perl nicht mehr meine Lieblingssprache, sondern Haskell. Außerdem hatte ich zu der Zeit beruflich oft mit Java zu tun. Und so kam die Idee auf, so etwas wie Haskell für die JVM zu machen. Nach vielen Irrungen und Wirrungen, Teilerfolgen und Zwischenstufen war es dann im Mai 2011 so weit: Ein in Frege geschriebener Frege-Compiler wurde der Öffentlichkeit unter BSD-Lizenz verfügbar gemacht. Damit gab es die erste und bis vor kurzem einzige rein funktionale Programmiersprache für die JVM. Auch bleiben die Typgarantien erhalten, wenn man Java aus Frege heraus aufruft. Das kann von den bekannten Sprachen sonst keiner.

JAXenter: Kannst du die Kernprinzipien der Sprache darlegen? 

Ingo Wechsung: Frege entspricht bis auf wenige nebensächliche Details Haskell 2010, zuzüglich eines native Interface, mit dem man Datentypen und Methoden der Wirtssprache Java in Frege verfügbar machen kann. Wer Haskell beherrscht, kann mit Frege sofort loslegen. Ebenso umgekehrt: Wer Frege lernt, kann später problemlos auf Haskell umsteigen. Bei Frege/Haskell haben wir es mit einer modularen, streng typisierten, rein funktionalen Programmiersprache zu tun. Die erzeugten Programme verwenden Bedarfsauswertung, Lazy Evaluation genannt.

Frege in Kürze

Mächtiges Typsystem

  • algebraische Datentypen
  • parametrischer Polymorphismus (ähnliches, aber weitergehendes Konzept wie Generic Types z. B. in Java)
  • Funktionstypen, auch höherer Ordnung
  • Typklassen
  • Trennung von reinen Funktionen (Pure Functions) und Code, der mit Seiteneffekten (etwa Ein/Ausgabe) behaftet ist
  • von Java importierte Typen. Sämtliche primitiven Java-Typen sowie Strings, BigInteger und weitere sind standardmäßig verfügbar

Funktionen ohne Seiteneffekte

  • deklarative, reichhaltige Syntax
  • Pattern Matching
  • List Comprehensions
  • Partial Function Application

Semantik

  • alle Daten sind unveränderliche Werte (Value Semantic)
  • Bedarfsauswertung (Lazy Evaluation) ermöglicht Umgang mit unendlichen Datenstrukturen

Was es nicht gibt:

  • Statements (Zuweisung, Schleifen, usw.)
  • null ist in keinem in Frege definierten Typ enthalten. Optionale Werte können mittels Parametrisierung des Maybe-Typs modelliert werden. Dies schließt Verwechslung von Werten, die vorhanden sein müssen, und optionalen Werten aus und führt zu klarerem und besser refaktorierbarem Code, falls sich die Spielregeln ändern. War z. B. ein Wert ursprünglich obligatorisch und ist nun optional, zeigt der Compiler alle Stellen an, wo der Fall „kein Wert vorhanden“ behandelt werden muss
  • Folge: Frege-Programme laufen ohne Null Pointer Exception.
  • Subtyping

JAXenter: Für welche Art von Anwendungen eignet sich Frege besonders gut? Für welche eher weniger?

Ingo Wechsung: Frege ist weder für bestimmte Anwendungen spezialisiert noch ungeeignet. Frege ist aber desto besser geeignet, je mehr Codekomponenten interagieren und je unübersichtlicher die Art und Weise ist, wie sie das tun. Das Typsystem stellt sicher, dass auch nach Änderungen alles stimmt.

Frege ist weder für bestimmte Anwendungen spezialisiert noch ungeeignet.

Sowohl Konkurrenz als auch Parallelität lassen sich einfach und sicher realisieren. Da Daten nicht modifiziert werden, gibt es z. B. keine Data Races. Ungeachtet dessen gibt es sicher Anwendungsfälle, wo man wegen immutabler Daten mit Performanceproblemen rechnen müsste, d.h. wo ein mutierender Algorithmus deutlich schneller und speicherplatzsparender sein kann. In dem Fall knapper Ressourcen wäre Frege ungeeignet.

JAXenter: Wie ist der derzeitige Status Quo der Sprache?

Ingo Wechsung: Recht ausgereift. Es gibt nur wenige Änderungen und Bugfixes. Entwicklungsschwerpunkt sind keine neuen Sprachfeatures, sondern eher Libraries, Tools, usw.

JAXenter: Wie steigt man am besten in die Arbeit mit Frege ein?

Ingo Wechsung: Es gibt den Compiler, einen Kommandozeileninterpreter – ebenso als Webseite verfügbar–, ein Eclipse-Plug-in und diverse Build-Tool-Unterstützung. Unter https://github.com/Frege/ wird detailliert und aktuell auf all dies verlinkt.

Menschen, die Haskell nicht können, sollten dies zuerst lernen. Dabei möglichst in Übungen und Tutorials die Frege Tools verwenden. Menschen, die Haskell können, brauchen nur die Software herunterzuladen und können loslegen. Dabei den Wiki-Eintrag zu den Unterschieden Frege-Haskell beachten

Beispiel: Ein typisches Programm mit Frege

Ein Frege-Programm ist eine Sammlung von Modulen. Typischerweise enthält ein Modul zusammengehörige Datentypen oder Funktionen. Ein Modul kann Typen und Funktionen eines anderen, zuvor kompilierten Modules importieren. Module werden in gleichnamige Java-Klassen übersetzt. Ein Modul, das die Funktion main enthält, kann mit dem Java-Kommando direkt ausgeführt werden.

Beispiel-Code für ein Programm in Frege

Zeile 1: Die Module-Klausel legt im Wesentlichen fest, wie die generierte Klasse heißt.

Zeilen 4, 16, 31, 36: Obwohl strenggenommen unnötig, werden Typdeklarationen für Top-level-Funktionen gern hingeschrieben und als eine Art Dokumentation verwendet. Der Compiler prüft natürlich nach, ob der Typ korrekt ist. Es ist nicht möglich, zu schummeln.

Für merge z. B. wird ein Funktionstyp deklariert. Vor jedem Rechstpfeil steht der Typen eines Argumentes, nach dem letzten Pfeil der Typ des Resultats. Kleinbuchstaben sind Typvariablen. Das erste Argument von merge ist wiederum eine Funktion, die zwei Argumente unbekannten Typs entgegennimmt, und einen Wert vom Typ Ordering liefert. Das zweite und dritte Argument sind Listen mit Elementen vom gleichen Typ wie auch die Argumente der Vergleichsfunktion. Eine eben solche Liste wird als Ergebnis versprochen.

Zeile 5: Links vom Gleichheitszeichen steht, was definiert wird, nämlich merge mit drei Argumenten, denen hier die Namen comp, xss und yss gegeben werden.

Syntaktischer Hinweis: Sowohl bei der Definition als auch der Anwendung von Funktionen werden die Argumente nicht in Klammern gesetzt, sondern einfach hintereinander geschrieben. D. h. wir schreiben in Frege „brate zehn Eier“ statt „brate(zehn, Eier)“.

Lesen Sie auch: Frege – echt funktionale Programmierung auf der JVM [Interview]

Zeilen 6-12: case leitet ein Pattern Matching für den angegebenen Ausdruck ein. Eine Liste ist entweder leer, das Muster dafür ist [], oder besteht aus einem Kopfelement und dem Rest der Liste, geschrieben hd:tl, wobei hd und tl für weitere Muster stehen. Der Code von case in Zeile 5 bis zum Pfeil in Zeile 6 bedeutet also sinngemäß: Untersuche das Argument xss, und wenn es keine leere Liste ist, mache mir die Komponenten in dem Ausdruck rechts vom Pfeil verfügbar unter den Namen x und xs. Diese Art der Benennung der Komponenten ist weit verbreitet, und soll symbolisieren: Ein x gefolgt von weiteren x-en.

Man beachte, dass die Einrückung wichtig ist. In derselben Spalte startende Muster gehören zusammen. Man kann das auch mit geschweiften Klammern und Semikolons schreiben, dann ist die Einrückung unwichtig. Folglich würde, falls xss die leere Liste ist, bei Zeile 12 weitergemacht.

Der Compiler prüft, ob beim Pattern Matching sämtliche Möglichkeiten behandelt wurden. Andernfalls erfolgt eine Warnung.

Zeile 8: Hier wird die als Argument übergebene Vergleichsfunktion verwendet, um x und y zu vergleichen. Rückgabewert ist ein Wert des vordefinierten Typs Ordering. Dies kann LT, EQ oder GT sein.

Zeile 10: Das Muster _ passt auf jeden Wert. Es wird verwendet, wenn der Wert rechts vom Pfeil nicht benötigt wird.

Zeilen 9, 10: In einem Ausdruck bedeutet a : as, dass eine Liste aus den Werten a und as konstruiert wird, wobei sowohl a als auch as beliebig komplexe Ausdrücke sein können. Das Kopfelement der neuen Liste wird a und der Rest entspricht as. Da Funktionsaufrufe höhere Präzedenz haben als Anwendung von Operatoren, kommen wir hier ganz ohne Klammern aus.

Man kann hier recht einfach die Korrektheit von merge überprüfen. Abgesehen von den Sonderfällen, in denen eines der beiden Argumente leer ist, wird deutlich, dass das Kopfelement des Resultats eines der Kopfelemente der Eingabelisten sein wird. Ferner, dass die zugehörige Restliste in die Rekursion eingeht und somit die Rekursion enden wird, sofern es sich um endliche Listen handelt.

Zeilen 17 bis 28: Statt eines case-Ausdrucks kann man auch mehrere Klauseln schreiben, um eine Funktion (hier sortBy) zu definieren. Dies ist oft übersichtlicher. Semantisch macht es keinen Unterschied.

Zeilen 17, 18, 19: Zuerst werden die trivialen Fälle behandelt. Bei einer Liste mit zwei Elementen (geschrieben [x, y]) werden die Elemente ggf. getauscht, damit sie in die richtige Reihenfolge kommen.

Lesen Sie auch: Pirates of the JVM – die Infografik, die Serie, das Spiel

Zeilen 23 bis 28: Im Falle einer längeren Liste wird diese in zwei Hälften geteilt, die separat sortiert und dann gemischt werden. Auch hier kann man den Beweis führen, dass die Rekursion für endliche Listen enden muss. Listen der Länge bis zwei führen sofort zum Ergebnis. Längere werden in jedem Rekursionsschritt halbiert, was sehr schnell zu Teillisten der Länge zwei oder kleiner führt.

In dieser Klausel wird Gebrauch von lokalen Definitionen (durch where eingeleitet) gemacht, damit die Sache übersichtlich bleibt. Ebenso kommen Standardfunktionen (take, drop, length, div) zur Anwendung. Dabei wird div in Zeile 28 syntaktisch als Operator verwendet, indem der Funktionsname in Backticks eingeschlossen wird. Dies kann man mit allen zweistelligen Funktionen machen, auch mit eigenen. Dabei wird der linke Operand als erstes, der rechte als zweites Argument verwendet.

Zeile 31: Hier wird eingeschränkt, welche Typen für die Typvariable a in Frage kommen. Nämlich nur solche, die der Typklasse Ord angehören. In unserem Falle bedeutet das, es existiert eine typ-spezifische Vergleichsfunktion, d. h. die Funktion compare ist für diesen Typ überladen.

Zeilen 32, 38-42: Nicht-funktionale Programmierer erwarten normalerweise, dass sowohl sortBy als auch merge unter Verwendung eines Operators <= oder einer generischen Vergleichsfunktion geschrieben werden, und fragen sich sicher schon die ganze Zeit, warum die Vergleichsfunktion umständlich als Argument herumgereicht wird. Für funktionale Programmierer ist hingegen einfaches Vergleichen (Standardfunktion compare) der Sonderfall. Ob Strings alphabetisch oder nach absteigender Länge geordnet werden, der Sortieralgorithmus bleibt derselbe! So kann man letzteres erreichen, indem man eine Vergleichsfunktion bereitstellt, die die Länge der Argumente berechnet und die dann in vertauschter Reihenfolge vergleicht.

Ingo Wechsung, geb. 1960 in Jena, lebt heute in der Nähe von Reutlingen, verheiratet, ein Kind, stanzte ab 1979 seine ersten Assembler-Programme in Lochkarten, lernte im Lauf der Zeit PL/1, Pascal, C, Perl, SQL, Java und Haskell. Er arbeitet seit 20 Jahren als IT-Berater für contexo Gesellschaft für Systemintegration mbH, Reutlingen, beschäftigt sich in der immer zu knappen Freizeit mit Frege, Hunden, Klavierspielen, Lesen und Wandern in den Alpen.

Mehr zum Thema:

Pirates of the JVM – die Infografik, die Serie, das Spiel

Geschrieben von
Kommentare

Schreibe einen Kommentar

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