Array Types Index types can be of any discrete type Component type must be definite i e have bounds type class list is array 1 100 of String 1 10 OK type class list is array 1 100 of String The subtype constrains all indices or none type Matrix is array positive range positive range of Long Float subtype Table is Matrix subtype Rotation is Matrix 1 3 1 3 Error arrays are objects with assignment unlike C C Table1 Table2 all components assigned Anonymous Array Types Grades array 1 Num Students of Natural type of Grades has no name distinct from any other array types Ar1 array 1 10 of Boolean Ar2 array 1 10 of Boolean Ar1 Ar2 Error different anonymous types If a type is a useful abstraction it deserves to have a name Array Attributes type Matrix is array Positive range Positive range of Float subtype Rect is Matrix 1 3 1 5 M3 Rect M3 First 1 Yields 1 M3 First same Rect length 2 Yields 5 applies to type M3 range 2 equivalent to 1 5 String Length ERROR unconstrained Arrays are self describing size information is built in Array Aggregates Expression that yields an array value A 1 2 3 10 positional A 1 others 0 notation for default A 1 3 1 4 999 component associations Default can only be used if bounds are known A String 1 10 others OK A String others Error unknown bounds Initializers in C Similar notion for declarations int v2 1 2 3 4 size from initializer char v3 2 a z int v5 10 1 char name Algol declared size default other components 0 String literals are aggregates but no array assignments so initializer is not an expression mechanism is less orthogonal Aggregates and Qualification Aggregate may be ambiguous type Vector is array 1 3 of Float procedure Display V vector type Assay is array 1 3 of Float procedure Display A assay Display 1 0 1 2 1 5 which ambiguous Display Vector 1 0 1 2 1 5 OK Multidimensional Arrays Aggregates given in row major order with subaggregates type Square is array 1 3 1 3 of Integer Unit constant Square 1 0 0 0 1 0 0 0 1 A two dimensional array is NOT array of arrays type vector is array 1 3 of Integer type V3 is array 1 3 of vector not convertible to Square Operations on One Dimensional Arrays Boolean operations extend pointwise type Set is array 1 Card of Boolean S1 S2 S3 Set S3 S1 and S2 Set Intersection lexicographic comparisons on arrays of discrete types S1 T T T S2 T T F S2 S1 yields True Concatenation and Slicing Both operations yield the base type type Table is array 1 10 of Integer T1 T2 Table T1 T2 What type Declaration equivalent to type Anon is array integer range of Integer subtype Table is Anon 1 10 T1 T2 T1 X Y are of type Anon A discrete range specifies a slice subtype Sub is Positive range 2 4 Label String 1 10 transcends Label 2 4 Yields ran Label Integer range 2 4 Same Label Sub Ditto 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 classes have similar functionalities Discriminated types can be allocated statically Run time code uses less indirection Compiler can enforce consistent use of discriminants Adding new variants is disruptive must modify every case statement Variant programming one procedure at a time Class programming one class at a time Free Unions Free unions can be used to bypass the type model union Value char s allocated at same address C semantics int i programmer must keep track of current type e g by using an explicit tag struct Entry int discr union anonymous component either s or i char s if discr 0 int i if discr 1 but run time system won t check Discriminated unions and dynamic typing In dynamically typed languages only values have types not names S 13 45 S 1 2 3 4 a floating point number a list Run time values are described by discriminated unions Discriminant denotes type of value S X Y arithmetic or concatenation The Variant type in BASIC has the same property The Tag in a class object functions like a discriminant 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 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