Transcript Functional programming - University of Cape Town

Functional programming in Clean
Gary Marsden
Semester 2 – 2000
University of Cape Town
Gary Marsden
Slide 1
What the heck is functional programming
 Functional languages are so called because
they require code to be written as functions
(in the mathematical sense)
 Note that everything is a function – there is no
notion of “state”
 This is radically different from other nonfunctional (dis-functional?) imperative
languages
University of Cape Town
Gary Marsden
Slide 2
So what the heck is imperative programming?
 The languages you are used to (C++, Java, C
etc.) are all based on the Von Neumann
computer architecture
 Simply put,the VN model has a CPU which
accesses a piece of memory. That memory
contains data and instructions to perform on
the data
Data
CPU
(Bottleneck)
University of Cape Town
Gary Marsden
Instructions
Slide 3
Should programming follow Von Neumann?
 The Von Neumann architecture worked so
well for low level hardware, that the idea was
carried over into programming languages
 Over time, it has become clear that some of
the low level ideas lead to problems in writing
good software – GOTO statements and global
variables being two culprits.
 Functional languages aim to rid us of the last
anachronism – the assignment statement
University of Cape Town
Gary Marsden
Slide 4
No assignment statement!
a=5
a=5
University of Cape Town
Gary Marsden
Slide 5
Reasons for ditching assignment
 Look at the last
‘if’ statement
 Shouldn’t the
expression
always evaluate
to true?
even = TRUE;
int calc (int x)
{
even = !even;
if (even) x++ else x-;
}
....
if (calc(6) == calc(6))
{....
 Having explicit
state results in
side effects
University of Cape Town
Gary Marsden
Slide 6
More reasons
 Because of side effects, it is impossible to
reason about the correctness of a program
 Proving a program correct becomes
important if software reliability is to improve
 One response to this was strongly types OO
languages (Java)
 Another response is the creation of
functional languages, where programs can be
proven correct
University of Cape Town
Gary Marsden
Slide 7
How do we remove assignment?
 One way to remove assignments (and
therefore explicit state) is to make everything
a function (even data values)
 One can program “functionally” in imperative
languages, but there is a temptation to the
dark side
 By making everything a function we can
ensure that our program calculates using
functions whose results can be determined
through parameters alone – referential
transparency
University of Cape Town
Gary Marsden
Slide 8
So can we keep variables?
 Kind of – a variable should be thought of as
an undefined constant
 As a variable can never be altered through a
direct assignment, the value of the variable
can be taken as constant at any given point in
the execution of a function
 This has important consequences for
serialisation and parallel tasks
University of Cape Town
Gary Marsden
Slide 9
Can functional languages be used for any
program?
 Yes!
 You should be familiar with the notion of a
Turing machine and Turing computability
 Functional languages are based on calculus
 Church (who invented -calculus) and Turing
managed to show that anything definable in calculus was Turing computable
University of Cape Town
Gary Marsden
Slide 10
What is the catch
 Functional languages have two main
problems
– Efficiency
• Underlying architectures optimised for imperative style
• Not as much experience in compiler technology
– Coding inherently imperative tasks
• Highly interactive programs rely on a non-functional
human
• Operating systems deal with machine hardware; i.e. state
University of Cape Town
Gary Marsden
Slide 11
Some terminology
 Before we look at a functional program we
need to learn some functional terms
– A function maps values from a domain to a range
– Independent values are taken from the domain
and converted to a dependent value in the range

y = f(x) where
– f: X Y
– y{Y} (the range)
– x{X} (the domain)
University of Cape Town
Gary Marsden
Slide 12
Defining functions
inc:: Int -> Int
square x = x * x
alwaysthree:: Int ->
Int
alwaysthree x = 3
Start:: Int
Start = square 5
University of Cape Town
Gary Marsden
Points to note
First line is
type definition
of function
No ‘;’
Case sensitive
‘main’
program
Slide 13
Evaluating functions
 Before getting into Clean, it is worth
considering how these programs are
evaluated
– Evaluation proceeds by re-writing the program to
a reduced form
– Each reduction is called a redex (reducible
expression)
– When there are no more redexs available, the
program is in its simplest (normal) form and the
result is printed out
– This leads to a very recursive style of
programming
University of Cape Town
Gary Marsden
Slide 14
Redex in action
“->“ denotes a redex step
square (1+2) -> (1+2) * (1+2)
-> 3 * (1+2)
-> 3 * 3
-> 9 (normal form)
– In the second step, there was a choice
about which bracket to evaluate
– Choice does not matter as no side effects –
parallel execution?
– Order of evaluation is called the reduction
strategy
University of Cape Town
Gary Marsden
Slide 15
Finding a result
 There is one warning about evaluation order –
some orders may result in no answer being
found
 Consider an infinitely recursive function (inf =
inf)
 What is the reduction of this call
alwaysthree inf -> alwaysthree inf -> ...
or
alwaysthree inf -> 3
University of Cape Town
Gary Marsden
Slide 16
Laziness
In some languages (e.g. ML), the
parameters to a function are evaluated
before the function body is executed
– eager evaluation
In newer languages (like Clean)
function parameters are only calculated
when needed
– lazy evaluation
University of Cape Town
Gary Marsden
Slide 17
Benefits of laziness
Lazy evaluation will always find a
normal form, if it is possible to find one
Functions written in a lazy language
can also deal with infinitely long lists
(should this be needed)
– this is a typical way to deal with user input
University of Cape Town
Gary Marsden
Slide 18
The ubiquitous factorial function
 Calculating a factorial is the “hello world” for
functional languages
– probably because the algorithm is elegantly
expressed recursively
fac:: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)
– Try redexing this by hand
University of Cape Town
Gary Marsden
Slide 19
What we can learn from fac
 First off, it looks like we have two declarations
