Armando Solar-Lezama

Armando Solar-Lezama

Auto-generated profile, based on publicly available information

Armando Solar-Lezama

Massachusetts Institute of Technology

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
2 August 2012 in International Journal on Software Tools for Technology Transfer
Verified
Journal Article
Open access
PDF file
ASArmando Solar-Lezama
Armando Solar-Lezama
Sketching is a synthesis methodology that aims to bridge the gap between a programmer’s high-level insights about a problem and the computer’s ability to manage low-level details. In sketching, the programmer uses a partial program, a sketch, to describe the desired implementation strategy, and leaves the low-level details of the implementation to an automated synthesis procedure. In order to generate an implementation from the programmer provided sketch, the synthesizer uses counterexample-guided inductive synthesis (CEGIS). Inductive synthesis refers to the process of generating candidate implementations from concrete examples of correct or incorrect behavior. CEGIS combines a SAT-based inductive synthesizer with an automated validation procedure, a bounded model-checker, that checks whether the candidate implementation produced by inductive synthesis is indeed correct and to produce new counterexamples. The result is a synthesis procedure that is able to handle complex problems from a variety of domains including ciphers, scientific programs, and even concurrent data-structures.

9 December 2021 in Foundations and Trends® in Programming Languages
Verified
Journal Article
Closed access
PDF file
SCSwarat Chaudhuri
Swarat Chaudhuri
KEKevin Ellis
Kevin Ellis
OPOleksandr Polozov
Oleksandr Polozov
RSRishabh Singh
Rishabh Singh
ASArmando Solar-Lezama
Armando Solar-Lezama
YYYisong Yue
Yisong Yue
We survey recent work on neurosymbolic programming, an emerging area that bridges the areas of deep learning and program synthesis. Like in classic machine learning, the goal here is to learn functions from data. However, these functions are represented as programs that can use neural modules in addition to symbolic primitives and are induced using a combination of symbolic search and gradient-based optimization. Neurosymbolic programming can offer multiple advantages over end-to-end deep learning. Programs can sometimes naturally represent long-horizon, procedural tasks that are difficult to perform using deep networks. Neurosymbolic representations are also, commonly, easier to interpret and formally verify than neural networks. The restrictions of a programming language can serve as a form of regular-ization and lead to more generalizable and data-efficient learning. Compositional programming abstractions can also be a natural way of reusing learned modules across learning tasks. In this monograph, we illustrate these potential benefits with concrete examples from recent work on neurosymbolic programming. We also categorize the main ways in which symbolic and neural learning techniques come together in this area. We conclude with a discussion of the open technical challenges in the field.

9 January 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MBMatthew Bowers
Matthew Bowers
TOTheo X. Olausson
Theo X. Olausson
LWLionel Wong
Lionel Wong
GGGabriel Grand
Gabriel Grand
JTJoshua B. Tenenbaum
Joshua B. Tenenbaum
ASArmando Solar-Lezama
Armando Solar-Lezama
This paper introduces corpus-guided top-down synthesis as a mechanism for synthesizing library functions that capture common functionality from a corpus of programs in a domain specific language (DSL). The algorithm builds abstractions directly from initial DSL primitives, using syntactic pattern matching of intermediate abstractions to intelligently prune the search space and guide the algorithm towards abstractions that maximally capture shared structures in the corpus. We present an implementation of the approach in a tool called Stitch and evaluate it against the state-of-the-art deductive library learning algorithm from DreamCoder. Our evaluation shows that Stitch is 3-4 orders of magnitude faster and uses 2 orders of magnitude less memory while maintaining comparable or better library quality (as measured by compressivity). We also demonstrate Stitch’s scalability on corpora containing hundreds of complex programs that are intractable with prior deductive approaches and show empirically that it is robust to terminating the search procedure early—further allowing it to scale to challenging datasets by means of early stopping.

14 July 2015
Verified
Book Chapter
Open access
PDF file
JJJinseong Jeon
Jinseong Jeon
XQXiaokang Qiu
Xiaokang Qiu
ASArmando Solar-Lezama
Armando Solar-Lezama
JFJeffrey S. Foster
Jeffrey S. Foster
Program synthesis tools work by searching for an implementation that satisfies a given specification. Two popular search strategies are symbolic search, which reduces synthesis to a formula passed to a SAT solver, and explicit search, which uses brute force or random search to find a solution. In this paper, we propose adaptive concretization, a novel synthesis algorithm that combines the best of symbolic and explicit search. Our algorithm works by partially concretizing a randomly chosen, but likely highly influential, subset of the unknowns to be synthesized. Adaptive concretization uses an online search process to find the optimal size of the concretized subset using a combination of exponential hill climbing and binary search, employing a statistical test to determine when one degree of concretization is sufficiently better than another. Moreover, our algorithm lends itself to a highly parallel implementation, further speeding up search. We implemented adaptive concretization for Sketch and evaluated it on a range of benchmarks. We found adaptive concretization is very effective, outperforming Sketch in many cases, sometimes significantly, and has good parallel scalability.

29 August 2022 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
JKJames Koppel
James Koppel
ZGZheng Guo
Zheng Guo
EVEdsko de Vries
Edsko de Vries
ASArmando Solar-Lezama
Armando Solar-Lezama
NPNadia Polikarpova
Nadia Polikarpova
Many problem domains, including program synthesis and rewrite-based optimization, require searching astronomically large spaces of programs. Existing approaches often rely on building specialized data structures—version-space algebras, finite tree automata, or e-graphs—to compactly represent such spaces. At their core, all these data structures exploit independence of subterms; as a result, they cannot efficiently represent more complex program spaces, where the choices of subterms are entangled. We introduce equality-constrained tree automata (ECTAs), a new data structure, designed to compactly represent large spaces of programs with entangled subterms. We present efficient algorithms for extracting programs from ECTAs, implemented in a performant Haskell library, ecta. Using the ecta library, we construct Hectare, a type-driven program synthesizer for Haskell. Hectare significantly outperforms a state-of-the-art synthesizer Hoogle+—providing an average speedup of 8×—despite its implementation being an order of magnitude smaller.

9 January 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
RDRia Das
Ria Das
JTJoshua B. Tenenbaum
Joshua B. Tenenbaum
ASArmando Solar-Lezama
Armando Solar-Lezama
ZTZenna Tavares
Zenna Tavares
We present a new algorithm that synthesizes functional reactive programs from observation data. The key novelty is to iterate between a functional synthesis step, which attempts to generate a transition function over observed states, and an automata synthesis step, which adds any additional latent state necessary to fully account for the observations. We develop a functional reactive DSL called Autumn that can express a rich variety of causal dynamics in time-varying, Atari-style grid worlds, and apply our method to synthesize Autumn programs from data. We evaluate our algorithm on a benchmark suite of 30 Autumn programs as well as a third-party corpus of grid-world-style video games. We find that our algorithm synthesizes 27 out of 30 programs in our benchmark suite and 21 out of 27 programs from the third-party corpus, including several programs describing complex latent state transformations, and from input traces containing hundreds of observations. We expect that our approach will provide a template for how to integrate functional and automata synthesis in other induction domains.