History of Programming Languages Functional ProgrammingCunning PlanSlide 3Slide 4Slide 5Slide 6Gone In Sixty SecondsPattern MatchingSlide 9Slide 10PolymorphismHigher-Order FunctionsThe House That Fold BuiltIt’s Lego TimeMap From FoldSlide 16Sorting ExamplesPartial Application and CurryingApplicabilitySlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Homework#1Functional ProgrammingFunctional ProgrammingIntroduction To CoolIntroduction To Cool#2Cunning Plan•ML Functional Programming– Fold– Sorting•Cool Overview– Syntax– Objects– Methods–Types#3CS 4501 – Compilers Practicum•Mondays 5:00 to 6:30, Olsson 011–Typically until 6:00•To be enrolled in CS 4501 (Compilers Practicum) you must be able to attend its listed lecture time.• First Meeting: Next Week!–Monday, January 30th#4PS1c Correct Answer Statistics•Language choice, as of noon today ...–Python 28 (+5 partially correct)–Ruby 22 (+2 partially correct) – C 8– OCaml 3– Cool 0•Students Submitting > 0 Times: 40• Students Taking Class For Credit: 46+• This assignment was originally named “PS0”.#5Undergraduate Research•Reminder: you can help Alex Landau, get +5 points of extra credit on PS1, be entered in a drawing for a $50 Amazon gift card, and advance human knowledge by completing – http://church.cs.virginia.edu/~zpf5a/code-quality/–by Midnight, Sunday January 29th •An undergraduate will be first author on this paper.#6This is my final day•... as your ... companion ... through Ocaml and Cool. After this we start the interpreter project.#7One-Slide Summary• Functions and type inference are polymorphic and operate on more than one type (e.g., List.length works on int lists and string lists).• fold is a powerful higher-order function (like a swiss-army knife or duct tape).• Cool is a Java-like language with classes, methods, private fields, and inheritance.#8Pattern Matching (Error?)•Simplifies Code (eliminates ifs, accessors)type btree = (* binary tree of strings *) | Node of btree * string * btree | Leaf of stringlet rec height tree = match tree with | Leaf _ -> 1 | Node(x,_,y) -> 1 + max (height x) (height y)let rec mem tree elt = match tree with | Leaf str | Node(_,str,_) -> str = elt | Node(x,_,y) -> mem x elt || mem y elt#9Pattern Matching (Error?)•Simplifies Code (eliminates ifs, accessors)type btree = (* binary tree of strings *) | Node of btree * string * btree | Leaf of stringlet rec height tree = match tree with | Leaf _ -> 1 | Node(x,_,y) -> 1 + max (height x) (height y)let rec mem tree elt = match tree with | Leaf str | Node(_,str,_) -> str = elt | Node(x,_,y) -> mem x elt || mem y eltbug?#10Pattern Matching (Error!)•Simplifies Code (eliminates ifs, accessors)type btree = (* binary tree of strings *) | Node of btree * string * btree | Leaf of stringlet rec bad tree elt = match tree with | Leaf str | Node(_,str,_) -> str = elt | Node(x,_,y) -> bad x elt || bad y eltlet rec mem tree elt = match tree with | Leaf str | Node(_,str,_) when str = elt -> true | Node(x,_,y) -> mem x elt || mem y elt#11Recall: Polymorphism•Functions and type inference are polymorphic–Operate on more than one type– let rec length x = match x with– | [] -> 0–| hd :: tl -> 1 + length tl –val length :  list -> int – length [1;2;3] = 3– length [“algol”; ”smalltalk”; ”ml”] = 3–length [1 ; “algol” ] = type error!means “any one type”#12Recall: Higher-Order Functions• Function are first-class values–Can be used whenever a value is expected–Notably, can be passed around–Closure captures the environment–let rec map f lst = match lst with–| [] -> []–| hd :: tl -> f hd :: map f tl–val map : ( -> ) ->  list ->  list –let offset = 10 in–let myfun x = x + offset in–val myfun : int -> int –map myfun [1;8;22] = [11;18;32]• Extremely powerful programming technique–General iterators–Implement abstractionf is itself a function!#13Recall: Fold•The fold operator comes from Recursion Theory (Kleene, 1952) –let rec fold f acc lst = match lst with–| [] -> acc– | hd :: tl -> fold f (f acc hd) tl –val fold : ( ->  -> ) ->  ->  list -> •Imagine we’re summing a list (f = addition):9 2 7 4 5 7 4 5… 11f4 518… 27acc lst#14Fold Is Powerful!Fold Is Powerful!•Let’s build things out of Fold!–length lst = fold (fun acc elt -> acc + 1) 0 lst– sum lst = fold (fun acc elt -> acc + elt) 0 lst– product lst=fold (fun acc elt -> acc * elt) 1 lst– and lst = fold (fun acc elt -> acc & elt) true lst#15Map From Fold•let map myfun lst = • fold (fun acc elt -> (myfun elt) :: acc) [] lst–Types: (myfun :  -> )–Types: (lst :  list)–Types: (acc :  list) –Types: (elt : )• How do we do sort? –(sort : ( ->  -> bool) ->  list ->  list)Do nothing which is of no use.- Miyamoto Musashi, 1584-1645#16Insertion Sort in OCamllet rec insert_sort cmp lst = match lst with | [] -> [] | hd :: tl -> insert cmp hd (insert_sort cmp tl)and insert cmp elt lst = match lst with | [] -> [elt] | hd :: tl when cmp hd elt -> hd :: (insert cmp elt tl) | _ -> elt :: lstWhat's the worstcase running time?#17Sorting Examples•langs = [ “fortran”; “algol”; “c” ]• courses = [ 216; 333; 415] • sort (fun a b -> a < b) langs–[ “algol”; “c”; “fortran” ] •sort (fun a b -> a > b) langs– [ “fortran”; “c”; “algol” ]• sort (fun a b -> strlen a < strlen b) langs–[ “c”; “algol”; “fortran” ]• sort (fun a b -> match is_odd a, is_odd b with | true, false -> true (* odd numbers first *) | false, true -> false (* even numbers last *) | _, _ -> a < b (* otherwise ascending *)) courses –[ 333 ; 415 ; 216 ]Java uses Inner Classes for this.#18Partial Application and Currying•let myadd x y = x + y•val myadd : int -> int -> int •myadd 3 5 = 8•let addtwo = myadd 2–How do we know what this means? We use referential transparency! Basically, just substitute it in. • val addtwo : int -> int •addtwo 77 = 79•Currying: “if you fix some arguments, you get a function of the remaining arguments”#20Modern Languages•This is the most widely-spoken first language in the European Union. It is the third-most taught foreign language in the English-speaking world, after French and Spanish. Its word