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

The project concerns the modular compilation of a class of powerful, mathematically based programming languages -- "higher-order functional programming languages." Owing to their expressive power, these high-level languages are great for programmers, but difficult to implement efficiently. The project's impacts are to make it possible for programmers to write software

that is more robust, more secure, easier to reason about, and with fewer bugs, even in application arenas where high performance is necessary. The project's novelties are two: its use of an annotated intermediate representation, called 3CPS, that allows "facts" determined by program analysis and "decisions"

determined by optimization policies to be associated with the program's representation; and a suite of higher-order control-flow analyses designed to direct transformations on programs in the 3CPS form. The goal of the work is to develop the architecture of a compiler that has higher-order flow analysis at

its center -- to explore the transformations and optimizations that are enabled by this combination of reasoning engine and code representation. One of the most important classes of fact annotations is explicit information about the environment structure required to manage bindings of variables; this

is designed to be closely connected to the run-time machine resources needed for these bindings (heap records, stack frames and registers). This information is key to mapping the source language efficiently onto these resources. The 3CPS intermediate form is unusual as an intermediate representation in that,

while it has direct connections to the target machine's hardware resources, it remains a higher-order, lambda-calculus representation. In particular, such a design enables specialized representations of environment structure, such as displays; specializing function linkages on a per-call basis; and the ability

to 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.