Programming Languages and Compilers (CS 421)First Class TypesSlide 3Higher Order FunctionsSlide 5Slide 6Slide 7ThriceSlide 9Slide 10Reversing ArgumentsPartial ApplicationLambda LiftingSlide 14Lambda Lifting and “Unknown Types”Slide 16Slide 17Curried vs Uncurriedcurry and uncurrySlide 20Folding Functions over ListsFoldingSlide 23Slide 24Encoding Recursion with FoldCombining Lists of FunctionsRepeating n TimesMappingRecall MapSlide 30Map from FoldRelated Fuction: ZipZipwithZip from ZipwithSlide 35ProblemsProblem 1Problem 2Problem 3Problem 4Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter First Class Types•A type is first class if it can be–Passed as an argument–Assigned as a value–Returned as a result•Examples:–C: scalars, pointers, structures–C++: same as C, plus classes–Scheme, LISP: scalars, lists (s-expressions), functions–ML: same as Scheme, plus user defined data typesElsa L. Gunter First Class Types•The kind of data that can be manipulated well in a language largely determines for which applications the language is well suited•The ability to treat functions as data is one of the strengths of applicative programming languagesElsa L. Gunter Higher Order Functions•A function is higher-order if it takes a function as an argument or returns one as a result•Example:# let compose f g = fun x -> f (g x);;val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>•The type ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b is a higher order type because of ('a -> 'b) and ('c -> 'a) and -> 'c -> 'bElsa L. Gunter Higher Order Functions•What are the types of the following functions:# plus_two;;- : int -> int = <fun># compose plus_two plus_two;; ?# compose plus_two;; ?Elsa L. Gunter Higher Order Functions•What are the types of the following functions:# plus_two;;- : int -> int = <fun># compose plus_two plus_two;;- : int -> int = <fun># compose plus_two;;- : ('_a -> int) -> '_a -> int = <fun>Elsa L. Gunter Higher Order Functions•What do the following functions do? # plus_two;;- : int -> int = <fun># compose plus_two plus_two;;- : int -> int = <fun># compose plus_two;;-: ('_a -> int) -> '_a -> int = <fun>Elsa L. Gunter Thrice•Recall:# let thrice f x = f (f (f x));;val thrice : ('a -> 'a) -> 'a -> 'a = <fun>Elsa L. Gunter Thrice•Recall:# let thrice f x = f (f (f x));;val thrice : ('a -> 'a) -> 'a -> 'a = <fun>•How do you write thrice with compose?Elsa L. Gunter Thrice•Recall:# let thrice f x = f (f (f x));;val thrice : ('a -> 'a) -> 'a -> 'a = <fun>•How do you write thrice with compose?# let thrice f = compose f (compose f f);;val thrice : ('a -> 'a) -> 'a -> 'a = <fun>•Is this the only way?Elsa L. Gunter Reversing Arguments# let flip f a b = f b a;;val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun># map ((-) 1) [5;6;7];;- : int list = [-4; -5; -6]# map (flip (-) 1) [5;6;7];;- : int list = [4; 5; 6]# let (-) = flip (-);;val ( - ) : int -> int -> int = <fun># 2 - 5;;- : int = 3Elsa L. Gunter Partial Application# (+);;- : int -> int -> int = <fun># (+) 2 3;;- : int = 5# let plus_two = (+) 2;;val plus_two : int -> int = <fun># plus_two 7;;- : int = 9•Patial application also called sectioningElsa L. Gunter Lambda Lifting•You must remember the rules for evaluation when you use partial application# let add_two = (+) (print_string "test\n"; 2);;testval add_two : int -> int = <fun># let add2 = (* lambda lifted *) fun x -> (+) (print_string "test\n"; 2) x;;val add2 : int -> int = <fun>Elsa L. Gunter Lambda Lifting# thrice add_two 5;;- : int = 11# thrice add2 5;;testtesttest- : int = 11•Lambda lifting delayed the evaluation of the argument to (+) until the second argument was suppliedElsa L. Gunter Lambda Lifting and “Unknown Types”•Recall compose plus_two: # let f1 = compose plus_two;;val f1 : ('_a -> int) -> '_a -> int = <fun>•Compare to lambda lifted version:# let f2 = fun g -> compose plus_two g;;val f2 : ('a -> int) -> 'a -> int = <fun>•What is the difference?Elsa L. Gunter Lambda Lifting and “Unknown Types”•‘_a can only be instantiated once for an expression# f1 plus_two;;- : int -> int = <fun># f1 List.length;;Characters 3-14: f1 List.length;; ^^^^^^^^^^^This expression has type 'a list -> int but is here used with type int -> intElsa L. Gunter Lambda Lifting and “Unknown Types”•‘a can be repeatedly instantiated# f2 plus_two;;- : int -> int = <fun># f2 List.length;;- : '_a list -> int = <fun>Elsa L. Gunter Curried vs Uncurriedval add_three : int -> int -> int -> int = <fun>How does it differ from# let add_triple (u,v,w) = u + v + w;;val add_triple : int * int * int -> int = <fun>add_three is curried;add_triple is uncurriedElsa L. Gunter curry and uncurry# let curry f x y = f (x,y);;val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun># let uncurry f (x,y) = f x y;;val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>•Remember these!Elsa L. Gunter curry and uncurry# (+);;- : int -> int -> int = <fun># let plus = uncurry (+);;val plus : int * int -> int = <fun># plus (3,4);;- : int = 7# curry plus 3 4;;- : int = 7Elsa L. Gunter Folding Functions over ListsHow are the following functions similar?# let rec sumlist list = match list with [ ] -> 0 | x::xs -> x + sumlist xs;;val sumlist : int list -> int = <fun># sumlist [2;3;4];;- : int = 9# let rec prodlist list = match list with [ ] -> 1 | x::xs -> x * prodlist xs;; val prodlist : int list -> int = <fun># prodlist [2;3;4];;- : int = 24Elsa L. Gunter Folding# let rec fold_left f a list = match list with [] -> a | (x :: xs) -> fold_left f (f a x) xs;;val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>fold_left f a [x1; x2;…;xn] = f(…(f (f a x1) x2)…)xn# let rec fold_right f list b = match list with [ ] -> b | (x :: xs) -> f x (fold_right f xs b);;val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>fold_right f [x1; x2;…;xn] b = f x1(f x2 (…(f xn b)…))Elsa L. Gunter Folding# let sumlist list = fold_right (+) list 0;;val sumlist : int list -> int = <fun># sumlist [2;3;4];;- : int = 9# let prodlist list = fold_right ( * ) list 1;;val prodlist : int list -> int = <fun># prodlist [2;3;4];;- : int = 24Elsa L. Gunter Folding•Can replace recursion by fold_right in any primitive recursive definition–Primitive recursive means
View Full Document
Unlocking...