of fac
– In a sense we do. This is called pattern matching,
where the most appropriate form of the function is
used to evaluate the given parameter
 There is a propagation part to the function,
which includes a recursive call (the last line)
 There is a termination line in the function (the
line matching to 0)
 Make sure there is always a termination
clause!
University of Cape Town
Gary Marsden
Slide 20
Guards!
 An alternative to pattern matching is the
guard mechanisim
 More flexible than pattern matching, but
harder (perhaps) to read
fac:: Int -> Int
fac n
|n == 0
= 1
= n * (n-1)
University of Cape Town
Gary Marsden
Slide 21
Data structures
 Data structures in functional languages can
only be read, once they have been created
– remember no assignment (no destructive update)
 There is no global state, so all structures
must be passed as a parameter
 Common to all functional languages is the list
data structure (like a linked list)
 Just as with arrays in imperative languages,
list operators are built in to the language
University of Cape Town
Gary Marsden
Slide 22
List definition
 Lists are ordered and can contain any data
type, provided every element is of the same
type
 The list is built using a constructor (or cons)
operation. In early languages, this was a
prefix operator – more recent languages
(including Clean) use the ‘:’ infix operator
 Lists end with the ‘empty list’ or ‘Nil’ symbol –
usually ‘[]’
University of Cape Town
Gary Marsden
Slide 23
List creation
 Lists in Clean are conceptually like this:
1 :
2 :
3 :
[]
 And can be written as
– 1:(2:(3:[]))
– 1:2:3:[]
– [1,2,3] – shorthand form, most popular
University of Cape Town
Gary Marsden
Slide 24
List manipulation – head and tail
There are many functions which work
on lists, but the most common are hd
and tl
hd:: [a] -> a
hd [x:xs] -> x
tl:: [a] -> [a]
tl [x:xs] -> xs
University of Cape Town
Gary Marsden
Slide 25
Notes on hd and tl
 The notation [a] is used to denote a list of
some type ‘a’
 Therefore, hd takes a list of ‘a’ and returns
the first element from that list (that element
being of type ‘a’)
 tl takes a list of type ‘a’, removes the first
element and returns the rest of the list
 Note how we use the cons operator to pattern
match
University of Cape Town
Gary Marsden
Slide 26
Sample list function
 How would we write a length function?
 Type
length:: [a] -> Int
 Code – Hint: think about termination first
length [] = 0
length [x:xs] = 1 + length xs
University of Cape Town
Gary Marsden
Slide 27
Sorting
 Quicksort is a recursive algorithm – can we
write a functional language equivalent?
qsort:: [Int] -> [Int]
qsort [] = []
qsort [x:xs] =qsort(seq x xs)++[x]++qsort(gt x xs)
seq:: Int [Int] -> [Int]
seq a [] = []
seq a [x:xs]
|x<=a = [x:seq a xs]
= seq a xs
University of Cape Town
Gary Marsden
gt:: Int [Int] -> [Int]
gt a [] = []
gt a [x:xs]
|x>a = [x:gt a xs]
= gt a xs
Slide 28
Tuples
 Besides lists, functional languages have the
equivalent of records – i.e. Tuples
 Tuples are denoted by normal brackets ( )
–
–
–
–
–
(1,’a’):: (Int,Char)
(“hi”,True,2):: (String,Bool,Int)
([1,2],sqrt):: ([Int], Real->Real)
(1,(2,3)):: (Int,(Int,Int))
[(1,’a’)]:: [(Int,Char)]
 Actually, Clean has a Record type, where
fields can be named
University of Cape Town
Gary Marsden
Slide 29
Higher order functions
 The final thing to look at (for now) is sending
functions as parameters:
map:: (a->b) [a]
-> [b]
map
f
[]
-> []
map
f
[x:xs] -> [f x: map f xs]
 So, we can pass a function to map which it
can apply to every element of the list
University of Cape Town
Gary Marsden
Slide 30
Applicative programming
 Another name for functional programming is
applicative programming
 This idea is that you state the solution you
want, not the means to calculate it (as in
imperative programming)
 Applicative languages are thought to be
easier to use, so most 4GL’s are built in this
way
 The proponents of FL’s say they represent the
highest level programming available
University of Cape Town
Gary Marsden
Slide 31
Some parting thoughts
 These extracts are taken from a XEROX PARC
paper on FL’s
– “Even if they never become useful for real
programmers, functional languages are useful
objects of study. Functional languages are entirely
mathematical, so the places where they don’t
work show where computing is not mathematics
and help to illuminate both fields.”
James H.
Morris
University of Cape Town
Gary Marsden
Slide 32