# Automatic Program Synthesis of Long Programs with a Learned Garbage Collector

arXiv: https://arxiv.org/abs/1809.04682 · HTML: https://mlsanity.com/paper/1809.04682/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2018.

## Built on by (most cited first, 24 of 24)

- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Reasoning Like Program Executors](https://mlsanity.com/paper/2201.11473/) (2022)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Neural-guided, Bidirectional Program Search for Abstraction and Reasoning](https://mlsanity.com/paper/2110.11536/) (2021)
- [CodeIt: Self-Improving Language Models with Prioritized Hindsight Replay](https://mlsanity.com/paper/2402.04858/) (2024)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [B-Coder: Value-Based Deep Reinforcement Learning for Program Synthesis](https://mlsanity.com/paper/2310.03173/) (2023)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)
- [Learning to Edit Visual Programs with Self-Supervision](https://mlsanity.com/paper/2406.02383/) (2024)
- [Scaling Neural Program Synthesis with Distribution-based Search](https://mlsanity.com/paper/2110.12485/) (2021)
- [Compositional Generalization and Decomposition in Neural Program Synthesis](https://mlsanity.com/paper/2204.03758/) (2022)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [Neural Machine Translation for Code Generation](https://mlsanity.com/paper/2305.13504/) (2023)
- [Neural Program Synthesis with Query](https://mlsanity.com/paper/2205.07857/) (2022)
- [Synthesizing Programs with Continuous Optimization](https://mlsanity.com/paper/2211.00828/) (2022)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [Understanding in Artificial Intelligence](https://mlsanity.com/paper/2101.06573/) (2021)
- [Searching for Better Database Queries in the Outputs of Semantic Parsers](https://mlsanity.com/paper/2210.07201/) (2022)
- [Improved Tree Search for Automatic Program Synthesis](https://mlsanity.com/paper/2303.07166/) (2023)
- [WikiCoder: Learning to Write Knowledge-Powered Code](https://mlsanity.com/paper/2303.08574/) (2023)
- [Learning-Based Automatic Synthesis of Software Code and Configuration](https://mlsanity.com/paper/2305.15642/) (2023)
- [mlirSynth: Automatic, Retargetable Program Raising in Multi-Level IR using Program Synthesis](https://mlsanity.com/paper/2310.04196/) (2023)

## Abstract (arXiv)

We consider the problem of generating automatic code given sample input-output pairs. We train a neural network to map from the current state and the outputs to the program's next statement. The neural network optimizes multiple tasks concurrently: the next operation out of a set of high level commands, the operands of the next statement, and which variables can be dropped from memory. Using our method we are able to create programs that are more than twice as long as existing state-of-the-art solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Our code, including an implementation of various literature baselines, is publicly available at https://github.com/amitz25/PCCoder