RecordsVariantsVariants are type safeDiscriminant checkingVariants and classesAccess Types and pointersDynamic data structuresIncomplete declarations in C++Pointers and dereferencing (address of a house and people inside)Three models for arraysVariations on Strings: AdaVariations on Strings: C++Variations on Strings: JavaPointers and safetyDangling referencesDeallocationGarbage Collection TechniquesRecordstype city is record -- Ada Name: String (1..10); Country : String (1..20); Population: integer; Capital : Boolean;end record;struct city { -- C, C++ char* name; char* country; int population bool capital }Variants•Need to treat group of related representations as a single type:type figure_kind is (Circle, Square, Line);type Figure (Kind : Figure_kind) is record Color : color_type; -- defined elsewhere Visible : Boolean; case Kind is when Line => Length : Integer; Orientation: Float; Start : Point; -- defined elsewhere when square => Lower_Left, Upper_Right : Point; when circle => Radius : Integer; Center : Point; end case;end record;Variants are type safeC1 : Figure (Circle); -- discriminant provides constraintS1 : Figure (Square);…C1. Radius := 15;if S1.Lower_Left = C1.Center then..function Area (F : Figure) return Float is -- applies to any figure, i.e. subtypebegin case F.Kind is when Circle => return Pi * Radius ** 2; ..Discriminant checkingC : Figure (Circle);L : Figure (Line);F : Figure; -- illegal, don’t know which kindP1, P2 := Point;…C := (Circle, Red, False, 10, P1); -- record aggregateif C.Orientation then -- illegal, circles have no orientationC := L; -- illegal, different kinds C.Kind := Square; -- Illegal, discriminant is constantDiscriminant is visible constant component of objectThere is a way of specifying a figure that can change kindsVariants and classes•Discriminated types and (Ada-style) classes have similar functionalities•Discriminated types can be allocated statically•Run-time code uses less indirection, but is uglier:•Adding new variants is disruptive–must modify every case statement•Variant programming: one procedure at a time•Class programming : one class at a timeAccess Types and pointers•Related (but distinct) notions:–a value that denotes a memory location–a dynamic name that can designate different objects–a mechanism to separate stack and heap allocationtype ptr is access integer; -- Ada: named typetypedef ptr int*; -- C, C++–A value of type (access T) designates a value of type TDynamic data structurestype Cell; -- an incomplete typetype Ptr is access Cell; -- an access to ittype Cell is record -- its full declaration value : Integer; next, prev : Ptr;end record; List: Ptr := new Cell ‘(10, null, null); … -- a list is just a pointer to its first element List.next := new Cell ‘(15, null, null); List.next.prev := List;Incomplete declarations in C++struct cell { int Value; cell* prev; // legal to mention name cell* next; }; // before end of declarationstruct List; // incomplete declarationstruct Link { link* succ; List* member_of; }; // a pointer to itstruct List { // full definition Link* head: // mutual references};Pointers and dereferencing (address of a house and people inside)•Need notation to distinguish pointer from designated object–in Ada : Ptr, Ptr.all–in C : Ptr, Ptr*–in Java: no notion of pointer•For pointers to composite values, dereference can be implicit:–in Ada : C1.Value equivalent to C1.all.Value–in C++ : distinguish C1.Value and C1 -> Value–in both : pointers to arrays are indexable: arr_ptr (5), arr_ptr[5]Three models for arrays•In Ada, arrays can be static or dynamic. Arrays are objects with assignment.•In C++ arrays can be static only if they have static bounds. There is no array assignment.•In Java arrays are always dynamic, assignment is a reference assignment.Variations on Strings: AdaStrings are arrays: type String is array (positive range <>) of character;type Str_Ptr is access String;Ptr1, Ptr2 : Str_Ptr; -- initially nullTitle : String := “Brave New World” ; -- fixed sizePtr3 : Str_Ptr := new String’(“Island”);…Ptr1 := Ptr3; -- pointer assignment makes synonymsPtr1.all := “what??”; -- array assignment: must be same sizePtr1 := new String (“the genius and the goddess”);Title := Ptr1.all; -- run time error: sizes don’t matchVariations on Strings: C++char* name1; char* name2;char title[ ] = “brave new world”; // 16 characters: implicit 0 at endchar* t = “island”; // pointer to constant arrayname1 = new char[16]; // allocate dynamic storagechar* ptr = &title[0]; // pointer to local array…while (*name1++ = *ptr++); // amusing C idiomname1 [0] = ‘B’; // t itle not affectedt [0] = “I”; // illegal: string literal is constant semantic equivalence: a[k] = * (a + k)Variations on Strings: Java•Strings are classes, not arrays: need special notation for indexing and slicing.•String values are constants: need to use arrays of characters to modify strings.String name = “Eyeless in Gaza”;…name = name + “(“ + 1939 + “); // assign different value // implicit conversion to string: “Eyeless in Gaza (1939)”if (name.StringAt (0) == ‘E’ ) { // truePointers and safety•Pointers create aliases: accessing the value through one name affects the retrieval through the other:int* tab1;int* tab2;…tab1 = new int [10]; // allocatetab2 = tab1; // sharedelete (tab1); // discard storagetab2 [5] = .. // error, tab2 does not denote anythingDangling references•If we can point to local storage, we can create a reference to an undefined value:int* f ( ) { // returns a pointer to an integer int local; // variable on stack frame of f … return local&; // reference to local entity };int x = f ( );… x + 1 ... // stack may have been overwrittenDeallocation•Manual deallocation is potentially dangerous, because not all current references to an
View Full Document