Learning to Represent Programs with Property Signatures

Abstract

We introduce the notion of property signatures, a representation for programs and program specifications meant for consumption by machine learning algorithms. Given a function with input type ${\tau }_{in}$ and output type ${\tau }_{out}$, a property is a function of type: $({\tau }_{in},{\tau }_{out})\to \text{Bool}$ that (informally) describes some simple property of the function under consideration. For instance, if ${\tau }_{in}$ and ${\tau }_{out}$ are both lists of the same type, one property might ask `is the input list the same length as the output list?'. If we have a list of such properties, we can evaluate them all for our function to get a list of outputs that we will call the property signature. Crucially, we can `guess' the property signature for a function given only a set of input/output pairs meant to specify that function. We discuss several potential applications of property signatures and show experimentally that they can be used to improve over a baseline synthesizer so that it emits twice as many programs in less than one-tenth of the time.

ICLR 2020

References in corpus (6)

• Learning Natural Coding Conventions
• DeepCoder: Learning to Write Programs
• RobustFill: Neural Program Learning under Noisy I/O
• Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
• Automatic Program Synthesis of Long Programs with a Learned Garbage Collector
• Learning to Infer Program Sketches

Cited by in corpus (11)

• Program Synthesis with Large Language Models
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
• MISIM: A Neural Code Semantics Similarity System Using the Context-Aware Semantics Structure
• Sketch-Driven Regular Expression Generation from Natural Language and Examples
• Representing Partial Programs with Blended Abstract Semantics
• Program Synthesis with Best-First Bottom-Up Search
• Context-Aware Parse Trees
• Latent Execution for Neural Program Synthesis
• Neural Program Generation Modulo Static Analysis
• Type-driven Neural Programming by Example
• Learning to Combine Per-Example Solutions for Neural Program Synthesis