CMSC 631, Fall 2004
Program Analysis and Understanding
evaluations will be available 11/19-12/10. Please take the time
to fill one out.
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.
There is no required textbook for this course. Instead, most weeks we
will read 1-3 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
- 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
- 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
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.
- Homework (10%) There will be short weekly written
assignments to give you an opportunity to practice the material we
will go over during lecture.
- Programming Assignments (20%) There will be bi-weekly
programming assignments in which you will implement some of the ideas
- Project (35%) 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
during the semester.
- Class particiation and paper presentations (10%) 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
- Final Exam (25%) In addition to the project, this course
will be graded based on a final exam. The final exam will cover
material from the homeworks and programming assignments.
Programming assignments are due at midnight on the due date.
Programming assignments may be turned in late until 9am the next
morning. Late submissions receive a 0.9 multiplier. Programming
assignment submission instructions will be provided later.
Written assignments are due at the beginning of class on the due
date. Written assignments may not be turned in late.
If you cannot make a due date because of extenuating circumstances, or
because it conflicts with a religious holiday, please inform the
instructor as soon as possible.
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.