Record

Record: Aggregates multiple values of potentially different types.

• Every element gets its own name, too.

// Declaration
record Student is
  string first-name
  string last-name
  int id
end record
// Instantiation
Student freddy := new Student
tag first-name := "Friedrich"
tag last-name := "Engels"
tag id := 1895

Tuple

Tuple; Aggregates values of potentially different types.

• Every element is anonymous (access via position).

In most languages, tuples are immutable.

More on Tuples and Records — Object Oriented languages lack records because they already have objects. Tuples are also unnecessary if you have arrays.

• Simpler languages like C and Rust tend to have records.
• Functional languages tend to have tuples.

Lists

List: ADT defined as a sequence of element, usually of the same type.

Appears in the definition of some languages.

• e.g., Functional languages can’t have arrays (arrays need constructive updates, which are forbidden), so they define lists in their language.

Implementation

1. Linked List: The obvious.

2. Array: You could also implement a linked-list with arrays (e.g., buffered arrays, etc.)

In functional languages, option 1 is the only option.

Other Operations

• Appending/Prepending

Note — If you have singly-linked list, prepending is O(1), but appending is O(n).

• Computing length
• Reverse lookup
• Element retrieval
• Returning head and tail (first element and rest of list, respectively)

Union

Union: Data types that are the union multiple other data typrs

• Use: Tree-handling functions, compilers, functions that can return multiple types.

Note — These things are useless in OOP languages.

• They are used in C though, because you lack polymorphism.

// Define
union U is
    int x
    String S
end union
// Usage
U a := new U
int b := 42
int c := TODO

Pointers and References

Variables that hold memory addresses (L-values).

• References: Read-only, the thing in memory cannot be manipulated.

char* str = "Hello";
str += 1;
print str;
// "ello"

String str = "Hello";
// can't do str += 1; 

Lifetime and Scope

In most languages, pointers and references are always active from creation to deallocation.

• We must be wary of dangling pointers/references and forgetting to deallocate (memory leaks).

func f is
  ...
  D x := new D
  ...
  // (end without deallocating)
end f

Another issue is aliasing, where we can have two references to the same thing and don’t fully deallocate (dangling pointers).

// Aliasing
p \to 0x0
q \to 0x0

// Free q
free q
// p has no idea it points to junk

Type Compatability

Two types are compatabile if we can assign one type to another.

Garbage Collection

Garbage Collector: Runtime support program that periodically identifiers and deallocates garbage.

• Garbage: Any resource which will not be used by the program in future compilations.
• Garbage collection is undecidable*
• Solves memory leaks and dangling pointers.
• Typically runs every few hundred milliseconds.

Practice — In practice, because GC is undecidable, we simplify the definition to be “garbage is unreachable resources”

• i.e., stuff without pointers to it

Algorithm: Naive Mark and Sweep

1. Mark: Traverse through every variable/object/field accessible from the top context (and their children).
   • Whenever something new is reached, mark it.
2. Sweep: Deallocate all unmarked resources.

Memory leaks happen in the heap — Notice how you only have to do this on the heap, as stuff is never deallocated on the stack.

Algorithm: Generational Mark and Sweep

Generations:

1. Break the heap into multiple generations.
2. After some fixed time, you promote an object to the next (older) generation.

We’ll garbage collect more often from the younger generation than the older generations.

• This dramatically reduces the amount of work we have to do marking and sweeping.

Why — Objects with a limited lifetime usually have a really short lifetime.

• e.g., Variables in a typical function or loop are usually only used for a few milliseconds. If it lasts longer than a few ms, it’s probably going to be alive for very long.

Type Equivalence

Two types T and S are equivalent, if whenver one is expected, the other may be used.

Example:

We say type S is compatible with type T if anything of type S can be assignment to type T