ICS 141 Klefstad

Data Types

Outline

Primitive Data Types

typically built into the language
usually abstractions of underlying hardware data types
typical primitive types:
- numeric
  - integral
  - floating point
  - fixed point
- character
- boolean

Character Strings

not a primitive type, but usually built in
classic design decision:
- should strings length be static or dynamic?
typical string operations
- concatenation, substring, relational ops, assignment, I/O
alternative implementations
- static string (FORTRAN)
- semi-dynamic strings (Ada)
- limited dynamic string (C++)
- flexible arrays (Java String class)
- linked lists (Snobol4)

Ordinal Types

includes integer, character, boolean, and enumeration

represented as a set of integral values

enum Day {mon, tue, wed, thu, fri, sat, sun};

proper use of enumeration types enhances two program qualities:
- readablilty through descriptive names
- reliability through better typechecking
subranges of ordinal types allow for more compiler checks
```
subtype Weekday is Day Range mon .. fri; -- Ada
```

Array Types

homogeneous aggregate type
also called a finite-mapping
design issues:
- what is the index notation?
- subscript ranges?
- bounds checking?
- allocation time?
- how many dimmensions?
- can you specify literals?
- can you take subranges?

allocation can be
- static
- semi-static (fixed stack-dynamic)
- semi-dynamic (stack-dynamic)
- dynamic (heap-dynamic)
implementation
- consider a: array(lower..upper) of element;
- size of array a is
```
(upper-lower+1)*sizeof(element)
```
- indexing formula
```
address(a[i])=address(a)+(i-lower)*sizeof(element)
```

Record Types

heterogeneous aggregate type
also called a cartesian product

contains a set of fields accessed by name

struct Person {
  char name[20];  // offset 0 bytes
  int age;		// offset 20 bytes
  char phoneNumber[20]; // offset 24 bytes
  int income;  // offset 44 bytes
}; // size of Person is 48 bytes

each field has an (integral) offset into the record
classes are implemented as records

Union Types

choice of alternative structures

variant - each alternative data member
discriminant - data member indicating which variant is alive

C has undiscriminated unions, size is max size of variants

union MyUnion {
  char name[20];  // offset 0 bytes
  int age;		// offset 0 bytes
  char phoneNumber[20]; // offset 0 bytes
  int income;  // offset 0 bytes
}; // size of MyUnion is 20 bytes

unions can be used to circumvent type system if unchecked
class hierarchies replace unions in object-oriented languages

Set Types

unordered collection of value from an ordinal type T

T is called the base type

type braces = set of ['(',')','[',']','{','}'];
if c in braces then ...

usually implemented as a bit vector
- ith bit is 1 only if ith element is in the set
current trend is to build sets via a generic class

Pointer Types

values are a set of addresses for objects of a specified type T
type T is called the domain type of the pointer
the value nil or null indicates a pointer to nothing
allow recursive data structures like lists, trees, etc.
often used to refer to anonymous heap variables

dereferencing is the most common operation
some languages (Ada, Java) have automatic dereferencing
issues
- scope and life-time of pointer and anonymous object
- are pointers typed?
- how is the heap managed?
some problems
- dangling pointer (or dangling reference)
- storage leaks (lost objects called 'garbage')
- uninitialized (garbage or nil) pointers
C++ references are like constant pointers

Heap management

explicit allocation and free (C)
- programmer's responsibility to keep track of allocated memory
- allocation
- free
stack based (UCSD Pascal)
- mark
- release
reference count
- freed when count = 0
- garbage collection time is spent incrementally
- problem with circular lists

parallel garbage collection
- low priority background thread collects garbage (Java)
mark and collect
- used for Lisp
- mark all referencable memory
- collect all pieces not marked