How do you define an anonymous function in lambda calculus terms (or how can I say some language supports anonymous functions)?

Question

Does java support in current version of 6 lambda expressions or "anonymous functions"? Is there something I can't do in java that I couldn't do with a programming language supporting lambda expressions? I understand that java is turing complete so you can do "anything" in it.

Why couldn't anonymous inner class wrapped functions represent functions as defined in lambda calculus?

What actually is an anonymous function and how you can say that some language supports anonymous functions?

Answer 1

As I already hinted at with my comment above, the question really hinges on how exactly you define "support". In your question you already mentioned that Java is Turing-complete, and thus Java "supports" (for some definition of "supports") everything that every other programming language supports.

Java does support anonymous functions: just write an interpreter for the λ-calculus in Java and pass the anonymous function in as a string.

However, I for one find that too much work for using an anonymous function. So, for me the interesting question is not so much whether Java supports anonymous functions but whether, when I want to use anonymous functions, Java supports me. IOW: does Java make it easy to use anonymous functions, does it guide me, does it help me?

Let's make a simple experiment: implement the map function and use it to increment every element of the list [1, 2, 3, 4, 5] by 1.

Haskell

Here's how the implementation of morph (which is what I'm going to call the function in order to not collide with the already existing builtin map function) looks like in Haskell:

morph _ []     = []
morph f (x:xs) = f x : morph f xs

That's all. Short and sweet: morphing the empty list with anything is just the empty list, and morphing a list with at least one element is applying the morphing function to the first element and concatenating that with the result of morphing the rest of the list.

As you can see, writing a function which accepts a function as an argument, is very easy, very lightweight.

Assuming that we have a list l:

l = [1, 2, 3, 4, 5]

We can now call morph like so:

morph (\x -> 1 + x) l

Again, passing an anonymous function to our higher-order function is very easy, very lightweight.

And it looks almost like λ-calculus. In fact, if you use a Haskell IDE, a text editor with a Haskell mode or a Haskell pretty-printer, it will actually be displayed like this:

morph (λx → 1 + x) l

It gets even easier if we use an operator section, which allows us to pass a partially applied operator:

morph (1+) l

Or, we can pass the pre-defined succ function which returns the successor of an integer:

morph succ l

Although this is of course not an anonymous function, it is a named one.

Scala

In Scala, it looks very similar. The main difference is that Scala's type system is more complex than Haskell's and thus requires more type annotations:

def morph[A, B](l: List[A])(f: A => B): List[B] = l match {
  case Nil     => Nil
  case x :: xs => f(x) :: morph(xs)(f)
}

It is still very lightweight. Essentially, all we had to do was to declare the f parameter to be of type A => B (i.e. a function from type A to type B), which is actually syntactic sugar for Function1[A, B].

Now we just need our list:

val l = List(1, 2, 3, 4, 5)

And morph it:

morph(l) {_ + 1}

This takes again advantage of some of Scala's syntactic sugar. In anonymous functions, you can leave off the parameter list; if use every parameter exactly once and in the order they are defined, you can simply refer to them as _.

But even the full form is not much heavier:

morph(l) {(e) => e + 1}

If I had gone through the trouble of making morph an instance method of some class and defined an implicit conversion from List to that class according to the Pimp My Library pattern, I could have even written something like

l morph {_ + 1}

Scheme

Scheme, of course, should have no problems with anonymous and higher-order functions. Here's morph:

(define (morph f l)
    (if (null? l)
        null
        (cons
            (f (first l))
            (morph f (rest l)))))

Here's our list:

