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