Wednesday, August 6, 2008

Can Java.next include F#? Please?

Stuart Halloway coined the term "Essence vs. Ceremony" to describe the future of maintainable code in a post-Java world, and we're indebted to him for clearly and uniquely stating the problem with some of the most popular programming languages (historical note: it happened live at Code Freeze 2008 - hooray Minneapolis). Now he's back, this time describing the similarities in the new JVM languages gaining mindshare, a group of languages he's calling Java.next.

So I'll ask the question that is sure to be on the minds of JVM language users everywhere: "Is F# Java.next?" Let's consider it by comparing some Groovy and F# code...

Low-Ceremony Property Definitions - Java.next eases the burden of type, field, accessor, mutator, and constructor creation. F# Record Types fit the bill.

// F#
type Person = {
firstName: string
lastName: string }

let fred = { firstName="Fred"; lastName="Flinstone" }

// Groovy
class Person {
def firstName
def lastName
}

new Person(firstName:
"Fred", lastName: "Flinstone")
Expressive Collections - Java.next offers simple, easy, concise syntax for lists and maps. F# does too. The following code finds all natural number odd squares under 100:
// F#
[ 1 .. 10 ]
|> List.map (fun x -> x * x)
|> List.filter (fun x -> x % 2 = 1)

// Groovy
(1..10).collect{ it * it }.findAll { it % 2 == 1}

Functional programming - Java.next supports functional programming concepts like first class functions, closures, and higher order programming. F# is a functional language, it doesn't just support it. I'm not sure about Clojure, but I'd be willing to conjecture that F# has better FP support than Groovy or Ruby. This code creates a function that performs addition:

// F#
let sum a b = a + b

// Groovy
adder = { add -> { val -> val + add } }
Overriding Operators - F# and Java.next support operator overloading. Groovy supports a limited number of predefined operators. In F# you're just redefining what certain symbols mean, so the options in F# should not be so limited. The motivating example is to produce a custom Rational number type that can be used like this:
balance + (balance * interest)
The syntax for this isn't that pretty in either language, but is a bit more intuitive, in my opinion, in F# than Groovy because there is no special syntax. You define a member of the class just like any other, while Groovy requires a named method and even C++ required an operator keyword.
// F#
type Rational (num:int,denom:int) =
member x.num = num
member x.denom = denom
static member (+) (r1: Rational ,r2: Rational) =
Rational((r1.num*r2.denom) + (r1.denom*r2.num), r1.denom*r2.denom)
static member ( * ) (r1: Rational ,r2: Rational) =
Rational(r1.num*r2.num, r1.denom*r2.denom)

// Groovy

class Rational {
def num
def denom

Rational plus(Rational other) {
new Rational(
num: (this.num * other.denom) + (
this.denom * other.num),
denom:
this.denom * other.denom)
}

Rational multiply(Rational other) {
new Rational(
num:
this.num * other.num,
denom:
this.denom * other.denom)
}
}

Maintainable Exception Handling - I love anyone willing to call checked exceptions a failed experiment. C# doesn't have checked exceptions and it doesn't seem F# does either. So far F# has 5 out of the 8 commonalities with Java.next... could it just be part of this group?

Adding Methods to Existing Types - Working with Groovy's metaprogramming system has been a real joy, with only a few exceptions. Venkat's chapters on the subject in his book are great, and there is always Groovy.mn's presentation. Opening types to add members in F# is possible but I was told it was "bad form". It can be done, but the following is only valid within the "compilation unit" not globally... maybe that's a good thing though. This code adds an isPositive method to our previous Rational type:

// F#
type Rational with
member x.isPositive =
if x.num > 0 && x.denom > 0 then true
elif x.num < 0 && x.denom < 0 then true
else false

// Groovy
Rational.metaClass.isPositive = {
if (delegate.num > 0 && delegate.denom > 0) return true
if (delegate.num < 0 && delegate.denom < 0) return true
false
}

Roll-Your-Own Constructs - I'm not 100% clear on what this means. In Java.next you can "create new constructs that work like core language features". But the example in Clojure just seems to define a function called most that has a calling syntax like other language keywords. My knowledge of F# starts to break down here, but OCaml has a preprocessor that would allow you to do anything (cite: Robert Fischer), and there is purportedly an OCaml library that changes the language to use a Scheme prefix-operator-and-parenthesis syntax. Seems like F# should be up to par in this area. Here's an implementation of a generic most function like the one on Stuart's blog, just for fun (doesn't exactly scale well to larger tuples, though).

