New Foundations for Control Flow Analysis

Brandeis University, Waltham MA

Investigators

Abstract

Proposal CCF-0811297 New Foundations for Control Flow Analysis Harry Mairson A time-bounded static analyzer can provide information about the runtime behavior of a computation-intensive program. The proposed research will address new foundations for control flow analysis of higher-order programs, including the design and implementation of novel analyzers, and the analysis of known methods and approximation problems. Using principles of linearity derived from linear logic, the researchers want to characterize precisely, in computational terms, the degree to which such static analysis approximates run-time behavior. Scientific software design ought to be founded on an analytical as well as practical and pragmatic understanding of the tradeoffs between the running time of static analyzers, and the accuracy of their computations. The broader impacts of such a program of research include an increased awareness and understanding of the feasibility of such compile-time analysis in the work of software developers. The analytic tools are also amenable to integration in undergraduate courses on programming language pragmatics and implementation.