DOC PREVIEW
U of I CS 421 - Programming Languages and Compilers

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 421 - Programming Languages and Compilers

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Programming Languages and Compilers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Programming Languages and Compilers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Programming Languages and Compilers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?