Data Types

Data Types

A more modern definition: A set of values together with a set of operations.
(Ada with packages, C++ and Java classes, or in general, an abstract data type)

The relationship of types to algebraic systems is limited to the computer's finite systems. For example the infinite integer range and real number continuum are only approximated by a finite system.

Each data object has a type:

• Values: for objects of that type
• Operations: for objects of that type
• Implementation: (Storage representation) for objects of that type
• Attributes: (e.g., name) for objects of that type
• Signature: (of binary operation f): f: type X type → type
  (of unary operation u): f: type → type

Type Declarations

The definition of a type beyond what is supplied by the base language. You are naming the type with an identifier.

E.g. typedef in C; class  in C++; type statement in Pascal/Ada. Classes in Java support (or cirumcumvent the need for a separate) type declarations.

Explicit type declaration: strongly typed if all variables must be declared.

No memory allocation is a direct result of a declaration.

Type declarations simplify type equivalence requirements.

Type checking

Data Objects

Binding of data objects

A compiler tracks two categories:

• Memory locations
• Numeric values

A variable is a binding of a name to a memory location:

• Contents of the location may change

L-value and R-value

Location for an object is its L-value. Contents of that location is its R-value.

Where did names L-value and R-value come from?

Consider executing: A = B + C;

1. Pick up contents of location B
2. Add contents of location C
3. Store result into address A.

For each named object, its position on the right-hand-side of the assignment operator (=) is a content-of access, and its position on the left-hand-side of the assignment operator is an address-of access.

• address-of then is an L-value
• contents-of then is an R-value
• a value, by itself, generally means R-value
• you retrieve the R-value by dereferencing the L-value

Subtypes

A is a subtype of B if every value of A is a value of B.

Note: In C almost everything (int, word, long, byte) other than floating point numbers is a subtype of integer.

Conversion between types:

Given variables A and B, when is A := B legal?

Explicit: All conversion between different types must be specified by the programmer

Implicit: Some conversions between different types are implied by the language definition

Coercion examples

Examples in Pascal:

var A: real;
    B: integer;

A := B - Implicit, called a coercion - an automatic conversion from one type to another

A := B is called a widening since the type of A has more values than B.

B := A (if it is allowed) is called a narrowing since B has fewer values than A. Information could be lost or corrupted in this case.

In most languages widening coercions are usually allowed; narrowing coercions must be explicit, as in Pascal:

B := round(A); {Go to integer nearest A}

B := trunc(A); {Delete fractional part of A}

Simple types

Varied precision: E.g., long int, double, short, or number of decimal places in COBOL or Ada

Enumerated types: user defined constant sequence. Implemented as an integer mapping. 
E.g. enum in C, user-defined types in Pascal.

Subranges of a base type.
Generally restricted to ordinal types. Not following the regular principle since it could apply to real types.

in Pascal:

TYPE
   ThermTempRange = -40..120;

Integer numeric data

Integers:

Binary representation is in 2's complement arithmetic

For 32-bit words:

Maximum value:  2³¹-1

Minimum value: -2³¹

Real numeric data

Float (real): hardware representations

Exponents usually biased

e.g., if 8 bits (you have 256 values) then +128 is added to exponent

• so coded exponent value of 128 is 128-128 = 0 as true exponent
• the coded exponent of 129 is 129-128 = 1 as true exponent
• and the coded exponent of 120 is 120-128 = -8 as true exponent

IEEE floating point format

IEEE standard 754 specifies both a 32- and 64-bit standard.

Numbers consist of three fields:

S: a one-bit sign field. 0 is positive.

E: an exponent in excess-127 notation. Values (8 bits) range from 0 to 255, corresponding to exponents of 2 that range from -127 to 128.

M: a mantissa of 23 bits. Since the first bit of the mantissa in a normalized number is always 1, it can be omitted and inserted automatically by the hardware, yielding an extra 24th bit of precision.

Examples:

• +1= 2⁰*1= 2^{127-127}*(1).0 (binary)     0 01111111 000000...
• +1.5= 2⁰*1.5= 2^{127-127}*(1).1 (binary) 0 01111111 100000...
• -5= -2²*1.25= 2^{129-127}*(1).01 (binary)1 10000001 010000...

This gives a range from 10^-38 to 10³⁸.

