CS 442 Principles of Programming Languages


Watch a video introduction to this course on YouTube.

Objectives

To provide an exposure to important abstractions and issues in contemporary programming languages. To explore fundamental programming methodologies, such as functional programming, logic programming, programming with abstract data types, and object-oriented programming. To provide an introduction to formalisms for describing programming languages.

Intended Audience

CS 442 is intended to be taken in the fourth year of a CS major academic plan. The course is of interest to students wishing to critically explore the breadth of programming methodologies. The course will be of interest to those involved in the construction of software in all application domains.

Related Courses

Prerequisites: CS 240; Computer Science students only.

Successors: Recommended for CS 486.

Hardware/Software

Used in Course: Standard UNIX environment with language compilers (Lisp or Scheme; standard ML; Ada, C++ or Modula-3; Prolog or CLP(R)).

Assumed Background: Some programming maturity, knowledge of data structures.

References

Types and Programming Languages, by B. Pierce, The MIT Press, 2002.

Schedule

3 hours of lectures per week. Normally available in Winter.

Outline

The Lambda Calculus (3 hours)

Reasoning about procedures and name binding. The untyped lambda calculus. Evaluation as substitution.

Functional Programming (6 hours)

Recursive functional programming. Introduction to a functional programming language. Procedures as parameters and return values. Continuations and coroutines.

Operational Semantics (3 hours)

Defining interpreters for programming languages. Environments and stores, dynamic and static scoping, functions and closures.

Data Types and Abstraction Mechanisms (12 hours)

Data types and data constructors. Parametric polymorphisms. Abstract data types and exceptions. Specifying ADTs. Module facilities: importing and exporting interfaces. Modules and data abstraction. Parameterized modules. Comparison of module facilities.

Object-oriented Programming (6 hours)

Objects as encapsulation of state. Objects and data abstraction. Classes and inheritance. Subtype polymorphism. Inheritance and subtyping. Introduction to an object-oriented language.

Logic Programming (3 hours)

Programming with Horn clauses. Unification and the logic variable. Backtracking, depth-first search, the Prolog cut. Constraint logic programming.