Tuesday, December 9, 2014

Functional Programming in Mainstream Languages, Part 6: Higher-Order Functions in Xtend

(Jump to Table of Contents)
I introduced the Xtend programming language in a previous post.  Xtend is similar to Java, and compiles to Java (not to bytecode), but is much more pleasant to use.  In particular, it supports functional programming in various ways, both in the language itself and in the libraries.  Some of these will have to wait for later posts in the series; for now, as in previous posts, I am only discussing higher-order functions.  Again, I will contrast Xtend with Java 8.

Here is the simple example of the curried addition function:
Java 8
IntFunction makeAdder = x -> y -> x + y; IntUnaryOperator increment = makeAdder.apply(1); int res = increment.applyAsInt(4);
val makeAdder = [int x|[int y|x + y]] val increment = makeAdder.apply(1) val res = increment.apply(4)

The syntax for anonymous functions (lambdas) in Xtend is different from all those we saw before; instead of some kind of arrow symbol, it uses square brackets with a vertical bar separating the parameters from the body.  Type inferencing is applied (as in Scala) to infer the types of the expressions.  Unlike Scala, and like Java, Xtend still requires the method-call syntax for function calls.

The recursive fixed-point function looks like this:

Java 8
public double fixedpoint(DoubleUnaryOperator f, double v) { double next = f.applyAsDouble(v); if (Math.abs(next - v) < epsilon) return next; else return fixedpoint(f, next); }
def double fixedpoint(Function1<Double, Double> f, double v) { val next = f.apply(v) if ((next - v).abs < epsilon) next else fixedpoint(f, next) }

This uses the Xtend interface for unary functions, Function1, with the Java wrapper type Double.  In principle, the compiler could have inferred the return type of this function (Scala can do it, see Part 5), but its type-inference mechanism doesn't handle recursion, so it is necessary to specify the type manually.  I hope this will be fixed in a future release.

In this example we can see a nice extension feature, one of those that gave Xtend its name.  Doubles in Java has no abs method; instead, you call the static method Math.abs with the number as a parameter.  This is awkward and places an unnecessary cognitive burden on programmers, who need to remember which methods each object has and which static methods are available for it.  (This is quite common in Java, which has many classes that offer services as static methods; Arrays and Collections are famous examples.)  In general, having different and mutually exclusive ways of expressing what is essentially the same concept is bad.  Xtend allows developers to define "extension methods," which are static methods that can be called like regular methods on the first argument.  In this example, for a double variable x the following are completely equivalent: Math.abs(x), and x.abs.  This equivalence (like many others) is defined in the standard Xtend libraries.

Because this recursive version of fixedpoint compiles in a straightforward manner to Java, tail-recursion optimization is not necesarily applied.  The imperative version is therefore preferred in this case as well:

Java 8
public double fixedpoint(DoubleUnaryOperator f, double v) { double prev = v; double next = v; do { prev = next; next = f.applyAsDouble(next); } while (Math.abs(next - prev) >= epsilon); return next; }
def fixedpoint(Function1<Double, Double> f, double v) { var next = v var prev = v do { prev = next next = f.apply(next) } while ((next - prev).abs >= epsilon) next }

A seemingly slight difference between the recursive and imperative versions is the use of the keyword to define variables.  Unmodifiable variables in Xtend (which are translated into Java final variables) are introduced by the keyword val, whereas modifiable variables (non-final) are introduced by the keyword var.  In Xtend it is therefore just as easy to define final variables as non-final ones.  This is a great incentive for writing functional programs, which don't have modifiable variables.  When you write Xtend code, you should always use val rather than var, unless you convince yourself that there is good reason why the variable should be modifiable.  And you should be hard to convince on this point!

At this point you know to expect the non-terminating sqrt; here it is:

Java 8
public double sqrt(double x) { return fixedpoint(y -> x / y, 1.0); }
def sqrt(double x) { fixedpoint([y|x / y], 1.0) }

The differences are minor: less type information is required in Xtend, and, like Scala, Xtend doesn't require the access-level designator (public) and the return keyword; however, the braces are still required.

By now you can surely write the terminating version yourselves:

Java 8
public double sqrt(double x) { return fixedpoint(y -> (y + x / y) / 2.0, 1.0); }
def sqrt(double x) { fixedpoint([y|(y + x / y) / 2.0], 1.0) }

The general average-damp and the corresponding sqrt again hold no surprises:

Java 8
public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) { return x -> (x + f.applyAsDouble(x)) / 2.0; } public double sqrt(double x) { return fixedpoint(averageDamp(y -> x / y), 1.0); }
def averageDamp(Function1<Double, Double> f) { [double x|(x + f.apply(x)) / 2.0] } def sqrt(double x) { fixedpoint(averageDamp[y|x / y], 1.0) }

As I said before, Xtend is a very pleasant alternative to Java, which has many similarities with Java but many points in which it improves on it significantly.  One of those is its support for functional programming (of which we have seen only one part, higher-order functions).  Java 8 has closed some (but not enough) of this distance, and made some choices that are different from Xtend's.  The most obvious is the lambda notation, but perhaps more important are the use of the functional interfaces, more limited type inference, and the inconsistent use of the method name (apply, applyAsDouble, test, etc.).  As we saw in Part 5, Scala is perhaps more pleasant that Xtend in some ways, but is places itself further away from Java (in many more ways than we have seen).

In summary, if you are now programming in Java and want a closely-related but better language, you should take a good look at Xtend.

#FunctionalProgramming #Xtend

No comments:

Post a Comment