Frege — bringing purely functional programming to the JVM! [Pirates of the JVM]
When we launched the Pirates of the JVM series, we promised we would put the spotlight on each and every programming language in the JVM universe so here we go. Our next port of call – Frege! We talked to Ingo Wechsung, the inventor of Frege, about the advantages and disadvantages of this language, its core principles and more.
We’re well into this journey across the JVM landscape. Having spent time in in the Dynamic Sea with Golo, we’ve been exploring the Functional Sea with Cloture and Xtend. Now, we’re stopping in with Frege, to discover more about this purely functional Haskell for the JVM.
Frege is named after Gottlob Frege, the German mathematician who can be considered the father of modern formal logic and analytic philosophy. This Haskell is non-strict and purely functional. Just as the original Frege would have liked!
Frege enjoys a strong static type system with type inference. The non-strict – also known as lazy – evaluation makes it easy to use. Frege compiles to Java, runs on the JVM, and uses any Java library you want. It can be used inside any Java project.
Frege – Background Information
JAXenter: What was your motivation for inventing Frege? What does Frege have to offer that other languages fail to provide?
The Frege project has come about rather gradually. Roughly 10 years ago, there was an article on a Perl blog that I regularly read. It presented the ML language, which focuses on writing entire programs without any type declarations (as in Perl) and simultaneously ensuring that those programs would nonetheless be type secure (not as in Perl). The magic word was type inference: one doesn’t have to write specific types down because the compiler finds out for itself and makes sure that everything is in its correct order. That really fascinated me and I wanted to understand how such a thing was possible.
At the time, there wasn’t so much information on the internet as there is nowadays, but after a while I found some work by Simon Peyton Jones, one of Haskell’s fathers. It was a good introduction into the world of types. Obviously, it was also an introduction to Haskell as well; because of course Simon Peyton Jones has his examples in Haskell.
So I studied that and some other works and tried to implement my favorite type checker in Perl. I succeeded doing so, learning and understanding a lot along the way. But above all, I had discovered that Perl wasn’t my favorite language anymore – Haskell was. I also had a lot of professional work with Java this time around, hence the idea to do something like Haskell for the JVM.
After many mistakes, confusions, and intermediate stages, the first real breaking point was reached at May 2011 when “A Compiler for Frege” was made public through the BSD license.
As a result, there was, until recently, only one purely functional programming language for the JVM.
One of Frege’s lead proponents, Dierk König, also notes that the type guarantees are also preserved if you call Java from Frege. This cannot be done by other known languages.
JAXenter: Can you describe the core principles of the language (if possible with short code examples)
Frege matches Haskell 2010 up until a few minor details, but adds a native interface which can make data types and methods of its mother language Java available in Frege. Anyone who has Haskell down cold can immediately start with Frege. The reverse is also true: anyone who learns Frege can easily switch to Haskell later.
With Frege / Haskell, we’re dealing with modular, strictly typed, purely functional programming languages. Generated programs use demand evaluation (lazy evaluation).
The main points being:
- A powerful type system
- Algebraic data types
- Parametric polymorphism (a similar but broader concept as (e.g.) generic types in Java)
- Function types, even of higher order
- Type classes
- Separation of pure functions and code, which is subject to page effects (like input / output)
- Java-imported types. All primitive Java types as well as Strings, BigInteger and others are available per default.
- Function without page effects
- Declarative, rich syntax
- Pattern matching
- List comprehension
- Partial function application
- All data are invalriable values (value semantic)
- Demand assessment (lazy evaluation), allows the handling of infinite data structures
- What doesn’t exist:
- Statements (assignment, loops, etc.)
- Null isn’t included in any type defined in Frege. Optional values can be modeled by using the maybe-type parameterization. This excludes the confusion of values that must be present and optional values, resulting in cleaner and more refactorable code, if the rules of the game change: if e.g. a value was originally mandatory, but is optional now, the compiler displays all locations where the “no value present” case must be treated.
- Result: Frege programs run without null pointer exception
JAXenter: What would a typical program with Frege look like? (if possible with code example)
Programs are collections of modules. Commonly, modules contain related data types or functions. Modules can import types or functions of other, previously compiled modules and are conveyed into Java classes of the same name. Also, modules which contain the main function can directly be executed using the java command.
I present a small, commented example:
- Line 1: The module clause eventually determines how the generated class will be named.
- Lines 4, 16, 31, 36: Although essentially unnecessary, type declarations for top-level functions are willingly written and used as a kind of documentation. Of course, the compiler checks whether the type is correct – cheating is impossible.
- For merge e.g., a function type is declared. Each argument is preceded by the type of said argument, and past the last arrow, the result type follows. Lowercase letters are type variables. The first argument of merge is, however, a function which accepts two arguments of unknown types, and supplies in return a value of the Ordering type. The second and third arguments are lists of elements of the same type as in the comparison function and as result, another one of those lists is promised.
- Line 5: Left to the equals sign, it shows what is to be defined: Namely merge with 3 arguments, which are named comp, xss and yss.
- Syntactic Side note: In both, definition and utilization of functions, the corresponding arguments are not placed in brackets, but simply written in succession. That is, we write in Frege: “fry 10 eggs” instead of “fry (10, eggs)”.
- Lines 6-12: case initiates pattern matching for the specified expression. A list is either empty (the pattern would be ), or consists of a head element, followed by the rest of the list (written hd:tl, whereas hd and tl represent additional patterns). The code of case in line 5, up to the arrow in line 6, thus means: Investigate the argument xss. If it is not an empty list, provide the components from the expression to the right of the arrow under the names x and xs (This specific way of naming components is widespread and is intended to symbolize: An x, followed by further x-es).
- Note that the indentation is important: patterns starting in the same column belong together (only if you write the same expression using curly braces and semicolons, the indentation will be rendered unimportant). Thus, if xss is an empty list, the program would go to line 12.
- The compiler checks whether all possibilities have been treated through pattern matching. Otherwise, a warning is issued.
- Line 8: Here, the comparison function (which was passed as an argument) is used to compare x and y. The return value is of the predefined type Ordering. It can be LT, EQ or GT.
- Line 10: The pattern _ matches every value. It is used when the value to the right of the arrow is not needed.
- Lines 9, 10: As an expression a : as means, that a list is to be constructed from the values a and as, where both can be arbitrarily complex expressions. a will become head element of the new list, whereas as represents the rest. Since function calls have higher precedence than the use of operators, we get by without any brackets.
- It is easy to verify the correctness of merge at this point: Apart from special cases, where on of the two arguments is empty, it is obvious that the result’s head will be one of the heads from the input lists. Furthermore, the corresponding residual list is included in the recursion and thus the recursion will end, as long as the lists are finite.
- Lines 17 – 28: Instead of writing one expression, you can also write several clauses to define a function (e.g. sortBy). This is often clearer and makes no difference semantically.
- Lines 17, 18, 19: First, the trivial cases are treated. For a list with 2 elements (written [x, y]), the elements are, if necessary, exchanged, thus bringing them in the correct order.
- Lines 23 – 28: In case of a longer list, it is divided into two halves, which are sorted separately and mixed afterwards. Again, one can prove that the recursion for finite lists must end. Lists of length up to 2 result immediately. Longer ones are halved in each recursion step, which leads very quickly to sub-lists of length 2 or smaller.
- In this clause, the use of local definitions (introduced by where) is made to keep matters clear. Standard functions (take, drop, length, div) are equally used. At the same time, div is syntactically used as an operator on line 28, encasing the function name in backticks. This can be done with all 2-digit functions, even your own. The left operand is, in doing so, used as the first, the right as the second argument.
- Line 31: At this point, we restrict which types are suitable for the type variable a, namely all which belong with the type class Ord. In our case, this means that there is a type-specific comparison function, i.e. the compare function is overloaded for this type.
- Lines 32, 38 – 42: Non-functional programmers commonly expect both sortBy and merge to be written using the operator <= or a generic comparison function, and are certainly wondering at this point why the comparison function is “laboriously” passed as an argument. For functional programmers however, “simple comparison” (standard function compare) is the special case. Whether strings are sorted alphabetically or by descending length, the sorting algorithm remains the same! The latter can be archived by providing a comparison function which computes the argument’s length and then compares them in reversed order.
JAXenter: For what kind of applications/use cases is Frege well-suited? – for which ones it is not?
Frege is neither specialized nor unsuitable for certain applications.
As discussed above, however, the following can be derived:
- Frege is more appropriate the more code components interact and the more unclear on how they do so. The type system ensures that everything is correct, even after changes.
- Both competition and parallelism can be realized simply and safely. Since data is not modified, there are no data races.
- Regardless, there are certainly applications where one would have to reckon with performance problems because of immutable data, i.e. where a mutating algorithm can save space and be significantly faster. In the case of scarce resources Frege would be unsuitable.
JAXenter: What is the current state of the language?
Roughly matured. There are few changes and bugfixes to come. The development focuses no longer on new language features, but rather on libraries, tools, etc.
JAXenter: How can people interested in Frege get started?
There is the compiler, a command line interpreter (also available as a web page), an Eclipse plugin, and various build tool support. Everything is linked in detail and up-to-date at the GitHub page for Frege.
People who don’t know Haskell should learn it first. If possible, use FregeTools in those exercises, tutorials, etc.
People need only download the software and can get started. Note the Wiki entry for the differences in Frege-Haskell.
Ingo Wechsung was born in Jena in 1960 and now lives near Reutlingen with his wife. He started his first assembler programs with punch cards starting in 1979. Over the years, he’s used PL / 1, Pascal, C, Perl, SQL, Java, and Haskell. He has been working as an IT consultant for Contexto Automation in Reutlingen for over 20 years. He is always busy with Frege, dogs, piano playing, reading, and hiking in the Alps.
Pirates of the JVM — The series:
Are you familiar with all the programming languages from the JVM universe? Have you discovered them all?
If the answer is “no”, we’ll leave no stone unturned in the search for knowledge. Therefore, the Pirates of the JVM infographic is accompanied by a series of articles in which we put the spotlight on the languages you may or may not know.
Don’t forget to check out the Pirates of the JVM series.