(define l '(1 2 3 4 5))

And our anonymous function usage:

(morph (lambda (e) (+ e 1)) '(1 2 3 4 5))

Ruby

module Enumerable
  def morph
    [].tap {|r| each {|e| r << yield(e) }}
  end
end

This is extremely lightweight. We didn't even have to define a parameter for the function, because in Ruby, every method has an implied function parameter, called a block.

l = [1, 2, 3, 4, 5]

Calling it is almost as lightweight as Scala

l.morph {|e| e + 1 }

I can sort-of replicate the operator sections from the Haskell example by grabbing a reference to the + method of 1:

l.morph(&1.method(:+))

Ruby also has a pre-defined succ method for integers which we can pass using the Symbol#to_proc trick:

l.morph(&:succ)

Some people criticize blocks in Ruby, because every method can only take a single block, and methods taking more than one function are much uglier, but it's actually not that bad. Here's the same code as above, but without using blocks:

module Enumerable
  def morph(f)
    [].tap &-> r { each &-> e { r << f.(e) }}
  end
end

l = [1, 2, 3, 4, 5]

l.morph -> e { e + 1 }
l.morph(1.method(:+))

ECMAScript (pre-2015)

ECMAScript is a direct descendant of Scheme, so it's no surprise that it can handle our problem nicely, although with some amount of syntax clutter:

Array.prototype.morph = function (f) {
    var r = [];
    this.forEach(function (e) { r.push(f(e)); });

    return r;
}

The main distraction here is the generally ugly syntax, not so much the handling of higher-order functions.

Let's build our list (well, array):

var l = [1, 2, 3, 4, 5];

And call the morph function (actually, a method in this case) passing an anonymous function as an argument:

l.morph(function (e) { return e + 1; });

ECMAScript (post-2015)

ECMAScript 2015 introduced "fat arrow" anonymous function literals:

Array.prototype.morph = f => {
    const r = [];
    this.forEach(e => r.push(f(e)));

    return r;
}

Let's build our list (well, array):

const l = [1, 2, 3, 4, 5];

And call the morph function (actually, a method in this case) passing an anonymous function as an argument:

l.morph(e => e + 1);

C#

Now we're moving closer to our ultimate target language. Here's C#:

public static IEnumerable<B> Morph<A, B>(this IEnumerable<A> l, Func<A, B> f)
{
    IList<B> r = new List<B>();
    foreach (var e in l) r.Add(f(e));

    return r;
}

Not too bad. Note the type of the function: Func<A, B>. This is a pre-defined type which is part of the core library, just like Function1[A, B] in Scala or a → b in Haskell. (This is an important distinction to Java.)

Thanks to type inference and collection initializers, creating the list isn't all too painful:

var l = new List<int> { 1, 2, 3, 4, 5 };

And passing a lambda which consists only of a single expression is basically as lightweight as Ruby, Scala, Scheme or Haskell and even more lightweight than ECMAScript, because you don't need the function or return keywords:

l.Morph(e => e + 1);

But even using the "full" syntax isn't too bad:

l.Morph((e) => { return e + 1; });

(You'll notice that I made Morph an extension method, which means I can call it like l.Morph(f) in addition to Morph(l, f).)

Java (pre-8)

static <A, B> List<B> morph(List<A> l, Function1<A, B> f) {
    List<B> r = new ArrayList<>();
    for (A e: l) r.add(f.apply(e));

    return r;
}

At first glance, this isn't too bad, actually. In fact, it looks pretty much exactly like the C# version. But why can't I write f(e)? Why do I have to write f.apply(e)? In all other languages I could use the same (or in the case of Ruby, almost the same) syntax for calling a function that was passed as an argument as I would for calling any other function, procedure or method.

I know it isn't much, but it leaves this kind of bitter taste that somehow functions aren't quite first-class. Also, as we'll see further on, there is one of those small annoyances at every single step along the way, and even though every single one of them is insignificant by itself, they do add up.

Here's our list:

List<Integer> l = Arrays.asList(1, 2, 3, 4, 5);

And this is how we call our morph:

morph(l, new Function1<Integer, Integer>() {
    @Override public Integer apply(Integer n) {
        return n + 1;
    }
});

This is pretty heavy stuff. I mean, all I'm doing is calling a method and passing two arguments. Why does that explode into four lines? In all other languages it was just a simple one-liner. Of course, I could remove all line breaks and it would still be valid:

morph(l, new Function1<Integer, Integer>() { @OVerride public Integer apply(Integer n) { return n + 1; }});

But I think you see what I'm getting at. The actual operation that is being performed, incrementing each element by 1, is pretty much invisible between all that noise.

Note also that in some of the other languages I actually used anonymous functions inside the definition of the morph function, for example in Ruby and ECMAScript and it was no big deal. If I were to do that in Java, it would lead to even more clutter and cruft and an explosion of lines.

So, even at this point we are seeing that working with higher-order and anonymous functions in Java is way more cumbersome than in pretty much any other mainstream (and not so mainstream) language.

But we haven't even gotten to the really ugly part yet: what is that Function1<A, B> type there? Where did that come from?

Well, I actually had to write that type myself!

interface Function1<A, B> {
    B apply(A a);
}

This is, of course, a so-called SAM interface, i.e. an interface or an abstract class with a Single Abstract Method. Which is the closest thing to a function type Java has. In some sense, a function is just an object with a single method, so that's perfectly fine. The fact that function types are represented via SAM interfaces isn't the problem either. In fact, that's basically how they are are represented in Scala (in Scala, f(a) is just syntactic sugar for f.apply(a), so any object with an apply method is essentially a function), Ruby (in Ruby, f.(a) is just syntactic sugar for f.call(a), so every object with a call method is essentially a function) and similarly in C#.

The problem is that I had to write it, that it wasn't already there.

Not only did I have to write it myself, I had to come up with a name for it. And I had to come up with a name for the method. None of which I had to do with any of the other languages here. Well, actually, I just stole the names from Scala, so the actual "coming up with the names" part wasn't so difficult.

What's really important are the implications of having to come up with a name. Java has a nominal type system, i.e. a type system based on names. And thus the fact that I had to come up with a name myself means that everybody else also has to come up with names. And because their names are different than mine (and if they aren't, then that will be a compile error), that means that I cannot pass the same function to two different libraries. Say, for example, I want to pass the same filtering function to my gridview and to my ORM. But the gridview expects, say, a javax.swing.Predicate<T> with a single method apply(T el) whereas my ORM expects an org.sleepy.Predicate<T> with a single method apply(T el).

Note that these two types are really exactly the same, it's just that they have different names and thus I cannot pass the same function to both libraries. This is not a hypothetical example. During the recent discussions about Project Lambda for Java, someone counted how many duplicate instances of a Predicate type there were already in Java SE 6, and IIRC the number was in the double digits.

It is perfectly possible to solve this problem in a nominal type system. After all, there aren't dozens of incompatible copies of a List type, simply because Sun put a single one in the library, and everybody uses that. They could have done the same with Function, but they didn't, which leads to a proliferation of identical, yet mutually incompatible types not only in third-party libraries but even within the JRE. (For example, Runnable is arguably a function type, as is Comparator. But why do they have to be special-cased?) In .NET, it works just fine, because Microsoft put one single type into the runtime. (Well, actually not quite one single type, but close enough.)

Because there is no single function type in the JRE, there are also only very few methods which take a function type. This is another thing that makes first-class and anonymous functions hard to use in Java. Once you have one, there's not much you can do with it. You can't filter an array with a predicate function, you can't transform a list using a mapping function, you can't sort a gridview using a comparator function.

This is also one of the reasons why I am so disappointed with some of the iterations of Project Lambda. They keep dropping the introduction of Function Types from the project, although the lack of function types is IMHO one of the biggest problems. The ugly syntax can be fixed with IDE trickery, the lack of standard function types can't. (Not to mention all those people who use the JVM and the JRE but don't use Java. They don't benefit one bit from adding syntactic sugar for anonymous inner SAM classes to the Java language, simply because they do not use the Java language. What they need are function types, and an updated collection library which uses function types.)

So, we're up to four problems now:

1. syntactic overhead because you have to use stuff like f.apply(a) and new Function1<A, A>() { public A apply(A a) { return a; }} (BTW, that's the identity function, i.e. the function which does absolutely nothing, and it takes up 58(!) characters),
2. modelling overhead because you have to define your own function types yourself, in addition to the domain types you actually care about,
3. limited usefulness because once you have created your lambdas, there aren't actually that many methods which take lambdas as arguments and
4. limited reuse because even if you find a method that takes a lambda, it doesn't take your lambda, since the types don't match up.

And when I talk about "modelling overhead", I'm not just talking about one Function1 type. Enter primitive types …

Have you noticed how I used Integers and not ints in my code above? Yes, that's right, the single biggest design screwup in the history of programming languages, Java's Original Sin, the bane of every Java programmer's existence, has once again come to bite us in the ass: primitive types.

You see, in Scala, there is exactly one class that represents a function with n arguments. It's called FunctionN[T₁, T₂, …, Tn, R]. So, there is exactly one class Function0[R] for functions without any arguments, one class Function1[T, R] for functions with one argument, one class Function3[A, B, C, R] for functions with three arguments and so forth, all the way up to something around 20, I believe.

In C#, there are exactly two classes that represent a function with n arguments: Func<T₁, T₂, …, Tn, R> and Action<T₁, T₂, …, Tn>. This is because there is no type which represents "no type". So, you cannot declare a function which doesn't return anything using C# (void is a modifier, not a type), and thus you need a separate type (Action) to represent functions that don't return anything. So, you have two classes Func<R> and Action, which represent functions that don't take any arguments, two classes Func<T, R> and Action<T> which represent functions of one argument and so forth, again up to circa 20. (In Scala, a function that doesn't return anything simply has the return type Unit, so you can just have a Function2[Int, Int, Unit], for example.)

In Java, however, you need 10×9ⁿ types to represent a function of n arguments. Let me demonstrate that with just one argument:

interface Action1_T                 { void    apply(T       a); }
interface Action1_byte              { void    apply(byte    a); }
interface Action1_short             { void    apply(short   a); }
interface Action1_int               { void    apply(int     a); }
interface Action1_long              { void    apply(long    a); }
interface Action1_float             { void    apply(float   a); }
interface Action1_double            { void    apply(double  a); }
interface Action1_boolean           { void    apply(boolean a); }
interface Action1_char              { void    apply(char    a); }
interface Function1_T_R             { R       apply(T       a); }
interface Function1_T_byte          { byte    apply(T       a); }
interface Function1_T_short         { short   apply(T       a); }
interface Function1_T_int           { int     apply(T       a); }
interface Function1_T_long          { long    apply(T       a); }
interface Function1_T_float         { float   apply(T       a); }
interface Function1_T_double        { double  apply(T       a); }
interface Function1_T_boolean       { boolean apply(T       a); }
interface Function1_T_char          { char    apply(T       a); }
interface Function1_byte_R          { R       apply(byte    a); }
interface Function1_byte_byte       { byte    apply(byte    a); }
interface Function1_byte_short      { short   apply(byte    a); }
interface Function1_byte_int        { int     apply(byte    a); }
interface Function1_byte_long       { long    apply(byte    a); }
interface Function1_byte_float      { float   apply(byte    a); }
interface Function1_byte_double     { double  apply(byte    a); }
interface Function1_byte_boolean    { boolean apply(byte    a); }
interface Function1_byte_char       { char    apply(byte    a); }
interface Function1_short_R         { R       apply(short   a); }
interface Function1_short_byte      { byte    apply(short   a); }
interface Function1_short_short     { short   apply(short   a); }
interface Function1_short_int       { int     apply(short   a); }
interface Function1_short_long      { long    apply(short   a); }
interface Function1_short_float     { float   apply(short   a); }
interface Function1_short_double    { double  apply(short   a); }
interface Function1_short_boolean   { boolean apply(short   a); }
interface Function1_short_char      { char    apply(short   a); }
interface Function1_int_R           { R       apply(int     a); }
interface Function1_int_byte        { byte    apply(int     a); }
interface Function1_int_short       { short   apply(int     a); }
interface Function1_int_int         { int     apply(int     a); }
interface Function1_int_long        { long    apply(int     a); }
interface Function1_int_float       { float   apply(int     a); }
interface Function1_int_double      { double  apply(int     a); }
interface Function1_int_boolean     { boolean apply(int     a); }
interface Function1_int_char        { char    apply(int     a); }
interface Function1_long_R          { R       apply(long    a); }
interface Function1_long_byte       { byte    apply(long    a); }
interface Function1_long_short      { short   apply(long    a); }
interface Function1_long_int        { int     apply(long    a); }
interface Function1_long_long       { long    apply(long    a); }
interface Function1_long_float      { float   apply(long    a); }
interface Function1_long_double     { double  apply(long    a); }
interface Function1_long_boolean    { boolean apply(long    a); }
interface Function1_long_char       { char    apply(long    a); }
interface Function1_float_R         { R       apply(float   a); }
interface Function1_float_byte      { byte    apply(float   a); }
interface Function1_float_short     { short   apply(float   a); }
interface Function1_float_int       { int     apply(float   a); }
interface Function1_float_long      { long    apply(float   a); }
interface Function1_float_float     { float   apply(float   a); }
interface Function1_float_double    { double  apply(float   a); }
interface Function1_float_boolean   { boolean apply(float   a); }
interface Function1_float_char      { char    apply(float   a); }
interface Function1_double_R        { R       apply(double  a); }
interface Function1_double_byte     { byte    apply(double  a); }
interface Function1_double_short    { short   apply(double  a); }
interface Function1_double_int      { int     apply(double  a); }
interface Function1_double_long     { long    apply(double  a); }
interface Function1_double_float    { float   apply(double  a); }
interface Function1_double_double   { double  apply(double  a); }
interface Function1_double_boolean  { boolean apply(double  a); }
interface Function1_double_char     { char    apply(double  a); }
interface Function1_boolean_R       { R       apply(boolean a); }
interface Function1_boolean_byte    { byte    apply(boolean a); }
interface Function1_boolean_short   { short   apply(boolean a); }
interface Function1_boolean_int     { int     apply(boolean a); }
interface Function1_boolean_long    { long    apply(boolean a); }
interface Function1_boolean_float   { float   apply(boolean a); }
interface Function1_boolean_double  { double  apply(boolean a); }
interface Function1_boolean_boolean { boolean apply(boolean a); }
interface Function1_boolean_char    { char    apply(boolean a); }
interface Function1_char_R          { R       apply(char    a); }
interface Function1_char_byte       { byte    apply(char    a); }
interface Function1_char_short      { short   apply(char    a); }
interface Function1_char_int        { int     apply(char    a); }
interface Function1_char_long       { long    apply(char    a); }
interface Function1_char_float      { float   apply(char    a); }
interface Function1_char_double     { double  apply(char    a); }
interface Function1_char_boolean    { boolean apply(char    a); }
interface Function1_char_char       { char    apply(char    a); }

That's 90(!) different types just to represent the concept of "something that takes one argument".

And, of course, if I want to write something which takes a function as an argument, I need to have a corresponding number of overloads as well, so if I want to write a method which filters some values based on a predicate, I need 9 overloads of that function which take Function1_T_boolean, Function1_byte_boolean, Function1_short_boolean, Function1_int_boolean, Function1_long_boolean, Function1_float_boolean, Function1_double_boolean, Function1_boolean_boolean and Function1_char_boolean.

(By the way: this still ignores checked exceptions. Technically, we also need 2ⁿ copies of every single one of those 90 interfaces, where n is the number of different types of checked exceptions that exist in Java.)

So, that's reasons number 5 and 6: a massive explosion in the number of types and correspondingly the number of methods.

If you put all of that together, then I guess you would agree that anonymous inner classes in Java are much more cumbersome than anonymous functions in, well, pretty much every other programming language.

But there's still more!

We haven't even talked about closures yet! While closures are orthogonal to first-class and anonymous functions, they are also one of the most important (and interesting) use cases of anonymous and first-class functions. Inner classes (whether anonymous or not) are closures, but as @Jon Skeet already pointed out, they are severely limited.

In conclusion, I would say that No, Java does not support anonymous functions.

Java (post-11)

Java 8 introduced target-typed lambda literals into the language, as well as the notion of a functional interface, and some standard library functional interface types, plus a new collection API based on Streams that makes heavy use of functional interfaces. Java 9, 10, and 11 added further standard library functional interface types and expanded Streams. Java 11 added local variable type inference.

So, what does target-typed mean? It is the answer to the problem I talked about above: since there were no standardized library types for representing functions, everybody invented their own types. Therefore, even if I want to perform the same logic, I have to write a different functions for every API I am using.

If they had simply introduced a set of new function types, e.g.

interface Function1_int_int {
    int apply(int x)
}

And said that lambda literals expand to instantiations of that function type like this:

(int x) -> x + 1

is equivalent to

new Function1_int_int {
    @Override public int apply(int x) {
        return x + 1;
    }
}

Then, you would not be able to use lambdas anywhere, since no existing library takes a Function1_int_int as an argument! You would have had to add new overloads to every existing library that has the concept of "taking a piece of code as an argument". This is simply not scalable.

What they did instead was to introduce a bit of structural typing into Java, where the names of the types are irrelevant, and a lambda like this:

(int x) -> x + 1

can be passed anywhere a type of the following form is expected:

interface * {
    int *(int *)
}

or

class * {
    int *(int *) // abstract!
}

And it will automatically implement the class or interface with the correct name, and automatically implement the method with the correct name.

And not only is this based on structural typing, as opposed to the entire rest of Java's type system which is nominal, it is also based on the context it is used in, and that is what is meant by "target-typed": the type of the lambda depends not on the lambda itself, but on what its target is, i.e. where it is used.

Back to our example:

static <A, B> List<B> morph(List<A> l, Function<A, B> f) {
    List<B> r = new ArrayList<>();
    for (var e: l) r.add(f.apply(e));

    return r;
}

The only significant difference to Java pre-8 here is that I am using the pre-defined java.util.function.Function<T, R> functional interface, which means I don't have to write my own.

Here's our list again (same code as before):

List<Integer> l = Arrays.asList(1, 2, 3, 4, 5);

But here, how we call our morph, is the major difference. Instead of this:

morph(l, new Function<Integer, Integer>() {
    @Override public Integer apply(Integer n) {
        return n + 1;
    }
});

We now have this:

morph(l, n -> n + 1);

---

Oh, I almost forgot: there was another question somewhere:

What actually is an anonymous function

That's easy. A function with no name.

and how you can say that some language supports anonymous functions?

If it makes it easy to work with them.

Java pre-8 doesn't: there is a difference between supporting anonymous functions and being able to emulate a subset of the features of anonymous functions by encoding them into anonymous inner SAM classes. Java post-8 is much nicer.