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

This preview shows page 1-2-3-23-24-25-26-46-47-48 out of 48 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 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 48 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 48 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 48 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 48 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 48 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 48 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 48 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 48 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 48 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 48 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. GunterRecords• Records serve the same programmingpurpose as tuples• Provide better documentation, morereadable code• Allow components to be accessed bylabel instead of position– Labels (aka field names must be unique)– Fields accessed by suffix dot notationElsa L. GunterRecord Types• Record types must be declared beforethey can be used# type person = {name : string; ss : (int *int * int); age : int};;type person = { name : string; ss : int * int* int; age : int; }• person is the type being introduced• name, ss and age are the labels, orfieldsElsa L. GunterRecord Values• Records built with labels; order does notmatter# let teacher = {name = "Elsa L. Gunter";age = 102; ss = (119,73,6244)};;val teacher : person = {name = "Elsa L. Gunter"; ss = (119, 73,6244); age = 102}Elsa L. GunterRecord Values# let student = {ss=(325,40,1276);name="Joseph Martins"; age=22};;val student : person = {name = "Joseph Martins"; ss = (325, 40,1276); age = 22}# student = teacher;;- : bool = falseElsa L. GunterRecord Pattern Matching# let {name = elsa; age = age; ss =(_,_,s3)} = teacher;;val elsa : string = "Elsa L. Gunter"val age : int = 102val s3 : int = 6244Elsa L. GunterRecord Field Access# let soc_sec = teacher.ss;;val soc_sec : int * int * int = (119,73, 6244)Elsa L. GunterNew Records from Old# let birthday person = {person with age =person.age + 1};;val birthday : person -> person = <fun># birthday teacher;;- : person = {name = "Elsa L. Gunter"; ss= (119, 73, 6244); age = 103}Elsa L. GunterNew Records from Old# let new_id name soc_sec person = {person with name = name; ss =soc_sec};;val new_id : string -> int * int * int ->person -> person = <fun># new_id "Guieseppe Martin"(523,04,6712) student;;- : person = {name = "Guieseppe Martin";ss = (523, 4, 6712); age = 22}Elsa L. GunterVariants - Syntax(slightly simplified)• type name = C1 [of ty1] | . . . | Cn [of tyn]• Introduce a type called name• (fun x -> Ci x) : ty1 -> name• Ci is called a constructor; if the optionaltype agrument is omitted, it is called aconstant• Constructors are the basis of almost allpattern matchingElsa L. GunterEnumeration Types asVariantsAn enumeration type is a collection ofdistinct valuesIn C and Caml they have an orderstructure; order by order of inputElsa L. GunterEnumeration Types asVariants# type weekday = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday;;type weekday = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | SundayElsa L. GunterFunctions over Enumerations# let day_after day = match day with Monday -> Tuesday | Tuesday -> Wednesday | Wednesday -> Thursday | Thursday -> Friday | Friday -> Saturday | Saturday -> Sunday | Sunday -> Monday;; val day_after : weekday -> weekday = <fun>Elsa L. GunterFunctions over Enumerations# let rec days_later n day = match n with 0 -> day | _ -> if n > 0 then day_after (days_later (n - 1) day) else days_later (n + 7) day;;val days_later : int -> weekday -> weekday =<fun>Elsa L. GunterFunctions over Enumerations# days_later 2 Tuesday;;- : weekday = Thursday# days_later (-1) Wednesday;;- : weekday = Tuesday# days_later (-4) Monday;;- : weekday = ThursdayElsa L. GunterDisjoint Union Types• Disjoint union of types, with somepossibly occurring more than once• We can also add in some new singletonelementsty ty’ tyElsa L. GunterDisjoint Union Types# type id = DriversLicense of int| SocialSecurity of int | Name of string;;type id = DriversLicense of int | SocialSecurityof int | Name of string# let check_id id = match id with DriversLicense num -> not (List.mem num [13570; 99999]) | SocialSecurity num -> num < 900000000 | Name str -> not (str = "John Doe");; val check_id : id -> bool = <fun>Elsa L. GunterPolymorphism in Variants• The type 'a option is gives us somethingto represent non-existence or failure# type 'a option = Some of 'a | None;;type 'a option = Some of 'a | None• Used to encode partial functions• Often can replace the raising of anexceptionElsa L. GunterFunctions over option# let rec first p list = match list with [ ] -> None | (x::xs) -> if p x then Some x else first p xs;;val first : ('a -> bool) -> 'a list -> 'a option = <fun># first (fun x -> x > 3) [1;3;4;2;5];;- : int option = Some 4# first (fun x -> x > 5) [1;3;4;2;5];;- : int option = NoneElsa L. GunterMapping over Variants# let optionMap f opt = match opt with None -> None | Some x -> Some (f x);;val optionMap : ('a -> 'b) -> 'a option -> 'boption = <fun># optionMap (fun x -> x - 3) (first (fun x -> x > 3) [1;3;4;2;5]);;- : int option = Some 1Elsa L. GunterFolding over Variants# let optionFold someFun noneVal opt = match opt with None -> noneVal | Some x -> someFun x;;val optionFold : ('a -> 'b) -> 'b -> 'a option-> 'b = <fun># let optionMap f opt = optionFold (fun x -> Some (f x)) Noneopt;;val optionMap : ('a -> 'b) -> 'a option -> 'boption = <fun>Elsa L. GunterRecursive Types• The type being defined may be acomponent of itselftyty’tyElsa L. GunterRecursive Data Types# type int_Bin_Tree = Leaf of int | Node of (int_Bin_Tree *int_Bin_Tree);;type int_Bin_Tree = Leaf of int | Node of(int_Bin_Tree * int_Bin_Tree)Elsa L. GunterRecursive Data Type Values# let bin_tree = Node(Node(Leaf 3, Leaf 6),Leaf (-7));;val bin_tree : int_Bin_Tree = Node (Node(Leaf 3, Leaf 6), Leaf (-7))Elsa L. GunterRecursive Data Type Values bin_tree = Node Node Leaf (-7)Leaf 3 Leaf 6Elsa L. GunterRecursive Functions# let rec first_leaf_value tree = match tree with (Leaf n) -> n | Node (left_tree, right_tree) -> first_leaf_value left_tree;;val first_leaf_value : int_Bin_Tree -> int =<fun># let left = first_leaf_value bin_tree;;val left : int = 3Elsa L. GunterMapping over RecursiveTypes# let rec ibtreeMap f tree = match tree with (Leaf n) -> Leaf (f n) | Node (left_tree, right_tree) -> Node (ibtreeMap f left_tree, ibtreeMap f right_tree);;val ibtreeMap : (int -> int) -> int_Bin_Tree-> int_Bin_Tree = <fun>Elsa L. GunterMapping over RecursiveTypes# ibtreeMap ((+) 2) bin_tree;;- : int_Bin_Tree = Node (Node (Leaf 5,Leaf 8), Leaf (-5))Elsa L. GunterFolding over Recursive Types# let rec ibtreeFoldRight leafFun nodeFun tree = match tree with Leaf n -> leafFun n | Node (left_tree, right_tree) -> nodeFun


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?