# Skills

This page lists all technical skills of relevance to this class,
as a study guide. If you find that you possess all the skills
listed here, you can consider yourself to have mastered the class.
The final exam will draw its expectations from this list: each
question in the exam can be solved by using
*and combining* the skills listed here, basic arithmetic, and
general computer science knowledge from the undergraduate core
classes.

Some skills (marked by a ★) are *prerequisites*. They
may be partly or fully covered in class, but you will be able to
find a more thorough treatment in the accompanying literature.

Note that the list will be changing during the course.

## Concepts

For each concept (maked in**bold-face**below) be able to do the following:

- Give matching examples
- Distinguish it from other concepts
- Explain its relationship to any other concepts (is-part-of, is-alternative-to, is-generalisation-of etc.)
- Explain the
*purpose*or*utility*of the concept

## 1. Syntax

- ★ Be able to read
**BNF grammars** - ★ Derive a
**parse**for a given input phrase according to a given BNF grammar - Distinguish between
**concrete syntax**and**abstract syntax**

## 2. Semantics

- ★ Evaluate a program according to an
**operational semantics**, including**stores** - ★ Undestand the difference between
**expressions**and**values** - Understand notions of
**names**and**bindings**, as well as**binding time**s - Understand
**scopes**, both static and dynamic, as well as**referencing environments** - Understand the differences between
**static**,**stack-dynamic**, and**heap-dynamic**storage - Understand
**arity**,**fixity**, and**precedence**, and**associativity**of operators - Be able to explain the notion of
**referential transparency** - Be able to differentiate between operators that use
**short-circuit evaluation**and those that don't - Be able to utilise
**assignments**,**blocks**, and**conditional statements**including**multiple selection**statements in your programming - Understand the difference between
**logically controlled**and**variable controlled**loops - Be able to describe
**pre-test**and**post-test**loops - Subprograms:
- Understand the difference between
**declaring**,**defining**, and**invoking**subprograms - Familiarity with basic terms surrounding subprograms, specifically
**formal parameters**and**actual parameters** - Understanding of
**default parameters** - Understanding of
**keyword parameters** - Understanding of
**variable parameters** - Understanding and ability to use
**indirect subprograms** - Understanding of the importance of
**parameter-passing order** - Understanding of the semantics of various parameter passing modes:
**pass-by-value**,**pass-by-result**,**pass-by-value-result**,**pass-by-reference**, and**pass-by-name** - Meta-Programming:
- Understand the notions of
**staged computation**and**meta-program** - Be able to read or write a
**meta-program**

- Understand the notions of
- Understand the purpose and value of
**reflection**in programming languages

## 3. Assembly and Systems Programming

- ★ Understand the difference between
**registers**and**random-access memory (RAM)** - ★ Understand the
**two's complement representation of integers** - ★ Understand the use of
**stack memory** - ★ Read and write C code
- Read and write simple
**2OPM assembly**programs, given a description of all relevant operations - ★ Understand the concept of
**arithmetic overflow**

## 4. Programming Language Implementation

- Understand the differences between
**interpretation**,**(static) compilation**, and**dynamic compilation** - Distinguish the tasks of compiler
**frontends**,**middle-ends**, and**backends** - Can describe the purpose of a language
**run-time system** - Be able to implement
**pre-test**and**post-test**loops in assembly - Understand the standard mechanisms for implementing subprograms discussed in class, including
**pass-by-value**,**pass-by-result**, and**pass-by-reference**parameters - Be able to implement
**closure**creation and invocation - Be able to utilise
**type descriptors**to represent dynamic type information - Understand
**boxing**and**unboxing**of primitive values - Be able to implement and use
**virtual method tables**for dynamic dispatch - Understand the functionality of
**selector tables**for dynamic dispatch - Understand how
**dynamic compilation**, including**just-in-time compilation**and**dynamic optimisation**, can be implemented effectively - Understand the utility of
**Profile-Directed Optimisation** - Understand the use of
**trampoline code**in the implementation of dynamic compilation

## 5. Types

