PoPL Course Objectives and Syllabus
Table of Contents
This section is linked from the main course page.
1 Prerequisites
Some knowledge of discrete mathematics (sets, functions and relations). Programming in any programming language.
2 Objective
Why aspiring programmers and computer scientists should take this course and what they can expect to learn in it:
This course is an introduction to the principles behind the design and interpretation of programming languages.
2.1 What is a programming language?
A programming language is a medium that allows one to communicate and reason with abstract, computational ideas in a precise and constructive way. This precision also makes it possible for the program to run on a computer, among other things. Therefore, understanding the abstraction mechanisms in the language and their implementation is key to successfully using the language, ie., doing programming. If we allow for a more generous interpretation of "programming" and "programming languages" as any formal and semi-formal notation, we find often a need to create our own little programming languages when solving problems. Examples: BNF grammars, state diagrams, constraints, data languages like XML, schema, domain specific languages, database query languages, etc. The quality of this notation and our ability to understand and reason with them will be greatly enhanced by our knowledge of how these notations are designed and interpreted.
2.2 Approaches to Studying Programming Languages
2.2.1 Compiling
How does a program run? One way to answer this question is to understand that programs are translated (compiled) into another, lower-level language, which is executed by hardware. That is the stuff of a compilers course.
2.2.2 Mathematical specification of programming languages
Another way to think of programs and programming languages is that they are mathematical objects. Programming languages draw their foundations from mathematical logic, universal algebra and the theory of computation. Consider this statement by the mathematician and computer scientist Gregory Chaitin:
The computer and programming languages were invented by logicians as the unexpected by-product of their unsuccessful effort to formalize reasoning completely.
The meaning of every program is given by a mathematical specification of the semantics of its underlying programming language. Three main approaches exist: denotational, where programs and the programming language are mapped to a set of continuous functions over complete partial orders, operational, where the meaning of a program is explicated as a sequence of transition rules on a virtual machine, or axiomatic semantics, where programs are thought of as predicate transformers. The mathematical semantics approach will be taught in an advanced course.
2.2.3 Definitional Interpreters
In this course, we take a different, but related approach. We build a series of interpreters, each a virtual machine for a mini language with specific features. This approach draws from the denotational and the operational formalisms, but couches them in the notation of a programming language, viz., Scheme. The bulk of the course will therefore be driven by studying and constructing definitional interpreters in Scheme. Using this approach we study standard features of procedural languages like abstract syntax, lexical scoping, stack architectures, parameter passing, environments and store, and also more advanced features like computational effects, continuations, exceptions, threads, and type reconstruction, and object-oriented and logic programming.
3 Utility and Learning outcomes
PoPL is useful because it encourages the student to think about software artefacts as virtual machines, with a well-defined interface (a programming language) and an internal structure consisting of symbolic structures operating according to well-defined rules. With a background in the Principles of Programming Languages, one starts thinking about the quality of a software artefact by relating it to the properties of the virtual machine that is implicitly defined underneath it.
More concretely, a student graduating from a PoPL course should be able to perform each of the following sample tasks:
- Identify the abstract syntax of any programming language like C or Java
- Design small, domain purpose languages like a language for propositional logic, or an object language, or a language for pattern matching from scratch and implement them either as interpreters or embeddings in another language.
- Analyse and critique the design of programming languages like C, C++ or Python.
- Specify the structure of a software application like a spreadsheet or a word processor in terms of its interface as a language of user operations and its internal structure as a virtual machine.
4 Texts
- How to Design Programs
- by Felleisen, Findler, Flatt and Krishnamurti, MIT Press, Available in PHI and also online at http://www.htdp.org . This will be used in the initial part of the course for the student to pick up Scheme.
- Essentials of Programming Languages 3rd Ed.
- by Friedman and Wand, MIT Press 2007, Available in PHI. This is the main text book.
- Structure and Interpretation of Computer Programs
Abelson and Sussman. Available online
- Programming Languages: Application and Interpretation
by Shriram Krishnamurti. Available online http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/
This book is for additional readings.
5 Syllabus
Values, types and expressions. Abstract syntax. Contract Backus-Naur form. Block structure and lexical environments. Scope and binding. Procedures and closures. Recursion. Implementing recursion. Stores. Computational effects. Explicit and implicit references. Implementing mutation. Expressible and denotable values. Parameter passing. Tail recursion. Iterative systems. Continuation-passing style (CPS). Converting to CPS. Continuation-passing interpreters. Trampolining. Imperative interpreters. Modeling exceptions and threads.
If time permits: Type checking and Type reconstruction. Logic Programming.
6 Grading
Please see the main course page