Records type city is record Name String 1 10 Country String 1 20 Population integer Capital Boolean end record struct city char name char country int population bool capital Ada C C 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 safe C1 Figure Circle S1 Figure Square discriminant provides constraint C1 Radius 15 if S1 Lower Left C1 Center then function Area F Figure return Float is applies to any figure i e subtype begin case F Kind is when Circle return Pi Radius 2 Discriminant checking C Figure Circle L Figure Line F Figure illegal don t know which kind P1 P2 Point C Circle Red False 10 P1 record aggregate if C Orientation then illegal circles have no orientation C L illegal different kinds C Kind Square Illegal discriminant is constant Discriminant is visible constant component of object There is a way of specifying a figure that can change kinds Variants 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 time Access 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 allocation type ptr is access integer Ada named type typedef ptr int C C A value of type access T designates a value of type T Dynamic data structures type Cell an incomplete type type Ptr is access Cell an access to it type 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 cell next struct List struct Link link succ List member of struct List Link head legal to mention name before end of declaration incomplete declaration a pointer to it full definition 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 Ada Strings are arrays type String is array positive range of character type Str Ptr is access String Ptr1 Ptr2 Str Ptr initially null Title String Brave New World fixed size Ptr3 Str Ptr new String Island Ptr1 Ptr3 pointer assignment makes synonyms Ptr1 all what array assignment must be same size Ptr1 new String the genius and the goddess Title Ptr1 all run time error sizes don t match Variations on Strings C char name1 char name2 char title brave new world 16 characters implicit 0 at end char t island pointer to constant array name1 new char 16 allocate dynamic storage char ptr title 0 pointer to local array while name1 ptr amusing C idiom name1 0 B title not affected t 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 true Pointers 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 allocate tab2 tab1 share delete tab1 discard storage tab2 5 error tab2 does not denote anything Dangling 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 overwritten Deallocation Manual deallocation is potentially dangerous because not all current references to an object may be visible System is safer if storage reclamation is automated Manual solution make deallocation more explicit procedure free is new Ada Unchecked Deallocation String Ptr Semi automatic solution Ada C destructors controlled types Automatic Solution Java ML garbage collector Garbage Collection Techniques Reference counting if nothing points to an object you can free it Start with active variables and then follow all their references in order to delete objects Which can leave garbage around