- Understand the notions of
**strong typing**and**type safety** - Understand the differences between
**dynamic typing**and**static typing** - Ability to utilise
**primitive types**, including common types such as booleans and integers - Ability to utilise
**product types** - Ability to utilise
**sum types**, including**tagged unions**and**untagged unions** - Ability to utilise
**enumeration types** - Ability to utilise
**function types** - Understanding of the notion of
**type equality**, specifically**nominal type equality**and**structural type equality** - Ability to utilise
**reference type** - Understanding of when a type is
**lifted**and when it is not - Ability to distinguish between
**ad-hoc polymorphism**,**parametric polymorphism**and**subtype polymorphism** - Understanding of
**overloading**and**implicit coercions** - Ability to take advantage of
**parametric polymorphism** - Familiarity with
**subtyping**, including the**arrow rule**for function type subtyping - The ability to use Algorithm
*W*for**type inference**in the monomorphic case - Ability to abstract types with type variables into
**type schemas**and to**instantiate**type schemas - Understand when and how subtyping applies to
**object types** - Ability to correctly utilise
**variance**for type specifications, both for**definition-site**and for**use-site**variance

## 6. Object Orientation

- Understand the differences between
**subclassing/inheritance**,**subtyping**, and**dynamic dispatch** - Understand the concept of
**instantiation**of**classes**into objects - Understand the semantics of
**dynamic dispatch** - Understand and be able to explain the
**Diamond Problem**

## 7. Automatic Memory Management

- Understand the motivation behind
**automatic memory management** - Understand the differences between
**reference counting**and**tracing garbage collection** - Understand the notion of a
**root set**and how such a root set is determined at run-time, including the use of**stack maps** - Understand the
**tracing**process of tracing garbage collection and how dynamic type information can be used to implement it - Understand the basic
**mark and sweep**algorithm for automatic garbage collection - Understand
**Cheney's copying collector**for automatic garbage collection - Understand the motivation (
**weak generational hypothesis**) and purpose behind**generational garbage collectors**and the principal implementation challenge they face in the form of**entry tables/remembered sets**

## 8. Program Analysis

- Understand the components of a
**lattice**and be able to use one to model information in program analysis - Understand the notions of
**soundness**and**precision**in the context of program analysis - Understand the notions of a
**conservative**program analysis - Understand
**control-flow graphs**and be able to read and construct them, with and without**labels**and**basic blocks** - Understand the difference between an
**interprocedural**and an**intraprocedural**program analysis - Understand the notions of
**context-sensitivity**and**flow-sensitivity**in the context of program analyses - Understand the notion of
**call graphs**, with and without**call-site sensitivity** - Understand the notion of
**procedure summaries**and how and why they are useful - Understand the notion of
**Dynamic Program Analysis**and the relative strengths and disadvantages of**counting**and**sampling**strategies

## 9. Data Flow Analysis

- Understand the notions of
**transfer functions**and**join functions**in the context of Data Flow analysis - Understand the notion of
**monotone frameworks**with their notions of**bounded lattice height**and**monotonicity** - Understand the notion of
**distributive frameworks**and how they specialise monotone frameworks - Understand the notion of
**paths**in the context of (interprocedural) Data Flow analysis - Understand the notion of
**call strings**in the context of interprocedural Data Flow analysis - Understand how bounding the shape of call strings can be used to implement a precision/performance trade-off in
**interprocedural Data Flow analysis**

## 10. Abstract Interpretation

- Understand the notions of
**representation functions**and**abstract domains** - Understand the notions of
**abstraction functions**and**concretisation functions** - Understand the notion of a
**Galois Connection**and a**Galois Insertion**, and how they can be used to derive program analyses.

## 11. Optimisations

- Understand the purpose and effect of the
**inlining**optimisation - Understand why the
**loop-invariant code motion**optimisation is important and under what conditions it is applicable - Be able to explain how program analysis supports compiler optimisations
- Be able to apply
**guarded inlining**to optimise a program - Understand the notion of
**on-stack replacement**

## 12. Points-To Analysis

- Understand the purpose and value of
**points-to analysis** - Understand
**Steensgaard's Points-To Analysis** - Understand the key differences between
**Steensgaard's**and*Anderson's Points-To Analysis*