Data types II: record, union, pointer and type equivalence

The previous page was about types that hold single values. This page covers types that bring values together (record, union), types that point to other values (pointer, reference), and the compatibility of types with each other (type checking, type equivalence). The most asked on exams: the difference between a dangling pointer and a memory leak, free and discriminated unions, name and structure equivalence.

Golden rules:

1. Dangling pointer: a pointer that points to a deleted cell. Leak: a cell that nobody points to.
2. A free union is not checked, a discriminated union carries a tag.
3. Name equivalence = same name, structure equivalence = same structure.
4. Reference counting cannot collect cycles.

Record

A record is a collection of heterogeneous elements (fields) accessed by their names. Unlike an array, the elements can be of different types; access is by name, not index: emp.name. COBOL and C struct, classes and record in Java.

record P(int x, int y) {}
P p = new P(1, 2), q = new P(1, 2);
System.out.println(p.equals(q) + " " + (p == q));
System.out.println(p);

true false
P[x=1, y=2]

Field access is translated at compile time into a fixed offset, which is why it is fast. A tuple is similar to a record but the fields have no names (Python (3, "a"), ML); access is by position.

Union

A union is a type in which a variable can hold values of different types at different times during execution. All fields share the same memory.

• Free union (C, C++): nothing keeps track of which field is valid. No type checking.
• Discriminated union (Ada, ML, Haskell): a tag (discriminant) field says which type is valid; reading the wrong field is an error.

union { int i; float f; } u;
u.i = 1;
printf("%g", u.f);   /* the bits of the int are read as a float */

The float interpretation of the same bits can be shown with Java:

System.out.println(Float.intBitsToFloat(1));
System.out.println(Float.intBitsToFloat(1065353216));
System.out.println(Float.floatToIntBits(1.0f));

1.4E-45
1.0
1065353216

The integer 1 as a float is 1.4E-45; the bits of 1.0f as an int are 1065353216. A free union makes this confusion silently. Java and C# did not take unions at all; for reliability, inheritance is used.

Pointer and reference

A pointer holds a memory address or the special value nil (null). It has two uses: indirect addressing and dynamic memory management on the heap.

int a[5] = {10, 20, 30, 40, 50};
int *p = a;     /* p = &a[0] */
p += 2;         /* p = &a[2] */
/* *p + 1 = 31,  *(p + 1) = 40,  p - a = 2 */

A reference type (C++ int&, Java and C# class variables) points to an object but arithmetic cannot be done. In Java, references never point to freed memory, because freeing is the job of the garbage collector. That is why there are no dangling references in Java.

Pointer problems

Dangling pointer

A pointer that still holds the address of a freed (deallocated) heap cell.

int *p = new int(5);
int *q = p;
delete p;      // p and q now point to the freed cell

You can set p to nullptr, but you forget q. If that cell is later given to another variable, writing through q overwrites other data.

Lost heap-dynamic variable (memory leak)

An allocated heap cell that no pointer can reach anymore. These are called garbage.

int *p = new int;   // cell 1
p = new int;        // cell 2; cell 1 is LOST
int *q = p;         // q points to cell 2
p = new int;        // cell 3; cell 2 was saved thanks to q

The number of lost cells is 1. On an exam, number every new, and at the end write which pointer points to each cell. If nobody points to it, it is a leak; if something points to it but the cell is deleted, it is dangling.

Dangling pointer solutions

• Tombstone: an extra cell for each heap object; pointers point to this cell. When the object is deleted, the tombstone becomes nil. Cost: time and memory.
• Locks-and-keys: a pointer is a (key, address) pair; the heap cell carries a lock. On access key == lock is checked; the lock of a deleted cell is changed.
• Best: not giving the programmer the power to delete (Java, C#, LISP: garbage collection).

Heap management: garbage collection

A.next = B;  B.next = A;  root = A;  root = null;
reference count: A = 1 (from B), B = 1 (from A)  → neither is 0, not collected
mark-sweep: no path from the root to A → both unmarked → collected

Type checking and strong typing

Type checking is checking that the operands of an operator are of compatible types. A compatible type is either directly valid or can be converted automatically by the language’s rules (coercion). Using an operand of an inappropriate type is a type error.

If type bindings are static, checking can be done almost entirely at compile time; with dynamic type binding (JavaScript, Python) checking has to be done at run time. The earlier you catch an error, the cheaper it is to fix.

A strongly typed language: type errors are always caught. ML and F# are strongly typed. Java and C# nearly (an explicit cast can produce an error but it is caught at run time). C and C++ are not: free unions and pointer conversions are outside checking. Too much coercion reduces the benefit of strong typing.

Type equivalence

When are two types considered “the same”?

type Celsius = float;
type Fahrenheit = float;
c: Celsius;  f: Fahrenheit;
f := c;       name equivalence: ERROR     structure equivalence: valid

PITFALL · Ada anonymous types. In the line A, B : array (1..10) of Integer;, A and B are not equivalent: an anonymous type expression produces a separate type for each variable. For them to be equivalent, the type must be given a name first.

Common mistakes

class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } }
Point a = new Point(1, 2);
Point b = a;
b.x = 5;
System.out.println(a.x);

record P(int x, int y) {}
P p = new P(1, 2), q = new P(1, 2);
System.out.println(p.equals(q) + " " + (p == q));

int *p = new int(5);
int *q = p;
delete p;

int *p = new int;
p = new int;
int *q = p;
p = new int;

type Celsius = float;
type Fahrenheit = float;

A.next = B;  B.next = A;
root = A;
root = null;