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.