Introduction to Functional Programming: Lecture 1 1

Introduction to
Functional Programming
John Harrison
University of Cambridge
Lecture 1
Introduction and Overview

Topics covered:
 Imperative programming
 Functional programming
 The merits of functional programming
 Overview of the course
 Lambda notation and its bene ts

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 2

Imperative programming
Imperative (or procedural) programs rely on
modifying a state by using a sequence of
commands.
The state is mainly modi ed by the assignment
command, written v = E or v := E.
We can execute one command before another by
writing them in sequence, perhaps separated by a
semicolon: C1 ; C2 .
Commands can be executed conditionally using
if, and repeatedly using while.
Programs are a series of instructions on how to
modify the state.
Imperative languages, e.g. FORTRAN, Algol, C,
Modula-3 support this style of programming.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 3

An abstract view
We ignore input-output operations, and assume
that a program runs for a limited time, producing
a result.
We can consider the execution in an abstract way
as:

0 ! 1 ! 2 !


! n

The program is started with the computer in an

initial state 0 , including the inputs to the
program.
The program nishes with the computer in a nal
state n , containing the output(s) of the program.
The state passes through a nite sequence of
changes to get from 0 to n ; in general, each
command may modify the state.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 4

Functional programming
A functional program is simply an expression, and
executing the program means evaluating the
expression.
 There is no state, i.e. there are no variables.
 Therefore there is no assignment, since there's
nothing to assign to.
 And there is no sequencing and no repetition,
since one expression does not a ect another.
But on the positive side:
 We can have recursive functions, giving
something comparable to repetition.
 Functions can be used much more exibly,
e.g. we can have higher order functions.
Functional languages support this style of
programming.
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 5

Example: the factorial

The factorial function can be written imperatively
in C as follows:
int fact(int n)
{ int x = 1;
while (n > 0)
{ x = x * n;
n = n - 1;
}
return x;
}
whereas it would be expressed in ML as a
recursive function:
let rec fact n =
if n = 0 then 1
else n * fact(n - 1);;

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 6

Why?
At rst sight a language without variables,
assignment and sequencing looks very impractical.
We will show in this course how a lot of
interesting programming can be done in the
functional style.
Imperative programming languages have arisen as
an abstraction of the hardware, from machine
code, through assemblers and macro assemblers,
to FORTRAN and beyond.
Perhaps this is the wrong approach and we should
approach the task from the human side. Maybe
functional languages are better suited to people.
But what concrete reasons are there for preferring
functional languages?

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 7

Merits of functional programming

By avoiding variables and assignments, we gain

the following advantages:
 Clearer semantics. Programs correspond more
directly to abstract mathematical objects.
 More freedom in implementation, e.g.
parallelizability.
By the more exible use of functions, we gain:
 Conciseness and elegance.
 Better parametrization and modularity of
programs.
 Convenient ways of representing in nite data.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 8

Denotational semantics
We can identify our ML factorial function with an
abstract mathematical (partial) function Z ! Z :
8
< n! if n  0
[ fact]](n) = :
? otherwise

where ? denotes unde nedness, since for negative

arguments, the program fails to terminate.
Once we have a state, this simple interpretation
no longer works. Here is a C `function' that
doesn't correspond to any mathematical function:
int rand(void)
{ static int n = 0;
return n = 2147001325 * n + 715136305;
}
This gives di erent results on successive calls!

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 9

Semantics of imperative programs

In order to give a corresponding semantics to
imperative programs, we need to make the state
explicit. For example we can model commands as:
 Partial functions  !  (Strachey)
 Relations on    (Hoare)
 Predicate transformers, i.e. total functions
( ! bool) ! ( ! bool) (Dijkstra)
If we allow the goto statement, even these are not
enough, and we need a semantics based on
continuations (Wadsworth, Morris).
All these methods are quite complicated.
With functional programs, we have a real chance
of proving their correctness, or the correctness of
certain transformations or optimizations.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 10

Problems with functional programs

Functional programming is not without its
de ciencies. Some things are harder to t into a
purely functional model, e.g.
 Input-output
 Interactive or continuously running programs
(e.g. editors, process controllers).
However, in many ways, in nite data structures
can be used to accommodate these things.
Functional languages also correspond less closely
to current hardware, so they can be less ecient,
and it can be hard to reason about their time and
space usage.
ML is not a pure functional language, so you can
use variables and assignments if required.
However most of our work is in the pure
functional subset.
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 11

Overview of the course (1)

We start with the theoretical underpinning,

-calculus, and move up to the practical business
of programming in ML.
Roughly 31 of the course is devoted to the
theoretical parts, and 32 to the practical parts.
The theoretical parts are:
1. Introduction and overview (this lecture)
2. -calculus as a formal system
3. -calculus as a programming language
4. Types

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 12

Overview of the course (2)

The practical or `applied' parts of the course are:

