Topics

In rough chronological order:

• Abstract syntax and operational semantics
• Functional programming with lists and recursion
• First-class and higher-order functions; continuations
• Functional programming with algebraic data types and static types (in ML)
• Type systems and parametric polymorphism
• ML type inference
• Object-orientation and inheritance
• ML Module System
• Lambda calculus; small-step semantics

Description

COMP105 is a course about the principles of programming languages and their application. The emphasis is on ideas and techniques relevant to practitioners, but includes theoretical foundations crucial for deeper understanding: abstract syntax, formal semantics, type systems, and lambda calculus. Work in the course involves exploring programming languages and features both as a user (by writing programs in those languages), as a language designer (by implementing interpreters for those languages), and as a scholar (by proving mathematical properties of them).

COMP105 is a survey course in programming languages. To succeed in this field, you will combine code and math. The goal of the course is to give you intellectual tools that will help you use, evaluate, choose, and design programming languages. You will learn to ask questions about language safety and classification of errors, type systems, formal semantics, and abstraction mechanisms for both functions and data.

COMP105 provides an introduction to the study of programming languages as an intellectual discipline. The elements of this discipline include specifications based on abstract syntax, lambda calculus, type systems, and dynamic semantics. You must be comfortable with recursion and with basic mathematical ideas and notations for sets, functions, etc.

COMP105 uses the case-study method to give you experience with languages that go beyond the simple imperative paradigm. Case studies will cover languages from the imperative, functional, and object-oriented families. Example languages may include Standard ML, Smalltalk, and Scheme.

Case studies are reinforced by suitable programming exercises. COMP105 assumes previous experience programming in imperative languages like C, C++, or Java. Good programming skills are essential, and we assume some knowledge of C. Plan to complete ten or twelve programming assignments over the course of the term. The more interesting or amusing assignments include Hindley-Milner type inference, arbitrary-precision arithmetic, and some game-playing programs.

COMP105 is recommended for graduate students, especially those whose primary research interests lie in related fields such as compilers, software systems, or artificial intelligence. Graduate students whose primary interests lie in programming languages may find that COMP105 overemphasizes programming practice and underemphasizes foundations.