Programming Languages and Compilers (CS 421)RecordsRecord TypesRecord ValuesSlide 5Record Pattern MatchingRecord Field AccessNew Records from OldSlide 9Variants - Syntax (slightly simplified)Enumeration Types as VariantsSlide 12Functions over EnumerationsSlide 14Slide 15Disjoint Union TypesSlide 17Polymorphism in VariantsFunctions over optionMapping over VariantsFolding over VariantsRecursive TypesRecursive Data TypesRecursive Data Type ValuesSlide 25Recursive FunctionsMapping over Recursive TypesSlide 28Folding over Recursive TypesSlide 30Mutually Recursive TypesMutually Recursive Types - ValuesSlide 33Slide 34Slide 35Mutually Recursive FunctionsSlide 37Nested Recursive TypesNested Recursive Tyep ValuesSlide 40Slide 41Nested Recursive Type ValuesSlide 43Slide 44Infinite Recursive ValuesSlide 46Slide 47Slide 48PowerPoint PresentationProgramming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter Records•Records serve the same programming purpose as tuples•Provide better documentation, more readable code•Allow components to be accessed by label instead of position–Labels (aka field names must be unique)–Fields accessed by suffix dot notationElsa L. Gunter Record Types•Record types must be declared before they 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, or fieldsElsa L. Gunter Record Values•Records built with labels; order does not matter# 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. Gunter Record 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. Gunter Record Pattern Matching# let {name = elsa; age = age; ss = (_,_,s3)} = teacher;;val elsa : string = "Elsa L. Gunter"val age : int = 102val s3 : int = 6244Elsa L. Gunter Record Field Access# let soc_sec = teacher.ss;; val soc_sec : int * int * int = (119, 73, 6244)Elsa L. Gunter New 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. Gunter New 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. Gunter Variants - 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 optional type agrument is omitted, it is called a constant•Constructors are the basis of almost all pattern matchingElsa L. Gunter Enumeration Types as VariantsAn enumeration type is a collection of distinct valuesIn C and Caml they have an order structure; order by order of inputElsa L. Gunter Enumeration Types as Variants# type weekday = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday;;type weekday = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | SundayElsa L. Gunter Functions 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. Gunter Functions 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. Gunter Functions over Enumerations# days_later 2 Tuesday;;- : weekday = Thursday# days_later (-1) Wednesday;;- : weekday = Tuesday# days_later (-4) Monday;;- : weekday = ThursdayElsa L. Gunter Disjoint Union Types•Disjoint union of types, with some possibly occurring more than once•We can also add in some new singleton elementsty ty’ tyElsa L. Gunter Disjoint Union Types# type id = DriversLicense of int | SocialSecurity of int | Name of string;;type id = DriversLicense of int | SocialSecurity of 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. Gunter Polymorphism in Variants•The type 'a option is gives us something to 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 an exceptionElsa L. Gunter Functions 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. Gunter Mapping over Variants# let optionMap f opt = match opt with None -> None | Some x -> Some (f x);;val optionMap : ('a -> 'b) -> 'a option -> 'b option = <fun># optionMap (fun x -> x - 3) (first (fun x -> x > 3) [1;3;4;2;5]);;- : int option = Some 1Elsa L. Gunter Folding 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)) None opt;;val optionMap : ('a -> 'b) -> 'a option -> 'b option = <fun>Elsa L. Gunter Recursive Types•The type being defined may be a component of itselftyty’tyElsa L. Gunter Recursive 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. Gunter Recursive 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
View Full Document
Unlocking...