CSCI 3155, Summer 2007: Skills

Below are the skills you are expected to acquire during this course. This list will grow as the course progresses and help you focus on what is expected of you. Mastery of all skills will give you the neccessary background to complete roughly 80% of the questions in the exams and exercises. The remaining 20% will be synthesis questions.

Skill set #1: Language Critique

The book provides a convenient common framework for arguing about the benefits and disadvantages of language features and programming languages in general. Table 1.1 and, more generally, Chapter 1 in the book describe a number of axes along which the effect of language features and the qualities of languages can be measured.
  1. You should be able to recall and describe all the characteristics listed in Table 1.1, as well as the three basic criteria listed therein.
  2. For some language feature, you should be able to recognise the characteristics affected by that feature.
  3. For some language feature, you should be able to recognise how the feature affects the language, based on the three criteria from Table 1.1.
  4. For two related language features, you should be able to compare them, based on the three criteria from Table 1.1.

Skill set #2: Syntax

Syntax describes the possible structure (or form) of programs of a given programming language. Backus-Naur Form (BNF) grammars have emerged as the standard mechanism for describing language syntax. BNF grammars used to describe languages when communicating with language adopters and compiler implementors. There are also many tools (particularly the yacc and antlr families of programs) for automatically generating parsers, programs that recognise whether an input program matches a grammar and, if it does, execute user-defined actions upon encountering certain language constructs.
  1. You should be able to determine whether a given property of a language is part of the syntax, of the static semantics, or of the dynamic semantics.
  2. You should be able to read a BNF grammar and understand the difference between terminals and nonterminals.
  3. Given a BNF grammar, you should be able to write down examples of programs that can be generated by the grammar.
  4. Given a BNF grammar, you should be able to tell whether a given program can be generated by the grammar. If the program is generated by the grammar, you should also be able to generate a parse tree for the program.
  5. You should be able to determine whether a given BNF grammar is ambiguous.
  6. Given a BNF grammar, you should be able to determine the associativity of any operator used therein.
  7. You should be able to describe the difference between an object language and a meta-language.

Skill set #3: Basic Denotational Semantics

Semantics describe the meaning of a program. Unlike syntax, there is no generally agreed-upon formalism for semantics among programming language developers or researchers. Of the various proposals, denotational semantics present the easiest description, particularly for programs without recursion or goto. Furthermore, denotational semantics provide a good foundation for understanding the notion of an interpreter, a program which takes a program and executes it step-by-step.
Note that you do not have to understand the notion of environments or their use in denotational semantics for any of these skills.
  1. You should be able to read a specification of basic denotational semantics.
  2. Given a basic denotational semantics and a parse tree (or unambiguous expression), you should be able to compute the semantics of a program.
  3. Given a basic denotational semantics and a BNF grammar, you should be able to tell whether any parts of the semantics are undefined.
  4. Given an understanding of what a state-free expression language is supposed to do, you should be able to write down a basic denotational semantics for it, including error handling rules.

Skill set #4: Bindings and Lifetime

Bindings are a general language concept that associates variables with a number of properties. The most prominent of these are type, storage location (called, less generally, address in the book) and value. Bindings may happen statically, at compile time, or dynamically, at run-time. While there are further possible distinctions (as mentioned in the book), we will be focussing on the static/dynamic separation.
  1. You should understand the difference between static and dynamic type binding and be able to take advantage of either property in your programming.
  2. Given a syntax, a compiler and a run-time system for a language, you should be able to determine whether the language is using static or dynamic type binding.
  3. You should understand the differences between static, stack-dynamic, explicit heap-dynamic, and implicit heap-dynamic binding.
  4. Given a syntax, a compiler and a run-time system for a language, you should be able to determine which storage binding(s) the language is using.

Skill set #5: Scoping

For any definition, be it type of variable, the scope determines the definition's extent, i.e., the parts of the program to which it is visible. There are two major approaches to scoping: static scoping and dynamic scoping.
  1. You should understand the difference between static and dynamic scoping and be able to exploit either in your programming.
  2. Given a language implementation, you should be able to write a program to determine whether the language uses static or dynamic scoping.
  3. Given a Mystery program and its output, you should be able to determine which scoping rules might have produced the output.

Skill set #6: Parameter Passing

