U of I CS 421 - Programming Languages and Compilers (48 pages)

Previewing pages 1, 2, 3, 23, 24, 25, 26, 46, 47, 48 of 48 page document View the full content.
View Full Document

Programming Languages and Compilers



Previewing pages 1, 2, 3, 23, 24, 25, 26, 46, 47, 48 of actual document.

View the full content.
View Full Document
View Full Document

Programming Languages and Compilers

65 views


Pages:
48
School:
University of Illinois
Course:
Cs 421 - Natural Language Processing
Natural Language Processing Documents
Unformatted text preview:

Programming Languages and Compilers CS 421 Elsa L Gunter 2112 SC UIUC http www cs uiuc edu class sp07 cs421 Based in part on slides by Mattox Beckman as updated by Vikram Adve and Gul Agha 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 notation Elsa 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 fields Elsa 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 false Elsa L Gunter Record Pattern Matching let name elsa age age ss s3 teacher val elsa string Elsa L Gunter val age int 102 val s3 int 6244 Elsa 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 matching Elsa L Gunter Enumeration Types as Variants An enumeration type is a collection of distinct values In C and Caml they have an order structure order by order of input Elsa L Gunter Enumeration Types as Variants type weekday Monday Tuesday Wednesday Thursday Friday Saturday Sunday type weekday Monday Tuesday Wednesday Thursday Friday Saturday Sunday Elsa 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 Thursday Elsa L Gunter Disjoint Union Types Disjoint union of types with some possibly occurring more than once ty ty ty We can also add in some new singleton elements Elsa 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 exception Elsa 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 None Elsa 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 1 Elsa 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 itself ty Elsa L Gunter ty ty 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 7 Elsa L Gunter Recursive Data Type Values bin tree Node Node Leaf 3 Elsa L Gunter Leaf 6 Leaf 7 Recursive 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 3 Elsa L Gunter Mapping over Recursive Types 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 Gunter Mapping over Recursive Types ibtreeMap 2 bin tree int Bin Tree Node Node Leaf 5 Leaf 8 Leaf 5 Elsa L Gunter Folding over Recursive Types let rec ibtreeFoldRight leafFun nodeFun tree match tree with Leaf n leafFun n Node left tree right tree nodeFun ibtreeFoldRight leafFun nodeFun left tree ibtreeFoldRight leafFun nodeFun right tree val ibtreeFoldRight int a a a a int Bin Tree a fun Elsa L Gunter Folding over Recursive Types let tree sum ibtreeFoldRight fun x x val tree sum int Bin Tree int fun tree sum bin tree int 2 Elsa L Gunter Mutually Recursive Types type a tree TreeLeaf of a TreeNode of a treeList and a treeList Last of a tree More of a tree a treeList type a tree TreeLeaf of a TreeNode of a treeList and a treeList Last of a tree More of a tree a treeList Elsa L Gunter Mutually Recursive Types Values let tree TreeNode More TreeLeaf 5 More TreeNode More TreeLeaf 3 Last TreeLeaf 2 Last TreeLeaf 7 Elsa L Gunter Mutually Recursive …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?