Programming Languages and Compilers (CS 421)User Defined TypesData Structures in a Functional LanguageSlide 4Data Structures with PointersSlide 6ArraysArray LayoutArray Component AccessSummary: Records, Variant Records, Pointers, ArraysSlide 11Information Hiding - EncapsulationNeed for Abstract TypesSML -> OcamlAbstract Types in SMLSlide 16Slide 17Abstract Type – ExampleSlide 19Abstract TypesUser Defined Abstract TypesModulesSlide 23Slide 24Parameterized ModulesSlide 37Slide 38Object-Oriented ProgrammingVariables and MethodsInheritanceInheritance Polymorphism and Dynamic BindingVirtual (or Abstract) MethodsSingle Versus Multiple InheritanceInfinite Data and Evaluation MethodsCall by ValueCall by Value ExampleSlide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Call by Value pros/consCall by Value nonterminationCall by NameCall by Name ExampleSlide 65Slide 66Slide 67Slide 68Slide 69Using Call by Name in OcamlCall by Name pros/consSide EffectsSlide 73But…Call by NeedCall by Need ExampleSlide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Side-Effects in OcamlImplementing ThunksSlide 86Slide 87The Lazy ModuleInfinite DataSlide 90Lazy ListsInfinite Data the Lazy wayMap on an Infinite ListSlide 94The List of Natural NumbersSlide 96QuestionAnswerProgramming 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 User Defined Types•Records and variants allow for more accurate modeling of needed data structures than can be had from just arrays and pairs•Better modeling leads to better encapsulationElsa L. Gunter Data Structures in a Functional Languagetype tree = Node of int * tree * tree | Leaf of int | Emptylet t1 = Node(8,Node(5, Leaf 3, Leaf 7), Node(13,Leaf 11,Empty)let t2 = add t1 17Elsa L. Gunter Data Structures in a Functional Language t1: t2: 8 ==> 8 8 5 13 5 13 133 7 11 _ 3 7 11 _ 17•Empty --> Leaf 17•Must rebuild Node 13 and Node 8Elsa L. Gunter Data Structures with Pointerstype mtree={n: int; mutable left: mtree option; mutable right: mtree option};;•let t1= {n=8; left= Some {n=5;left= Some {n=3; left=None; right=None}; right=Some {n=7; left=None; right=None}}; right=Some {n=13; left= Some {n=11; left=None; right=None}; right=None}};;Elsa L. Gunter Data Structures in a Functional Language t1: t1 = t2: 8 ==> 8 5 13 5 13 3 7 11 _ 3 7 11 17•Update rightmost None with Some{n=17,left=None,rigth=None}Elsa L. Gunter Arrays•Ordered sequence of fixed number of objects all of the same type•Indexed by integer, subrange, or enumeration type, called subscript•Multidimensional arrays have one subscript per each dimension•L-value for array element given by accessing formulaElsa L. Gunter Array Layout•Assume one dimension1 dim arrayVirtual Origin (VO)Lower Bound (LB)Upper Bound (UB)Comp typeComp size (E)A[LB]A[LB+1]A[UB]A[0]Elsa L. Gunter Array Component Access•Component access through subscripting, both for lookup (r-value) and for update (l-value)•Component access should take constant time (ie. looking up the 5th element takes same time as looking up 100th element)Elsa L. Gunter Summary: Records, Variant Records, Pointers, Arrays•Record types are good for grouping heterogeneous data andnaming them–All instances have identical structure–Easy to access field information - constnat time•Disjoint types (variants) are good for types that have multiple structures.–Allows for more abstract treatment of data–Allows for recursive user-defined typesElsa L. Gunter Summary: Records, Variant Records, Pointers, Arrays•Pointer types allow explicit management of memory–Allows 'in-place' modifications to large data structures–Limits structure sharing•Array types are good for many homogenous data values.–Allows efficient memory organization–Allows efficient memory access–Allows proving independent accesses: A[i][j], A[i+1][j]Elsa L. Gunter Information Hiding - Encapsulation•Consider the C code:typedef struct RationalType { int numerator; int denominator;} RationalRational mk_rat (int n,int d) { …}Rational add_rat (Rational x, Rational y) { … }•Can use mk_rat, add_rat without knowing the details of RationalTypeElsa L. Gunter Need for Abstract Types•Problem with previous example: abstraction not enforced–User can create Rationals without using mk_rat–User can access and alter numerator and denominator directly without using provided functionsElsa L. Gunter SML -> Ocaml•SML (still) supports a mechanism for creating abstract types without needing the module system•Modules can implement abstract types, so Ocaml doesn’t support simple abstract type any more•fun ---> let rec•val ---> let•case _ of _=>_ ---> match _ with _->_Elsa L. Gunter Abstract Types in SMLabstype rational = C of {numerator:int, denominator:int} with fun mk_rat (n,d) = case d of 0 => raise Div | _ => C {numerator = n, denominator = d} fun add_rat (C{numerator=n1,denominator=d1}, C{numerator=n2,denominator=d2}) = C{numerator = n1 * d2 + n2 * d1, denominator = d1 * d2}end;Elsa L. Gunter Abstract Types in SMLtype rationalval mk_rat = fn : int * int -> rationalval add_rat = fn : rational * rational -> rationalval half = mk_rat(1,2);val half = - : rationalcase half of C info => info;stdIn:4.1-4.28 Error: non-constructor applied to argument in pattern: CElsa L. Gunter Abstract Types in SML•Can create objects of type rational•Can use associated functions defined in abstype•Can not use the implementation–Constructor C not in scope - only in scope inside interface function definitionsElsa L. Gunter Abstract Type – Example•Creates a new type (not equal to int list)•Functional implementation of integer sets – insert creates new intset•Exports type intset, empty_set, insert, union, elt_of, and set_to_list; act as primitive–Cannot use pattern matching or list functions; won’t type checkElsa L. Gunter Abstract Type – Example•Implementation: just use record, except for type checking•Data
View Full Document
Unlocking...