Java 8

Introducing Lambda Expressions to the Java Programming Language

Alen Ribic / @alenribic

April 2013, Jozi Java User Group
λ

In this talk...

  • What's all this lambda (λ) speak about?
    • Brief History
    • Informal introduction to Lambda calculus
  • Lambda expressions and Java
  • Lambda syntax and semantics in Java (JSR 335)
  • Time to write some code
  • JSR 335, work in progress

Brief History

In the 17th century, a famous philosopher and mathematician named Leibniz had an ideal

  • Create a 'universal language' in which all possible problems can be stated.
  • Find a decision method to solve all the problems stated in the universal language.

Leibniz' ideal became an important philosophical question. 'Can one solve all problems formulated in the universal language?'

In 1936/7, the problem was solved independently by Alonzo Church and Alan Turing.

Church and Turing did this in two different ways by introducing two models of computation.

Alonzo Church invented λ-calculus

The λ-calculus is a formal system that defines the notion of computable function.

The λ-calculus influenced the design of the Lisp programming language and functional programming languages in general.

Alan Turing invented Turing Machines

A Turing machine defines the notion of computable function in a form of a hypothetical device that manipulates symbols on a strip of tape according to a table of rules.

Imperative programming languages such as Java, C, C# as well as all the assembler languages are based on the way a Turing machine is instructed: by a sequence of statements.

Informal introduction to Lambda calculus

Lambda terms

A valid λ-calculus expression is called a lambda term.

  • a variable \(x\) is itself a valid lambda term
  • if \(t\) is a lambda term, and \(x\) is a variable, then \( \lambda x.t \) is a lambda term (called a lambda abstraction)
  • if \(t\) and \(s\) are lambda terms, then \((ts)\) is a lambda term (called an application)

Nothing else is a lambda term.

Lambda abstraction

\(\lambda x.t\) is a definition of an anonymous function that is capable of taking a single input \(x\) and substituting it into the expression \(t\).

It thus defines an anonymous function that takes \(x\) and returns \(t\).

Quiz

The lambda abstraction \(\lambda x.x^2 + 2\) represents what mathematical function?

\(f(x) = x^2 + 2\), using the term \(x^2 + 2\) for \(t\)

Functions that operate on functions

In λ-calculus, functions are first class values, so these functions, also known as higher-order functions, may be used as the inputs and returned as outputs from other functions.

For example, \(\lambda x.x\) represents the identity function, \(x \mapsto x\), and \((\lambda x.x)y\) represents the identity function applied to \(y\).

Quiz

The \(\lambda x.y\) is a lambda abstraction that represents what well known function?

The constant function.

Alpha equivalence

\(\lambda x.x\) and \(\lambda y.y\) are \(\alpha\)-equivalent lambda terms.

The terms \(x\) and \(y\) are not alpha-equivalent, because they are not bound in a lambda abstraction.

Free variables

The free variables of a term are those variables not bound by a lambda abstraction.

  • The free variables of \(x\) are just \(x\)
  • The set of free variables of \(\lambda x.t\) is the set of free variables of \(t\), but with \(x\) removed
  • The set of free variables of \(ts\) are the union of the set of free variables of \(t\) and the set of free variables of \(s\).

Quiz

The lambda term representing the identity \(\lambda x.x\) has what free variable(s)?

The identity lambda term has no unbound variables.

Quiz

The lambda term \(\lambda x.\frac{y}{x}\) has what free variable(s)?

The variable \(y\) is free. (Variable \(x\) is bound in the given lambda term.)

Capture-avoiding substitutions

Suppose \(t\), \(s\) and \(r\) are any lambda terms and \(x\) and \(y\) are only variables.

Substitution, written \(t[x := r]\), is the process of substituting all free occurrences of the variable \(x\) with \(r\) in the expression \(t\) in a capture-avoiding manner. We define it as follows:

  • \(x[x := r]\) \(\equiv\) \(r\)
  • \(y[x := r]\) \(\equiv\) \(y\) if \(x \neq y\)
  • \((ts)[x := r]\) \(\equiv\) \(t[x := r]\)\(s[x := r]\)
  • \((\lambda x.t)[x := r]\) \(\equiv\) \(\lambda x.t\)
  • \((\lambda y.t)[x := r]\) \(\equiv\) \(\lambda y.(t[x := r])\) if \(x \neq y\) and \(y\) is not in the free variables of \(r\)

Beta reduction

The \(\beta\)-reduction captures the idea of function application. An application of the form \((\lambda x.t)s\) reduces to the term \(t[x := s]\).

For example, for every \(s\), \((\lambda x.x)s \mapsto x[x := s] \equiv s\).

This demonstrates that \(\lambda x.x\) really is the identity.

Quiz

Given the application of \(s\) to \(\lambda x.y\), what would the substitution look like?

In term \(y\), \(x\) is substituted with \(s\) as follows: \(y[x := s] \equiv y\)

This demonstrates that \(\lambda x.y\) really is a constant function.

Final note on Lambda calculus

Lambda abstractions can only ever have single parameters.

But this is not really a limitation. Let's look at an example:

\(\lambda x.\lambda y. y + x\)

This effectively means a lambda abstraction that when applied returns another lambda abstraction that itself takes a single argument (currying).


In the standard λ-calculus notation, there is a relevant convention that keeps things uncluttered that enables us to write \(\lambda xy. y + x\).

