CAREER: Algorithmic Foundations and Modern Applications for Program Synthesis

我们世界的几乎每一个方面都通过软件系统被自动化所触及。能够有效地构建复杂的软件为企业提供了竞争优势，简化了我们的官僚系统，并改善了我们的个人日常生活。但构建软件仍然是一个繁琐且容易出错的过程。该项目通过自动合成所需程序的技术简化了软件开发过程。在基础层面上，该项目开发了有效和自动构建软件系统的现代算法技术，从而推进了程序合成领域。这个项目特别强调的是数据分析应用程序的自动合成。具体来说，该项目为最终用户开发工具，以自动构建可以在云基础设施上运行的数据分析，而无需任何必要的编程系统知识。因此，该项目有可能彻底改变和民主化数据分析。该项目将研究与教育和外展紧密联系起来：让女性和代表性不足的少数族裔本科生参与研究，将项目综合理念纳入现代课程，并开展包容性综合主题的黑客马拉松。该项目将程序合成应用程序的范围扩展到可以在云基础设施上运行的数据并行程序。为了实现高效的合成，该项目提供了一系列新颖的算法技术。具体而言，该项目(1)开发并利用关系规范的概念来指导具有语义知识的综合算法；(2)开发学习任意api的关系规范的技术；(3)开发了一套技术，用于有效地合成在重排序存在时确定的程序。

Almost every aspect of our world has been touched by automation through software systems. Being able to efficiently construct complex software provides a competitive advantage to businesses, streamlines our bureaucratic systems, and improves our personal day-to-day lives. But building software remains a cumbersome, error-prone process. This project simplifies the software development process through techniques that automatically synthesize desired programs. At a foundational level, the project develops modern algorithmic techniques for efficiently and automatically constructing software systems, thus advancing the field of program synthesis. The particular emphasis of this project is on automated synthesis of data-analysis applications. Specifically, the project develops tools for end users to automatically construct data analyses that can run on cloud infrastructure, without any necessary knowledge of programming systems. Thus, the project has the potential to revolutionize and democratize data analytics. The project strongly connects research with education and outreach: by involving women and underrepresented minority undergraduate students in research, incorporating program synthesis ideas in modern curricula, and developing inclusive synthesis-themed hackathons.This project expands the range of program synthesis applications to data-parallel programs that can run on cloud infrastructure. To enable efficient synthesis, the project contributes a portfolio of novel algorithmic techniques. Specifically, the project (1) develops and utilizes the notion of relational specifications to guide synthesis algorithms with semantic knowledge; (2) develops techniques for learning relational specifications of arbitrary APIs; and (3) develops a suite of techniques for efficiently synthesizing programs that are deterministic in the presence of reorderings.