Enumerable TypesScalar TypesComposite TypesTypes --- OverviewDiscreet Types --- EnumerationsDiscreet Types --- SubrangesStructured TypesArrays -- Storage LayoutArray Indexing -- 1 DimensionsArray Indexing -- 2 DimensionsArray Indexing -- $n$ DimensionsRecord TypesRecord Typesldots Pointer TypesProcedure TypesClass TypesSet TypesReadings and References520—Spring 2005—26CSc 520Principles of ProgrammingLanguages26: Types — ClassificationChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—26Enumerable TypesAlso called discrete types or ordinal types.Discrete types are countable, or 1-to-1 with the integers.Examples:1.integer2.boolean3.char4.subranges5.enumeration types[2]520—Spring 2005—26Scalar TypesAlso called simple types.The scalar types include:1.discrete types2. real3.rational4.complex[3]520—Spring 2005—26Composite TypesAlso called constructed types.They are created by applying type constructors toother, simpler, types.The composit types include:1.records2.variant records3.arrays4.sets5.pointers6. lists7.files[4]520—Spring 2005—26Types — Overviewintegerbooleancharsubrangeenumerationscalar typesrealrationalcomplexrecordvariant recordarraysetpointerlistfilecomposite typesdiscrete types[5]520—Spring 2005—26Discreet Types — EnumerationsPascal, Ada, Modula-2, C have some variant ofenumeration types.C’s enumerations are just syntactic sugar for integerconstants.In Pascal and Ada, enumerations are real types,incompatible with other types.In Ada and C, enumeration values can be userspecified.TYPE Color = (white,blue,yellow,green,red);TYPE Fruits = (apple=4,pear=9,kumquat=99);VAR A : ARRAY Color OF Fruit;FOR c := white TO red DOIF c != yellow THEN A[c] := apple;[6]520—Spring 2005—26Discreet Types — SubrangesSubranges can be used to force additional runtimechecks.Some languages use subrange types as array indextypes.TYPE S1 = [0..10];TYPE S2 = [’a’..’z’];TYPE Color = (white,blue,yellow,green,red);TYPE S3 = [blue..green];TYPE A = ARRAY S3 OF INTEGER;VAR X : S3 := white; (* ⇐ error *)[7]520—Spring 2005—26Structured Types[8]520—Spring 2005—26Arrays – Storage LayoutMost languages lay out arrays in row-major order.FORTRAN uses column-major.A[1,1] A[1,2]A[2,1] A[2,2]A[3,1] A[3,2]A[4,1] A[4,2]0 A[1,1]1 A[1,2]2 A[2,1]3 A[2,2]4 A[3,1]5 A[3,2]6 A[4,1]7 A[4,2]0 A[1,1]1 A[2,1]2 A[3,1]3 A[4,1]4 A[1,2]5 A[2,2]6 A[3,2]7 A[4,2]Matrix Row Major Column Major[9]520—Spring 2005—26Array Indexing – 1 DimensionsHow do we compute the address (L-value) of the n:thelement of a 1-dimensional array?Aelszis A’s element-size, Aaddris its base address.VAR A : ARRAY [l .. h] OF T;L − VAL(A[i]) ≡ Aaddr+ (i − l) ∗ Aelsz≡ Aaddr+ (l ∗ Aelsz) + i ∗ AelszC ≡ Aaddr+ (l ∗ Aelsz)L − VAL(A[i]) ≡ C + i ∗ AelszNote that C can be computed at compile-time.[10]520—Spring 2005—26Array Indexing – 2 DimensionsVAR A :ARRAY [l1..h1][l2..h2] OF T;w1≡ h1− l1+ 1w2≡ h2− l2+ 1L − VAL(A[i1, i2]) ≡ Aaddr+ ((i1− l1) ∗ w2+ i2+ l2) ∗ Aelsz≡ Aaddr+ (i1∗ w2+ i2) ∗ Aelsz−(l1∗ w2− l2) ∗ AelszC ≡ Aaddr− (l1∗ w2− l2) ∗ AelszL − VAL(A[i1, i2]) ≡ (i1∗ w2+ i2) ∗ Aelsz+ CC can be computed at compile-time.[11]520—Spring 2005—26Array Indexing – n DimensionsVAR A : ARRAY [l1..h1] ... [ln..hn] OF T;wk≡ hk− lk+ 1C ≡Aaddr− ((· · · (l1∗ w2+ l2) ∗ w3+ l3) · · ·) ∗ wn+ ln) ∗ AelszL − VAL(A[i1, i2, ..., in]) ≡((· · · (i1∗ w2+ i2) ∗ w3+ i3) · · ·) ∗ wn+ in) ∗ Aelsz+ C[12]520—Spring 2005—26Record TypesPascal, C, Modula-2, Ada and other languages havevariant records (C’s union type):TYPE R1 = RECORD tag : (red,blue,green);CASE tag OFred : r : REAL; |blue : i : INTEGER; |ELSE c : CHAR;END;END;Depending on the tag value R1 has a real, integer, orchar field.The size of a variant part is the max of the sizes of itsconstituent fields.[13]520—Spring 2005—26Record Types...Oberon has extensible record types:TYPE R3 = RECORDa : INTEGER;END;TYPE R4 = (R3) RECORDb : REAL;END;R4has both the a and the b field.Extensible records are similar to classes in otherlanguages.[14]520—Spring 2005—26Pointer TypesIn order to build recursive structures, most languagesallow some way of declaringrecursive types. These arenecessary in order to construct linked structures suchas lists and trees:TYPE P = POINTER TO R;TYPE R = RECORDdata : INTEGER;next : P;END;Note that P is declared before its use. Languages suchas Pascal and C don’t allow forward declarations, butmake an exception for pointers.[15]520—Spring 2005—26Procedure TypesC, Modula-2, and other languages support proceduretypes. You can treat the address of a procedure like anyother object.Languages differ in whether they allow procedureswhose address is taken to be nested or not. (Why?)TYPE P = PROCEDURE(x:INTEGER; VAR Y:CHAR):REAL;VAR z : P; VAR c : CHAR; VAR r : REAL;PROCEDURE M (x:INTEGER; VAR Y:CHAR):REAL;BEGIN· · ·END;BEGINz := M; /* z holds the address of M. */r := z(44,c);END.[16]520—Spring 2005—26Class TypesJava’s classes are just pointer to record types. Somelanguages (Object Pascal, Oberon, MODULA-3) defineclasses just like records.Nore about classes later.TYPE C1 = CLASSx : INTEGER;void M() { · · · };void N() { · · · };END;TYPE C2 = CLASS EXTENDS C1r : REAL; // Add another field.void M(){ · · · }; // Overrides C1.Mvoid Q() { · · · }; // Add another method.END;[17]520—Spring 2005—26Set TypesPascal and Modula-2 support sets of ordinal types.Sets are implemented as bitvectors.Many implementations restrict the size of a set to 32(the size of a machine word), or 256 (so you candeclare aset of char).type letset = set of ’A’ .. ’z’;var x, y, z, w: letset;beginx := [’A’..’Z’,’a’]; y := [’a’..’z’];z := x + y; (* set union *)z := x * y; (* set intersection *)w := x - y; (* set difference *)if ’A’ in z then ...; (* set membership *)end.[18]520—Spring 2005—26Readings and ReferencesRead Scott,
View Full Document
Unlocking...