Functional Programming Functional vs Imperative Referential transparency Imperative programming concerned with how The main good property of functional programming is referential transparency COMS W4115 Functional programming concerned with what Based on the mathematics of the lambda calculus Church as opposed to Turing Programming without variables Prof Stephen A Edwards Fall 2003 Columbia University Department of Computer Science It is inherently concise elegant and difficult to create subtle bugs in It s a cult once you catch the functional bug you never escape Every expression denotes a single value The value cannot be changed by evaluating an expression or by sharing it between different parts of the program No references to global data there is no global data There are no side effects unlike in referentially opaque languages Original version by Prof Simon Parsons The Joy of Pascal program example output var flag boolean Strange behavior Variables This prints 5 then 4 At the heart of the problem is fact that the global data flag affects the value of f Odd since you expect In particular function f n int int begin if flag then f n else f 2 n flag not flag end begin flag true writeln f 1 f 2 writeln f 2 f 1 end f 1 f 2 f 2 f 1 flag not flag Mathematical functions only depend on their inputs gives the offending behavior They have no memory Eliminating assignments eliminates such problems In functional languages variables not names for storage What does this print Simple functional programming in ML A function that squares numbers sml Standard ML of New Jersey Version 110 0 7 fun square x x x val square fn int int square 5 val it 25 int Instead they re names that refer to particular values Think of them as not very variables A more complex function fun max a b if a b then a else b val max fn int int int max 10 5 val it 10 int max 5 10 val it 10 int Notice the odd type int int int This is a function that takes an integer and returns a function that takes a function and returns an integer Currying Functions are first class objects that can be manipulated with abandon and treated just like numbers fun max a b if a b then a else b val max fn int int int val max5 max 5 val max5 fn int int max5 4 val it 5 int max5 6 val it 6 int Tuples and arguments Polymorphism You can also pass and return tuples to from functions Reverse has an interesting type fun max a b if a b then a else b val max fn int int int max 10 5 val it 10 int fun reverse a b b a val reverse fn a b b a reverse 10 5 val it 5 10 int int max reverse 10 5 val it 10 int fun reverse a b b a val reverse fn a b b a This means it can reverse a two tuple of any type and any other type reverse 10 5 2 val it 5 2 10 real int reverse foo 3 14159 val it 3 14159 foo real string Recursion ML doesn t have variables in the traditional sense so you can t write programs with loops So use recursion fun sum n if n 0 then 0 else sum n 1 n val sum fn int int sum 2 val it 3 int sum 3 val it 6 int sum 4 val it 10 int Power operator Using the same thing twice The let expression You can also define functions as infix operators Without variables duplication may appear necessary fun x y if y 0 then 1 else x x y 1 val fn int int int 2 2 val it 4 int 2 3 val it 8 int fun f x g square max x 4 if x 1 then 1 else g square max x 4 The easiest way is to introduce a local name for the thing we need multiple times let is not assignment Data Types Lists let val a 5 in let val a a 2 in a end a end val it 7 5 int int Programs aren t very useful if they only manipulate scalars Tuples have parenthesis lists have brackets One fix use an extra function fun f1 a b b if a 1 then 1 else b fun f x f1 x g square max x 4 Functional languages are particularly good at manipulating more complex data types fun f x let val gg g square max x 4 in gg if x 1 then 1 else gg end 5 3 val it 5 3 int int 5 3 val it 5 3 int list You ve already seen tuples which is a fixed length list of specific types of things Concatenate lists with ML also has lists arbitrary length vectors of things of the same type 1 2 3 4 5 val it 1 2 3 4 5 int list Cons Other list functions Add things to the front with pronnounced cons null 1 2 val it false bool 1 2 3 null nil val it 1 2 3 int list val it true bool 5 it null val it 5 1 2 3 int list val it true bool Concatenating is not the same as consing val a 1 2 3 4 val a 1 2 3 4 int list 1 2 3 4 stdIn Error operator and operand don t agree literal hd a val it 1 int operator domain int list int list list tl a operand int list int list val it 2 3 4 int list in expression Fun with recursion fun addto if null else hd val addto l v l then nil l v addto tl l v fn int list int int list addto 1 2 3 2 val it 3 4 5 int list 1 2 nil 3 4 nil More recursive fun But why always name functions fun map f l if null l then nil else f hd l map f tl l val map fn a b a list b list map fn x x 5 10 11 12 val it 15 16 17 int list This is called a lambda expression it s simply an unnamed function Recursion with Lambda Expressions Q How do you call something recursively if it doesn t have a name A Give it one map add5 10 11 12 val it 15 16 17 int list val add5 fn x x 5 val add5 fn int int add5 10 val it 15 int let val rec f fn x if null x then nil else hd x 1 f tl x in f end 1 2 3 val it 2 3 4 int list Pattern Matching Pattern Matching Call by need Functions are often defined over ranges More fancy binding Most imperative languages as well as ML use call by value or call by reference All arguments are evaluated before being passed copied to the callee fun …
View Full Document
Unlocking...