Source-linked AI summary
Abstract Syntax Networks for Code Generation and Semantic Parsing
Maxim Rabinovich, Mitchell Stern, Dan Klein
TL;DR
Code generation and semantic parsing must produce well-formed outputs despite mismatched input and output structures. The paper introduces abstract syntax networks, which recursively decode abstract syntax trees through grammar-specific modules. The model reaches 79.2 BLEU and 22.7% exact match on Hearthstone, improves JOBS to 92.9% exact match, and performs competitively on ATIS and GEO.
Problem
Code generation and semantic parsing require structured, well-formed outputs, but existing sequence-to-sequence approaches do not model richer output constraints such as well-formedness, well-typedness, and executability.
Method
Abstract syntax networks extend encoder-decoder models with modular decoders that recursively generate abstract syntax trees in a top-down manner using grammar-specific submodels.
Results
The model substantially improves Hearthstone code generation, reaches 92.9% exact match on JOBS, and performs competitively on ATIS and GEO.
Takeaways & Limitations
ASNs provide a modular architecture for structured-output tasks, particularly those involving recursive decompositions, with minimal adaptation across tasks.
Takeaways & Limitations
Existing evaluation metrics only approximate functional equivalence, while semantic coherence, long-distance dependencies, well-typedness, and executability remain unresolved.
Abstract
from arXiv · showhide
Tasks like code generation and semantic parsing require mapping unstructured (or partially structured) inputs to well-formed, executable outputs. We introduce abstract syntax networks, a modeling framework for these problems. The outputs are represented as abstract syntax trees (ASTs) and constructed by a decoder with a dynamically-determined modular structure paralleling the structure of the output tree. On the benchmark Hearthstone dataset for code generation, our model obtains 79.2 BLEU and 22.7% exact match accuracy, compared to previous state-of-the-art values of 67.1 and 6.1%. Furthermore, we perform competitively on the Atis, Jobs, and Geo semantic parsing datasets with no task-specific engineering.
1 Introduction
Abstract syntax networks address structured but nonsynchronous code generation and semantic parsing by decoding abstract syntax trees with a modular, recursively chosen decoder. They substantially improve Hearthstone code generation and remain competitive across semantic parsing benchmarks.
- Motivation: Code generation and semantic parsing require well-formed outputs even when output structure diverges from input structure.Sequence-to-sequence models exploit sequential structure but do not account for richer output constraints such as well-formedness, well-typedness, and executability.
- Approach: Abstract syntax networks use modular encoder-decoder models whose submodels recursively generate abstract syntax trees in a top-down manner.Each module corresponds to a specific construct in the AST grammar, and the recursion mirrors the structure of the produced tree.
- Results: 92.9% exact match on JOBS improves over the previous record of 90.7%, while ATIS and GEO results match or exceed Dong and Lapata (2016).The model does not reach the records held by the best previous semantic parsing approaches on ATIS and GEO.
- Related work: ASNs differ from related tree-prediction approaches through recursive top-down generation and modules tied to AST grammar constructs.Compared with doubly-recurrent decoding, the model uses separate modules for grammar constructs and exploits labeled AST nodes and edges.
2 Data Representation
The paper represents code and logical forms as typed abstract syntax trees specified with ASDL grammars. Constructors define language constructs and their named, typed fields, while inputs are encoded as named token sequences.
- Abstract Syntax Trees: ASDL represents code fragments as trees with typed primitive and composite nodes.Primitive nodes store atomic values such as identifiers, while composite nodes represent language constructs through constructors.
- Abstract Syntax Trees: Each composite node selects a constructor that specifies how the node expands into named, typed children.Examples include ClassDef for class definitions and Call for function calls.
- Abstract Syntax Trees: Constructor fields have singular, optional, or sequential cardinality, with sequential fields representing zero or more children.Sequential fields commonly encode statement blocks such as class and function bodies.
- Semantic Parsing: Semantic-parsing logical forms can also be specified with ASDL using primitive variables, predicates, and atoms alongside composite logical operators.The resulting representations are lambda-calculus or Prolog-style logical-form trees.
- Inputs: Inputs are represented as named components containing token sequences, with Hearthstone cards using names, descriptions, and categorical attributes.For Hearthstone, input and output vocabularies are restricted to values occurring more than once.
3 Model Architecture
The model uses a hierarchical-attention encoder-decoder whose mutually recursive modules mirror the AST grammar and generated tree. Modules choose constructors, propagate recurrent state through fields, generate primitive values, and attend over input components and tokens.
- Architecture: The decoder is a collection of mutually recursive modules corresponding to AST grammar elements, with vertical LSTM state passed between modules.Its recursive call graph mirrors the structure of the output tree.
- Attention: The encoder uses bidirectional LSTMs for input components, while component- and token-level attention supplies input representations during decoding.Token-level scores combine raw token scores with component-level scores before a softmax produces attention weights.
- Decoder Modules: Composite type modules select constructors with a feedforward network and softmax, then pass control to the chosen constructor module.Constructor modules compute context-dependent intermediate vertical states for each constructor field.
- Decoder Modules: Field modules handle cardinality-specific expansion: optional fields make a zero-or-one decision, while sequential fields use a horizontal LSTM for repeated child decisions and updates.Sequential generation stops when its continuation decision is zero; otherwise, the model updates states and proceeds to the next child.
- Decoder Modules: Primitive modules select values from closed lists or choose whether to synthesize open-class strings with a character-level LSTM.For open-class types, training includes the binary decision probability for using the character generator.
- Attention: Supervised attention uses string-match alignments to encourage primitive-node attention toward matched input tokens through an additional loss term.When no matches are found, the supervised token set defaults to the whole input, and the term is interpretable as the negative log probability of attending to that set.
4 Experimental evaluation
The evaluation measures abstract syntax networks on three semantic parsing datasets and HEARTHSTONE code generation, using exact-match and BLEU-based comparisons. Results show strong benchmark performance, while error analysis identifies greater difficulty with complex imperative code and limitations of current evaluation metrics.
- Data: The experiments use JOBS, GEO, and ATIS semantic parsing datasets plus HEARTHSTONE code-generation data.JOBS contains 640 pairs, GEO 880, ATIS 5,410, and HEARTHSTONE 665 card-implementation pairs.
- Evaluation: Evaluation uses tree exact match for semantic parsing and exact match, token-level BLEU, and tree metrics for HEARTHSTONE.Semantic-parsing comparisons canonicalize conjunction and disjunction child order; HEARTHSTONE additionally evaluates node-based precision, recall, and F1.
- Semantic parsing results: 92.9% exact-match accuracy is achieved on JOBS with supervised attention, improving on the basic system’s 91.4%.The model exceeds or matches Dong and Lapata (2016) on ATIS and GEO but remains below prior best results reported by Wang et al. (2014).
- HEARTHSTONE results: 22.7% exact match and 79.2 BLEU are achieved on HEARTHSTONE with supervised attention, improving over prior results of 6.1% and 67.1.Without supervised attention, exact match rises from 6.1% to 18.2% and BLEU from 67.1 to 77.6.
- Error analysis: Cards with minimal descriptions or mostly nested function calls are usually predicted correctly because their code shares common, regular structure.The simplest cases mainly require matching a common structure and inserting correct values; nested-call cases still show occasional undergeneration, overgeneration, or incorrect predicates.
- Error analysis: Complex imperative card logic is most challenging, and the most complex predictions can deviate significantly from the correct implementation.Variable naming, nontrivial control flow, and library conventions contribute to the difficulty.
- Limitations: Functional equivalence remains difficult to evaluate because BLEU, tree F1, and exact match only approximate it, while direct testing requires integration with the game engine.Canonicalized metrics, such as anonymizing variables, may be more meaningful, but direct functional-equivalence evaluation is generally impossible and practically challenging here.
5 Conclusion
Abstract syntax networks provide a modular encoder-decoder architecture for structured output spaces, especially recursive decompositions. Their decoding process parallels output structure, supporting tree prediction and suggesting broader applications.
- ASNs provide a modular encoder-decoder architecture for tasks with structured output spaces.
- ASNs are particularly applicable when outputs admit recursive decompositions.Their decoding process can closely parallel the inherent structure of those outputs.
- The reported results demonstrate promise for tree prediction tasks.
- Applying ASNs to more general output structures is identified as future work.
A Appendix
The appendix presents the λ-calculus grammar used by the system and the Prolog-style grammar used for the JOBS task.
- The JOBS task uses a Prolog-style grammar.
- The system uses a λ-calculus grammar.