In my thesis work, I used static analysis techniques to ensure the termination of off-line partial evaluation. Partial evaluation is a program specialization operation in which programs with multiple inputs are specialized to take into account known values for some of their inputs. The intent of partial evaluation is that the specialized program will usually run faster than the original program, because computations that are dependent only on the known inputs will be eliminated in the specialized program. An off-line partial evaluator is divided into two phases: An analysis phase (termed binding-time analysis or BTA) that determines which parts of the program are computable using only the known inputs (these are `static' computations), and a program specialization phase. In recent years, partial evaluators have been developed for a variety of programming languages and paradigms. As a result, partial evaluators are increasingly being used as `black-box' tools by users who are not familiar with the design of partial evaluators. Therefore, it is important to ensure that partial evaluators terminate and return a specialized program to the user regardless of the input program. However, partial evaluators commonly fall short of this requirement, either because the binding-time analysis is `incorrect', in the sense that it marks computations that require unknown values as static, or because the partial evaluator attempts to enumerate an unbounded set of values for a static program variable.

I showed that incorrect partial evaluators arise because their BTA phase fails to account for hidden data flow through control dependences when tracing the flow of dynamic values through a program. I therefore used the data and control dependences that are explicit in the structure and semantics of program dependence graphs to define `correct' binding-time analyses that are simple reachability operations on dependence graphs. The argument against using control dependences for BTA has been that the analysis becomes overly conservative (too little of the program is marked static). However, I have shown that it is possible to identify the particular situations in which control dependences should be followed. Therefore, the analyses developed in my thesis research have the advantage of a semantic guarantee of safety, without unduly compromising the performance of the specialized program. As part of this work, I extended program representation graphs, a form of dependence graph with a well-defined semantics, to a class of programs containing recursive procedure calls. I also developed a correct binding-time analysis for C programs.

Partial Evaluation Using Dependence Graphs Manuvir Das, Ph.D. Thesis and Technical Report 1362, Computer Sciences Department, University of Wisconsin - Madison, February 1998. BTA Termination Using CFL-Reachability Manuvir Das and Thomas Reps, Technical Report 1329, Computer Sciences Department, University of Wisconsin - Madison, November 1996. Semantic Foundations of Binding-Time Analysis for Imperative Programs Manuvir Das, Thomas Reps, and Pascal Van Hentenryck, PEPM '95: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 1995, pp. 100-110.

In my thesis, I addressed the problem of unbounded static code by defining termination analyses based on graph reachability that identify function parameters that take values from a bounded set. Finally, I extended the operation of program specialization to dependence graphs. As a consequence, I developed a partial evaluator for imperative programs that transforms a program into its dependence graph, performs binding-time analysis and specialization on the dependence graph, and transforms the specialized dependence graph into program text.

Since my graduation, I have not actively pursued research in the area of partial evaluation, for two reasons: First, the analysis algorithms developed in my thesis are cubic in their worst-case complexity. The largest programs I was able to analyze consisted of 2000 lines of C source code. Thus, it is not clear whether these methods will be applicable to larger programs. Second, I believe that the major hurdle with partial evaluation as it stands today is that programs must be written in a certain style for a partial evaluator to exploit maximum benefit. This is where I feel research in the area should be focused. Although I don't have the time to work on this problem, I continue to track the latest research in the area of partial evaluation, and I am hopeful that partial evaluation will become a useful, practical method.