// F#
let most (x, y, z) =
match (x, y, z) with
| Some(x), Some(y), Some(z) -> true
| None, Some(y), Some(z) -> true
| Some(x), None, Some(z) -> true
| Some(x), Some(y), None -> true
| _ -> false
Everything is an Object - Java.next languages don't have primitive types... everything is an object. This helps with DSL funness because you can write code like 5.days.from.now, producing a Date object representing 5 days in the future. Cool. But to quote a Yegge post: "Dude, not everything is an object."
F# seems focused on creating operations that work on types rather than adding operations to types. F# still has the .NET value types like int and float, which can't have operations added to them. Adding a method to System.Int32 seems out of the question... at least I can't figure out how, which is quite different from impossible! A preprocessor should make quick work of this, but on the surface it doesn't seem supported. More research on my part is needed here. Bummer, F# only got 7 out of 8 Java.next commonalities.

Conclusion - The only logical conclusion is that we should start work on a .NET implementation running on the JVM. Starting Google Code project in 3...2...1...
Seriously though, cool ideas aren't restricted to the JVM and I've had a great time playing with F# and putting this post together. It's always fun to compare languages, isn't it?
(and curses to blogger's mangling of escape characters and whitespace, I did my best)

13 comments:

Unknown said...

'Extension methods' allow you to add methods to 'int' or whatever. You can do this in C# too.

#light

type System.Int32 with
member x.IsEven() =
x % 2 = 0
let x = 4
printfn "%A" (x.IsEven())

Peter Pascale said...

.Net.next?

I'd be curious to know if there are other contenders that could add to the .Net.next list.

Jon Harrop said...

I'm surprised you have not enumerated the substantial list of hugely-productive features that F# already offers but that the JVM does not support and, consequently, none of these so-called "Java.next" languages can even hope to provide.

For example, tail calls (essential for functional programming), interoperable closures (!), value types (the JVM is still incapable of representing complex numbers efficiently, let alone the multitude of value types used heavily by game and scientific apps) and so on.

As a functional programmer, the lack of tail calls alone makes the JVM a joke platform because it cannot be trusted to handle either combinators (ubiquitous in parsing) or continuation passing style (ubiquituous in concurrent programming).

Your statement about checked exceptions is also interesting. Have you seen OCaml's completely-automated static code analysis tool for checking exceptions with none of the burden of doing it by hand as you must in Java?

leonardoavs said...

Si los metodos de extensión me permiten agregar metodos a otros tipos pero para ello tengo que importan las librerias assemblys que los contengan. Con la metaprogramación esto ocurre en Runtime y en el tipo como tal con lo que no tengo que agregar una referencia a otra clase u otro assembly. Y si quieren ver un lengauje mas poderoso que JRuby o Groovy visiten www.scala-lang.org => que es un lengauje tanto Funcional como OO.

Hamlet D'Arcy said...

@flying frog
Thanks for the leads on other cool F# areas. I'm very new to F# so this helps.

It is my understanding that Scala supports some tail calls via the compiler.

http://saloon.javaranch.com/cgi-bin/ubb/ultimatebb.cgi?ubb=get_topic&f=91&t=000004

But true, this seems supported better in F#.

Do you have a link/project name for the OCaml exception tool?

Anonymous said...

Scala does support tail calls on functions which are *self* recursive, but you are quite correct in saying that the JVM as a whole does not. This makes it impossible for any language on the JVM to support tail call folding on functions which are *mutually* recursive. Since mutual recursion is quite common, it's not hard to see why this is a crippling limitation for FP on the JVM.

With that said, there are efforts afoot to alleviate this situation. The Da Vinci Machine project (MVM) has a number of proposals for additions to the JVM, among them is tail call optimization at the runtime level. In general, there has been a renewed interest in this topic, so I wouldn't be surprised if we see improvement in the near future.

Oh, and Scala does have a combinator library which has no problems at all running in the absence of mutually-recursive tail call optimization. I'm not sure if this is just because they structured everything to be self-recursive, or if they folded the recursion by hand (through reference passing), but however they did it, it works. I've never had a stack overflow in a combinator deployment due to the library itself -- other factors, yes, but not combinators.

Hamlet D'Arcy said...

@brian

The extension methods don't exactly work for me. It is possible to call x.isEven() like you show, but it doesn't seem to be possible to call 4.isEven(), as Ruby and Groovy let you. The error I get on 1.9.4.17 is "This is not a valid numeric literal"

Jon Harrop said...

@Hamlet

OCaml's tool for static analysis of exceptions is called OCamlExc:

http://caml.inria.fr/pub/old_caml_site/ocamlexc/ocamlexc.htm

This is like type inference for checked exceptions: you run a program on your program and it generates all of the checked exception information so that you don't have to work it out by hand and you don't have to litter your source code with it.

Regarding tail calls: Imagine I created a new language called X. My new language X includes an implementation of generics. Unlike other implementations of generics, language X only works reliably when generic functions are instantiated with certain types. You can try to use other types but it will cause your program to crash in an unpredictable way. Absurd, right? You wouldn't use it, right? Well, that is equivalent to saying "Scala supports some tail calls". You are literally saying that some function calls will work but others will crash unpredictably.

@Daniel:

I have read the discussions of adding tail calls to the JVM, including the Da Vinci Machine project. Sun have been making noises about tail calls for many years now but they have shipped absolutely nothing. Moreover, I do not believe that will change any time soon because Sun have prematurely optimized the JVM for Fortran-style code at the cost of modern paradigms. So they have no way forward from here. Finally, that project is specifically about dynamic languages so it is highly unlikely to build a better foundation for modern or popular functional languages (all of which are statically typed except Erlang).

Having discussed this with John Rose, I would say that the JVM developers have isolated themselves from the non-Java world and are only aware of other languages and paradigms when they knock at the door with JVM-based implementations. In particular, they are completely unaware of just how far behind the JVM is in many respects including support for other languages, features (value types, closures, tail calls) and the performance of non-Java code.

Ricky Clarkson said...

The case with Scala is that if you rely on tail calls, you need to understand the rules about when they happen. That's not the same as them being unpredictable.

If you look at Haskell, where tail calls are always optimised out, you'll see that writing tail-recursive code is often considered "doing it by hand", as they have fix, iterate and other functions that help you to write what would be tail-recursive functions without actually writing the recursion yourself.

Now, you might need to write some of those functions in Scala in terms of while loops instead of tail calls, but once you've done that (or used some from the standard library) you can then use them quite happily instead of 'manual' recursion.

That said, I'd love to have JVM-supported tail-call elimination. It's an open RFE, and Neal Gafter has hinted that it might arrive soon. It'd be good to hear it from John Rose though.

By the by, IBM's JVM does support tail calls, properly, as far as I know.

Anonymous said...

@flying frog

Actually, Sun's VM is optimized for object-oriented code, which is precisely why it doesn't include tail-call optimizations (yet). Considering the absolutely startling performance that languages like Clojure and even JRuby are able to achieve, I think that it's a little unfair to be putting off the platform as a whole. The JVM Languages Google group is *extremely* active in discussing various ways to make the JVM a good fit for non-OO languages. And yes, John Rose is deeply involved in those discussions.

I don't think there's any arguing that the JVM is a sub-optimal platform for non-OO languages *right now*. Give it some time though. Sun has been incrementally developing the JVM and significantly improving its optimizations over the last few releases. Now that they're looking into ways to improve the architecture itself (including new bytecodes), the sky is the limit.

Ricky Clarkson said...

Daniel,

OO code would also benefit from tail call elimination, e.g., in Smalltalk there is no if built-in, but a boolean object takes in two blocks to execute (one if it's true, the other if it's false). Then it executes it. If the result of the if is being returned from the method, there is no need to keep the calling stack frame around, and in fact using this technique excessively could blow the stack without the optimisation.

But then, you probably didn't mean that the JVM is optimised for OO code, but Java code, a different kettle of fish.

(actually, I can't find evidence that any Smalltalk supports tail call elimination - which seems to be because they wanted to ensure that all stack frames are visible reflectively).

Robert Fischer said...

It's undoubtable that the JVM is suboptimal for functional languages. However, calling it "a joke" is pretty ridiculous, considering the relative speeds.

Note that when it comes to commercially successful languages, speed is secondary to a variety of other aspects -- management marketing, ease of adoption, and libraries topping the list. So even if the JVM is slow or has other problems inherent in functional programming, a language that interoperates with Java is going to have a lot easier time getting commercial buy-in than one that doesn't.

Jon, your own experience with F# should show that this is a true statement: F#'s major success doesn't come from the natural fit between the CLR and functional programming (how speedy is it with immutable data again?), but from the built-in credibility, interoperability, and existing code that is out there for .Net.

So, insofar as the functional language revolution is mandatory, a functional language is going to hit the JVM, too. And, just like how the current conversation over dynamic languages on the JVM is going to bring in invokedynamic, non-recursive tail call optimizations and other functional admissions will make it into the JVM when the time comes.

Jon Harrop said...

@Daniel

Reliability is more important to me than performance. The absence of tail calls makes it impossible to write robust functional code. It literally takes you all the way back down the language ladder to Lisp (which is right at the bottom, where it all began).

@Robert

You argument applies as much to Fortran as it does to Java. I'm not about to start using Fortran in a commercial setting just because it can generate some fast code despite the fact that it utterly cripples all non-native programming paradigms. Same goes for Java.

And F#'s success absolutely revolves around core support in .NET. It is no coincidence that the guy bringing us F# was the same guy who put tail calls in the CLR over 7 years ago and was the same guy who put parametric polymorphism (aka .NET generics) from ML into all .NET languages. That solid foundation is absolutely critical to F#'s success and is precisely why it is the world's gold standard industrial-strength functional programming language. Don's been building that infrastructure at Microsoft for the best part of a decade. Meanwhile, Sun haven't even committed to starting down that path.

I have no doubt that the Clojure and Scala guys could muster something decent if they weren't permanently being held back by the JVM's limitations. If Sun fix their platform, great for everyone. Until then, I'm not touching it with a 40' pole.