Understanding Lambda/Closure, Part 6 - First Class Functions and Lambda Calculus

A value can be assigned to a variable. A first-class value can be passed into a function or returned from a function. In most programming languages, primitives or objects are first-class values, but how about functions or expressions?

In several languages, functions are first-class citizens (or so-called high order functions). For example, we've seen in Understanding Lambda/Closure, Part 1 that JavaScript's functions are objects; that is, they are first-class values. They can be assigned to a variable, passed into a function or returned from a function.

But, why is a first-class functions also called lambda? Before answering this question, we have to know what lambda calculus (also written as λ-calculus) is. Simply speaking, a function in λ-calculus is an expression which only takes one parameter. A parameter may also accept a function which takes one parameter. The λ-calculus treats functions "anonymously". For example, the mathematics function f(x) = x * 2 can be written in anonymous form as:

λ x. x * 2

If we use the form which JDK8 finally takes, it can be written as:

x -> x * 2

That is, the lambda expression will map x to x * 2. If we apply 2 to x, the mapping process will be:

(x -> x * 2)(2)
= 2 * 2
= 4

If there's a function g(y) = y - 1 and the function f(x) = x * 2 is applied to y, we'll get a new function h(x) = g(f(x)) as follows:

h(x)
= g(f(x))
= f(x) - 1
= x * 2 - 1

Using lambda expressions to rewrite the above mapping process will get a new lambda expression.

(y -> y - 1)(x -> x * 2)
= x -> x * 2 - 1

A function in λ-calculus is an expression, also called a lambda function, which only takes one parameter. Then, how to express a mathematics function that requires two input?

Let's think a function f(x, y) = x * x + y * y. If a is applied to x, we get a new function f(a, y) = a * a + y * y. We may let g(y) = f(a, y) = a * a + y * y. Applying b to y will result in g(b) = a * a + b * b = f(a, b). That is, a function that requires two inputs can be reworked into an equivalent function that accepts a single input and returns another function which accepts a single input. If we write f(x, y) = x * x + y * y in anonymous form, it can be reworked as follows:

(x, y) -> x * x + y * y
= x -> (y -> x * x + y * y)

Applying a to x and in turn b to y will be:

(x -> (y -> x * x + y * y))(a)(b)
= (y -> a * a + y * y)(b)
= a * a + b * b

In λ-calculus, any function with more than one parameter can be got by in turn applying multiple functions with one parameter. We can also use lambda expressions to implement flow control functions, such as if, forEach, etc. Basically, we can use lambda expressions to implement a small general-purpose language. For example, not, and, or, and if function can be implemented as follows:

let not =
* false -> true
* true -> false

let and =
* false value -> false
* true value -> value
* value false -> false
* value true -> value

let or =
* false value -> value
* true value -> true
* value false -> value
* value true -> true

let if = cond -> tv -> fv -> (cond and tv) or (not cond and fv)

The above if function is like an if expression in several languages. It returns the first tv if cond is true. For example:

if(true)(a)(b)
= ((cond or fv) and (cond and tv))(true)(a)(b)
=((true and tv) or (not true and fv))(a)(b)
=((true and a) or (not true and fv))(b)
=(true and a) or (not true and b)
= a or (false and b)
= a or false
= a

We can also implement a unless function.

let unless = cond -> fv -> tv -> (cond or fv) and (cond and tv)

The unless function returns the second tv if cond is true. For example:

unless(true)(a)(b)
= ((cond or fv) and (cond and tv))(true)(a)(b)
= ((true or fv) and (true and tv))(a)(b)
= ((true or a) and (true and tv))(b)
= (true or a) and (true and b)
= true and b
= b

Different languages provide different syntax supports for lambda expressions. For example, the lambda expression (x -> x * 2) can be written in JavaScript as follows:

function(x) {
return x * 2;
};

The syntax seems a little verbose. Basically, we only concern that x will be mapped to x * 2. Maybe we should not be too picky, at least, JavaScript provides first-class functions directly, and it's a dynamically-typed language. If we use a statically-typed language that doesn't support first-class functions, such as Java, what will happen?

We've even seen that, in Java, an anonymous class is a similar thing to a lambda function. What should we do if we'd like to express (x -> x * 2)? First, a function with one parameter and a return value can be defined by an interface with a single abstract method.

public interface Func<P, R> {
R apply(P p);
}

Then, we can implement (x -> x * 2) with an anonymous class, it'll be as follows:

new Func<Integer, Integer>() {
public Integer apply(Integer x) {
return x * 2;
}
};

Wow, what a big stuff! The syntax of the anonymous class is already an annoying thing. We even have to declare types because Java is a statically-typed language. If we want to do function composition, such as f(g(x)), a method compose can be written as follows:

public static <A, B, C> Func<A, C> compose(final Func<A, B> f, final Func<B, C> g) {
return new Func<A, C>() {
public C apply(A, x) {
return g.apply(f.apply(x));
}
};
}

Can you figure out what you're concerning with? Basically, you only need g.apply(f.apply(x)), but you'll be strayed from the syntax of the anonymous class. If you use the compose method to do function composition g(f(x)), where f(x) = x + 2 and g(y) = y * 3, you have to write the following code:

compose(
new Func<Integer, Integer>() {
public Integer apply(Integer x) {
return x + 2;
}
},
new Func<Integer, Integer>() {
public Integer apply(Integer y) {
return y * 3;
}
}
);

As mentioned in Understanding Lambda/Closure, Part 5, the argument that Java doesn't need lambda/closure is true. The cost is writing more code. Sometimes, maybe most of the time, we'll hardly figure out what our code wants to express, even the simple function composition g(f(x)) mentioned in the above. With the upcoming lambda features in JDK8, can we solve these questions? That's what we'll look at the next article.