Neural Attribute Machines for Program Generation

Matthew Amodio, Swarat Chaudhuri, Thomas W. RepsarXiv 2017 · arXiv

Abstract

Generating highly structured artifacts like source code remains a challenge for standard Recurrent Neural Networks (RNNs) due to complex, non-local constraints. We present Neural Attribute Machines (NAMs), an architecture that integrates deterministic logical machines based on attribute grammars into the RNN framework. By augmenting inputs with structural context and employing a specialized three-level loss function, NAMs significantly improve the generation of valid programs, producing over three times more legal code structures than vanilla models.

Introduction

While Recurrent Neural Networks (RNNs) have achieved remarkable success in natural language processing, their application to formal languages like source code is hindered by the strict requirements of compilers. In programming, a single violation—such as an undeclared variable or a type mismatch—invalidates the entire sequence. These constraints are often non-local, requiring the model to maintain long-term dependencies that exceed the practical memory capacity of standard LSTMs. Rather than forcing models to learn these rigid rules implicitly from data, Neural Attribute Machines (NAMs) bake known language logic directly into the neural architecture.

Methodology: The Neural Attribute Machine

The core innovation of the NAM is the coupling of a standard RNN with a deterministic "logical machine" derived from Attribute Grammars (AGs). AGs provide a formal way to describe context-sensitive constraints by associating attributes with grammar symbols and defining rules for their evaluation.

Attribute grammar rules and corresponding evaluation tree showing attribute flow.

Architecture and Input Augmentation

The NAM enhances the standard sequence generation process in two ways. First, it provides the RNN with a context vector at each time step. This vector, generated by the logical machine, represents the current state of the environment (e.g., a symbol table of declared variables). This offloads the burden of tracking scope and declarations from the RNN's hidden state to a deterministic lookup mechanism.

Three-Level Loss Function

Standard training utilizes cross-entropy loss, which treats all incorrect tokens equally. NAMs introduce a specialized loss function that categorizes potential outputs into three tiers:

  1. Correct: The ground-truth token.
  2. Incorrect-but-Legal: A token that is not the ground truth but satisfies the language's formal constraints.
  3. Incorrect-and-Illegal: A token that violates grammar or scoping rules.

By penalizing illegal moves more severely, the model is incentivized to stay within the "legal manifold" of the program space.

Comparison of standard RNN, context-augmented RNN, and the full NAM architecture incorporating constraint loss.

Experimental Evaluation

The NAM was evaluated on a synthetic corpus of 1,500 C programs containing arithmetic, control flow, and variable manipulations. Programs averaged 101 lines of code with multiple unique variables and types. The programs were represented as linearized Abstract Syntax Trees (ASTs).

Results

The performance was measured by generating 1,000 samples and checking for constraint violations and overall tree legality.

Model Declared-Variable Violations Legal Trees (per 1000)
Vanilla RNN 9,426 187
NAM (Context only) 2,105 532
Full NAM (Context + Loss) 1,846 582

The results demonstrate that providing structural context is the primary driver of performance, while the specialized loss function provides additional refinement. The full NAM architecture produced 582 legal programs out of 1,000, a significant improvement over the 187 produced by the vanilla RNN.

Conclusion

Neural Attribute Machines demonstrate that integrating domain-specific logical constraints into neural architectures is more effective than pure end-to-end learning for highly structured data. By offloading non-local dependency tracking to an attribute-grammar-based logical machine, NAMs achieve higher fidelity to the underlying rules of programming languages. Future work involves extending this framework to more complex subsets of C and other structured domains like mathematical proofs.

Summary updated

Abstract

Recurrent neural networks have achieved remarkable success at generating sequences with complex structures, thanks to advances that include richer embeddings of input and cures for vanishing gradients. Trained only on sequences from a known grammar, though, they can still struggle to learn rules and constraints of the grammar. Neural Attribute Machines (NAMs) are equipped with a logical machine that represents the underlying grammar, which is used to teach the constraints to the neural machine by (i) augmenting the input sequence, and (ii) optimizing a custom loss function. Unlike traditional RNNs, NAMs are exposed to the grammar, as well as samples from the language of the grammar. During generation, NAMs make significantly fewer violations of the constraints of the underlying grammar than RNNs trained only on samples from the language of the grammar.
BibTeX
@misc{amodio2017neural,
  author = {Matthew Amodio and Swarat Chaudhuri and Thomas W. Reps},
  title = {{Neural Attribute Machines for Program Generation}},
  year = {2017},
  eprint = {1705.09231},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.09231},
}
Figure