  Generating formal-language programs represented by relational tuples, such as
Lisp programs or mathematical operations, to solve problems stated in natural
language is a challenging task because it requires explicitly capturing
discrete symbolic structural information implicit in the input. However, most
general neural sequence models do not explicitly capture such structural
information, limiting their performance on these tasks. In this paper, we
propose a new encoder-decoder model based on a structured neural
representation, Tensor Product Representations (TPRs), for mapping
Natural-language problems to Formal-language solutions, called TP-N2F. The
encoder of TP-N2F employs TPR `binding' to encode natural-language symbolic
structure in vector space and the decoder uses TPR `unbinding' to generate, in
symbolic space, a sequential program represented by relational tuples, each
consisting of a relation (or operation) and a number of arguments. TP-N2F
considerably outperforms LSTM-based seq2seq models on two benchmarks and
creates new state-of-the-art results. Ablation studies show that improvements
can be attributed to the use of structured TPRs explicitly in both the encoder
and decoder. Analysis of the learned structures shows how TPRs enhance the
interpretability of TP-N2F.
