# Representing Partial Programs with Blended Abstract Semantics

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2020.

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

- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutions](https://mlsanity.com/paper/2205.14318/) (2022)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [Static Prediction of Runtime Errors by Learning to Execute Programs with External Resource Descriptions](https://mlsanity.com/paper/2203.03771/) (2022)
- [Towards Efficient Neurally-Guided Program Induction for ARC-AGI](https://mlsanity.com/paper/2411.17708/) (2024)
- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)
- [A Divide-Align-Conquer Strategy for Program Synthesis](https://mlsanity.com/paper/2301.03094/) (2023)
- [Learning to Edit Visual Programs with Self-Supervision](https://mlsanity.com/paper/2406.02383/) (2024)
- [ObSynth: An Interactive Synthesis System for Generating Object Models from Natural Language Specifications](https://mlsanity.com/paper/2210.11468/) (2022)
- [Neural Abstructions: Abstractions that Support Construction for Grounded Language Learning](https://mlsanity.com/paper/2107.09285/) (2021)
- [SwissNYF: Tool Grounded LLM Agents for Black Box Setting](https://mlsanity.com/paper/2402.10051/) (2024)
- [Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery](https://mlsanity.com/paper/2607.01280/) (2026)

## Abstract (arXiv)

Synthesizing programs from examples requires searching over a vast, combinatorial space of possible programs. In this search process, a key challenge is representing the behavior of a partially written program before it can be executed, to judge if it is on the right track and predict where to search next. We introduce a general technique for representing partially written programs in a program synthesis engine. We take inspiration from the technique of abstract interpretation, in which an approximate execution model is used to determine if an unfinished program will eventually satisfy a goal specification. Here we learn an approximate execution model implemented as a modular neural network. By constructing compositional program representations that implicitly encode the interpretation semantics of the underlying programming language, we can represent partial programs using a flexible combination of concrete execution state and learned neural representations, using the learned approximate semantics when concrete semantics are not known (in unfinished parts of the program). We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs, such as loops and higher-order functions, and can be used to synthesize programs more accurately for a given search budget than pure neural approaches in several domains.