Frege: a Haskell-like Language for the JVM
Frege, named after the German mathematician Gottlob Frege, is a purely functional, strongly typed language for the JVM that is so similar to Haskell that “most idiomatic Haskell code will run unmodified or with only minimal, obvious adaptions”.
According to Frege’s developers, Frege brings to the JVM a type system that is “unparalleled with its combination of power, simplicity and expressiveness”. It supports non-strict evaluation and type inference and enforces immutability, which is the default, and purity, so side-effects can be used only when declared. Frege supports most of Haskell’s features, such as:
- ADTs and typeclasses with parametric polymorphism
- Higher rank types
- Pattern matching
- list comprehension
- point-free style
- mathematical abstractions such as functors, monoids, semigroups, and monads.
A significant advantage of Frege’s is Java interoperability, so it is possible to both reuse Java libraries and call Frege code from Java. Frege is especially strict when it comes to calling Java and requires programmers to declare Java types in Frege terms. This allows it to preserve the type system integrity and thus enforce purity, thread safety, and laziness.
Having Frege available on the JVM means that a mostly Java project can benefit from Haskell’s power to solve specific problems.
This is an example of a Frege program that displays the current time on standard output:
module examples.CommandLineClock where data Date = native java.util.Date where native new :: () -> IO (MutableIO Date) -- new Date() native toString :: Mutable s Date -> ST s String -- d.toString() --- 'IO' action to give us the current time as 'String' current :: IO String current = do d <- Date.new () -- reads system timer, hence IO d.toString main args = forever do current >>= print -- print formatted date print "\r" -- followed by carriage return stdout.flush -- make sure it's shown Thread.sleep 999L -- wait 0.999 seconds
The Frege compiler, standard library, REPL, and more tools, are all written in Frege itself, which should attest the language stability and completeness.
Frege has an online REPL to try out its features.
InfoQ has spoken with Ingo Wechsung, Frege’s creator.
Could you recount Frege’s history? How was it born, how did it evolve?
Frege actually came into existence merely by accident. Back in 2003/2004, I read a blog post about type inference in ML. I was totally fascinated and tried to understand what at that time seemed like black magic to me. Eventually, I stumbled over a paper by Simon Peyton-Jones (who is co-inventor of Haskell and creator of GHC, the Glasgow Haskell Compiler, whose leading maintainer he still is). The paper was about “Practical Type Inference for Higher Ranked Types” and it contained an example implementation of a type checker in Haskell. But my favorite language at that time was Perl, and I didn’t understand Haskell at all. So I decided to implement the type inference algorithm in Perl, in order to really understand it. This worked out quite well, however, the “code” that the type checker worked on was a representation of a sugared lambda calculus encoded in Perl. (Nowadays you’d call it an “embedded DSL”). And since I always enjoyed writing parsers and such, I added a frontend that would read the expressions from a text file. Once this was working, I thought that one could as well translate the type-checked expressions to Perl code. It worked, but was miserably slow. No way to have a self hosting compiler. This was Frege 1.
Once I realized that Perl was too slow for this business, I looked for a faster host language. I was fluent in PASCAL, C, C++ and several scripting languages but I decided against C on the ground that there existed already Haskell compilers that emitted C, so this would’ve been nothing new. And I had yet to learn Java, so why not make this a pet project in Java? You see, like many programmers, I prefer learning by doing.
So, in late 2006/ early 2007, I started Frege 2, with Java as host language. And I learned a lot along the way. Unfortunately, I had no clear idea of the language to compile. This was because I still was too uneducated with respect to functional programming, despite my reading anything I could get. But believe it or not, this was not too much back then. Fortunately, people like Simon Peyton-Jones, Phil Wadler, Paul Hudak to name a few, had published a lot, though mostly academic papers. I often had a hard time to understand but a fraction of those papers.
In particular, I had a hard time understanding monads. I even interrogated my father, who is a mathematician by profession, but his research field was number theory. I called up the Wiki article about monads, and asked him to explain it to me. He read it and said something like: “Yes, this is very nice stuff. You have objects, and transformations and homomorphisms and identity. This is all really easy. What’s not to understand here? And, after all, why do you want to know this?” Well, that was exactly the question I had: Why do I, as a programmer, have to know about monads?
Nevertheless, I managed to make some self hosting Frankenstein language, and that was Frege 2. It had no clear semantics, it was not pure, and it was neither lazy nor strict. And it even had a while loop. It was a mess, but it did work. And it taught me some lessons about the virtues of purity, immutability and composability. I was very unhappy with the whole thing, since in the process of writing the compiler of Frege 2 in Frege 2, I recognized the shortcomings of my apporach more and more clearly.
This was also the time when I started the blog fregepl.blogspot.com. You can find there my original postings from 2007 and later, which reflect my struggles at that time.
In 2008/2009, little was done, as I had some personal affairs to manage, and in addition moved into another house, so instead of programming, I was busy painting walls, etc.
The experiences from Frege 2 finally led me to a complete overhaul of the language. This time, I had a clear goal, a subset of Haskell 98 (later Haskell 2010). This goal was achieved (more or less) in May 2011, and I published the Frege on code.google.com. Later, we moved to GitHub, as Google Code started to deteriorate.
The next year I was busy fixing all sorts of bugs and developing the Eclipse plugin for frege.
Meanwhile, early adopters had found out about the existence of Frege. I name here Yorrik Laupa and Daniel Gronau. They encouraged me to adopt a different layout of the “category theory” type classes Applicative, Monad, and so on, and contributed implementations thereof. (This “Applicative-Monad” structure was proposed for years in the Haskell community, but only adopted recently in GHC.)
Only a bit later, Marimuthu Madasamy, a programmer from New York with Indian heritage, started to contribute. He is the creator of the Frege REPL, which exists in an online version and as a stand-alone application one can use locally. He also did the JSR 223 scripting support, that allows one to run Frege scripts from Java. Over the years, his steady and passionate effort has done very much for Frege. Too sad we never met each other in real life, I’d really like to hug that guy!
James Earl Douglas and Mark Derricut cared about the Web Page, SBT and Maven Support and checked out OSGi conformity of Frege. Later, Sean Corfield contributed a plugin that enables the Clojure lein tool to work with Frege, and Mark Perry did the same with gradle, the Groovy build tool. (So, at this time, Frege actually has 4 build tools!)
One of the biggest wins for the popularity of Frege is certainly the collaboration of Dierk König, famous in Groovy circles for his book “Groovy in Action”, a thoughtful and knowledgeable advocate of the pure functional principles and a JVM-ecosystem expert at the same time. He is busy travelling around and giving Frege talks at conferences, writes blog posts, and last, but not least, contributed a JavaFX version of the Frege REPL.
What is Frege’s level of maturity? Do you know of any projects that are using it?
First off, there are no commercial projects using it as far as I know. There are, however, activities in the education sector, i.e. people writing their master thesis about Frege or using Frege.
The maturity is a double edged sword. While I would claim that the language itself and compiler is fairly settled and robust, it is the libraries where much work is to be done yet, along with the accompanying infrastructure (i.e. a module repository). On the one hand, ports of eminent Haskell libraries, on the other hand important JVM libraries must be done, tested, documented and made available. This is perhaps a good place to advertise that every contributor interested in FP is welcome. Newbies included! It goes without saying that we don’t ask for nationality, race, religion, gender, age or other things that are irrelevant with repect to programming. Already, I am proud to say that the Frege community, as tiny as it may be, is multi-ethnic and international. The sun never goes down in Frege land!
Are you planning to close the feature gap with Haskell? What is on Frege’s roadmap?
This will be the hot topic of the upcoming Frege Day in Basel, on Sep 11, at the premisies of the Canoo Corporation, which is organized by Dierk (@mittie on twitter, in case one wants to attend). I think it will be a great day, where a core of the community will meet and discuss the future of Frege.
The main points, as far as I see it, will be:
Community building. Desirable IMHO would be that the Frege community understands itself as part of the Haskell community, and the Haskell community in turn accepts “us” as part of their kind.
Ever more Haskell compatibility. In fact, Frege should first and foremost become and be advertised as Haskell variant or dialect. In any case, Frege will finally become a true subset of Haskell 2010, plus support for some well known GHC extensions, plus some extra goodies. (Already today, there is code that compiles in Frege and Haskell likewise, and behaves the same.)
Code generation will exploit Java 8 features, while staying usable and (at least partly) binary compatible with Java7. Even Java 6, for Android development, should not be abandoned too early. In general, keep up with JVM developments and make the best out of it.
Libraries, libraries, libraries! (and tools, of course) support for more well known, proven and frequently used GHC exstensions. For example, multi paramerter type classes, GADTs or existential types come to mind.
In short, Frege should seek to excel and convince as “the Haskell variant on the JVM”, and be a practical pure FP language for the JVM.
In closing, I should point out that we enjoy and want to keep up friendly, cooperative relationships with our fellow functional JVM programmers of the Scala and Clojure camp. I say this because I know the tendency of journalists and writers to make a story juicy by inventing and exaggerating conflicts and rivalry. This is not so in our case, sorry! As you might note, Scala, Clojure, Groovy, JRuby and others have a certain niche on the JVM, and Frege is no exception: we offer (uniquely, as far as I know) the purely functional, non-strict FP variant. But that does not mean that we want to forcibly impose this paradigm onto others.