CSc 520Principles of Programming Languages26: Types — ClassificationChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Enumerable Types• Also called discrete types or ordinal types.• Discrete types are countable, or 1-to-1 with the integers.• Examples:1. integer2. boolean3. char4. subranges5. enumeration types2 Scalar Types• Also called simple types.• The scalar types include:1. discrete types2. real3. rational4. complex13 Composite Types• Also called constructed types.• They are created by applying type constructors to other, simpler, types.• The composit types include:1. records2. variant records3. arrays4. sets5. pointers6. lists7. files4 Types — Overviewintegerbooleancharsubrangeenumerationscalar typesrealrationalcomplexrecordvariant recordarraysetpointerlistfilecomposite typesdiscrete types5 Discreet Types — Enumerations• Pascal, Ada, Modula-2, C have some variant of enumeration types.• C’s enumerations are just syntactic sugar for integer constants.• In Pascal and Ada, enumerations are real types, incompatible with other types.• In Ada and C, enumeration values can be user specified.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;26 Discreet Types — Subranges• Subranges can be used to force additional runtime checks.• Some languages use subrange types as array index types.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 *)Structured Types7 Arrays – Storage Layout• Most 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 Major8 Array Indexing – 1 Dimensions• How do we compute the address (L-value) of the n:th element 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 ∗ Aelsz• Note that C can be computed at compile-time.39 Array 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+ C• C can be computed at compile-time.10 Array 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+ C11 Record Types• Pascal, 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, or char field.• The size of a variant part is the max of the sizes of its constituent fields.412 Record Types. . .• Oberon has extensible record types:TYPE R3 = RECORDa : INTEGER;END;TYPE R4 = (R3) RECORDb : REAL;END;R4 has both the a and the b field.• Extensible records are similar to classes in other languages.13 Pointer Types• In order to build recursive structures, most languages allow some way of declaring recursive types.These are necessary in order to construct linked structures such as lists and trees:TYPE P = POINTER TO R;TYPE R = RECORDdata : INTEGER;next : P;END;• Note that P is declared before its use. Languages such as Pascal and C don’t allow forward declarations,but make an exception for pointers.14 Procedure Types• C, Modula-2, and other languages support procedure types. You can treat the address of a procedurelike any other object.• Languages differ in whether they allow procedures whose 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.15 Class Types• Java’s classes are just pointer to record types. Some languages (Object Pascal, Oberon, MODULA-3)define classes just like records.5• 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;16 Set Types• Pascal 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 a set 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.17 Readings and References•Read Scott,
View Full Document