---
title: "Just-in-Time Learning for Bottom-Up Enumerative Synthesis (2020)"
description: "Their synthesizer builds a probabilistic context-free grammar (PCFG) during the search… 68% accuracy. 48 references, cited by 5 papers here."
authors: ["Shraddha Barke", "Hila Peleg", "Nadia Polikarpova"]
year: 2020
venue: "arXiv:2010.08663"
source: "https://arxiv.org/abs/2010.08663"
doi: "10.1145/3428295"
arxiv: "2010.08663"
licence: "CC BY-SA 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by-sa/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/barke-2020-just-time-learning-bottom-up/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/barke-2020-just-time-learning-bottom-up/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2020](https://md.research.elamur.ai/free/en/papers/2020/page/7/) / Just-in-Time Learning for Bottom-Up Enumerative Synthesis

# Just-in-Time Learning for Bottom-Up Enumerative Synthesis

**Authors:** Shraddha Barke, Hila Peleg and Nadia Polikarpova · **Year:** 2020 · **Venue:** [arXiv:2010.08663](https://md.research.elamur.ai/free/en/venues/proceedings-of-the-acm-on-programming-languages/) ([Proceedings of the ACM on Programming Languages 2020](https://md.research.elamur.ai/free/en/venues/proceedings-of-the-acm-on-programming-languages/2020/)) · **Publisher:** [Association for Computing Machinery](https://md.research.elamur.ai/free/en/publishers/association-for-computing-machinery/) · **Licence:** [CC BY-SA 4.0 (arXiv)](http://creativecommons.org/licenses/by-sa/4.0/)

**Links:** [Publisher's page](https://doi.org/10.1145/3428295) · [PDF](https://arxiv.org/pdf/2010.08663) · [DOI 10.1145/3428295](https://doi.org/10.1145/3428295) · [arXiv 2010.08663](https://arxiv.org/abs/2010.08663) · [OpenAlex](https://openalex.org/W3092881338)

**Citations:** 33 citations (OpenAlex, 2026-10-14) · 5 in our library, of the 149,439 papers whose bibliographies we read

## Summary
Program synthesizers must search enormous program spaces. Earlier systems speed this up with probabilistic models of code, but those models need large corpora of existing solutions, which many domains lack. Barke, Peleg and Polikarpova avoid pre-training. Their synthesizer builds a probabilistic context-free grammar (PCFG) during the search itself. Whenever enumeration finds a short program that satisfies some, but not all, input-output examples, the grammar rules used in that program gain probability. To use this signal, the authors design guided bottom-up search. It keeps the dynamic programming and observational-equivalence pruning of classic bottom-up enumeration but visits programs from most to least likely under the PCFG. Because every enumerated program is complete, it can be run on the examples, so partial solutions are found quickly. The tool, Probe, accepts SyGuS problems. On 140 benchmarks it solves roughly twice as many as unguided search and clearly more than the pre-trained EuPhony. Its programs also stay compact and generalize well. This makes guided synthesis practical for new domains without training data.

## Key points
- **Benchmarks and results:** Probe was tested on 140 SyGuS problems covering strings, bit-vectors and circuit transformation. Within a 10-minute limit it solved 91, compared with 44 for baseline bottom-up enumeration and 50 for EuPhony.
- **Comparison with CVC4:** CVC4, the 2019 SyGuS competition winner, solves more tasks. However, its programs are about 9× larger on average. Where extra held-out data existed, CVC4 reached only 68% accuracy on it, while Probe scored 100%.
- **Example task:** On pick-date, whose shortest solution has size 14, the learned PCFG lets Probe succeed in 34 seconds. The other tools tested found no comparable solution within ten minutes.
- **Specification support:** Universally quantified specifications are handled by converting them to examples through standard CEGIS.
- **Related work:** Probe extends the authors' earlier Bester tool, which collects partial solutions cheaply. Unlike EuPhony's top-down A* search, Probe's bottom-up guidance adds almost no overhead.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of California San Diego](https://md.research.elamur.ai/free/en/universities/university-of-california-san-diego/) — University, San Diego, United States · 101 works · 54,571 citations

📚 Shelves (3): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🖥️ Computer Science Applications](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-science-applications/) · 184 works

## Cite

Cite as: Shraddha Barke, Hila Peleg and Nadia Polikarpova. 2020. Just-in-Time Learning for Bottom-Up Enumerative Synthesis. arXiv:2010.08663.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{barke2020just,
  title = {{Just-in-Time Learning for Bottom-Up Enumerative Synthesis}},
  author = {Shraddha Barke, Hila Peleg and Nadia Polikarpova},
  year = {2020},
  doi = {10.1145/3428295},
  eprint = {2010.08663},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1145/3428295}
}
```

- [← previous Continual Adaptation for Efficient Machine Communication](https://md.research.elamur.ai/free/en/papers/hawkins-2020-continual-adaptation-efficient-machine-communication/)
- [next → The Potsdam Commentary Corpus 2.2: Extending Annotations for Shallow Discourse Parsing](https://md.research.elamur.ai/free/en/papers/bourgonje-2020-potsdam-commentary-corpus-2-2/)
- [↑ back to papers of 2020](https://md.research.elamur.ai/free/en/papers/2020/page/7/)

## References

48 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. 2018. Euphony Benchmark Suite. [https://github.com/wslee/euphony/tree/master/benchmarks](https://github.com/wslee/euphony/tree/master/benchmarks) [↗](https://github.com/wslee/euphony/tree/master/benchmarks)
2. Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recursive program synthesis. In International Conference on Computer Aided Verification. Springer, 934–950. [find](https://scholar.google.com/scholar?q=Aws+Albarghouthi%2C+Sumit+Gulwani%2C+and+Zachary+Kincaid%2E+2013%2E+Recursive+program+synthesis%2E+In+International+Conference+on+Computer+Aided+Verification%2E+Springer%2C+934%E2%80%93950%2E)
3. Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. 2018. [A survey of machine learning for big code and naturalness](https://md.research.elamur.ai/free/en/papers/allamanis-2017-survey-machine-learning-big-code/). ACM Computing Surveys (CSUR) 51, 4 (2018), 1–37.
4. Ethem Alpaydin. 2014. Introduction to Machine Learning (3 ed.). [find](https://scholar.google.com/scholar?q=Ethem+Alpaydin%2E+2014%2E+Introduction+to+Machine+Learning+%283+ed%2E%29%2E)
5. MIT Press, Cambridge, MA. Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. [Syntax-guided synthesis](https://md.research.elamur.ai/free/en/papers/alur-2013-syntax-guided-synthesis/). In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR,…
6. Sygus-comp 2016: results and analysis. arXiv preprint arXiv:1611.07627 (2016). — [arXiv:1611.07627](https://arxiv.org/abs/1611.07627) [find](https://scholar.google.com/scholar?q=Sygus%2Dcomp+2016%3A+results+and+analysis%2E+arXiv+preprint+arXiv%3A1611%2E07627+%282016%29%2E+%E2%80%94+%5BarXiv%3A1611%2E07627%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1611%2E07627%29)
7. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. 2017a. [find](https://scholar.google.com/scholar?q=Rajeev+Alur%2C+Dana+Fisman%2C+Rishabh+Singh%2C+and+Armando+Solar%2DLezama%2E+2017a%2E)
8. Sygus-comp 2017: Results and analysis. arXiv preprint arXiv:1711.11438 (2017). — [arXiv:1711.11438](https://arxiv.org/abs/1711.11438) [find](https://scholar.google.com/scholar?q=Sygus%2Dcomp+2017%3A+Results+and+analysis%2E+arXiv+preprint+arXiv%3A1711%2E11438+%282017%29%2E+%E2%80%94+%5BarXiv%3A1711%2E11438%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1711%2E11438%29)
9. Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. 2017b. Scaling enumerative program synthesis via divide and conquer. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 319–336. [find](https://scholar.google.com/scholar?q=Rajeev+Alur%2C+Arjun+Radhakrishna%2C+and+Abhishek+Udupa%2E+2017b%2E+Scaling+enumerative+program+synthesis+via+divide+and+conquer%2E+In+International+Conference+on+Tools+and+Algorithms+for+the+Construction+and+A)
10. Rajeev Alur, Rishabh Singh, Dana Fisman, and Armando Solar-Lezama. 2018. Search-based Program Synthesis. Commun. ACM 61, 12 (Nov. 2018), 84–93. https://doi.org/10.1145/3208071 — [doi:10.1145/3208071](https://doi.org/10.1145/3208071) [↗](https://doi.org/10.1145/3208071)
11. Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2016. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989 (2016). [find](https://scholar.google.com/scholar?q=Matej+Balog%2C+Alexander+L+Gaunt%2C+Marc+Brockschmidt%2C+Sebastian+Nowozin%2C+and+Daniel+Tarlow%2E+2016%2E+Deepcoder%3A+Learning+to+write+programs%2E+arXiv+preprint+arXiv%3A1611%2E01989+%282016%29%2E)
12. Shraddha Barke, Hila Peleg, and Nadia Polikarpova. 2020. [Just-in-Time Learning for Bottom-up Enumerative Synthesis](https://md.research.elamur.ai/free/en/papers/barke-2020-just-time-learning-bottom-up/). (2020). [https://shraddhabarke.github.io/publication/probe-oopsla](https://shraddhabarke.github.io/publication/probe-oopsla) [↗](https://shraddhabarke.github.io/publication/probe-oopsla)
13. Pavol Bielik, Veselin Raychev, and Martin Vechev. 2016. PHOG: probabilistic model for code. In International Conference on Machine Learning. 2933–2942. [find](https://scholar.google.com/scholar?q=Pavol+Bielik%2C+Veselin+Raychev%2C+and+Martin+Vechev%2E+2016%2E+PHOG%3A+probabilistic+model+for+code%2E+In+International+Conference+on+Machine+Learning%2E+2933%E2%80%932942%2E)
14. Yanju Chen, Chenglong Wang, Osbert Bastani, Isil Dillig, and Yu Feng. 2020. Program Synthesis Using Deduction-Guided Reinforcement Learning. In International Conference on Computer Aided Verification. Springer, 587–610. [find](https://scholar.google.com/scholar?q=Yanju+Chen%2C+Chenglong+Wang%2C+Osbert+Bastani%2C+Isil+Dillig%2C+and+Yu+Feng%2E+2020%2E+Program+Synthesis+Using+Deduction%2DGuided+Reinforcement+Learning%2E+In+International+Conference+on+Computer+Aided+Verification%2E)
15. Kevin Ellis, Lucas Morales, Mathias Sablé Meyer, Armando Solar-Lezama, and Joshua B Tenenbaum. 2018. Search, compress, compile: Library learning in neurally-guided bayesian program learning. Advances in neural information processing systems (2018). [find](https://scholar.google.com/scholar?q=Kevin+Ellis%2C+Lucas+Morales%2C+Mathias+Sabl%C3%A9+Meyer%2C+Armando+Solar%2DLezama%2C+and+Joshua+B+Tenenbaum%2E+2018%2E+Search%2C+compress%2C+compile%3A+Library+learning+in+neurally%2Dguided+bayesian+program+learning%2E+Advances+)
16. Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. 2017a. Component-based synthesis of table consolidation and transformation tasks from examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spai… [find](https://scholar.google.com/scholar?q=Yu+Feng%2C+Ruben+Martins%2C+Jacob+Van+Geffen%2C+Isil+Dillig%2C+and+Swarat+Chaudhuri%2E+2017a%2E+Component%2Dbased+synthesis+of+table+consolidation+and+transformation+tasks+from+examples%2E+In+Proceedings+of+the+38th+)
17. Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W Reps. 2017b. Component-based synthesis for complex APIs. ACM SIGPLAN Notices 52, 1 (2017), 599–612. [find](https://scholar.google.com/scholar?q=Yu+Feng%2C+Ruben+Martins%2C+Yuepeng+Wang%2C+Isil+Dillig%2C+and+Thomas+W+Reps%2E+2017b%2E+Component%2Dbased+synthesis+for+complex+APIs%2E+ACM+SIGPLAN+Notices+52%2C+1+%282017%29%2C+599%E2%80%93612%2E)
18. John K Feser, Swarat Chaudhuri, and Isil Dillig. 2015. Synthesizing data structure transformations from input-output examples. In ACM SIGPLAN Notices, Vol. 50. ACM, 229–239. [find](https://scholar.google.com/scholar?q=John+K+Feser%2C+Swarat+Chaudhuri%2C+and+Isil+Dillig%2E+2015%2E+Synthesizing+data+structure+transformations+from+input%2Doutput+examples%2E+In+ACM+SIGPLAN+Notices%2C+Vol%2E+50%2E+ACM%2C+229%E2%80%93239%2E)
19. Jonathan Frankle, Peter-Michael Osera, David Walker, and Steve Zdancewic. 2016. Example-directed Synthesis: A Type-theoretic Interpretation. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (St. Petersburg, FL, USA) (POPL ’16). ACM, New York, NY,… — [doi:10.1145/2837614](https://doi.org/10.1145/2837614) [find](https://scholar.google.com/scholar?q=Jonathan+Frankle%2C+Peter%2DMichael+Osera%2C+David+Walker%2C+and+Steve+Zdancewic%2E+2016%2E+Example%2Ddirected+Synthesis%3A+A+Type%2Dtheoretic+Interpretation%2E+In+Proceedings+of+the+43rd+Annual+ACM+SIGPLAN%2DSIGACT+Sympos)
20. Sumit Gulwani. 2011. [Automating String Processing in Spreadsheets Using Input-output Examples](https://md.research.elamur.ai/free/en/papers/gulwani-2011-automating-string-processing-spreadsheets-input/). In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Austin, Texas, USA) (POPL ’11). ACM, New York, NY, USA, 317–330. https://doi.org/10.1145/1926385.19264… [↗](https://doi.org/10.1145/1926385.19264…)
21. Sumit Gulwani. 2016. Programming by Examples (and its applications in Data Wrangling). In Verification and Synthesis of Correct and Secure Systems, Javier Esparza, Orna Grumberg, and Salomon Sickert (Eds.). [find](https://scholar.google.com/scholar?q=Sumit+Gulwani%2E+2016%2E+Programming+by+Examples+%28and+its+applications+in+Data+Wrangling%29%2E+In+Verification+and+Synthesis+of+Correct+and+Secure+Systems%2C+Javier+Esparza%2C+Orna+Grumberg%2C+and+Salomon+Sickert+%28)
22. IOS Press. Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan. 2011. Synthesis of loop-free programs. ACM SIGPLAN Notices 46, 6 (2011), 62–73. [find](https://scholar.google.com/scholar?q=IOS+Press%2E+Sumit+Gulwani%2C+Susmit+Jha%2C+Ashish+Tiwari%2C+and+Ramarathnam+Venkatesan%2E+2011%2E+Synthesis+of+loop%2Dfree+programs%2E+ACM+SIGPLAN+Notices+46%2C+6+%282011%29%2C+62%E2%80%9373%2E)
23. Tihomir Gvero, Viktor Kuncak, Ivan Kuraj, and Ruzica Piskac. 2013. Complete completion using types and weights. In ACM SIGPLAN Notices, Vol. 48. ACM, 27–38. [find](https://scholar.google.com/scholar?q=Tihomir+Gvero%2C+Viktor+Kuncak%2C+Ivan+Kuraj%2C+and+Ruzica+Piskac%2E+2013%2E+Complete+completion+using+types+and+weights%2E+In+ACM+SIGPLAN+Notices%2C+Vol%2E+48%2E+ACM%2C+27%E2%80%9338%2E)
24. Jeevana Priya Inala and Rishabh Singh. 2018. WebRelate: integrating web data with spreadsheets using examples. PACMPL 2, POPL (2018), 2:1–2:28. [https://dl.acm.org/doi/10.1145/3158090](https://dl.acm.org/doi/10.1145/3158090) — [doi:10.1145/3158090](https://doi.org/10.1145/3158090) [↗](https://dl.acm.org/doi/10.1145/3158090)
25. Susmit Jha, Sumit Gulwani, Sanjit A Seshia, and Ashish Tiwari. 2010. Oracle-guided component-based program synthesis. In 2010 ACM/IEEE 32nd International Conference on Software Engineering, Vol. 1. IEEE, 215–224. [find](https://scholar.google.com/scholar?q=Susmit+Jha%2C+Sumit+Gulwani%2C+Sanjit+A+Seshia%2C+and+Ashish+Tiwari%2E+2010%2E+Oracle%2Dguided+component%2Dbased+program+synthesis%2E+In+2010+ACM%2FIEEE+32nd+International+Conference+on+Software+Engineering%2C+Vol%2E+1%2E+IE)
26. Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. 2018. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv:1804.01186 (2018). — [arXiv:1804.01186](https://arxiv.org/abs/1804.01186) [find](https://scholar.google.com/scholar?q=Ashwin+Kalyan%2C+Abhishek+Mohta%2C+Oleksandr+Polozov%2C+Dhruv+Batra%2C+Prateek+Jain%2C+and+Sumit+Gulwani%2E+2018%2E+Neural%2Dguided+deductive+search+for+real%2Dtime+program+synthesis+from+examples%2E+arXiv+preprint+arXiv)
27. Etienne Kneuss, Ivan Kuraj, Viktor Kuncak, and Philippe Suter. 2013. Synthesis Modulo Recursive Functions. SIGPLAN Not. 48, 10 (Oct. 2013), 407–426. [find](https://scholar.google.com/scholar?q=Etienne+Kneuss%2C+Ivan+Kuraj%2C+Viktor+Kuncak%2C+and+Philippe+Suter%2E+2013%2E+Synthesis+Modulo+Recursive+Functions%2E+SIGPLAN+Not%2E+48%2C+10+%28Oct%2E+2013%29%2C+407%E2%80%93426%2E)
28. Manos Koukoutos, Etienne Kneuss, and Viktor Kuncak. 2016. An Update on Deductive Synthesis and Repair in the Leon Tool. In Proceedings Fifth Workshop on Synthesis, SYNT@CAV 2016, Toronto, Canada, July 17-18, 2016. 100–111. [find](https://scholar.google.com/scholar?q=Manos+Koukoutos%2C+Etienne+Kneuss%2C+and+Viktor+Kuncak%2E+2016%2E+An+Update+on+Deductive+Synthesis+and+Repair+in+the+Leon+Tool%2E+In+Proceedings+Fifth+Workshop+on+Synthesis%2C+SYNT%40CAV+2016%2C+Toronto%2C+Canada%2C+July)
29. Manos Koukoutos, Mukund Raghothaman, Etienne Kneuss, and Viktor Kuncak. 2017. On repair with probabilistic attribute grammars. arXiv preprint arXiv:1707.04148 (2017). — [arXiv:1707.04148](https://arxiv.org/abs/1707.04148) [find](https://scholar.google.com/scholar?q=Manos+Koukoutos%2C+Mukund+Raghothaman%2C+Etienne+Kneuss%2C+and+Viktor+Kuncak%2E+2017%2E+On+repair+with+probabilistic+attribute+grammars%2E+arXiv+preprint+arXiv%3A1707%2E04148+%282017%29%2E+%E2%80%94+%5BarXiv%3A1707%2E04148%5D%28https%3A%2F%2Farxi)
30. Vu Le and Sumit Gulwani. 2014. FlashExtract: a framework for data extraction by examples. In Proceedings of the 35th Conference on Programming Language Design and Implementation, Michael F. P. O’Boyle and Keshav Pingali (Eds.). ACM, 55. https://doi.org/10.1145/2594291.2594333 — [doi:10.1145/2594291.2594333](https://doi.org/10.1145/2594291.2594333) [↗](https://doi.org/10.1145/2594291.2594333)
31. Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. 2018. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices 53, 4 (2018), 436–449. [find](https://scholar.google.com/scholar?q=Woosuk+Lee%2C+Kihong+Heo%2C+Rajeev+Alur%2C+and+Mayur+Naik%2E+2018%2E+Accelerating+search%2Dbased+program+synthesis+using+learned+probabilistic+models%2E+ACM+SIGPLAN+Notices+53%2C+4+%282018%29%2C+436%E2%80%93449%2E)
32. Aditya Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Kalai. 2013. A machine learning framework for programming by example. In International Conference on Machine Learning. 187–195. [find](https://scholar.google.com/scholar?q=Aditya+Menon%2C+Omer+Tamuz%2C+Sumit+Gulwani%2C+Butler+Lampson%2C+and+Adam+Kalai%2E+2013%2E+A+machine+learning+framework+for+programming+by+example%2E+In+International+Conference+on+Machine+Learning%2E+187%E2%80%93195%2E)
33. Peter-Michael Osera and Steve Zdancewic. 2015. [Type-and-example-directed program synthesis](https://md.research.elamur.ai/free/en/papers/osera-2015-type-example-directed-program-synthesis/). In ACM SIGPLAN Notices, Vol. 50. ACM, 619–630.
34. Hila Peleg and Nadia Polikarpova. 2020. Perfect is the Enemy of Good: Best-Effort Program Synthesis. In 34th European Conference on Object-Oriented Programming, ECOOP. [find](https://scholar.google.com/scholar?q=Hila+Peleg+and+Nadia+Polikarpova%2E+2020%2E+Perfect+is+the+Enemy+of+Good%3A+Best%2DEffort+Program+Synthesis%2E+In+34th+European+Conference+on+Object%2DOriented+Programming%2C+ECOOP%2E)
35. Daniel Perelman, Sumit Gulwani, Dan Grossman, and Peter Provost. 2014. Test-driven synthesis. ACM Sigplan Notices 49, 6 (2014), 408–418. [find](https://scholar.google.com/scholar?q=Daniel+Perelman%2C+Sumit+Gulwani%2C+Dan+Grossman%2C+and+Peter+Provost%2E+2014%2E+Test%2Ddriven+synthesis%2E+ACM+Sigplan+Notices+49%2C+6+%282014%29%2C+408%E2%80%93418%2E)
36. Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodik, and Dinakar Dhurjati. 2016. Scaling up Superoptimization. SIGARCH Comput. Archit. News 44, 2 (March 2016), 297–310. https://doi.org/10.1145/2980024.2872387 — [doi:10.1145/2980024.2872387](https://doi.org/10.1145/2980024.2872387) [↗](https://doi.org/10.1145/2980024.2872387)
37. Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code completion with statistical language models. In ACM SIGPLAN Notices, Vol. 49. ACM, 419–428. [find](https://scholar.google.com/scholar?q=Veselin+Raychev%2C+Martin+Vechev%2C+and+Eran+Yahav%2E+2014%2E+Code+completion+with+statistical+language+models%2E+In+ACM+SIGPLAN+Notices%2C+Vol%2E+49%2E+ACM%2C+419%E2%80%93428%2E)
38. Andrew Reynolds, Haniel Barbosa, Andres Nötzli, Clark Barrett, and Cesare Tinelli. 2019. cvc 4 sy: smart and fast term enumeration for syntax-guided synthesis. In International Conference on Computer Aided Verification. Springer, 74–83. [find](https://scholar.google.com/scholar?q=Andrew+Reynolds%2C+Haniel+Barbosa%2C+Andres+N%C3%B6tzli%2C+Clark+Barrett%2C+and+Cesare+Tinelli%2E+2019%2E+cvc+4+sy%3A+smart+and+fast+term+enumeration+for+syntax%2Dguided+synthesis%2E+In+International+Conference+on+Computer+)
39. Rohin Shah, Sumith Kulal, and Rastislav Bodik. 2018. Scalable Synthesis with Symbolic Syntax Graphs. (2018). [find](https://scholar.google.com/scholar?q=Rohin+Shah%2C+Sumith+Kulal%2C+and+Rastislav+Bodik%2E+2018%2E+Scalable+Synthesis+with+Symbolic+Syntax+Graphs%2E+%282018%29%2E)
40. Kensen Shi, Jacob Steinhardt, and Percy Liang. 2019. FrAngel: component-based synthesis with control structures. Proceedings of the ACM on Programming Languages 3, POPL (2019), 1–29. [https://dl.acm.org/doi/10.1145/3290386](https://dl.acm.org/doi/10.1145/3290386) [↗](https://dl.acm.org/doi/10.1145/3290386)
41. Xujie Si, Yuan Yang, Hanjun Dai, Mayur Naik, and Le Song. 2019. Learning a Meta-Solver for Syntax-Guided Program Synthesis. [https://openreview.net/forum?id=Syl8Sn0cK7](https://openreview.net/forum?id=Syl8Sn0cK7) [↗](https://openreview.net/forum?id=Syl8Sn0cK7)
42. Calvin Smith and Aws Albarghouthi. 2019. Program Synthesis with Equivalence Reduction. In Verification, Model Checking, and Abstract Interpretation - 20th International Conference, VMCAI 2019, Cascais, Portugal, January 13-15, 2019, Proceedings. 24–47. https://doi.org/10.1007/978-3-030-11245-5_2 — [doi:10.1007/978-3-030-11245-5_2](https://doi.org/10.1007/978-3-030-11245-5_2) [↗](https://doi.org/10.1007/978-3-030-11245-5_2)
43. Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. 2006. Combinatorial sketching for finite programs. ACM SIGOPS Operating Systems Review 40, 5 (2006), 404–415. [find](https://scholar.google.com/scholar?q=Armando+Solar%2DLezama%2C+Liviu+Tancau%2C+Rastislav+Bodik%2C+Sanjit+Seshia%2C+and+Vijay+Saraswat%2E+2006%2E+Combinatorial+sketching+for+finite+programs%2E+ACM+SIGOPS+Operating+Systems+Review+40%2C+5+%282006%29%2C+404%E2%80%93415%2E)
44. Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador-Haim, Milo MK Martin, and Rajeev Alur. 2013. TRANSIT: specifying protocols with concolic snippets. ACM SIGPLAN Notices 48, 6 (2013), 287–296. [find](https://scholar.google.com/scholar?q=Abhishek+Udupa%2C+Arun+Raghavan%2C+Jyotirmoy+V+Deshmukh%2C+Sela+Mador%2DHaim%2C+Milo+MK+Martin%2C+and+Rajeev+Alur%2E+2013%2E+TRANSIT%3A+specifying+protocols+with+concolic+snippets%2E+ACM+SIGPLAN+Notices+48%2C+6+%282013%29%2C+287)
45. Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017a. Synthesizing highly expressive SQL queries from input-output examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 452–466. [find](https://scholar.google.com/scholar?q=Chenglong+Wang%2C+Alvin+Cheung%2C+and+Rastislav+Bodik%2E+2017a%2E+Synthesizing+highly+expressive+SQL+queries+from+input%2Doutput+examples%2E+In+Proceedings+of+the+38th+ACM+SIGPLAN+Conference+on+Programming+Langua)
46. Xinyu Wang, Isil Dillig, and Rishabh Singh. 2017c. Program Synthesis Using Abstraction Refinement. Proc. ACM Program. Lang. 2, POPL, Article 63, 30 pages. https://doi.org/10.1145/3158151 — [doi:10.1145/3158151](https://doi.org/10.1145/3158151) [↗](https://doi.org/10.1145/3158151)
47. Xinyu Wang, Isil Dillig, and Rishabh Singh. 2017b. Synthesis of Data Completion Scripts Using Finite Tree Automata. Proc. ACM Program. Lang. 1, OOPSLA, Article 62, 26 pages. https://doi.org/10.1145/3133886 — [doi:10.1145/3133886](https://doi.org/10.1145/3133886) [↗](https://doi.org/10.1145/3133886)
48. Henry S Warren. 2013. Hacker’s delight. Pearson Education. [find](https://scholar.google.com/scholar?q=Henry+S+Warren%2E+2013%2E+Hacker%E2%80%99s+delight%2E+Pearson+Education%2E)

*Updated 3 November 2026*