Programming Languagues Study Notes
Notes I studied from before the PL final exam in Fall 2021.
Heap Management / Garbage Collection
1. Reference Counter (Eager Approach)
- Maintains a counter in every cell, stores number of pointers currently pointing to that cell
- When counter drops to 0, reclaim cell
2. Mark & Sweep (Lazy Approach)
- Recursively follow all live pointers, mark them as useful
- Sweep over entire heap & reclaim unmarked cells
- Also turns off markers
3. Stop & Copy (Lazy Approach)
- Splits heap in half, all new allocations go to the active half
- Recursively follows all live pointers, copy discovered structures to the active half, which now becomes the active half
- Inactive half now only contains garbage; it can be reclaimed
4. Generational Copies
- Keeps track of cell lifetimes and collect long lifetime structures less
frequently
- Lifetime: how many collections they survived
5. Escape Analysis
- Is lifetime of pointer restricted to current procedure?
- YES: value can be stored on stack, which do not need to be allocated or freed
Overriding vs. Overloading
1. Overriding
- Overriding implements runtime polymorphism (virtual)
- Occurs between superclass and subclass
- Methods have same signature (same name & arguments)
- Method to call determined at runtime based on object time
2. Overloading
- Overloading implements compile time polymorphism
- Occurs between methods in the same class
- Method names are same, different parameters
- Method to call determined at compile-time
Static Binding vs. Dynamic Binding
1. Static Binding
- Static binding occurs at compile time & remains unchanged
- Type specified through default conventions
- Static typing w/o explicit declaration (e.g. auto)
- “int x” - type info. supplied in source code and known at compile time
2. Dynamic Binding
- Dynamic binding occurs at runtime (during execution) & can change
- Type specified through runtime polymorphism
- Variable bound to a type when assigned a value
- High cost: run-time type checking & interpretation
Prolog
% Tail recursion for length of list
len_acc([], Acc, Acc) :- !.
len_acc([_|T], Acc, Result) :- Acc2 is Acc + 1,
len_acc(Tail, Acc2, Result).
len(Lst, Result) :- len_acc(Lst, 0, Result).
% Tail recursion for factorial
fac_acc(0, Acc, Acc) :- !.
fac_acc(N, Result, Acc) :- N2 is N - 1,
Acc2 is N * Acc,
fac_acc(N2, Result, Acc2).
fac(N, Result) :- fac_acc(N, Result, 1).
% Max of list
max_acc([], Acc, Acc]) :- !.
max_acc([Head|Tail], Result, Acc) :- Head > Acc,
max_acc(Tail, Result, Head).
max_acc([Head|Tail], Result, Acc) :- Head <= Acc,
max_acc(Tail, Result, Acc).
max([H|T], Result) :- max_acc([H|T], Result, H).