CS412 : Introduction to Program Analysis 2001-2002
Welcome to the course homepage. Your course instructor is Uday Khedker.
You will find the latest
announcements highlighted in this colour.
Please ensure that your browser does not hide the back ground colour of this
statement.
Announcements
This course is scheduled in slot 6 implying that we will have lectures as per
the following schedule :
| Day | Time |
|---|
| Monday | 11:30 |
| Thursday | 08:30 |
| Friday | 11:30 |
Overall Plan
The course begins with the traditional data flow analysis done by
compilers for imperative languages (something which usually does
not get discussed in sufficient details in a compilers course).
Then the course looks at other semantic analyses performed
for declarative languages using constraint based analysis, abstract
interpretations, and type based analysis. The upshot of the
course is that though all these seemingly different methods of
analysis differ in their strengths and their reach, they share
the same foundation and one kind of analysis can often be
modelled as another kind of analysis.
Course Contents
- Characteristics of Program Analysis.
- Data Flow Analysis.
Modelling Data Flow Analysis, Solutions of Data Flow Analysis, Flow Functions.
Data Flow Information, Data Flow Frameworks and Their Instances, Information
Flow Paths, Safe and Fixed Point Solutions of Flow Analysis.
Round Robin Interative Method, Worklist Based Inerative Method, Elimination Methods,
Solution Complexities. Interprocedural Data Flow Analysis. Semantic Issues in Data
Flow Analysis.
- Constraint Based Analysis.
Abstract 0-CFA Analysis, Senamtic Correctness, Existence of Solutions, Constraint
Based 0-CFA Analysis, Adding Data Flow Analysis.
- Type Based Analysis.
Control Flow Analysis, Semantic Correctness, Existence of Solutions, Inference
Algorithms, Effects Analysis, Communication Analysis.
- Abstract Interpretation.
Abstract and Concrete Domains of Values. Approximation of Fixed Points. Galois
Connections, Design of Galois Connection, Induced Operations.
Reading Material
- Text book :
Principles of Program Analysis.
F. Nielson, H. R. Nielson, C. Hankin.
Springer (1999).
(Central Library has two copies of this book.)
-
Some other papers may be referred for data flow analysis, abstract
interpretation, and type based analysis.
Prerequisites
Abstractions and Paradigms for Programming (CS 152) and
Programming Languages (CS-329 and CS-389).
Note that Language Processors (CS324) is not a prerequisite for this
since detailed knowledge of compilers is not necessary for this course.
Back to top of the page
Back to main page
Last updated on 9 January 2002.