</img>

Die Auswahl an Programmiersprachen für die JVM ist riesig. Auch für funktionale Programmierer wird einiges geboten, von Scala über verschiedene ML-Dialekte bis hin zu Clojure. Die Nische der Haskell-artigen, also rein funktionalen Sprachen mit Bedarfsauswertung (lazy evaluation) und Typinferenz, blieb jedoch bislang unbesetzt, trotz wachsender Beliebtheit von Haskell außerhalb der JVM-Welt. Dies soll sich nun mit der neuen Programmiersprache Frege ändern. Der folgende Artikel soll einführend Idee und Motivation des Projekts vorstellen.

JVM ohne Haskell

Eine häufig gestellte Frage im Haskell-Wiki ist folgende: Warum ist GHC nicht für JVM oder .NET verfügbar?

Die Antwort ist recht detailliert, und lautet zusammengefaßt ungefähr so: Es sei ein lohnendes, aber nicht zu unterschätzendes Unterfangen, die größten Schwierigkeiten ergäben sich daraus, daß man letztlich die GHC Laufzeitumgebung samt aller primitiven Operationen für die jeweiligen Umgebungen neu implementieren und dann auch pflegen müßte. Diese Herausforderung sei jedoch „mostly broad rather than deep“.

Letzteres ist meiner Auffassung nach eine Fehleinschätzung. Es lauern durchaus schwierige, meines Wissens bisher ungeklärte, technische Probleme, beispielsweise im Bereich der Nebenläufigkeit: Das Thread-Modell der JVM ist ein ganz anderes als das der GHC-Umgebung. Man denke nur an GHC-Features wie green threads. Ob so etwas 1:1 in der JVM implementiert werden kann, ist durchaus nicht klar.

Eine Nummer kleiner

Wenn 100% Haskell-Kompatibilität so schwer (oder evtl. auch gar nicht) zu haben ist, geht es dann vielleicht eine Nummer kleiner?

Ohnehin ist ja voraussehbar, daß Programme in einem fiktivem JVM-Haskell vorrangig der Interoperabilität mit anderen JVM-Sprachen wegen geschrieben würden - diejenigen Programme, die so etwas nicht brauchen, laufen ja bisher auch ohne JVM-Ballast wunderbar. Genau solcher JVM-Haskell-Code wäre aber mit der restlichen Haskell-Welt unverträglich in dem Sinne, daß er nicht einfach in einer anderen Umgebung übersetzt und ausgeführt werden könnte, und umgekehrt gälte dasselbe für Haskell-Programme, die C/C++ Bibliotheken via FFI nutzen: ohne weiteres wären diese wiederum auf der JVM nicht lauffähig. Nur derjenige Teil, der keinerlei Code aus anderen Sprachen nutzt, wäre in beiden Welten nutzbar.

Mit der Programmiersprache Frege wird solch ein eine Nummer kleinerer Weg beschritten. Der Anspruch ist, die Essenz, derentwegen viele Menschen zu Haskell-Freunden wurden, in die JVM-Welt zu holen:

  • die geniale Haskell-Syntax ohne geschweifte Klammern und Semikolons
  • das Hindley-Milner Typsystem, das vollständige Typinferenz gewährleistet, ergänzt durch Funktionstypen höherer Ordnung und Typklassen (vorerst nur einfache)
  • das Ausführungsmodell mit Bedarfsauswertung (lazy evaluation)
  • die Trennung von rein funktionalem Code von solchem, der mit Seiteneffekten behaftet ist mit Hilfe des Typsystems (Monaden)

Frege ist eine Sprache etwa im Umfang von Haskell 2010, zuzüglich einiger Erweiterungen, die aus GHC bekannt sind, allerdings ohne FFI (foreign function interface). An dessen Stelle tritt ein ähnlicher Mechanismus, der aber speziell auf das Einbinden von JVM-Typen (also Klassen und Interfaces) und JVM-Methoden zugeschnitten ist.

Wie groß die Ähnlichkeit zwischen Haskell und Frege ist, mag folgendes kleine Beispielprogramm in Frege zeigen. Tatsächlich gibt es nur zwei Hinweise darauf, daß dies nicht Haskell ist. Der geneigte Leser wird sicher Spaß dabei haben, sie zu finden.

module Main where

import Data.List

main _ = print $ take 10 pyth
    where
        pyth = [ (x, y, m*m+n*n) |
                    m <- [2..], n <- [1..m-1],
                    let { x = m*m-n*n; y = 2*m*n },
               ]

Vorteile der Unabhängigkeit

Trotz der bewußt aufgegebenen Haskell-Kompatibilität laufen in Frege die Dinge vielfach genauso wie in Haskell.

Es gibt jedoch Unterschiede, die aus der grundsätzlichen Entscheidung herrühren, in erster Linie eine praktische Sprache für die JVM sein (oder werden) zu wollen und erst in zweiter Linie eine möglichst Haskell-ähnliche.

So werden beispielsweise für die primitiven Datentypen die entsprechenden der JVM verwendet. Folglich ist Bool in Frege kein algebraischer Datentyp, sondern ein primitiver, und es gibt zwei Literale true und false anstelle der Konstruktoren True und False. Ebenso ist String nicht dasselbe wie [Char], sondern basiert auf der eingebundenen Klasse java.lang.String, die wie alle anderen eingebundenen JVM Typen auf Frege-Ebene als abstrakter Datentyp erscheint.

