Functional ProgrammingCOMS W4115Prof. Stephen A. EdwardsFall 2003Columbia UniversityDepartment of Computer ScienceOriginal version by Prof. Simon ParsonsFunctional vs. ImperativeImperative programming concerned with “how.”Functional programming concerned with “what.”Based on the mathematics of the lambda calculus(Church as opposed to Turing).“Programming without variables”It is inherently concise, elegant, and difficult to createsubtle bugs in.It’s a cult: once you catch the functional bug, you neverescape.Referential transparencyThe main (good) property of functional programming isreferential transparency.Every expression denotes a single value.The value cannot be changed by evaluating an expressionor 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 opaquelanguages.The Joy of Pascalprogram example(output)var flag: boolean;function f(n:int): intbeginif flag then f := nelse f := 2*n;flag := not flagendbeginflag := true;writeln(f(1) + f(2));writeln(f(2) + f(1));endWhat does this print?Strange behaviorThis prints 5 then 4.Odd since you expectf(1) + f(2) = f(2) + f(1)Mathematical functions only depend on their inputsThey have no memoryVariablesAt the heart of the “problem” is fact that the global dataflag affects the value of f.In particularflag := not flaggives the offending behaviorEliminating assignments eliminates such problems.In functional languages, variables not names for storage.Instead, they’re names that refer to particular values.Think of them as not very variables.Simple functional programming inMLA function that squares numbers:% smlStandard ML of New Jersey, Version 110.0.7-fun square x = x * x;val square = fn : int -> int-square 5;val it = 25 : int-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 -> intThis is a function that takes an integer and returns afunction that takes a function and returns an integer.CurryingFunctions are first-class objects that can be manipulatedwith 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 argumentsYou can also pass and return tuples to/from functions:-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-PolymorphismReverse has an interesting type:-fun reverse(a,b) = (b,a);val reverse = fn : ’a * ’b -> ’b * ’aThis means it can reverse a two-tuple of any type and anyother type:-reverse (10,5.2);val it = (5.2,10) : real * int-reverse ("foo", 3.14159);val it = (3.14159,"foo") : real * stringRecursionML doesn’t have variables in the traditional sense, so youcan’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 : intPower operatorYou can also define functions as infix operators:-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-Using the same thing twiceWithout variables, duplication may appear necessary:fun f x =g(square(max(x,4))) +(if x <= 1 then 1else g(square(max(x,4))));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))));The let expressionThe easiest way is to introduce a local name for the thingwe need multiple times:fun f x =letval gg = g(square(max(x,4)))ingg + (if x <=1 then 1 else gg)end;let is not assignment- let val a = 5 in= (let= val a = a + 2= in= a= end,= a)= end;val it = (7,5) : int * intData TypesPrograms aren’t very useful if they only manipulatescalars.Functional languages are particularly good atmanipulating more complex data types.You’ve already seen tuples, which is a fixed-length list ofspecific types of things.ML also has lists, arbitrary-length vectors of things of thesame type.ListsTuples have parenthesis, lists have brackets:-(5,3);val it = (5,3) : int * int-[5,3];val it = [5,3] : int listConcatenate lists with @:-[1,2] @ [3,4,5];val it = [1,2,3,4,5] : int listConsAdd things to the front with :: (pronnounced “cons”)-[1,2,3];val it = [1,2,3] : int list-5 :: it;val it = [5,1,2,3] : int listConcatenating is not the same as consing:-[1,2] :: [3,4];stdIn: Error: operator and operand don’t agree [literal]operator domain: int list * int list listoperand: int list * int listin expression:(1 :: 2 :: nil) :: 3 :: 4 :: nilOther list functions- null [1,2];val it = false : bool-null nil;val it = true : bool-null [];val it = true : bool-val a = [1,2,3,4];val a = [1,2,3,4] : int list-hd a;val it = 1 : int-tl a;val it = [2,3,4] : int listFun with recursion- fun addto (l,v) == if null l then nil= else hd l + v :: addto(tl l, v);val addto = fn : int list * int -> int list-addto([1,2,3],2);val it = [3,4,5] : int listMore recursive fun- 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- fun add5 x = x + 5;val add5 = fn : int -> int- map(add5, [10,11,12]);val it = [15,16,17] : int listBut why always name functions?- map( fn x => x + 5, [10,11,12]);val it = [15,16,17] : int listThis is called a lambda expression: it’s simply anunnamed function.The fun operator is similar to a lambda expression:-val add5 = fn x => x + 5;val add5 = fn : int -> int-add5 10;val it = 15 : intRecursion with LambdaExpressionsQ: How do you call something recursively if it doesn’t havea name?A: Give it one.-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 listPattern MatchingFunctions are often defined over rangesf(x) =x if x ≥ 0−x otherwise.Functions in ML are no different. How to cleverly avoidwriting if-then:fun map (f,[]) = []| map (f,l) = f (hd l) :: map(f,tl l);Pattern matching is order-sensitive. This gives an error.fun map (f,l) = f (hd l) :: map(f,tl l)| map (f,[]) = [];Pattern MatchingMore fancy bindingfun map (_,[]) = []| map (f,h :: t) = f h :: map(f,t);“_” matches anythingh :: t matchs a
View Full Document
Unlocking...