CMSC 631, Fall 2003

Program Analysis and Understanding

Basic Information

Location CSIC 3120, TuTh 3:30-4:45pm
Final Exam Take home: start Thursday 12/11 at 5pm, due Friday 12/12 at 5pm in instructor's office
Instructor Jeff Foster
4129 A.V. Williams
jfoster at
Office Hours TuTh 10am-11am, or by appointment


This core course is about techniques for analyzing and understanding software artifacts. Ultimately, the goal of this area of study is to improve the quality of software. In this course, we will cover three related areas of programming language research:

  1. Static analysis. This is the main focus of this course. Static analysis is the name for any automatic technique that reasons about a program's source code. Abstract interpretation underlies any practical static analysis tool. We will discuss data flow analysis, the classical technique used in optimizing compilers. We will also study type systems, which have been gaining popularity in program analysis recently, theorem proving, which can perform deep reasoning about software, and model checking, which has traditionally been applied to hardware. In addition to static analysis, we will also look at dynamic program analysis techniques and the interaction between static and dynamic analysis.
  2. Formal systems. In order to develop techniques for analyzing software, we must agree on a notation for talking about programs. We will discuss lambda calculus, which is a convenient archetypical programming language to study. And we will use techniques from axiomatic, denotational, and operational semantics as a foundation for reasoning about programs. In all cases, our study of formal systems will be undertaken with the goal of developing practical tools and ideas.
  3. Programming language features. The presence or absence of features in a programming language greatly affects techniques for analyzing and understanding programs written in that language. In order to enlarge our view of programming, we will look at standard imperative programming, functional programming, and object-oriented programming. We will also study memory management in programming languages and other features such as polymorphism.

The course catalog blurb: Techniques for static analysis of source code and modern programming paradigms. Analysis techniques: data flow analysis, program dependence graphs, program slicing, abstract interpretation. The meaning of programs: denotational semantics, partial evaluation. Advanced treatment of abstraction mechanisms: polymorphic types, operation overloading, inheritance, object-oriented programming and ML-like programming languages.

Prerequisite: CMSC 430 or equivalent. Most of the material covered in a typical compilers course (CMSC 430) will not be used in this class, so even if you have not taken such a course you may be perfectly fine in 631. Contact the instructor if you are interested in the taking 631 but aren't sure if you have the background.

For a more detailed list of possible topics, please see last year's version of the course, although this year the topics covered will not be exactly the same.


There is no required textbook for this course. Instead, most weeks we will read 2-4 papers, which will either be available electronically on the web or will be handed out in class.

We will use the class wiki to briefly discuss each paper before class. In particular, students will be required to participate in the discussion by posting at least once in the wiki about each paper. The topics covered in the discussion should be:

Clearly some of these points will be easier to address than others, and the first student to post will have the luxury of answering the easiest question they like (e.g., by posting a summary of the contributions). Later posts must take earlier posts into account--re-posting previously-covered material will not get you much credit.

The discussion for each paper ends at noon on the day of class. Any comments posted after that time will not be considered in your grade. (And attempting to hack the wiki server to change the revision history or the time will be considered academic dishonesty!)

Grading and Expectations

As always, these expectations are subject to change.

Academic Dishonesty

The college policy on academic dishonesty is strictly followed. All graded materials (whether exams, wiki comments, presentations, or projects) must be strictly individual efforts. In the case of a group project, only collaboration within the group is permitted.

Valid HTML 4.01!