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

• Append/Prepend

e.g., 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)

TODO I don’t understanding returning head and tail’s explanation

Union

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

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

These things are useless in OOP languages.

• Useful in C 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 from creation to deallocation.

• We must be wary of dangling pointers/references and doing stuff like never deallocating stuff and causing memory leaks.

Example: Memory Leak

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 causing dead pointers.

// Aliasing
p \to 0x0
q \to 0x0
// Free q
free q
// p has no idea it points to junk

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 counter are usually only used for a few milliseconds