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