General musings on programming languages, and Java.

Friday, September 14, 2007

Point-free Programming in Java 7 - Beyond Closures

Here is an introduction to point-free programming, using Haskell, Scheme, Java 5 and the proposed Java 7 for examples, and a couple of ideas for how the Java 7 proposal could improve to make point-free programming more practical.

I've grown quite accustomed to programming in lambda style now, in Common Lisp, Scheme and Haskell. Here's a quick example of how that looks:

Scheme: (lambda (x y) (+ x y))
Haskell: \x y -> x+y
Java 5:

new FunctionIII()
    public int invoke(int x,int y)
        return x+y;
Java 7: {int x,int y => x+y} Not too bad. You could use this to fold (or reduce) across a list. To fold is to apply a function on a starting number and an element of a list, and then to apply the same function on the returned value and the next element of the list, until the end of the list. You could use this to compute the sum of all the elements of a list:

Scheme: (foldl (lambda (x y) (+ x y)) 0 (list 3 4 5 6 7))
Haskell: foldl (\x y -> x+y) 0 [3,4,5,6,7]
Java 5:

foldl(new FunctionIII()
    public int invoke(int x,int y)
        return x+y;
Java 7: foldl({int x,int y => x+y},0,asList(3,4,5,6,7));

One point to note here is that you could, in Scheme, write this as (+ 3 4 5 6 7), because Scheme's + function takes any number of arguments, even 0 (whereupon it returns 0). So this is a contrived example using non-optimal code.

It's not idiomatic Haskell either. For a start, you can write sum [3,4,5,6,7], and avoid foldl altogether. Bear with me for a moment though. In Haskell, you can shorten \x y -> x+y to simply (+), which means 'the function called +'. In Scheme you don't even need the parentheses. +, used in a 'value position', which is anything other than the first in a list, refers to the function +, rather than calling it. So you can do:

Scheme: (foldl + 0 '(3 4 5 6 7))
Haskell: foldl (+) 0 [3,4,5,6,7]

This is the simplest example I can think of of pointfree style, which is where you remove lambda expressions but without introducing mutable variables. Here's a better example:

I want to multiply all elements of a list by 2. Here's the lambda style:

Scheme: (map (lambda (x) (* x 2)) (list 3 4 5 6 7))
Haskell: map (\x -> x*2) [3,4,5,6,7]
Java 5:

map(new FunctionII()
    public int invoke(int x)
        return x*2;
Java 7: map({int x => x*2},asList(3,4,5,6,7));

But these lambda expressions don't really express my intent that well. I want to map the function 2* across the list. Haskell has a convenient syntax for this:

Haskell: map (2*) [3,4,5,6,7]

What I've done there is to specify the * function, with its first argument filled in. This works because all functions in Haskell are automatically curried. If I type this at the REPL:

:type (*)
Output: (*) :: (Num a) => a -> a -> a
This looks a bit confusing if you're not familiar with it. What it means is that (*) is a function with a type parameter, a, which in Java terms would look like <a extends Number>. It takes one parameter of type a, and returns a function that (takes one parameter of type a, and returns a value of type a). Parentheses used for disambiguation there, this turns out to be hard to write in English.
:type (2*)
Output: (2*) :: (Num t) => t -> t
That means that (2*) is a function with a type parameter, t, which is an instance of the Num typeclass (the same as 'a' in the first example). It takes one parameter of type t, and returns a value of type t.

So I can call (2*) as an ordinary function, adding a value (this is called taking a section, and is a way of partially applying a function). The following expressions all have the same output, 8:

(2*) 4
(*2) 4
(*) 2 4
((*) 2) 4
This seems like an interesting but not-so-useful result of automatic currying at first, but you can actually rewrite any lambda expression in this style. Sometimes the code will be easier to read than a lambda expression, sometimes not. Here's a more complex example:map ((+10) . (*2)) [3..6]

The . operator means function composition, like in mathematics - f(g(x)) would be written as (f . g) x. You can compose functions before you have the values to give them, so f . g has a meaning. Read ((+10) . (*2)) as: "multiply by 2 then add 10". Look ma, no variables!

Scheme doesn't have any support for this, as its procedures are not automatically curried, but you can make something similar happen:

(map (compose (plus 10) (multiply-by 2)) (list 3 4 5 6))

plus and multiply-by need defining in an odd way:

(define plus
    (lambda (x)
      (lambda (y)
        (+ x y))))
(define multiply-by (lambda (x) (lambda (y) (* x y))))

You can write a general curry procedure in Scheme, but as there's no portable way of discovering how many args a procedure takes, you have to supply the arity. Plus, some procedures are of variable arity.

(curry 2 +) would return a procedure that takes a value, and returns a procedure that takes a value and returns the sum of the two values, used like this:

(((curry 2 +) 4) 5) ;; output: 9

Java 5:

public static final FunctionIO<FunctionII> plus=new FunctionIO<FunctionII>()
    public FunctionII invoke(final int x)
        return new FunctionII()
            public int invoke(int y)
                return x+y;
For brevity I'll leave multiply-by out.. it's the same but with + changed to *!

Java 7:

public static final {int => {int => int}} plus={int x => {int y => x+y}};
public static final {int => {int => int}} multiplyBy={int x => {int y => x*y}};


Because both Scheme and Java make you curry explicitly, they discourage point-free programming (although it's still possible, and quite useful). I'd like to see all function types in Java 7 be automatically curried. In other words:

{int,int => int} should be the same as {int => {int => int}}.

This doesn't have to have any negative impacts at runtime, as demonstrated by Haskell's great performance.

To make it really useful, it should also be applicable to operators, so that #+ gives a {int,int => int} and #+.invoke(2) gives a {int => int}. (where #+ is a possible syntax for taking a reference to +).

Sometimes you'll want to provide the second argument rather than the first. Haskell's solution to this is a function called flip:

(flip (/)) 3 6 -- gives 2, the result of 6/3. I could use it in this possible future of Java with #/:

flip(#/).invoke(3) would return a {int => int}, that, when you pass it a number, it returns that number divided by 3. Equivalent to Haskell's (/3).

As you do more and more in point-free style, you get more and more used to it, as one would expect, and some constructs that seem unnatural at first seem normal later. I'm still a novice, but I'm having fun.

Blog Archive

About Me

A salsa dancing, DJing programmer from Manchester, England.