April 2013, Jozi Java User Group
λ
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.
A valid λ-calculus expression is called a lambda term.
Nothing else is a lambda term.
\(\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\).
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\)
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\).
The \(\lambda x.y\) is a lambda abstraction that represents what well known function?
The constant function.
\(\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.
The free variables of a term are those variables not bound by a lambda abstraction.
The lambda term representing the identity \(\lambda x.x\) has what free variable(s)?
The identity lambda term has no unbound variables.
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.)
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:
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.
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.
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.
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.
JSR 335
lambda = ArgList '->' Body
ArgList = Identifier
| "(" Identifier [ "," Identifier ]* ")"
| "(" Type Identifier [ "," Type Identifier ]* ")"
Body = Expression
| "{" [ Statement ";" ]+ "}"
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;
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.
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)
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"); } }
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
Unfinished items since 0.6.1