In 64-bit format, the exponent is extended to 11 bits giving a range from -1022 to +1023, yielding numbers in the range 10^-308 to 10³⁰⁸.

Other numeric data

Short integers (C) - 16 bit, 8 bit

Long integers (C) - 64 bit

Boolean or logical - 1 bit with value true or false

Byte - 8 bits

Character - Single 8-bit byte - 256 characters

• ASCII is a 7 bit 128 character code

In C, a char variable is simply 8-bit integer numeric data

Enumerations

typedef enum thing {A, B, C, D } NewType;

Implemented as small integers with values: A = 0, B = 1, C = 2, D = 3

NewType X, Y, Z;

X = A

Why not simply write: X=0 instead of X=A?

• Readability
• Error detection

Example:

enum { fresh, soph, junior, senior} ClassLevel;
enum { old, new } BreadStatus;

BreadStatus = fresh; //An error which can be detected

Decimal data

Fixed decimal in PL/I and COBOL (For financial applications). You see this in database data definition languages.  SQL has the DECIMAL attribute type.

DECLARE X FIXED DECIMAL(p,q);

• p = number of decimal digits
• q = number of fractional digits

Example of PL/I fixed decimal:

DECLARE X FIXED DECIMAL (5,3),
Y FIXED DECIMAL (6,2),
Z FIXED DECIMAL (6,1);

X = 12.345;
Y = 9876.54;

What is Z=X+Y?:   By hand you would line up decimal points and add:

0012.345
9876.540
9888.885 = FIXED DECIMAL(8,3)

• p=8 since adding two 4 digit numbers can give 5 digit result and need 3 places for fractional part.
• p=8 and q=3 is known before addition
• Known during compilation - No runtime testing needed.

Implementing decimal data

Algorithm:

1. Store each number as an integer (12345, 987654) Compiler knows scale factor (S=3 for X, S=2 for Y). True value printed by dividing stored integer by 10^S
2. To add, align decimal point. Adjust S by 1 by multiplying by 10.
3. 10*Y+X = 9876540 + 12345 = 9888885, Compiler knows S=3
4. S=1 for Z, so need to adjust S of addition by 2; divide by 10² (98888)
5. Store 98888 into Z. Compiler knows S=1

Note: S never appears in memory, and there is no loss of accuracy by storing data as integers.

Pointer type

Usually all addresses associated with a particular type

PL/I has just an ADDRESS type. This is easy to lose track of what should be dereferenced.

Pointers support recursive types.

TYPE LinkedListNode = RECORD
   data: Integer;
   next: LinkedListNode;
END;

The following is a solution that gives a fixed size to the record but dynamic in structure.

TYPE LLNodePtr = POINTER TO LLNode; /*known size*/
TYPE LLNode = RECORD
   data: Integer;
   next: LLNodePtr; /*this is known*/
END;

We see many examples of the use of pointers in C/C++ especially in the compiler project.

Files and strings

Files are objects and structures found outside the program module and are part of the operating system. Their access are accomplished through function and subroutine system calls. 

Courses such as operating systems, database management, etc consider these structures in great detail.

String issues in implementation

Each language has its own interpretation and implementation of strings.  Some treat strings as an array of characters, others as a simple type.

Static length strings are found in early languages of FORTRAN, COBOL and Pascal and Ada. 

Dynamic length strings are found in interpreted languages such as BASIC, LISP.  Support for dynamic strings are found in Java

Implementation of dynamic strings varies between using a terminating character (null byte) or using a byte or two to represent the length of the string.

String Declarations

Character Strings: Primitive object made up of more primitive character data.

Fixed length:

char A[10]; /** C  note A itself is a pointer to 10 bytes **/

DCL B CHAR(10); /** PL/I  **/

var C: packed array [1..10] of char; (** Pascal **)

Variable length:

DCL D CHAR(20) VARYING; /** PL/I - 0 to 20 characters **/

E = "ABC"  /** SNOBOL4 - any size, dynamic **/

char * F = "ABCDEFG\0";  /** C - any size, programmer defined **/
     /** F is a pointer into the string constant pool*/

String Operations

Usually expressed as built-in function.

• concatenation-- often expressed as an operator "+" or "." or even implied by adjacent strings
• length-- length of actual string or length of declared size
• substring-- extract a substring, usually not permitted to change a substring
• searching-- find a character or substring
• pattern matching-- use regular expressions to specify the pattern