CSc 520 - Principles of Programming Languages
33 : Functional Programming
Christian Collberg
Department of Computer Science
University of Arizona
- During the next few weeks we are going to
work with functional programming. Before I
can explain to you what FP is, I thought I'd
better put things into perspective by talking
about other programming paradigms.
- Over the last 40 or so years, a number of
programming paradigms (a programming paradigm
is a way to think about programs and programming)
have emerged.
A programming paradigm
- is a way to think about programs, programming,
and problem solving,
- is supported by one or more programming languages.
Being familiar with several paradigms makes you
a better programmer and problem solver. The most
popular paradigms:
- Imperative programming.
- Functional programming.
- Object-oriented programming.
- Logic Programming.
When all you have is a hammer, everything looks like a nail.
Imperative Programming
- Programming with state.
- Also known as procedural programming.
The first to emerge in the 1940s-50s. Still
the way most people learn how to program.
- FORTRAN, Pascal, C, BASIC.
Functional Programming
- Programming with values.
- Arrived in the late 50s with the LISP language.
LISP is still popular and widely used by AI people.
- LISP, Miranda, Haskell, Gofer.
Object-Oriented Programming
- Programming with objects that
encapsulate data and operations.
- A variant of imperative programming first
introduced with the Norwegian language Simula
in the mid 60s.
- Simula, Eiffel, Modula-3, C++.
Logic Programming
- Programming with relations.
- Introduced in the early 70s. Based on
predicate calculus. Prolog
is popular with Computational Linguists.
- Prolog, Parlog.
We program an abstraction of the Von Neumann
Machine, consisting of a store (memory),
a program (kept in the store), A CPU
and a program counter (PC):
| | |
<184>>10cm<184>>
Computing x:=x+1
- Compute x's address, send it to the store,
get x's value back.
- Add 1 to x's value.
- Send x's address and
new value to the store
for storage.
- Increment PC.
|
|
The programmer...
- uses control structures
(IF, WHILE, ...) to alter the
program counter (PC),
- uses assignment statements
to alter the store.
- is in charge of memory management,
i.e. declaring variables to hold values during the
computation.
1#1
Procedural programming is difficult because:
- A procedural program can be in a large
number of states. (Any combination of
variable values and PC locations constitutes
a possible state.) The programmer has to
keep track of all of them.
- Any global variable can be changed from any
location in the program. (This is particularly true
of languages like C & C++ [Why?]).
- It is difficult to reason mathematically about
a procedural program.
In contrast to procedural languages, functional programs
don't concern themselves with state and memory
locations. Instead, they work exclusively
with values, and expressions and functions
which compute values.
- Functional programming is not
tied to the von Neumann machine.
- It is not necessary to know
anything about the underlying hardware when
writing a functional program, the
way you do when writing an imperative program.
- Functional programs are more declarative
than procedural ones; i.e. they describe what
is to be computed rather than how it should
be computed.
Common characteristics of functional programming
languages:
- Simple and concise syntax and semantics.
- Repetition is expressed as recursion
rather than iteration.
- Functions are first class objects.
I.e. functions can be manipulated just
as easily as integers, floats, etc.
in other languages.
- Data as functions. I.e. we can build
a function on the fly and then
execute it. (Some languages).
- Higher-order functions. I.e. functions
can take functions as arguments and
return functions as results.
- Lazy evaluation. Expressions are
evaluated only when needed. This allows
us to build infinite data structures,
where only the parts we need are actually
constructed. (Some languages).
- Garbage Collection. Dynamic memory that
is no longer needed is automatically
reclaimed by the system. GC is also
available in some imperative languages
(Modula-3, Eiffel) but not in others
(C, C++, Pascal).
- Polymorphic types. Functions can
work on data of different types.
(Some languages).
- Functional programs can be more
easily manipulated mathematically
than procedural programs.
Pure vs. Impure FPL
- Some functional languages are pure, i.e.
they contain no imperative features at all.
Examples: Haskell, Miranda, Gofer.
- Impure languages may have assignment-statements,
goto:s, while-loops, etc. Examples: LISP, ML, Scheme.
- A function maps argument values (inputs)
to result values (outputs).
- A function takes argument values from
a source set (or domain).
- A function produces result values that lie in
a target set (or range).
Capitals
- A function must not map an input value to
more than one output value. Example:
MultiOutput
- If a function 2#2 maps every element in the
domain to some element in the range, then
2#2 is total. I.e. a total function is
defined for all arguments.
Plus
- A function that is undefined for some inputs,
is called partial.
Divide
- Divide is partial since 3#3 is undefined.
A function can be specified extensionally or
intentionally.
Extensionally:
- Enumerate the elements of the (often infinite)
set of pairs ``(argument, result)'' or
``
4#4.''
- The extensional view emphasizes the external
behavior (or specification), i.e. what
the function does, rather than how it does it.
5#5
Intensionally:
- Give a rule (i.e. algorithm) that
computes the result from the arguments.
- The intentional view emphasizes the process
(or algorithm) that is used to compute the result
from the arguments.
6#6
Graphically:
- The graphical view is a notational variant
of the intentional view.
EitherEven
- The most important operation in a functional
program is function application,
i.e. applying an input argument to the function,
and retrieving the result:
7#7
- Function composition makes the result of one function
application the input to another application:
8#8
Example: How many numbers are there between
9#9 and 10#10, inclusive?
Extensional Definition:
11#11
Intentional Definition:
12#12
Graphical Definition:
SumBetween
To define a function we must specify the
types of the input and output sets
(domain and range, i.e. the function's signature),
and an algorithm that maps inputs to outputs.
FunctionTypes
- The most important concept of functional programming
is referential transparency. Consider the
expression
13#13
- 14#14 occurs twice in the expression, but
it has the same meaning (6) both times.
- RT means that the value of a particular expression
(or sub-expression) is always the same, regardless
of where it occurs.
- This concept occurs naturally in mathematics,
but is broken by imperative programming languages.
- RT makes functional programs easier to reason about
mathematically.
- RT is a fancy term for a very simple concept.
- What makes FP particularly simple, direct, and expressive,
is that there is only one mechanism (function application)
for communicating between subprograms.
- In imperative programs we can communicate either through
procedure arguments or updates of global variables. This is
hard to reason about mathematically.
- A notation (programming language) where the value of an
expression depends only on the values of the sub-expressions
is called referentially transparent.
- Pure functional programming languages are
referentially transparent.
- This means that it is easy to find the meaning (value)
of an expression.
- We can evaluate it by substitution.
I.e. we can replace a function application by the function definition
itself.
Evaluate
15#15:
16#16
So, isn't Pascal referentially transparent???
Well, sometimes, yes, but not always. If a Pascal
function 17#17 has side-effects (updating a
global variable, doing input or output), then
18#18 may not be the same as 19#19.
I.e. The second 20#20 has a different meaning
than the first one.
21#21
Furthermore, in many imperative languages the
order in which the arguments to a binary operator
are evaluated are undefined.
22#22
This cannot happen in a pure functional language.
- Expressions and sub-expressions always
have the same value, regardless of the
environment in which they're evaluated.
- The order in which sub-expressions are
evaluated doesn't effect the final result.
- Functions have no side-effects.
- There are no global variables.
- Variables are similar to variables in
mathematics: they hold a value, but
they can't be updated.
- Variables aren't (updatable) containers the way
they are imperative languages.
- Hence, functional languages are much more
like mathematics than imperative languages.
Functional programs can be treated
as mathematical text, and manipulated
using common algebraic laws.
- Here is a mathematical definition of the
combinatorial function 23#23 ``n choose r'',
which computes the number of ways to pick 24#24 objects from 10#10:
25#25
- Give an extensional, intentional, and graphical
definition of the combinatorial function, using
the notations suggested in this lecture.
- You may want to start by defining an auxiliary
function to compute the factorial function,
26#26.
Christian Collberg
2008-04-14