G6021 Comparative Programming
G6021 Comparative Programming
Copyright By PowCoder代写 加微信 powcoder
Part 2 – Functional Programming
Part 2 – Functional Programming G6021 Comparative Programming 1 / 41
Functional Programming
General Concepts
Functional programs consist entirely of functions.
A function can be defined in terms of other functions (previously
defined by the programmer, in the libraries, or language
primitives).
The focus is in what is to be computed, not how it should be
Modern functional languages are strongly typed (no run-time type
errors) and have built-in memory management.
Advantages: shorter programs, easier to understand, easier to
design and maintain than imperative programs.
Disadvantage: often slower than imperative programs.
Reading list
See web page for books
www.haskell.org
Part 2 – Functional Programming G6021 Comparative Programming 2 / 41
Examples of applications
Music composition
Theorem provers and proof assistants
Graphical interfaces
Expert Systems
Telephony (Ericsson)
Part 2 – Functional Programming G6021 Comparative Programming 3 / 41
use Haskell as the main example functional programming
language in this module.
A modern functional programming language
Several interpreters and compilers available.
More information about Haskell, including the language report,
learning resources, user manuals, etc. can be found on the web
site www.haskell.org
Part 2 – Functional Programming G6021 Comparative Programming 4 / 41
Syntax of functional programs
The notation is inspired by the mathematical definition of functions,
using equations.
We can compute the square of a number using a function square
defined by the equation:
square x = x * x
Execution of programs
The role of the computer is to evaluate and display the results of the
expressions that the programmer writes, using the available functions
(like a sophisticated calculator).
Part 2 – Functional Programming G6021 Comparative Programming 5 / 41
When we enter an expression, such as
the computer will display the result: 36
As in mathematics, expressions may contain numbers, variables
or names of functions.
For instance 36, square 6, x * x are expressions.
Part 2 – Functional Programming G6021 Comparative Programming 6 / 41
Evaluation
To evaluate square 6 the computer will use the definition of
square and replace this expression by 6*6. Then using the
predefined * operation, it will find the result 36.
The process of evaluating an expression is a simplification
process, also called reduction or evaluation.
The goal is to obtain the value or normal form associated to the
expression, by a series of reduction steps.
1 square 6 → 6 * 6 → 36
36 is the value or normal form of square 6
2 ((3 + 1) + (2 + 1)) → ((3 + 1) + 3) → (4 + 3) → 7
7 is the value denoted by the expression
((3 + 1) + (2 + 1))
The meaning of an expression is its value.
Part 2 – Functional Programming G6021 Comparative Programming 7 / 41
There may be several reduction sequences for an expression.
The following is also a correct reduction sequence:
((3 + 1) + (2 + 1)) → (4 + (2 + 1)) → (4 + 3) → 7
In both cases the value is the same.
Can you draw a reduction graph of all possible reductions starting from
((3 + 1) + (2 + 1))
Part 2 – Functional Programming G6021 Comparative Programming 8 / 41
Properties
1 Unicity of normal forms:
In (pure) functional languages the value of an expression is
uniquely determined by its components, and is independent of the
order of reduction.
Advantage: readability of programs.
2 Non-termination:
Not all reduction sequences lead to a value, some reduction
sequences do not terminate.
Part 2 – Functional Programming G6021 Comparative Programming 9 / 41
Let us define the constant function
fortytwo x = 42
and the function infinity:
infinity = infinity + 1
The evaluation of infinity never reaches a normal form.
For the expression
fortytwo infinity
some reduction sequences do not terminate, but those which
terminate give the value 42 (unicity of normal forms).
Can you draw a reduction graph of all possible reductions starting from
fortytwo infinity ?
Part 2 – Functional Programming G6021 Comparative Programming 10 / 41
Strategies
Although the normal form is unique, the order of reductions is
important.
The strategy of evaluation defines the reduction sequence that the
language implements.
Most popular strategies:
1 Call-by-name (Normal order): reduce first the application using the
definition of the function, and then the argument
2 Call-by-value (Applicative order): evaluate first the argument and
then the application using the definition of the function
Part 2 – Functional Programming G6021 Comparative Programming 11 / 41
Strategies, continued
Different strategies require different number of reduction steps
(efficiency).
Call-by-name always finds the value, if there is one.
Call-by-value is in general more efficient, but may fail to find a
Haskell uses a strategy called lazy evaluation, which guarantees
that if an expression has a normal form, the evaluator will find it.
lazy evaluation = call-by-name + sharing
Part 2 – Functional Programming G6021 Comparative Programming 12 / 41
Example: Strategies
An example reduction graph for the expression: square (3+4)
square (3 + 4) – (3 + 4) ∗ (3 + 4)
(3 + 4) ∗ 7
7 ∗ (3 + 4)
Note: we underline each reducible expression (redex), all reductions
lead to the same answer, and some reductions are longer than others.
Part 2 – Functional Programming G6021 Comparative Programming 13 / 41
Example: Strategies
The previous example had the shortest path for call-by-value.
But let’s look at another example:
fortytwo (3 + 4)
fortytwo 7
In this case, call-by-value gives the longest reduction path…
Part 2 – Functional Programming G6021 Comparative Programming 14 / 41
Functional Values
Functions are also values, even though we cannot display them or
print them.
A function is a mapping that associates to each element of a given
type A, called the domain of the function, an element of type B,
called the codomain.
If a function f of type A → B is applied to an argument x of type A,
it gives a result (f x) of type B.
In Haskell the notation to associate a type to a function is:
square :: Integer → Integer
fortytwo :: Integer → Integer
Part 2 – Functional Programming G6021 Comparative Programming 15 / 41
Application is denoted by juxtaposition: (f x)
Example: (square 3)
To avoid writing too many brackets there are some
conventions:
▶ We will not write the outermost brackets:
square 3 instead of (square 3)
▶ Application has precedence over other operations:
square 3 + 1 means (square 3) + 1
▶ Application associates to the left:
square square 3 means (square square) 3
Part 2 – Functional Programming G6021 Comparative Programming 16 / 41
Syntax of Function Definitions
Functions are defined in terms of equations.
square x = x * x
min x y = if x <= y then x else y
We can also use conditional equations (aka guarded equations).
| x <= y = x
| x > y = y
| x < 0 = -1 | x == 0 = 0 | x > 0 = 1
The latter is equivalent to, but clearer than:
if x < 0 then -1 else if x == 0 then 0 else 1
Part 2 - Functional Programming G6021 Comparative Programming 17 / 41
Recursive Definitions
In the definition of a function f we can use the function f:
fact :: Integer → Integer
fact n = if n==0 then 1 else n*(fact(n-1))
Recursive definitions are evaluated by simplification, as any other
expression.
if 0 == 0 then 1 else 0 * (fact (0 - 1)) →
if True then 1 else 0 * (fact (0 - 1)) → 1
Note the operational semantics of the conditional:
1 Evaluate first the condition.
2 If the result is True then evaluate only the expression in the left
branch (then).
3 If the result is False then evaluate only the expression in the right
branch (else).
Therefore the only reduction sequence for fact 0 is the one shown
above, and this program is terminating.
Part 2 - Functional Programming G6021 Comparative Programming 18 / 41
Recursive Definitions, continued
However, if we start with
the reduction sequence does not terminate.
To avoid this problem we should write:
fact :: Integer → Integer
| n > 0 = n * (fact (n – 1))
| n == 0 = 1
| n < 0 = error "negative argument"
error is a predefined function that takes a string as argument.
When evaluated it causes immediate termination of the evaluator
and displays the string.
Part 2 - Functional Programming G6021 Comparative Programming 19 / 41
Local Definitions
As in mathematics, we can write:
f x = a + 1 where a = x/2
or equivalently,
f x = let a = x/2 in a + 1
The words let and where are used to introduce local definitions, valid
just on the right-hand side of the equation that we are writing.
We can write several local definitions:
f x = square (successor x) where
square z = z * z ; successor x = x + 1
Part 2 - Functional Programming G6021 Comparative Programming 20 / 41
Arithmetic Functions
Arithmetic operations are also functions (primitives), used in infix
notation: e.g. 3 + 4
In Haskell we can use them in prefix notation if we enclose them in
brackets: e.g (+) 3 4
(+) denotes the Curryfied version of +.
+ :: (Integer, Integer) → Integer
(+) :: Integer → Integer → Integer
3 - 1 - 2 should be read as (3 - 1) - 2
(+)1 is the successor function
(*)2 is the function that doubles its argument
Application has priority:
square 1 + 4 * 2 should be read as
(square 1) + (4 * 2)
Part 2 - Functional Programming G6021 Comparative Programming 21 / 41
Functional Composition
Functions are the building blocks of functional languages.
One way of combining functions is composition.
Composition is itself a function (predefineds).
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)
We can only compose functions whose types match.
square :: Integer → Integer
quad = square · square
Part 2 – Functional Programming G6021 Comparative Programming 22 / 41
Types: General Concepts
Values are divided in classes, called types.
Each type is associated with a set of operations.
Predefined Types:
Basic data types: Booleans, Characters, Numbers.
In Haskell: Bool, Char, Int, Integer, Float . . .
Structured types: Tuples, Strings, Lists.
In Haskell [Integer] is the type of lists of integers.
Function types: Integer → Integer, Integer → Float
Example: (Integer → Integer) → Integer
This is the type of a function that takes a function on integers as
input and returns an integer.
Convention: arrows associate to the right!
Part 2 – Functional Programming G6021 Comparative Programming 23 / 41
User-defined types
The programmer can also define new types.
Every valid expression must have a type. Expressions that cannot
be typed are considered erroneous and are rejected by the
compiler without evaluation (static typing).
Advantage of Statically Typed Languages
Types help detecting errors at an early stage.
Types help in the design of software since they are a simple form
of specification.
A program that passes the type controls is not guaranteed to be
correct, but it is free of type errors at runtime.
Part 2 – Functional Programming G6021 Comparative Programming 24 / 41
Polymorphism
Type systems can be
monomorphic: every expression has at most one type, or
polymorphic: some expressions have more than one type.
Functional composition:
(.) :: (b -> c) -> (a -> b) -> a -> c
where a,b,c are type variables.
Type variables can be instantiated to different types in different
Therefore (.) is a polymorphic function.
Part 2 – Functional Programming G6021 Comparative Programming 25 / 41
1 quad = square . square
square :: Int → Int
quad :: Integer → Int
(.) :: (Int → Int) → (Int → Int) → (Int → Int)
But we can also define sqrt :: Integer → Float and
compose sqrt . square using
(.) :: (Int → Float) → (Int → Int) → (Int → Float)
Part 2 – Functional Programming G6021 Comparative Programming 26 / 41
Examples, continued
1 The error function is also polymorphic
error :: String → a
fact :: Integer → Integer
| n > 0 = n * (fact (n – 1))
| n == 0 = 1
| n < 0 = error "negative argument"
Here the function error is used with type
String → Integer
Part 2 - Functional Programming G6021 Comparative Programming 27 / 41
Polymorphism and Overloading
Formally, the language of polymorphic types is defined as a set of
terms built out of type-variables (a,b,c), and type constructors
which are either atomic (Integer, Float, . . . ) or take arguments
(e.g. T1 → T2, [T]).
A polymorphic type represents the set of its instances, obtained
by substituting type variables by types.
Overloading is a related notion (also called ad-hoc polymorphism)
where several functions, with different types, share the same
Part 2 - Functional Programming G6021 Comparative Programming 28 / 41
Example (Overloading)
Arithmetic operations (such as addition) can be used both with
integers or reals. But a polymorphic type such as
+ :: a → a → a
is too general: it allows addition to be used with characters.
There are several solutions to this problem:
1 Use different symbols for addition on integers and on reals.
E.g. + and +. in Caml
2 Enrich the language of types:
E.g. + :: (Integer → Integer → Integer) ∧
(Float → Float → Float)
3 Define a notion of type class.
E.g. in Haskell: (+) :: Num a ⇒ a → a → a
(+) has type a → a → a where a is in the class Num.
Part 2 - Functional Programming G6021 Comparative Programming 29 / 41
Type Inference
Most modern functional languages do not require that the programmer
provides the type for the expressions used. The compiler is able to
infer a type, if one exists.
Intuitively:
The expression is decomposed into smaller sub-expressions, and
when a basic atomic expression is found, the information available
is used (if it is a predefined constant) or otherwise it is assigned
the most general type possible.
The way that the different components are put together to form the
expression indicates the constraints that the type variables must
The type of an expression can be deduced from its components only.
Part 2 - Functional Programming G6021 Comparative Programming 30 / 41
Type Inference, continued
With the definition:
square x = x * x
the expression1
square square 3
is rejected since
square :: Integer → Integer
and therefore its argument cannot be a function.
1This expression is equivalent to (square square) 3 because application
associates to the left.
Part 2 - Functional Programming G6021 Comparative Programming 31 / 41
Disjoint Sums
We can define several constructors in a type.
data Nat = Zero | Succ Nat
Zero and Succ are constructors. In this case they are not
polymorphic, but we could define a type with polymorphic constructors.
data Seq a = Empty | Cons a (Seq a)
The constructors are Empty and Cons (polymorphic).
Constructors are used to build terms. What distinguishes a constructor
from a function is that:
There is no definition associated to a constructor.
Constructors can be used in patterns.
isempty Empty = True
isempty (Cons x y) = False
Part 2 - Functional Programming G6021 Comparative Programming 32 / 41
Built-in Data Types
Bool: True, False
Char: ’a’,’2’, ...
You can find the type of an expression using :type
(or just:t), for example:
Prelude> :t True
True :: Bool
Prelude> :t 5
5 :: (Num t) => t
Prelude> 5
Prelude> :t it
it :: Integer
Prelude> :t ’c’
’c’ :: Char
Part 2 – Functional Programming G6021 Comparative Programming 33 / 41
Constructing data types: Pairs (x,y)
Components do not need to have same type: (2,True)
Built-in functions: fst, snd project the first and second
component respectively.
Prelude> fst (’a’,True)
Prelude> snd (’a’,True)
n-tuples: (2,3,5), (True,’c’,42,(3,4)), etc.
Note that you can build also n-tuples from pairs: e.g.,
((True,’c’),42)
Exercises. Write functions to:
extract ’c’ from ((True,’c’),42) using only fst and snd.
extract ’c’ from (True,’c’,42,(3,4))
Part 2 – Functional Programming G6021 Comparative Programming 34 / 41
A collection of things of the same type:
Examples: [1,2,3,7,9], [True,False,True],
Strings in Haskell are just: [Char]
Built-in constructors and functions:
:, [], head, tail, null, length, …
(:) :: a -> [a] -> [a]
length :: [a] -> Int
head :: [a] -> a
tail :: [a] -> [a]
null :: [a] -> Bool
We can generate lists in a number of different ways:
1:2:3:4:[]
Part 2 – Functional Programming G6021 Comparative Programming 35 / 41
Lists: generation
Cons and append. Try these:
[1,2,3] ++ [4,5]
’h’:”ello”
“h” ++ “ello”
What is the type of (++) ?
Try these:
head [3..]
List comprehension. Try these:
[x*x | x <- [1,2,3]]
[x*x | x <- [1..10], even x]
[(x,y) | x<-[1..10], y<-[1..5]]
Part 2 - Functional Programming G6021 Comparative Programming 36 / 41
Lists: writing functions
We can write the built-in functions ourselves:
len [] = 0
len (h:t) = 1+len t
hd [] = error "list is empty"
hd (h:t) = h
tl [] = error "list is empty"
tl (h:t) = t
app [] x = x
app (h:t) x = h:(app t x)
Here we are using pattern matching. Does the order of functions
matter? What if we miss some cases?
Exercise: can you think of a way of writing these functions without
pattern matching?
Part 2 - Functional Programming G6021 Comparative Programming 37 / 41
Worked example
Write a function to sum all the elements of a list.
Example: sum [1..10] = 55
First try:
sum x = if null x then 0 else head x+sum (tail x)
Using guarded equations:
| null x = 0
| otherwise = head x + sum (tail x)
Using pattern matching:
sum [] = 0
sum (h:t) = h+sum t
Which way is better? Are there other ways?
Part 2 - Functional Programming G6021 Comparative Programming 38 / 41
Algebraic data types
We can define our own data types:
data Bool = True | False
data Suit = Club | Diamond | Heart | Spade
data List a = nil | Cons a (List a)
And we can write functions over these types using pattern
not True = False
not False = True
head Nil = error "list is empty"
head (Cons x y) = x
Part 2 - Functional Programming G6021 Comparative Programming 39 / 41
Algebraic data types: Trees
data Tree a = Leaf a | Branch (Tree a) (Tree a)
toList (Leaf a) = [a]
toList (Branch l r) = (toList l) ++ (toList r)
toList (Branch (Leaf 1) (Leaf 2))
Exercise: List to Tree? Insert in order?
Part 2 - Functional Programming G6021 Comparative Programming 40 / 41
We have given a summary of many aspects of functional
programming, and the syntax of Haskell through examples.
In the following lectures we will look at many of the topics in these
notes again in more detail, and discuss foundations,
implementations and applications of functional programming.
Try out examples, and also exercises, by experimenting with
Haskell in the labs.
Test functions, find out about built-in functions, and know how to
find out the type of these functions
Next: foundations of functional programming
Part 2 - Functional Programming G6021 Comparative Programming 41 / 41
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com