1. Introduction to ML
2. More about polymorphism
3. Recursive types
4. Proofs about programs
5. Further ML
6. Other styles of functional programming
7. ML examples (1)
8. ML examples (2)

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 13

Lambda notation
Lambda notation is a way of denoting functions,
invented by Alonzo Church in the 1930s. We
write:

x: E [x]

to denote `the function of x that yields E [x]'.

Here E [x] is any expression which may or may
not contain x.
For example x: x is the identity function, which
simply returns its argument, while x: x2 is the
squaring function.
The letter  is arbitrary, a historical accident.
Originally Church used x^: E [x], and a series of
typesetting errors transformed it into the present
form. One also sees x 7! E [x] and [x] E [x].
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 14

Why?
In informal mathematics, when talking about a
function, one normally gives it a name: `de ne
f (x) = E [x] . . . then


f


'.
Similarly, most programming languages will only
let you de ne functions if you are prepared to
give them a name.
This approach is rather inconsistent. It means we
are not treating functions on a par with other
mathematical objects. We don't say:
De ne x and y by x = 2 and y = 4
respectively. Then xx = y
Lambda notation helps to put functions on an
equal footing. This is important in functional
programming.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 15

Bene ts of -notation
The -notation can be useful too in order to make
mathematics clearer.
When we discuss x + xy, we are often vague
about whether we mean the value for a particular
x, or a function of x (or y . . . ). Using -notation
this can be made explicit.
In fact, using just:
 Variables, e.g. x, y.
 Constants, e.g. 3, true, +.
 Applications of functions to arguments, e.g.
f x.
 Lambda abstractions of expressions over
variables, e.g. x: x + y
we reach a general `abstract syntax' for
mathematics.
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 16

Currying
We can have functions of more than one
argument by using, for example x: y: x + y.
We can think of this as a function Z ! (Z ! Z ).
When given one argument, say 2, it returns a
function Z ! Z that adds 2 to its argument, and
this takes the second argument. This device is
known as currying, after Haskell Curry.
We adopt the conventions that x y: E [x; y] means
x: y: E [x; y], and that function application
associates to the left, e.g. that f x y means
(f (x))(y). This supports the use of currying, e.g.

(x y: x + y) 1 2 = (y: 1 + y) 2 = 1 + 2

Note that the brackets round function arguments

are optional.
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 17

Variable binding
Many constructs in mathematics bind variables.
The variable x in
Za
3x2 dx
0

is bound, whereas a is free; likewise n is bound

and k free in

kn=0 n2

Free and bound variables can be quite

complicated, as we shall see. Using -notation, all
these variable binding constructs can be broken
down so that the only binding operation is
-abstraction.

John Harrison University of Cambridge, 16 January 1997

Introduction to Functional Programming: Lecture 1 18

Example of di erentiation
For example, the everyday construct d x2 can be
dx
analyzed as follows:

D (x: EXP x 2) x

where D is the (curried) di erentiation operator

(R ! R ) ! R ! R giving the derivative of its
rst argument at the point indicated by its second
argument, and EXP the exponentiation function.
So there are really two instances of x here, one
bound, one free. The same occurs in
Zx
2x dx
0

but here the everyday notation separates the two

properly.
John Harrison University of Cambridge, 16 January 1997
Introduction to Functional Programming: Lecture 1 19

Russell's paradox
Originally, Church hoped to use -notation to
give a foundation for mathematics, by introducing
constants for logical operations, e.g. : to mean
`not'. Unfortunately this turned out to be
inconsistent, because de ning R = x: : (x x) we
have:

R R = (x: : (x x)) R = : (R R)

We know there is a correspondence between sets

and their characteristic function, so if we think of
s x as meaning x 2 s, this is simply the well
known Russell paradox of the set of all sets that
do not contain themselves:

R = fx j x 62 xg

John Harrison University of Cambridge, 16 January 1997