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:

1. Syntax

  1. ★ Be able to read BNF grammars
  2. ★ Derive a parse for a given input phrase according to a given BNF grammar
  3. Distinguish between concrete syntax and abstract syntax

2. Semantics

  1. ★ Evaluate a program according to an operational semantics, including stores
  2. ★ Undestand the difference between expressions and values
  3. Understand notions of names and bindings, as well as binding times
  4. Understand scopes, both static and dynamic, as well as referencing environments
  5. Understand the differences between static, stack-dynamic, and heap-dynamic storage
  6. Understand arity, fixity, and precedence, and associativity of operators
  7. Be able to explain the notion of referential transparency
  8. Be able to differentiate between operators that use short-circuit evaluation and those that don't
  9. Be able to utilise assignments, blocks, and conditional statements including multiple selection statements in your programming
  10. Understand the difference between logically controlled and variable controlled loops
  11. Be able to describe pre-test and post-test loops
  12. Subprograms:
    1. Understand the difference between declaring, defining, and invoking subprograms
    2. Familiarity with basic terms surrounding subprograms, specifically formal parameters and actual parameters
    3. Understanding of default parameters
    4. Understanding of keyword parameters
    5. Understanding of variable parameters
    6. Understanding and ability to use indirect subprograms
    7. Understanding of the importance of parameter-passing order
    8. 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
  13. Meta-Programming:
    1. Understand the notions of staged computation and meta-program
    2. Be able to read or write a meta-program
  14. Understand the purpose and value of reflection in programming languages

3. Assembly and Systems Programming

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

4. Programming Language Implementation

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

5. Types

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

6. Object Orientation

  1. Understand the differences between subclassing/inheritance, subtyping, and dynamic dispatch
  2. Understand the concept of instantiation of classes into objects
  3. Understand the semantics of dynamic dispatch
  4. Understand and be able to explain the Diamond Problem

7. Automatic Memory Management

  1. Understand the motivation behind automatic memory management
  2. Understand the differences between reference counting and tracing garbage collection
  3. Understand the notion of a root set and how such a root set is determined at run-time, including the use of stack maps
  4. Understand the tracing process of tracing garbage collection and how dynamic type information can be used to implement it
  5. Understand the basic mark and sweep algorithm for automatic garbage collection
  6. Understand Cheney's copying collector for automatic garbage collection
  7. 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

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

9. Data Flow Analysis

  1. Understand the notions of transfer functions and join functions in the context of Data Flow analysis
  2. Understand the notion of monotone frameworks with their notions of bounded lattice height and monotonicity
  3. Understand the notion of distributive frameworks and how they specialise monotone frameworks
  4. Understand the notion of paths in the context of (interprocedural) Data Flow analysis
  5. Understand the notion of call strings in the context of interprocedural Data Flow analysis
  6. 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

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

11. Optimisations

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

12. Points-To Analysis

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