Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterFirst 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 datatypesElsa L. GunterFirst Class Types• The kind of data that can bemanipulated well in a languagelargely determines for whichapplications the language is wellsuited• The ability to treat functions as datais one of the strengths ofapplicative programming languagesElsa L. GunterHigher Order Functions• A function is higher-order if it takes afunction as an argument or returns oneas 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 -> 'bis a higher order type because of('a -> 'b) and ('c -> 'a) and -> 'c -> 'bElsa L. GunterHigher Order Functions• What are the types of the followingfunctions:# plus_two;;- : int -> int = <fun># compose plus_two plus_two;; ?# compose plus_two;; ?Elsa L. GunterHigher Order Functions• What are the types of the followingfunctions:# plus_two;;- : int -> int = <fun># compose plus_two plus_two;;- : int -> int = <fun># compose plus_two;;- : ('_a -> int) -> '_a -> int = <fun>Elsa L. GunterHigher 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. GunterThrice• Recall:# let thrice f x = f (f (f x));;val thrice : ('a -> 'a) -> 'a -> 'a = <fun>Elsa L. GunterThrice• 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. GunterThrice• 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. GunterReversing 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. GunterPartial 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. GunterLambda Lifting• You must remember the rules forevaluation when you use partialapplication# 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. GunterLambda Lifting# thrice add_two 5;;- : int = 11# thrice add2 5;;testtesttest- : int = 11• Lambda lifting delayed the evaluation of theargument to (+) until the second argumentwas suppliedElsa L. GunterLambda Lifting and “UnknownTypes”• 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. GunterLambda Lifting and “UnknownTypes”• ‘_a can only be instantiated once for anexpression# f1 plus_two;;- : int -> int = <fun># f1 List.length;;Characters 3-14: f1 List.length;; ^^^^^^^^^^^This expression has type 'a list -> int but is hereused with type int -> intElsa L. GunterLambda Lifting and “UnknownTypes”• ‘a can be repeatedly instantiated# f2 plus_two;;- : int -> int = <fun># f2 List.length;;- : '_a list -> int = <fun>Elsa L. GunterCurried 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. Guntercurry 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. Guntercurry 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. GunterFolding 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. GunterFolding# 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. GunterFolding# 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. GunterFolding• Can replace recursion by fold_right inany primitive recursive definition– Primitive recursive means it only recurseson immediate subcomponents of recursivedata structure• Can replace recursion by fold_left in anytail recursive definitionElsa L. GunterEncoding Recursion with Fold# let rec append list1 list2 = match list1 with [ ] -> list2 | x::xs -> x :: append xs list2;;val append : 'a list -> 'a list -> 'a list = <fun> Base Case Operation Recusive Call# let append list1 list2 = fold_right (fun x y -> x :: y) list1 list2;;val append : 'a list -> 'a list -> 'a list = <fun># append [1;2;3] [4;5;6];;- : int list = [1; 2; 3; 4; 5; 6]Elsa L. GunterCombining Lists of
View Full Document