19. Lambda

Part of CS:2820 Object Oriented Software Development Notes, Spring 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

Where Were We?

We had just reduced our code to the following, using a call to a method of an anonymous subclass of an interface, with the body of the method placed directly in the constructor call:

                ScanSupport.lineEnd(
                        sc,
                        new ScanSupport.ErrorMessage () {
                                public toString s() {
                                        return "Intersection " + name
                                }
                        }
                )

The Outcome

Java lets you write the code we started with as follows:

                ScanSupport.lineEnd(
                        sc,
                        () -> "Intersection " + name
                )

This is called a lambda expression or λ-expression.

This notation comes with severe restrictions: It only applies if the expression is passed in a context where the expected class of the argument permits a subclass, and where there is just one public method of that class that matches the argument list. Furthermore, in the interest of efficient implementation, Java restricts the set of permitted variable references inside the λ-expression. Specifically, the only variables you are allowed to reference are final or "effectively final" variables. Java's definition of the latter leaves quite a bit to be desired, but this usually doesn't cause much trouble.

Lambda?

The idea of lambda expressions is old, dating back to the 1930s, when it was first developed by Alonzon Church. Computers had not been invented yet, and church was interested in the foundations of mathematics, not programming languages. He was trying to give a clear definition of the concept of a computable function. Alan Turing was also working on this problem, and came up with a compltetely different approach, using what is now called a Turing machine. Church and Turing learned of each other's work, and it was not long before the proof that both Church's approach to defining computable functions using his lambda calculus and Turing's approach using Turing machines were equivalent. As a result, we now refer to their definition of computability as the Church-Turing thesis.

Why is it called Lambda notation (and Lambda calculus)? Because Church used the Greek letter lambda λ in his notation. Where conventional mathematical notation might define the function f as:

f(x) = x + 1

Church used a new notation:

f = λx.x + 1

The advantage of this notation is that it allows function names such as f to be treated as variables. The symbol λ can be treated as an operator that takes two arguments (separated by a period), the parameter list, in this case x, and the expression used to compute the value of the function, x+1 here.

Lambda notation was viewed as an arcane mathematical notation until 1960, when the developers of the LISP programming language at MIT decided to use lambda notation. The LISP equivalent of the above example would be:

(SET F (LAMBDA (X) (ADD X 1)))

LISP stands for LIst and String Processing language, but critics have described the LISP syntax as involving Lots of Infuriating Small Parentheses. LISP became the favored language for large areas of artificial intelligence research, and it lives on today in a variety of guises. The text editor EMACS, for example, is largely written in LISP, and uses LISP as its macro extension language. As with Church's lamda notation, LISP allows dynamic construction of new functions and it allows variables and parameters to have functions as their values.

Tools in other programming languages that allow the same basic flexibility are generally known as lambda notation even if they do not use the letter λ