Latent Programmer: Discrete Latent Codes for Program Synthesis

Abstract

In many sequence learning tasks, such as program synthesis and document summarization, a key problem is searching over a large space of possible output sequences. We propose to learn representations of the outputs that are specifically meant for search: rich enough to specify the desired output but compact enough to make search more efficient. Discrete latent codes are appealing for this purpose, as they naturally allow sophisticated combinatorial search strategies. The latent codes are learned using a self-supervised learning principle, in which first a discrete autoencoder is trained on the output sequences, and then the resulting latent codes are used as intermediate targets for the end-to-end sequence prediction task. Based on these insights, we introduce the \emph{Latent Programmer}, a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language. We evaluate the Latent Programmer on two domains: synthesis of string transformation programs, and generation of programs from natural language descriptions. We demonstrate that the discrete latent representation significantly improves synthesis accuracy.

arXiv commentICML 2021; 15 pages, 9 figures

References in corpus (22)

• Auto-Encoding Variational Bayes
• Categorical Reparameterization with Gumbel-Softmax
• Neural Discrete Representation Learning
• Stochastic Backpropagation and Approximate Inference in Deep Generative Models
• The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
• DeepCoder: Learning to Write Programs
• Fast Decoding in Sequence Models using Discrete Latent Variables
• RobustFill: Neural Program Learning under Noisy I/O
• Neuro-Symbolic Program Synthesis
• Learning to Search Better Than Your Teacher
• Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models
• Code Generation as a Dual Task of Code Summarization
• Theory and Experiments on Vector Quantized Autoencoders
• Program Synthesis and Semantic Parsing with Learned Code Idioms
• Neural Sketch Learning for Conditional Program Generation
• Language as a Latent Variable: Discrete Generative Models for Sentence Compression
• Automatic Program Synthesis of Long Programs with a Learned Garbage Collector
• Just-in-Time Learning for Bottom-Up Enumerative Synthesis
• Learning to Infer Program Sketches
• Write, Execute, Assess: Program Synthesis with a REPL
• Variational Attention for Sequence-to-Sequence Models
• Neural Program Synthesis with a Differentiable Fixer