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.