Transcript Document

6. Introduction to the Lambda Calculus
PS — Introduction to the Lambda Calculus
Roadmap
>
>
>
>
What is Computability? — Church’s Thesis
Lambda Calculus — operational semantics
The Church-Rosser Property
Modelling basic programming constructs
© O. Nierstrasz
6.2
PS — Introduction to the Lambda Calculus
References
>
>
>
Paul Hudak, “Conception, Evolution, and Application of Functional
Programming Languages,” ACM Computing Surveys 21/3, Sept.
1989, pp 359-411.
Kenneth C. Louden, Programming Languages: Principles and
Practice, PWS Publishing (Boston), 1993.
H.P. Barendregt, The Lambda Calculus — Its Syntax and
Semantics, North-Holland, 1984, Revised edition.
© O. Nierstrasz
6.3
PS — Introduction to the Lambda Calculus
Roadmap
>
>
>
>
What is Computability? — Church’s Thesis
Lambda Calculus — operational semantics
The Church-Rosser Property
Modelling basic programming constructs
© O. Nierstrasz
6.4
PS — Introduction to the Lambda Calculus
What is Computable?
Computation is usually modelled as a mapping from inputs to outputs,
carried out by a formal “machine,” or program, which processes its
input in a sequence of steps.
yes
………
………
………
input
no
Effectively
computable
function
output
An “effectively computable” function is one that can be computed in
a finite amount of time using finite resources.
© O. Nierstrasz
6.5
PS — Introduction to the Lambda Calculus
Church’s Thesis
Effectively computable functions [from positive integers to positive
integers] are just those definable in the lambda calculus.
Or, equivalently:
It is not possible to build a machine that is more powerful than a
Turing machine.
Church’s thesis cannot be proven because “effectively computable” is
an intuitive notion, not a mathematical one. It can only be refuted by
giving a counter-example — a machine that can solve a problem not
computable by a Turing machine.
So far, all models of effectively computable functions have shown to be
equivalent to Turing machines (or the lambda calculus).
© O. Nierstrasz
6.6
PS — Introduction to the Lambda Calculus
Uncomputability
A problem that cannot be solved by any Turing machine in finite time
(or any equivalent formalism) is called uncomputable.
Assuming Church’s thesis is true, an uncomputable problem cannot be
solved by any real computer.
The Halting Problem:
Given an arbitrary Turing machine and its input tape, will the machine
eventually halt?
The Halting Problem is provably uncomputable — which means that it
cannot be solved in practice.
© O. Nierstrasz
6.7
PS — Introduction to the Lambda Calculus
What is a Function? (I)
Extensional view:
A (total) function f: A  B is a subset of A  B (i.e., a
relation) such that:
1.
for each a  A, there exists some (a,b)  f
(i.e., f(a) is defined), and
2.
if (a,b1)  f and (a, b2)  f, then b1 = b2
(i.e., f(a) is unique)
© O. Nierstrasz
6.8
PS — Introduction to the Lambda Calculus
What is a Function? (II)
Intensional view:
A function f: A  B is an abstraction x.e, where x is a
variable name, and e is an expression, such that when a
value a  A is substituted for x in e, then this expression
(i.e., f(a)) evaluates to some (unique) value b  B.
© O. Nierstrasz
6.9
PS — Introduction to the Lambda Calculus
Roadmap
>
>
>
>
What is Computability? — Church’s Thesis
Lambda Calculus — operational semantics
The Church-Rosser Property
Modelling basic programming constructs
© O. Nierstrasz
6.10
PS — Introduction to the Lambda Calculus
What is the Lambda Calculus?
The Lambda Calculus was invented by Alonzo Church [1932] as a
mathematical formalism for expressing computation by functions.
Syntax:
e ::=
x
a variable
|
x.e
an abstraction (function)
|
e1 e2
a (function) application
Examples:
 x . x — is a function taking an argument x, and returning x
f x — is a function f applied to an argument x
NB: same as f(x) !
© O. Nierstrasz
6.11
PS — Introduction to the Lambda Calculus
Parsing Lambda Expressions
Lambda extends as far as possible to the right
 f.x y

 f.(x y)
Application is left-associative
xyz

(x y) z
Multiple lambdas may be suppressed
 f g.x
© O. Nierstrasz

 f .  g.x
6.12
PS — Introduction to the Lambda Calculus
What is the Lambda Calculus? ...
(Operational) Semantics:
 conversion
 x . e   y . [ y/x ] e
(renaming):
 reduction
( x . e1) e2  [ e2/x ] e1
(application):
 reduction:
x.ex  e
where y is not free
in e
avoiding name
capture
if x is not free in e
The lambda calculus can be viewed as the simplest possible pure
functional programming language.
© O. Nierstrasz
6.13
PS — Introduction to the Lambda Calculus
Beta Reduction
Beta reduction is the computational engine of the lambda calculus:
Define:
Ix.x
Now consider:
I I = ( x . x) ( x . x )
© O. Nierstrasz
 [ x . x / x] x  reduction