Die Unterschiede setzen sich fort auf der Ebene der Standardbibliotheken (soweit schon vorhanden), insbesondere in Bezug auf Ein- und Ausgabe, Ausnahmen, Threads und dergleichen. Es werden hier jeweils die entsprechenden Java-SE API genutzt.

Zum Beispiel nutzen Ein- und Ausgabe in Frege Klassen wie java.io.BufferedReader und java.io.PrintWriter, wie in folgendem Programm, das die Standardeingabe stdin zeichenweise liest und die Zeichen in umgekehrter Reihenfolge auf der Standardausgabe stdout wieder ausgibt. Die Funktionen read und write sind jeweils IO-Aktionen, die auf die gleichnamigen Java-Methoden zurückgreifen.

--- Reverse the standard input
module examples.ReverseStdin where

main _ = loop []  >>= mapM_ stdout.write

loop :: [Int] -> IO [Int] 
loop acc  = do
    ch <- stdin.read             -- read next char (as Int)
    if ch < 0 then return acc    -- end of input?
    else loop (ch:acc)

Es wäre natürlich möglich gewesen, dem Haskell-Standard penibel zu folgen, der Ein- und Ausgabe auf abstrakten Filedeskriptoren (Datentyp Handle aus System.IO) basieren läßt. Dies hätte bedeutet, für Frege eine eigene Ein-/Ausgabeschicht bereitzustellen, die natürlich sämtlichen anderen JVM Sprachen völlig unbekannt wäre. Für die Interoperabilität mit letzteren würde dann doch wieder die von Java bekannte Funktionalität gebraucht, sowie Abbildungen zwischen den verschiedenen Modellen.

Die unterschiedliche Basis für Ein-/Ausgabe hindert am Ende nicht, daß bekannte Funktionen wie getChar oder putStrLn existieren und aus Nutzersicht genauso funktionieren wie in Haskell, jedoch gibt es zahlreiche von Haskell 2010 spezifizierten systemnahen Pakete, Datentypen und Funktionen nicht. Auf der anderen Seite haben wir die Erfahrung gemacht, daß rein funktionaler Code praktisch unverändert von Haskell übernommen werden konnte, so z.B. Module wie Data.List.

Der Vorteil der Nutzung des Java-API liegt u.a. darin, daß Frege nur ein minimales Laufzeitsystem benötigt, das sich hauptsächlich mit Bedarfsauswertung und Funktionen beschäftigt, also mit den Dingen, die in Java unbekannt sind.

Ein weiterer Vorteil der Unabhängigkeit vom Haskell-Standard ist, daß ein Problem von vornherein vermieden werden konnte, über das in Haskell-Kreisen seit vielen Jahren diskutiert wird, ohne daß eine Lösung absehbar wäre. Ich rede von den Feldbezeichnern in Datentypen (record fields). In Haskell sind diese Namen global, was mehrere Datentypen im gleichen Modul mit gleichen Feldnamen unmöglich macht.

In Frege hat jeder Datentyp einen eigenen Namensraum, in dem Feldbezeichner, aber auch beliebige weitere Funktionen definiert sein können, ohne den globalen Namensraum zu beeinträchtigen. Dazu kommen syntaktische Unterstützung für Feldzugriffe sowie Unterstützung des Typsystems für typgesteuerte Feldnamenauflösung.

Nicht zuletzt erlaubt Freges Eigenständigkeit, Dinge richtig zu machen, die ziemlich unumstritten in Haskell korrekturbedürftig sind. So in einer Frage der mathematisch korrekten Typklassenhierarchie: in Frege war bereits von Anfang an Applicative eine Superklasse von Monad, und demnächst wird die Hierarchie gemäß dem Vorschlag in Edward Kmetts Paket semigroupoids vervollständigt.

Anwendung

Das folgende Beispiel zeigt Übersetzung und Ausführung des obigen Programms von der Linux-Kommandozeile aus. Das JAR-File fregec.jar enthält den selbst in Frege geschriebenen Compiler sowie die Standardbibliothek.

ingo@ubuntu:~/x/dev/frege$ java -jar fregec.jar -d build examples/ReverseStdin.fr 
ingo@ubuntu:~/x/dev/frege$ (echo foo; echo bar) | java -cp fregec.jar:build examples.ReverseStdin 

rab
oof

Dank der Plattformunabhängigkeit der JVM funktioniert dies in völlig gleicher Weise natürlich auch unter Windows-Betriebssystemen.

Status und Ausblick

Frege ist bislang ein Hobbyprojekt des Autors dieses Artikels sowie einer Handvoll Unterstützer. Der offene Quellcode steht unter BSD-Lizenz. Frege ist unfertig und in Entwicklung, sowohl in Hinblick auf implementierte Bibliotheken, Entwicklungs- und Dokumentationstools als auch die Sprache selbst.

Dennoch ist es kein Spielzeug mehr. Außer dem Compiler existiert ein Plugin für Eclipse, sowie ein Interpreter. Hier ein Screenshot des Eclipse-Plugins:


Eine Version des Interpreters läuft als Web-Service, also nur einen Klick entfernt (möglicherweise jedoch nicht auf Telefonen funktionsfähig).

Meine Hoffnung ist, diesem noch weithin unbekannten Projekt mehr Bekanntheit verschaffen zu können. Jeder ist herzlich eingeladen, sich die Sache einmal näher anzuschauen, mögliche Interessenten darauf aufmerksam zu machen oder gar - im besten Falle - etwas beizutragen.

Quellcode, Downloads inklusive Sprachbeschreibung und weiterführende Verweise sind auf der Projektseite zu finden.