Open Vocabulary Learning on Source Code with a Graph-Structured Cache

Often models that operate on source code consume ASTs by linearizing them (usually with a depth-first traversal) (Amodio et al., 2017; Liu et al., 2017; Li et al., 2017), but they can also be processed by deep learning models that take graphs as input, as in White et al. (2016) and Chen et al. (2018) who use Recursive Neural Networks (RveNNs) (Goller & Kuchler, 1996) on ASTs. RveNNs are models that operate on tree-topology graphs, and have been used extensively for language modeling (Socher et al., 2013) and on domains similar to source code, like mathematical expressions (Zaremba et al., 2014; Arabshahi et al., 2018). They can be considered a special case of Message Passing Neural Networks (MPNNs) in the framework of Gilmer et al. (2017): in this analogy RveNNs are to Belief Propagation as MPNNs are to Loopy Belief Propagation. They can also be considered a special case of Graph Networks in the framework of Battaglia et al. (2018). ASTs also serve as a natural basis for models that generate code as output, as in Maddison & Tarlow (2014), Yin & Neubig (2017), Rabinovich et al. (2017), Chen et al. (2018), and Brockschmidt et al. (2018).