= x.x
substitution
= I
6.14
PS — Introduction to the Lambda Calculus
Lambda expressions in Haskell
We can implement most lambda expressions directly in Haskell:
i = \x -> x
? i 5
5
(2 reductions, 6 cells)
? i i 5
5
(3 reductions, 7 cells)
© O. Nierstrasz
6.15
PS — Introduction to the Lambda Calculus
Lambdas are anonymous functions
A lambda abstraction is just an anonymous function.
Consider the Haskell function:
compose f g x = f(g(x))
The value of compose is the anonymous lambda abstraction:
 f g x . f (g x)
NB: This is the same as:
 f .  g .  x . f (g x)
© O. Nierstrasz
6.16
PS — Introduction to the Lambda Calculus
A Few Examples
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
(x.x) y
(x.f x)
xy
(x.x) (x.x)
(x.x y) z
(x y.x) t f
(x y z.z x y) a b (x y.x)
(f g.f g) (x.x) (x.x) z
(x y.x y) y
(x y.x y) (x.x) (x.x)
(x y.x y) ((x.x) (x.x))
© O. Nierstrasz
6.17
PS — Introduction to the Lambda Calculus
Free and Bound Variables
The variable x is bound by  in the expression:  x.e
A variable that is not bound, is free :
fv(x)
=
{x}
fv(e1 e2)
=
fv(e1)  fv(e2)
fv( x . e)
=
fv(e) - { x }
An expression with no free variables is closed.
(AKA a combinator.) Otherwise it is open.
For example, y is bound and x is free in the (open) expression:
y.xy
© O. Nierstrasz
6.18
PS — Introduction to the Lambda Calculus
“Hello World” in the Lambda Calculus
hello world
 Is this expression open? Closed?
© O. Nierstrasz
6.19
PS — Introduction to the Lambda Calculus
Roadmap
>
>
>
>
What is Computability? — Church’s Thesis
Lambda Calculus — operational semantics
The Church-Rosser Property
Modelling basic programming constructs
© O. Nierstrasz
6.20
PS — Introduction to the Lambda Calculus
Why macro expansion is wrong
Syntactic substitution will not work:
( x y . x y ) y
 [ y / x] ( y . x y)
≠
( y . y y )
 reduction
incorrect substitution!
Since y is already bound in ( y . x y), we cannot directly
substitute y for x.
© O. Nierstrasz
6.21
PS — Introduction to the Lambda Calculus
Substitution
We must define substitution carefully to avoid name capture:
[e/x] x = e
if x ≠ y
[e/x] y = y
[e/x] (e1 e2) = ([e/x] e1) ([e/x] e2)
[e/x] ( x . e1) = ( x . e1)
[e/x] ( y . e1) = ( y . [e/x] e1)
if x ≠ y and y  fv(e)
[e/x] ( y . e1) = ( z. [e/x] [z/y] e1)
if x ≠ y and
z  fv(e)  fv(e1)
Consider:
( x . (( y . x) ( x . x)) x ) y  [y / x] (( y . x) ( x . x)) x
= (( z . y ) ( x . x)) y
© O. Nierstrasz
6.22
PS — Introduction to the Lambda Calculus
Alpha Conversion
Alpha conversions allow us to rename bound variables.
A bound name x in the lambda abstraction ( x.e) may be substituted
by any other name y, as long as there are no free occurrences of y in e:
Consider:
( x y . x y ) y ( x z . x z) y
 [ y / x] ( z . x z)
 ( z . y z)
= y
© O. Nierstrasz
 conversion
 reduction
 reduction
6.23
PS — Introduction to the Lambda Calculus
Eta Reduction
Eta reductions allow one to remove “redundant lambdas”.
Suppose that f is a closed expression (i.e., there are no free variables in
f).
Then:
( x . f x ) y
 fy
 reduction
So, ( x . f x ) behaves the same as f !
Eta reduction says, whenever x does not occur free in f, we can rewrite
( x . f x ) as f.
© O. Nierstrasz
6.24
PS — Introduction to the Lambda Calculus







( x y . x y) ( x . x y) ( a b . a b)
( x z . x z) ( x . x y) ( a b . a b)
( z . ( x . x y) z) ( a b . a b)
( x . x y) ( a b . a b)
( a b . a b) y
( b . y b)
y
© O. Nierstrasz
NB: left assoc.
 conversion
 reduction
 reduction
 reduction
 reduction
 reduction
6.25
PS — Introduction to the Lambda Calculus
Normal Forms
A lambda expression is in normal form if it can no longer be reduced by
beta or eta reduction rules.
Not all lambda expressions have normal forms!
 = ( x . x x) ( x . x x)

[ ( x . x x) / x ] ( x x )
=
( x . x x) ( x . x x)
 reduction

( x . x x) ( x . x x)
 reduction

( x . x x) ( x . x x)
 reduction