In programming language terms, this could be implemented as syntactic sugar.

Lambda expressions and Java

Lambda expression

  • Computational units that operate on some data (input) and produce some data (output)
  • Can be passed around as any other values, thus termed higher-order functions
  • Naturally compose based on the formal parameters and return types, \((s \circ t)x\)
  • Synonymous with the terms Lambda function, Anonymous function, and Closure (Closure, if and only if the environment/stack is captured at the point that the lambda expression is created)

Why introduce Lambda expressions to Java?

Numerous programming patters require nothing more than defining a unit of behaviour, yet we spend large portions of our time writing ceremonious, boilerplate code.

We need greater expressive power.

Inner classes are syntactically bulky and can be seen as imperfect closures. (e.g. inability to capture the non-final local variables)

Lambda expressions can solve many of the parallel and concurrent programing problems. (e.g problems such as inherently serial constructs like for loops, mutable accumulator variables, etc.)

Let's start thinking bottom-up design where applicable. Build smaller computational units and compose upwards towards the problem at hand.

Lambda syntax and semantics in Java

JSR 335

Syntax of lambda expressions


lambda = ArgList '->' Body
ArgList = Identifier
    | "(" Identifier [ "," Identifier ]* ")"
    | "(" Type Identifier [ "," Type Identifier ]* ")"
Body = Expression
    | "{" [ Statement ";" ]+ "}"
                        

Examples of lambda expressions

  • () \(\rightarrow\) {} // No parameters (unit); result is void
  • () \(\rightarrow\) 42 // No parameters, expression body
  • () \(\rightarrow\) { return 42; } // No parameters, block body with return
  • () \(\rightarrow\) { System.gc(); } // No parameters, void block body
  • (int x) \(\rightarrow\) x+1 // Single declared-type parameter
  • x \(\rightarrow\) x+1 // Single inferred-type (parens optional for single parameter)
  • re \(\rightarrow\) re.compile("^hello/$") // Single inferred-type, expression body
  • (x, y) \(\rightarrow\) x+y // Multiple inferred-type parameters

More fun examples

  • factorial = i \(\rightarrow\) i == 0 ? 1 : i * factorial.apply(i - 1);
  •  
  • OptionalInt r = Streams.intRange(1, 11) // [1..10]
       .filter(n \(\rightarrow\) n % 2 == 0)
       .reduce((acc, n) \(\rightarrow\) acc * n);
  • out.println("What does this print? "
         + (r.isPresent() ? r.getAsInt() : 1));
  •  
  • Function<Integer,Integer> add2 = x -> x + 2; // add2 is a Functional interface; x is an inferred-type
    add2.compose(add2).apply(4) \(==\) 8; // (add2 o add2)4

Semantics of lambda expressions

Functional interface

A functional interface is an interface that has just one abstract method, and thus represents a single function contract.

Instances of functional interfaces can be created with a) standard instantiation, b) lambda expressions, c) method references, or d) constructor references.


Runnable r = new RunnableImpl();
Runnable r = () -> out.println("Running”);
BinaryOperator<Integer> max = Math::max;
Callable<List> mkList = LinkedList<Integer>::new;
                        

Scoping rules

  • The scope of a formal parameter of a lambda expression is the entire body of the lambda expression.
  • Any local variable, formal parameter, or exception handler parameter used but not declared in a lambda expression must be either declared final or effectively final.
  • The meaning of this and super keywords appearing in a lambda body are the same as in the surrounding context.
  • Lambda formal parameters cannot shadow the variables from the enclosing scope. See: JSR335, Part B, 6.4

Target type rules

An expression must be compatible with a type expected in the context; this type is called the target type.

First, lambda expressions, method and constructor references are termed poly expressions and their deduced type can be influenced by the target type. (The same expression can have different types in different contexts)

This enables us to take full advantage of bounded polymorphism.

Second, after the type of expression has been deduced, implicit conversion from type of the expression to the target type can sometimes be performed. (e.g. primitive to boxed types, etc.)

If neither strategy produces the appropriate type, a compile time error occurs.

Exception rules

If a checked exception is to be thrown from inside a lambda expression, the functional interface must declare that this checked exception can be thrown.

The exception is not propagated to the enclosing method or constructor. (So it doesn't help if the enclosing method throws the same checked exception)

Default methods

A default method is a method that is declared in an interface with the modifier default.

Its body provides a default implementation for any class that implements the interface without overriding the method.

It provides a mechanism for multiple inheritance of behavior.

Wait a minute, does this make Java interfaces mixins? :-)

And no, they don't fully replace abstract classes; default methods provide inheritance of behaviour (but not state)!

interface Superinterface { void foo() default { out.println("Hi"); } }

Time to write some code

Ada Lovelace (1815 - 1852), "Her notes on the Analytical Engine include what is recognized as the first algorithm intended to be processed by a machine. Because of this, she is often considered the world's first computer programmer." -Wikipedia

JSR 335, work in progress

Unfinished items since 0.6.1

  • Unchecked exceptions that can occur as the result of implicit overriding by lambda expressions need to be specified.
  • Various low-level details of type inference need to be fully specified.
  • New standard APIs need to be specified, including those to support implementation, reflection, and use of the new features.
  • Certain error checks are required to guarantee that a lambda expression corresponds to a legal class declaration.

References

THE END

Alen Ribic / @alenribic