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

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

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.