...
Reduction of a lambda expression to a normal form is analogous to a
Turing machine halting or a program terminating.
© O. Nierstrasz
6.26
PS — Introduction to the Lambda Calculus
Evaluation Order
Most programming languages are strict, that is, all expressions passed
to a function call are evaluated before control is passed to the function.
Most modern functional languages, on the other hand, use lazy
evaluation, that is, expressions are only evaluated when they are
needed.
Consider:
sqr n = n * n
Applicative-order reduction:
sqr (2+5)  sqr 7  7*7  49
Normal-order reduction:
sqr (2+5)  (2+5) * (2+5)  7 * (2+5)  7 * 7  49
© O. Nierstrasz
6.27
PS — Introduction to the Lambda Calculus
The Church-Rosser Property
“If an expression can be evaluated at all, it can be evaluated by
consistently using normal-order evaluation. If an expression can be
evaluated in several different orders (mixing normal-order and
applicative order reduction), then all of these evaluation orders yield
the same result.”
So, evaluation order “does not matter” in the lambda calculus.
© O. Nierstrasz
6.28
PS — Introduction to the Lambda Calculus
Roadmap
>
>
>
>
What is Computability? — Church’s Thesis
Lambda Calculus — operational semantics
The Church-Rosser Property
Modelling basic programming constructs
© O. Nierstrasz
6.29
PS — Introduction to the Lambda Calculus
Non-termination
However, applicative order reduction may not terminate, even if a
normal form exists!
( x . y) ( ( x . x x) ( x . x x) )
Applicative order reduction
Normal order reduction
 ( x . y) ( ( x . x x) ( x . x x) )
 ( x . y) ( ( x . x x) ( x . x x) )
…
y
Compare to the Haskell expression:
(\x -> \y -> x) 1 (5/0)  1
© O. Nierstrasz
6.30
PS — Introduction to the Lambda Calculus
Currying
Since a lambda abstraction only binds a single variable,
functions with multiple parameters must be modelled as
Curried higher-order functions.
As we have seen, to improve readability, multiple lambdas
are suppressed, so:
xy.x
bxy.bxy
© O. Nierstrasz
= x.y.x
= b.x.y.(bx)y
6.31
PS — Introduction to the Lambda Calculus
Representing Booleans
Many programming concepts can be directly expressed in the lambda
calculus. Let us define:
True
False
not
if b then x else y




xy.x
xy.y
 b . b False True
bxy.bxy
then:
not True =


if True then x else y =


© O. Nierstrasz
( b . b False True ) ( x y . x )
( x y . x ) False True
False
( b x y . b x y ) ( x y . x) x y
( x y . x) x y
x
6.32
PS — Introduction to the Lambda Calculus
Representing Tuples
Although tuples are not supported by the lambda calculus, they can
easily be modelled as higher-order functions that “wrap” pairs of values.
n-tuples can be modelled by composing pairs ...
Define:
then:
pair
first
second



( x y z . z x y)
( p . p True )
( p . p False )
(1, 2)
=




pair 1 2
( z . z 1 2)
(pair 1 2) True
True 1 2
1
first (pair 1 2)
© O. Nierstrasz
6.33
PS — Introduction to the Lambda Calculus
Tuples as functions
In Haskell:
t
f
pair
first
second
=
=
=
=
=
\x
\x
\x
\p
\p
->
->
->
->
->
\y -> x
\y -> y
\y -> \z -> z x y
p t
p f
? first (pair 1 2)
1
? first (second (pair 1 (pair 2 3)))
2
© O. Nierstrasz
6.34
PS — Introduction to the Lambda Calculus
What you should know!
 Is it possible to write a Pascal compiler that will






generate code just for programs that terminate?
What are the alpha, beta and eta conversion rules?
What is name capture? How does the lambda calculus
avoid it?
What is a normal form? How does one reach it?
What are normal and applicative order evaluation?
Why is normal order evaluation called lazy?
How can Booleans and tuples be represented in the
lambda calculus?
© O. Nierstrasz
6.35
PS — Introduction to the Lambda Calculus
Can you answer these questions?
 How can name capture occur in a programming
language?
 What happens if you try to program  in Haskell? Why?
 What do you get when you try to evaluate (pred 0)?
What does this mean?
 How would you model numbers in the lambda calculus?
Fractions?
© O. Nierstrasz
6.36
ST — Introduction
License
http://creativecommons.org/licenses/by-sa/3.0/
Attribution-ShareAlike 3.0 Unported
You are free:
to Share — to copy, distribute and transmit the work
to Remix — to adapt the work
Under the following conditions:
Attribution. You must attribute the work in the manner specified by the author or licensor
(but not in any way that suggests that they endorse you or your use of the work).
Share Alike. If you alter, transform, or build upon this work, you may distribute the
resulting work only under the same, similar or a compatible license.
For any reuse or distribution, you must make clear to others the license terms of this work. The
best way to do this is with a link to this web page.
Any of the above conditions can be waived if you get permission from the copyright holder.
Nothing in this license impairs or restricts the author's moral rights.
© Oscar Nierstrasz
1.37