OutlineBasic Data AbstractionAggregate TypesLimitationsAbstract Data TypesAbstract Data TypesADTs in AdaADTs in C++Parameterized ADTsParameterized ADTsParameterized ADTs in AdaParameterized ADTs in C++Problems with ADTsOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsCS421 Lecture 18: Data Abstraction1Mark [email protected] of Illinois at Urbana-ChampaignJuly 20, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsBasic Data AbstractionAbstract Data TypesParameterized ADTsMark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsObjectivesBy the end of this lecture, you should◮be familiar with differences in basic data abstractionconstructs (tuples, records, etc)◮understand the programming language concept of abstractdata typ e◮know, at a high level, how several languages handle dataabstraction◮understand parameterize d abstract data typesMark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsBasic Data Abstraction FacilitiesMost languages include at least one form of user-defined type.We ’ve already seen se veral examples in OCaml:◮tuples◮records◮variant recordsAnother is the array, available in OCaml but much more commonin imperative languages.Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsArraysArrays are simply ordered sequences of objects (in the non-OOsense) all of the same type.A[3] := 15;◮often of fixed size◮generally indexed by integers; occasionally by subrange orenumeration typ es◮can be multidimensional, with one index per dimension◮l-value of any element much be calculated using formulabased on index ranges and element sizes◮goal: l-value calculation should be constant-time◮heavily used in numeric computation; many languages provideextended support for arrays (slices, array reductions, etc)Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsTuplesLike most arrays, tuples are fixed size. Unlike arrays, tuples allowdifferent types in each position.(1, ’Bob’, 3.17): (Int × String × Float)◮provide an e asy way to group information◮do not provi de a way to label individual items◮tuples are order dependent – flipping items in a tuple c hangesthe typ eMark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsRecordsRecords provide functionality similar to tuples – we can groupmultiple items of different types together. However, recordsadditionally provide a way to name each item, making them orderindependent.◮generally referred to as records or structures◮lookup usually as var-name.field-name◮with ability to name fields, provide a way to model data in theproblem domain◮generally not recursive (at least without pointers)Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsVariant RecordsVariant records are like records, but allow different forms of data tobe stored in records of the same type, based (usually) on aconstructor or type tag.type ’a mylist = Empty | Cons of ’a * ’a mylist◮provide different groups of data items in the same type◮uses ty pe constructors in most functional languages◮variant records, dis joint unions, or just unions in mostnon-functional languages (imperative, OO)◮valid items usually determined with either pattern matching(functional) or tag/discriminator (imperative)Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsVariant Records Example: Modula-21 TYPE IntOrReal =2 RECORD3 CASE IsInt: BOOLEAN OF4 TRUE: i : INTEGER |5 FALSE: r : REAL6 END;7 END;8 ...9 x.IsInt := TRUE;10 x.i := 0;Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsLimitationsWhile these different abstraction mechanisms are useful, theyprovide no method for information hiding or encapsulation.Consider the C++ code:1 struct Rational {2 int numerator;3 int denominator;4 };5 Rational mk_rat (int n,int d) { ... }6 Rational add_rat (Rational x, Rational y) { ... }◮Can we use Rationals without knowing the implementationdetails?◮Can we access t he impl ementation directl y without goingthrough the interface?Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAggregate TypesLimitationsLimitationsThe proble m with t he last example was raised in the second point– structures give us the ability to group data, but theimplementation i s not hidden.◮Users can create Rationals without using mk rat◮Users can directly alter the contents of a rational◮Because the implementation is not hidden, changes may breakuser code that relies on itMark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAbstract Data TypesADTs in AdaADTs in C++Abstract Data TypesHow do we fix these limitations? Ideally:◮we c ould specify an interface through which the data ismanipulated;◮we c ould then prevent unsupported changes to the datareprese ntation, hiding the representation completely.To do t his, we need abstract data types.Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAbstract Data TypesADTs in AdaADTs in C++Abstract Data Types: A Simple ExampleWe actually use ADTs all the time. For instance, look at floatingpoint numbers.◮We can cre ate variables of floating point type;◮we c an then use syst em-provided operations on floating pointnumbers, but we cannot provide our own operations not basedon these;◮we c an hide the binary representation of the numbers.Ideally, our use r-defined ADTs would give us the same capabilities.Mark Hills CS421 Lecture 18: Data AbstractionOutlineBasic Data AbstractionAbstract Data TypesParameterized ADTsAbstract Data TypesADTs in AdaADTs in C++ADTs, More FormallyFormally, we want ADTs to have the following two
View Full Document
Unlocking...