Subprograms (procedures, functions, methods) are essential to any interesting program. Subprograms are usually not entirely fixed in what they do: instead, they are parameterised, i.e., they can be configured to some extent. For example, a factorial function has a parameter that indicates which factorial it should compute, and a print procedure has a parameter indicating the text it is supposed to print.
The book describes five different ways in which such parameters can be passed to functions: Pass by value, pass by result, pass by value-result, pass by reference, and pass by name.
  1. You should understand the differences between the five different parameter types and be able to exploit these differences in your programming.
  2. Given a language implementation, you should be able to write a program to determine which parameter passing modes the language uses in which situation.
  3. Given a Mystery program and its output, you should be able to determine which parameter passing modes might have produced the output.

Skill set #7: Basics of Types

  1. You should understand the differences between static typing, dynamic typing, strong typing, and weak typing.
  2. You should be able to exploit and expose static and dynamic typing in your programming.
  3. You should know what ordinal types, subrange types, and enumeration types are.
  4. You should be able to use subrange types and enumeration types in your programming.
  5. You should understand the difference between structural type equality and name type equality.
  6. You should be able to exploit and expose the difference between structural and name type equality in your programming.
  7. You should understand the notion of a type constructor
  8. You should understand the difference between tagged and untagged union types and be able to use them in your programming.

Skill set #8: Arrays

Sebesta discusses five different classes of arrays:
  1. You should be able to distinguish between static, stack-dynamic, and heap-dynamic arrays and use them in your programming.
  2. You should understand associative arrays and use them in your programming.

Skill set #9: Pointers and References

  1. You should be able to distinguish between pointers and references, and use either in your programming.
  2. You should know what the dangling pointer problem is.
  3. You should know what garbage in the context of heap management is.
  4. You should understand the difference between mark and sweep garbage collection and reference counting.

Skill set #10: Subtyping

  1. You should understand what a subtype is
  2. You should understand the concepts of widening and narrowing conversions
  3. You should understand the difference between explicit and implicit conversions
  4. Given a language with subtyping, you should be able to exploit the subtyping rules in your programming

Skill set #11: Control Constructs

  1. You should understand how a CASE/SWITCH statement works and use it in your programming.
  2. You should understand the difference between FOR and WHILE loops and use them in your programming.

Skill set #12: Subprograms

  1. You should know what a higher-order function is and how to use it in your programming.
  2. You should understand the notion of parameter evaluation order and be able to expose it in your programming.
  3. You should understand the notion of overloading and be able to employ it in your own programming.
  4. You should understand the notion of short-circuit evaluation and be able to employ it in your programming.

Skill set #13: Functional Programming

  1. You should be able to read core ML programs.
  2. You should understand the purpose of a let expression.
  3. You should understand the notion of an anonymous function.
  4. You should understand and be able to explain the notion of referential transparency.
  5. You should understand the notions of tuples and lists and be able to distinguish them.
  6. You should be capable of writing nontrivial recursive programs.
  7. You should be capable of converting a loop into a recursion.
  8. You should be able to construct and deconstruct values of algebraic datatypes.

Skill set #14: Advanced Types (functional)

  1. You should understand the notion of a function type and be able to explain and derive it.
  2. You should understand the notion of a tuple type and be able to explain and derive it.
  3. You should understand the notions of type variables and polymorphic types and be able to explain and derive them.
  4. You should understand the notion of type inference and be able to explain and utilise it in your programming.
  5. You should understand the notion of algebraic datatypes and be able to explain and utilise them in your programming.

Skill set #15: Abstract Datatypes

  1. You should understand what abstract datatypes are and be able to explain the concept.
  2. You should be able to construct abstract datatypes in an object-oriented language such as C++ or Java, and in SML.
  3. You should be able to construct generic abstract datatypes, using parametric polymorphism.

Skill set #16: Object-Oriented Programming

  1. You should be able to understand and utilise the notion of dynamic dispatch in your programming.
  2. You should understand the notion of inheritance and utilise it in your programming.
  3. Given a programming language with dynamic dispatch and a program in that language, you should be able to determine when which method is invoked.
  4. You should be able to distinguish subtyping from subclassing.
  5. You should understand what method overriding is and be able to employ it.

Skill set #17: Advanced Types (object-oriented)

  1. You should understand the subtyping rules for functions and methods.
  2. You should understand the notion of a Java Interface and be able to utilise it in your programming.
  3. You should understand the subtyping rules for classes and interfaces.
  4. You should be able to integrate parametric and subtype polymorphism.

Skill set #18: Exceptions

  1. You should understand the notion of an exception and be able to utilise it in your programming.
  2. You should understand the notion of an exception handler and be able to utilise it in your programming.
  3. In the presence of subtyping, you should be able to match up exceptions and exception handlers in an object-oriented program.
  4. You should understand and be able to use a finally clause in Java.
  5. You should understand the difference between checked and unchecked exceptions and be able to explain it.