' $FUNCTIONAL PROGRAMMING (1)PROF. SIMON PARSONS& %' $• Imperative programming is concerned with “how”.• Functional or applicative programming is, by contrast, concernedwith “what”.• It is based on the mathematics of the lambda calculus (Church asopposed to Turing).• “Programming without variables”.• It is inherently concise, elegant, and difficult to create subtlebugs in.Functional programming Lecture 1 2& %' $Referential transparency• The main (good) property of functional programming isreferential transparency.• Every expression denotes a single value.• This value cannot be changed by evaluating an expression or bysharing it between different parts of the program.• There can be no reference to global data.• (Indeed there is no such thing as global data.)• There are no side-effects, unlike in referentially opaque languages.Functional programming Lecture 1 3& %' $program example(output)var flag: booleanfunction f(n:int): intbeginif flag then f:= nelse f: 2*nflag := not flagendbeginflag := truewriteln(f(1) + f(2))writeln(f(2) + f(1))endFunctional programming Lecture 1 4& %' $• What is the output?Functional programming Lecture 1 5& %' $• Okay, so the answer is 5 followed by 4.• This is odd since if these were mathematical functions,f(1) + f(2) = f (2) + f (1)for any f.• But this is because mathematical functions are functions only oftheir inputs.• They have no memory.• We can always tell what the value of a mathematical functionwill be just from its inputs.Functional programming Lecture 1 6& %' $• At the heart of the “problem” is fact that the global data flagcontrols the value of f.• In particular the assignment:flag := not flagis the thing that gives this behaviour.• If we eliminate assignment, we eliminate this kind of behaviour.• Variables are no longer placeholders for values that change.• (They are much less variable than variables in imperativeprograms).Functional programming Lecture 1 7& %' $Simple functional programming in HOPE• We start with a function that squares numbers.• In the rather odd syntax of HOPE this is:dec square: num -> num;--- square(x) <= x * x;• Since we aren’t really interested in HOPE, we won’t explain thesyntax in any great detail.• Note though that first line includes a type definition.Functional programming Lecture 1 8& %' $• HOPE is strongly typed.• Other functional languages aren’t typed (LISP for example).• We call the function by:square(3)• Which evaluates to 3 * 3 by definition, and then to 9 by thedefinition of *.• Note only that, it will always evaluate to 9.Functional programming Lecture 1 9& %' $• More complex functions:dec max : num # num -> num;--- max(m, n) <= if m > n then m else n;• and:dec max3 : num # num # num -> num---max3(a, b, c) <= max(a, max(b, c));• The type definitions indicate that the functions take two andthree arguments respectively.Functional programming Lecture 1 10& %' $Tuples• Saying that these functions take two and three arguments isslightly misleading.• Instead they both have one argument— they are both tuples.• One is a two-tuple and one is a three-tuple.• This has one neat advantage—you can get functions to return atuple, and thus several values.dec IntDiv : num # num -> num # num;--- IntDiv(m, n) <= (m div n, m mod n);• And we can the compose max(IntDiv(11, 4)), which willgive 3.Functional programming Lecture 1 11& %' $• Another function:dec analyse : real -> char # trueval # num;---analyse(r) <= (if r < 0 then ’-’ else ’+’,(r > = -1.0) and (r=< 1.0),round(r));• Applyinganalyse(-1.04)• will give (’-’, false, -1)• Note the overloading of >.Functional programming Lecture 1 12& %' $Recursion• Without variables, we can’t write functional programs withloops.• So to get iteration, we need recursion.dec sum : num -> num;---sum(n) <= if n = 0 then 0else sum(n - 1) + n;• Which works in the same way as recursion normally does.• Recursion fits in perfectly with the functional approach.• Each application of the recursive function is referentiallytransparent and easy to establish the value of.Functional programming Lecture 1 13& %' $• Here is a classic recursive function, with a twist.• We can define functions to be infix.• Here is the power function as an infix function:infix ˆ : 7;dec ˆ : num # num -> num;--- x ˆ y <= if y = 0 then 1else x * x ˆ (y - 1);• Again, HOPE gives us a very elegant way of defining thefunction.Functional programming Lecture 1 14& %' $Qualified expressions• Because we don’t have variables, sometime it seems we have todo unecessary work when evaluating functions:dec f: num -> num;---f(x) <= g(square(max(x, 4))) +(if x <= 1 then 1else g(square(max(x, 4))));• Here we have to evaluate g(square(max(x, 4))) twice insome situations.• With variables, of course, we would have to do this just once.Functional programming Lecture 1 15& %' $• Once way around this would be to define the repeated bit as anew function:dec f: num -> num;---f(x) <= f1(g(square(max(x, 4))))dec f1: num -> num;---f1(a, b) <= a + (if b =< 1 then 1 else a)• Efficiency here relies on efficient evaluation in the language.• Another way is to use qualified expressions.Functional programming Lecture 1 16& %' $• Consider:dec f : num -> num--- f(x) <= let a == g(square(max(x, 4)))in a + (if x =< 1 then 1 else a))• Theˇlet construct allows us to extend the set of parameters of afunction.• In general:let <name> == <expression1> in <expression2>• The first expression defines <name> and the second uses it.Functional programming Lecture 1 17& %' $• We also have:<expression2> where <name> == <expression1>• So we could also write:dec f : num -> num--- f(x) <= a + (if x =< 1 then 1 else a))where a == g(square(max(x, 4)))• Note that == associates a name with an expression, it does not doassignment.Functional programming Lecture 1 18& %' $• To see this:let x == E1 inif (let x == E2 in E3)then xelse 1 + x• The first let associates E1 with x.• The second let doesn’t change this.• Instead it renames E2 as x within E3.• Outside E3 x has its original meaning.• So far we have used qualified expressions to save on evaluation.Functional programming Lecture 1 19& %' $• We also use them to clarify functions.• A third use is to decompose tuples.dec quot : num # num -> num;--- quot(q, r) <= q;dec rem : num # num -> num;--- rem(q, r) < = r;let pair == IntDiv(x, y) in
View Full Document
Unlocking...