Collaborative Research: SHF: Medium: Environment-Centric Analysis and Optimization for Higher-Order Languages

该项目涉及一类功能强大的、基于数学的编程语言--“高阶函数式编程语言”的模块化编译。由于它们的表达能力，这些高级语言对程序员来说是很好的，但很难有效地实现。该项目的影响是使程序员能够编写更健壮、更安全、更容易推理、错误更少的软件，即使在需要高性能的应用程序领域也是如此。该项目的创新之处有两个：它使用了一个称为3CPS的带注释的中间表示法，它允许由程序分析确定的“事实”和由优化策略确定的“决策”与程序的表示相关联；以及一套旨在指导3CPS形式的程序转换的高阶控制流分析。这项工作的目标是开发一个以更高阶流分析为中心的编译器的体系结构--探索这种推理引擎和代码表示的组合所实现的转换和优化。事实注释的最重要的类之一是关于管理变量绑定所需的环境结构的显式信息；它被设计为与这些绑定所需的运行时机器资源(堆记录、堆栈框架和寄存器)紧密相连。这些信息是将源语言有效地映射到这些资源上的关键。3CPS中间形式作为中间表示形式的不同寻常之处在于，尽管它与目标机器的硬件资源有直接连接，但它仍然是一种更高阶的lambda演算表示。特别是，这样的设计能够专门表示环境结构，如显示器；基于每个调用的专门函数链接；以及绑定变量和在寄存器或堆栈上分配函数的能力。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The project concerns the modular compilation of a class of powerful,mathematically based programming languages -- "higher-order functionalprogramming languages." Owing to their expressive power, these high-levellanguages are great for programmers, but difficult to implement efficiently.The project's impacts are to make it possible for programmers to write softwarethat is more robust, more secure, easier to reason about, and with fewer bugs,even in application arenas where high performance is necessary. The project'snovelties are two: its use of an annotated intermediate representation, called3CPS, that allows "facts" determined by program analysis and "decisions"determined by optimization policies to be associated with the program'srepresentation; and a suite of higher-order control-flow analyses designed todirect transformations on programs in the 3CPS form. The goal of the work is todevelop the architecture of a compiler that has higher-order flow analysis atits center -- to explore the transformations and optimizations that are enabledby this combination of reasoning engine and code representation.One of the most important classes of fact annotations is explicit informationabout the environment structure required to manage bindings of variables; thisis designed to be closely connected to the run-time machine resources neededfor these bindings (heap records, stack frames and registers). This informationis key to mapping the source language efficiently onto these resources. The3CPS intermediate form is unusual as an intermediate representation in that,while it has direct connections to the target machine's hardware resources, itremains a higher-order, lambda-calculus representation. In particular, such adesign enables specialized representations of environment structure, such asdisplays; specializing function linkages on a per-call basis; and the abilityto bind variables and allocate functions in the registers or on the stack.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.