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 cs.umd.edu
Office Hours	TuTh 10am-11am, or by appointment

Description

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:

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.
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.
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.

Readings

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:

What are the main contributions/key ideas of the paper? What do you think of those ideas?
What was unclear in the paper? What do we need to discuss in class?
What are some unsatisfactory aspects of the paper?
How does this paper relate to others we have covered in class?
If the paper describes an implementation, is it available? Has it been used by other people? Have the ideas made it out to standard practice?

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.

Project (40%) Students will be expected to complete a substantial research project during the semester on a topic related to the class. Projects may be completed individually or in groups of at most 2. The expectations for group projects will be twice that of individual projects. Students will write up the results of their project and give a brief presentation to the class and other interested parties at the end of the semester. More details about the project, as well as some project suggestions, will be made available at or near the beginning of the semester.
Class particiation and paper presentations (20%) Students will be graded on their contributions to class discussion and to the discussion on the wiki. Additionally, each student will give a lecture during the second half of the semester on one or two assigned papers; a list of these papers will be available in the middle of the semester.
Midterm and/or Final Exam (40%) In addition to the project, this course will be graded based on a midtern and/or final exam. As preparation, there will be written assignments during the semester (mostly towards the beginning).

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.