Referential transparency Imperative programming is concerned with how FUNCTIONAL PROGRAMMING 1 PROF SIMON PARSONS Functional or applicative programming is by contrast concerned with what The main good property of functional programming is referential transparency It is based on the mathematics of the lambda calculus Church as opposed to Turing Every expression denotes a single value Programming without variables This value cannot be changed by evaluating an expression or by sharing it between different parts of the program It is inherently concise elegant and difficult to create subtle bugs in 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 2 program example output var flag boolean for any f What is the output But this is because mathematical functions are functions only of their inputs They have no memory We can always tell what the value of a mathematical function will be just from its inputs 4 Functional programming Lecture 1 At the heart of the problem is fact that the global data flag controls the value of f 5 Simple functional programming in HOPE Variables are no longer placeholders for values that change Which evaluates to 3 3 by definition and then to 9 by the definition of Since we aren t really interested in HOPE we won t explain the syntax in any great detail They are much less variable than variables in imperative programs square 3 dec square num num square x x x If we eliminate assignment we eliminate this kind of behaviour We call the function by In the rather odd syntax of HOPE this is is the thing that gives this behaviour 6 Other functional languages aren t typed LISP for example We start with a function that squares numbers flag not flag Functional programming Lecture 1 HOPE is strongly typed In particular the assignment Functional programming Lecture 1 f 1 f 2 f 2 f 1 This is odd since if these were mathematical functions begin flag true writeln f 1 f 2 writeln f 2 f 1 end Functional programming Lecture 1 3 Okay so the answer is 5 followed by 4 function f n int int begin if flag then f n else f 2 n flag not flag end Functional programming Lecture 1 Note only that it will always evaluate to 9 Note though that first line includes a type definition 7 Functional programming Lecture 1 8 Functional programming Lecture 1 9 Tuples Another function More complex functions Saying that these functions take two and three arguments is slightly misleading dec max num num num max m n if m n then m else n dec analyse real char trueval num analyse r if r 0 then else r 1 0 and r 1 0 round r Instead they both have one argument they are both tuples and One is a two tuple and one is a three tuple Applying This has one neat advantage you can get functions to return a tuple and thus several values dec max3 num num num num max3 a b c max a max b c The type definitions indicate that the functions take two and three arguments respectively analyse 1 04 dec IntDiv num num num num IntDiv m n m div n m mod n will give false 1 Note the overloading of And we can the compose max IntDiv 11 4 which will give 3 Functional programming Lecture 1 10 Functional programming Lecture 1 11 Functional programming Lecture 1 We can define functions to be infix infix 7 Which works in the same way as recursion normally does 13 Functional programming Lecture 1 With variables of course we would have to do this just once 14 Consider Once way around this would be to define the repeated bit as a new function Functional programming Lecture 1 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 do assignment let name expression1 in expression2 Another way is to use qualified expressions The first expression defines name and the second uses it 16 Functional programming Lecture 1 expression2 where name expression1 In general Efficiency here relies on efficient evaluation in the language So we could also write The l et construct allows us to extend the set of parameters of a function dec f1 num num f1 a b a if b 1 then 1 else a 15 We also have dec f num num f x let a g square max x 4 in a if x 1 then 1 else a dec f num num f x f1 g square max x 4 Functional programming Lecture 1 Here we have to evaluate g square max x 4 twice in some situations Again HOPE gives us a very elegant way of defining the function Each application of the recursive function is referentially transparent and easy to establish the value of dec f num num f x g square max x 4 if x 1 then 1 else g square max x 4 dec num num num x y if y 0 then 1 else x x y 1 Recursion fits in perfectly with the functional approach Functional programming Lecture 1 Because we don t have variables sometime it seems we have to do unecessary work when evaluating functions Here is the power function as an infix function dec sum num num sum n if n 0 then 0 else sum n 1 n Qualified expressions Here is a classic recursive function with a twist So to get iteration we need recursion Recursion Without variables we can t write functional programs with loops 12 17 Functional programming Lecture 1 18 We also use them to clarify functions dec quot num num num quot q r q let x E1 in if let x E2 in E3 then x else 1 x The second let doesn t change this Outside E3 x has its original meaning 19 Even in Java we have to use the right constructors This latter expression pattern matches q r with the result of calling IntDiv Functional programming Lecture 1 20 In HOPE we just deal with the recursive definition of a list Here nil and cons are constructors A single element list is then cons 3 nil And the list comprising 1 2 and 3 is 22 Note that there is nothing special about the names nil or cons typevar any data list any AnyNil AnyCons any list any Functional programming Lecture 1 This is a polymorphic definition We parameterize the list by the kinds of objects contained in it 23 Functional programming Lecture 1 With this definition we can build lists of any type infix 7 data list alpha nil alpha list alpha AnyCons a AnyCons b nil We can also write lists as for example 1 2 3 AnyCons AnyNil AnyCons AnyCons 1 nil With this information it is easy to write functions to handle lists Functional programming Lecture 1 25 Functional programming Lecture …
View Full Document
Unlocking...