Hide Notes 

Slide 1: CS 2104 : Prog. Lang. Concepts. Functional Programming I Lecturer : Dr. Abhik Roychoudhury School of Computing From Dr. Khoo Siau Cheng’s lecture notes
Slide 2: Outline • • • • • What is Functional Programming? Basic Expressions Using Higher-order Functions List Processing Value and Type Constructions
Slide 3: Features of Functional Programming • • • • Expressions: The main construct in the language Functions : First-class citizens of the language Types : for specification and verification List Processing
Slide 4: Computation • Achieved via function application • Functions are mathematical functions without sideeffects. – Output is solely dependent of input. States Pure function Impure function with assignment
Slide 5: Outline • • • • • What is Functional Programming? Basic Expressions Using Higher-order Functions List Processing Value and Type Constructions
Slide 6: Basic SML Expressions <Exp> ::= <Constants> | <Identifiers> | <Exp1> <op> <Exp2> | | if <Exp0> then <Exp1> else <Exp2> | let {<Decl>} in <Exp> end | fn <Pattern> {<Pattern>} => <Exp> | <Exp1> <Exp2> | (<Exp1>, <Exp2> {, <Exp3>}) | <List-Exp> <Constants> ::= all constants <Identifiers> ::= all identifiers <op> ::= all binary operators
Slide 7: If-expression, Not If-statement if <e0> then <e1> else <e2> if (3 > 0) then 4+x else x-4 ; 4+x If-expression evaluates to a value.
Slide 8: Constructing a Linear List <List-Exp> ::=[[<Exp> {, <Exp>}] ] | nil | <Exp> :: <Exp> nil ; Note : A list must end with nil. 1::nil ; 1::(2::nil); (x+2)::(y-3)::(x*3)::nil ;
Slide 9: Constructing a Linear List <List-Exp> ::=[[<Exp> {, <Exp>}] ] | nil | <Exp> :: <Exp> nil ; Operator :: is right associative. 1::nil ; 1::(2::nil); (x+2)::(y-3)::(x*3)::nil ; head tail [] ; [1] ; [1,2]; [x+2,y-3,x*3] ;
Slide 10: Constructing a Tuple (<Exp> , <Exp> {, <Exp>}) Tuple is like a record without field names. (1,2) ; (1,2,True,4,False) ; (x+2,y=3,x*3) ;
Slide 11: Giving An Expression A Name Declaring an expression with a name enables easy reference. <decl> ::= val <pattern> = <exp> Identifiers are legally declared after proper pattern matching. val val val val x=3 (y,z) [a,b] [a,b] ; = (x+3,x-3) ; = [x+2,y-3] ; = [x+2] ; val (x::xs) = [1,2,3,4,5] ;
Slide 12: Pattern-Match a List val (x::xs) = [1,2,3,4,5] ; x 1 xs  [2,3,4,5] ; val (x::_::y::xs) = [1,2,3,4,5] ; x 1 y 3 xs  [4,5] ;
Slide 13: Local Declaration/Definition let {<decl>} in <exp> end let in end ; val x = (3,4) val (a,b) = x a+a*b 15 Identifiers are statically scoped
Slide 14: Nested bindings of same var. • Let val x =2 in let val x = x +1 in x*x end end • Let val x = 2 in let val y = x +1 in y * y end end • Let val x = 2 in (x+1)*(x+1) end •9
Slide 15: Function Declaration and Function Application <Decl> ::= fun <var> <para> = <exp> <para> ::= <pattern> {<pattern>} fun fac x = if (x > 0) then x * (fac (x-1)) else 1 fac 2 ⇒ if (2 > 0) then 2 * (fac (2-1)) else 1 ⇒ 2 * (fac 1) ⇒ 2 * (if (1 > 0) then 1 * (fac (1-1)) else 1) ⇒ 2 * (1 * (fac 0)) ⇒ 2 * (1 * 1) ⇒2
Slide 16: Function as Equations A function can be defined by a set of equations. <Decl> ::= fun <var> <para> = <exp> {| <var> <para> = <exp>} fun fac 0 | fac n =1 = n * (fac (n-1)) ⇒ 2 * (fac 1) ⇒ 2 * (1 * (fac 0)) ⇒2 Function application is accomplished via pattern matching. fac 2 ⇒ 2 * (fac (2-1)) ⇒ 2 * (1 * (fac (1-1))) ⇒ 2 * (1 * 1)
Slide 17: Outline • • • • • What is Functional Programming? Basic Expressions Using Higher-order Functions List Processing Value and Type Constructions
Slide 18: Functions as First-Class Citizens Lambda abstraction: A nameless function fn <para> => <Exp> (fn (x,y) => x + y) (2,3)  2+3  5 Definition Application val newfn = fn (x,y) => x + y ; newfn(2,4) + newfn(4,3)
Slide 19: Functions as First-Class Citizens Passing function as argument fun apply (f, x) = f x apply (fac, 3)   fac 3 6 apply (fn x => x*2, 3)  (fn x => x*2) 3  3*2 6
Slide 20: Functions as First-Class Citizens Returning function as result fun choose (x,f,g) = if x then f else g ; choose(a = b,fn x => x*2, fac)(4) returns either 8 or 24 fun compose (f,g) = fn x => f (g x) (compose (add3,fac)) 4  (fn x => add3 (fac x))(4)  (add3 (fac 4)) compose (f,g) is denoted as f o g  27
Slide 21: Functions as First-Class Citizens Storing function in data structure val flist = [ fac, fib, add3] ; let val [f1,f2,f3] = flist in (f1 2) + (f2 3) + (f3 4) end ;
Slide 22: Functions as Algorithms • A function describes a way for computation. • Self-Recursive function fun factorial (x) = if (x <= 1) then 1 else x * factorial (x-1) ; • Mutual-Recursive functions fun | | and even(0) = true even(1) = false even(x) = odd(x-1) odd(x) = even(x-1) ;
Slide 23: Passing Arguments to a Function How many argument does this function really take? fun f (x,y) = x + 2 * y ; a pair Calling f with argument (1,2) yields 5. fun g x y = x + 2 * y ; pattern 1 pattern 2 Calling g with arguments 1 and 2 yields 5.
Slide 24: Outline • • • • • What is Functional Programming? Basic Expressions Using Higher-order Functions List Processing Value and Type Constructions
Slide 25: Exploring a List fun length [] =0 | length (x::xs) = 1 + length(xs) ; length([10,10,10]) ==> ==> ==> ==> ==> 1 1 1 1 3 + + + + length([10,10]) 1 + length([10]) 1 + 1 + length([]) 1+1+0 Note how a list is being consumed from head to tail.
Slide 26: fun append([],ys) = ys | append(x::xs,ys) = x :: append(xs,ys); append([1,2],[3]) ==> 1::append([2],[3]) ==> 1::2::append([],[3]) ==> 1::2::[3] ==> [1,2,3] Note how a new list is being produced from head to tail. append(x,y) is denoted by x @ y.
Slide 27: fun rev(xs) = let fun r([],ys) = ys | r(x::xs,ys)= r(xs,x::ys) in r(xs,[])end rev([1,2,3]) ==> r([1,2,3],[]) ==> r([2,3],1::[]) ==> r([3],2::1::[]) ==> r([],3::2::1::[]) ==> [3,2,1] Note how lists are being produced and consumed concurrently.
Slide 28: Map operation map square [1,2,3,4] ==> [square 1, square 2,.., square 4] ==> [1,4,9,16] fun map f [] = [] | map f (x::xs) = (f x) :: (map f xs) map square [1,2] ==> (square 1) :: (map square [2]) ==> 1 :: (square 2) :: (map square []) ==> 1 :: 4 :: [] == [1,4]
Slide 29: Map operation fun map f [] = [] | map f (x::xs) = (f x) :: (map f xs) Law for Map : map f (map g list) = map (f o g) list map f (map g [a1,..,an]) = map f [g a1,..,g an] = [f (g a1),.., f (g an)] = [(f o g) a1,.., (f o g) an] = map (f o g) [a1,..an]
Slide 30: Reduce Operation reduce  [a1,..,an] a0 = a1  (a2  (..  (an  a0))) reduce f [a1,..,an] a0 = f(a1,f(a2,f(..,f(an,a0))))  : a1 a2 : : : an [] an a1 a2    a0
Slide 31: reduce (op *) [2,4,6] 1 ==> 2 * (4 * (6 * 1)) ==> 48 reduce (fn (x,y)=>1+y) [2,4,6] 0 ==> 1 + (1 + (1 + 0)) ==> 3 : 2 4 6 : : [] 1 1 1 + + + 0
Slide 32: Outline • • • • • What is Functional Programming? Basic Expressions Using Higher-order Functions List Processing Value and Type Constructions
Slide 33: Basic Types Type bool int real string Types: Classification of Values and Their Operators Values Operations true,false =, <>, … …,~1,0,1,2,… =,<>,<,+,div,… ..,0.0,.,3.14,.. =,<>,<,+,/,… “foo”,”\”q\””,…=,<>,… Boolean Operations: e1 andalso e2 e1 orelse e2
Slide 34: Types in ML • Every expression used in a program must be welltyped. – It is typable by the ML Type system. • Declaring a type : 3 : int [1,2] : int list • Usually, there is no need to declare the type in your program – ML infers it for you.
Slide 35: Structured Types Structured Types consist of structured values. • Structured values are built up through expressions. Eg : (2+3, square 3) • Structured types are denoted by type expressions. <type-expr> ::= <type-name> | <type-constant> | <type-expr> * <type-expr> | <type-expr> <type-expr> | <type-expr> list |…
Slide 36: Type of a Tuple (1,2) : int * int (3.14159, x+3,true) : real * int * bool A * B = set of ordered pairs (a,b) Data Type Constructor : Constructor : (,) * as in (a,b) as in A * B In general, (a1,a2,…,an) belongs to A1*A2*…*An.
Slide 37: Type of A List Type Constructor : list [1,2,3] : int list [3.14, 2.414] : real list [1, true, 3.14] : ?? Not well-typed!! A list = set of all lists of A -typed values. A in A-list refers to any types: (int*int) list : [ ], [(1,3)], [(3,3),(2,1)], … int list list : [ ], [[1,2]], [[1],[0,1,2],[2,3],…
Slide 38: Function Types Declaring domain & co-domain fac : int -> int A -> B = set of all functions from A to B. Type Constructor : Data Construction via : 1. Function declaration : 2. Lambda abstraction : -> fun f x = x + 1 ; fn x => x + 1; Value Selection via function application: f3  4 (fn x => x + 1) 3  4
Slide 39: Sum of Types Enumerated Types datatype Days New Type = Mo | Tu | We | Th | Fr | Sa | Su ; data / data constructors Selecting a summand via pattern matching: case d of Sa => “Go to cinema” | Su => “Extra Curriculum” | _ => “Life goes on”
Slide 40: Combining Sum and Product of Types: Algebraic Data Types Defining an integer binary tree: datatype IntTree = Leaf int | Node of (IntTree, int, IntTree) ; fun height (Leaf x) =0 | height (Node(t1,n,t2))= 1 + max(height(t1),height(t2)) ;
Slide 41: Conclusion • A functional program consists of an expression, not a sequence of statements. • Higher-order functions are first-class citizen in the language. – It can be nameless • List processing is convenient and expressive • In ML, every expression must be well-typed. • Algebraic data types empowers the language.