CSc 520 - Principles of Programming Languages
14 : Types -- Classification

Christian Collberg

Department of Computer Science

University of Arizona

1 Enumerable Types

• Also called discrete types or ordinal types.
• Discrete types are countable, or 1-to-1 with the integers.
• Examples:
  1. integer
  2. boolean
  3. char
  4. subranges
  5. enumeration types

2 Scalar Types

• Also called simple types.
• The scalar types include:
  1. discrete types
  2. real
  3. rational
  4. complex

3 Composite Types

• Also called constructed types.
• They are created by applying type constructors to other, simpler, types.
• The composit types include:
  1. records
  2. variant records
  3. arrays
  4. sets
  5. pointers
  6. lists
  7. files

4 Types -- Overview

types

5 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.

2#2

6 Discreet Types -- Subranges

• Subranges can be used to force additional runtime checks.
• Some languages use subrange types as array index types.

3#3

Structured Types

7 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 Major

8 Array Indexing - 1 Dimensions

• How do we compute the address (4#4-value) of the 1#1:th element of a 1-dimensional array?
• 5#5 is 6#6's element-size, 7#7 is its base address.

8#8

9#9

• Note that 10#10 can be computed at compile-time.

9 Array Indexing - 2 Dimensions

11#11

12#12

• 10#10 can be computed at compile-time.

10 Array Indexing - 1#1 Dimensions

13#13

14#14

15#15

16#16

11 Record Types

• Pascal, C, Modula-2, Ada and other languages have variant records (C's union type):
  17#17
  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.

12 Record Types...

• Oberon has extensible record types:
  18#18
  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:
  19#19
  
• 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 procedure like any other object.
• Languages differ in whether they allow procedures whose address is taken to be nested or not. (Why?)

20#20

15 Class Types

• Java's classes are just pointer to record types. Some languages (Object Pascal, Oberon, MODULA-3) define classes just like records.
• Nore about classes later.

21#21

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 can declare a set of char).

22#22

17 Readings and References

• Read Scott, pp. 312-320,336-361.