New Foundations for Control Flow Analysis

提案CCF-0811297控制流分析的新基础Harry Mairson时间限制静态分析器可以提供有关计算密集型程序的运行时行为的信息。 拟议的研究将解决高阶程序的控制流分析的新基础，包括新的分析器的设计和实现，以及已知方法和近似问题的分析。 使用从线性逻辑中导出的线性原则，研究人员希望在计算方面精确地描述这种静态分析近似运行时行为的程度。 科学的软件设计应该建立在对静态分析器的运行时间和计算精度之间的权衡的分析以及实际和务实的理解之上。 这样一个研究计划的更广泛的影响包括提高对软件开发人员工作中这种编译时分析的可行性的认识和理解。 分析工具也适合整合在本科课程的编程语言语用学和实施。

Proposal CCF-0811297New Foundations for Control Flow AnalysisHarry MairsonA 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.