Elamur Research⌕
☰
home / papers / 2016 / Programming with a Differentiable Forth Interpreter

Programming with a Differentiable Forth Interpreter

Paper · 2016 · Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky et al.

Summary

Neural networks that learn algorithms usually depend on large amounts of input-output data. A programmer, however, often knows the rough shape of a solution, such as how to walk through a sequence, without knowing the exact operation needed at each step. Bošnjak et al. present ∂4, a continuous, differentiable version of the abstract machine behind the stack-based language Forth. Users write program "sketches": ordinary Forth code with gaps (slots) that neural networks fill in. These slots are trained by backpropagation on input-output pairs. Execution runs as an RNN in TensorFlow over differentiable stacks, a heap and a program counter.

The authors tested sketches with different amounts of prior structure on sorting and addition tasks from Reed & de Freitas. With only the recursive structure provided, the learned programs generalised to input sizes not seen in training. Coupled with a BiLSTM and trained jointly on word algebra problems, ∂4 achieved state-of-the-art end-to-end accuracy without hand-built intermediate representations. This shows that partial code knowledge can act as a strong prior when data is scarce.

Key points

  • The machine state has a data stack D, a return stack R, a heap H and a program counter c. Each is implemented as a differentiable memory buffer with read/write operations similar to the Neural Turing Machine.
  • Forth words such as DUP, DROP and SWAP are turned into differentiable state transitions. Control flow reduces to jumps via BRANCH and BRANCH0.
  • Two sketch styles are demonstrated for Bubble sort:
    • PERMUTE learns how to reorder the top stack elements.
    • COMPARE learns whether to apply NOP or SWAP.
  • For word algebra problems, BiLSTM outputs (a representation of the whole problem, context vectors of the numbers, and the numbers themselves) are written into the heap H. This makes the whole pipeline end-to-end differentiable.
  • The paper also introduces code optimisations based on symbolic execution that speed up neural execution. It was published at ICML 2017 (PMLR 70), with authors from UCL, Oxford and Cambridge.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of CambridgeCambridge · United Kingdom287 works · 125,174 citations🎓University of OxfordOxford · United Kingdom138 works · 161,448 citations🎓University College LondonLondon · United Kingdom119 works · 23,545 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksComputer Science Applications · 184 works

Cite

Cite as Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky and Sebastian Riedel. 2016. Programming with a Differentiable Forth Interpreter. arXiv:1605.06640.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1605.06640 · arXiv 1605.06640

@misc{bosnjak2016programming,
  title = {{Programming with a Differentiable Forth Interpreter}},
  author = {Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky and Sebastian Riedel},
  year = {2016},
  doi = {10.48550/arxiv.1605.06640},
  eprint = {1605.06640},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1605.06640}
}

References

36 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Abadi, Martı́n, Agarwal, Ashish, Barham, Paul, Brevdo, Eugene, Chen, Zhifeng, Citro, Craig, Corrado, Greg S., Davis, Andy, Dean, Jeffrey, Devin, Matthieu, Ghemawat, Sanjay, Goodfellow, Ian, Harp, Andrew, Irving, Geoffrey, Isard, Michael, Jia, Yangqing, Jozefowicz, Rafal, Kaiser, Lukasz, Kudlur, Manj… find
  2. Albarghouthi, Aws, Gulwani, Sumit, and Kincaid, Zachary. Recursive program synthesis. In Computer Aided Verification, pp. 934–950. Springer, 2013. find
  3. Andreas, Jacob, Rohrbach, Marcus, Darrell, Trevor, and Klein, Dan. Neural module networks. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  4. ANSI. Programming Languages - Forth, 1994. American National Standard for Information Systems, ANSI X3.215-1994. find
  5. Bouchard, Guillaume, Stenetorp, Pontus, and Riedel, Sebastian. Learning to generate textual data. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1608–1616, 2016. find
  6. Brodie, Leo. Starting Forth. Forth Inc., 1980. find
  7. Bunel, Rudy, Desmaison, Alban, Kohli, Pushmeet, Torr, Philip HS, and Kumar, M Pawan. Adaptive neural compilation. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), 2016. find
  8. Gaunt, Alexander L, Brockschmidt, Marc, Singh, Rishabh, Kushman, Nate, Kohli, Pushmeet, Taylor, Jonathan, and Tarlow, Daniel. TerpreT: A Probabilistic Programming Language for Program Induction. arXiv preprint arXiv:1608.04428, 2016. find
  9. Goodman, Noah, Mansinghka, Vikash, Roy, Daniel M, Bonawitz, Keith, and Tenenbaum, Joshua B. Church: a language for generative models. In Proceedings of the Conference in Uncertainty in Artificial Intelligence (UAI), pp. 220–229, 2008. find
  10. Graves, Alex, Wayne, Greg, and Danihelka, Ivo. Neural Turing Machines. arXiv preprint arXiv:1410.5401, 2014. find
  11. Graves, Alex, Wayne, Greg, Reynolds, Malcolm, Harley, Tim, Danihelka, Ivo, Grabska-Barwińska, Agnieszka, Colmenarejo, Sergio Gómez, Grefenstette, Edward, Ramalho, Tiago, Agapiou, John, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471–476, 2016. find
  12. Grefenstette, Edward, Hermann, Karl Moritz, Suleyman, Mustafa, and Blunsom, Phil. Learning to Transduce with Unbounded Memory. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), pp. 1819–1827, 2015. find
  13. Gruau, Frédéric, Ratajszczak, Jean-Yves, and Wiber, Gilles. A Neural compiler. Theoretical Computer Science, 141 (1):1–52, 1995. find
  14. Hochreiter, Sepp and Schmidhuber, Jürgen. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997. find
  15. Joulin, Armand and Mikolov, Tomas. Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets. In Proceedings of the Conferences on Neural Information Processing Systems (NIPS), pp. 190–198, 2015. find
  16. Kaiser, Łukasz and Sutskever, Ilya. Neural GPUs learn algorithms. In Proceedings of the International Conference on Learning Representations (ICLR), 2015. find
  17. King, James C. Symbolic Execution and Program Testing. Commun. ACM, 19(7):385–394, 1976. find
  18. Kingma, Diederik and Ba, Jimmy. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference for Learning Representations (ICLR), 2015.
  19. Kitzelmann, Emanuel. Inductive Programming: A Survey of Program Synthesis Techniques. In International Workshop on Approaches and Applications of Inductive Programming, pp. 50–73, 2009. find
  20. Koncel-Kedziorski, Rik, Hajishirzi, Hannaneh, Sabharwal, Ashish, Etzioni, Oren, and Ang, Siena. Parsing Algebraic Word Problems into Equations. Transactions of the Association for Computational Linguistics (TACL), 3: 585–597, 2015. find
  21. Koza, John R. Genetic Programming: On the Programming of Computers by Means of Natural Selection, volume 1. MIT press, 1992. find
  22. Kurach, Karol, Andrychowicz, Marcin, and Sutskever, Ilya. Neural Random-Access Machines. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
  23. Kushman, Nate, Artzi, Yoav, Zettlemoyer, Luke, and Barzilay, Regina. Learning to Automatically Solve Algebra Word Problems. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pp. 271–281, 2014. find
  24. Lau, Tessa, Wolfman, Steven A., Domingos, Pedro, and Weld, Daniel S. Learning repetitive text-editing procedures with smartedit. In Your Wish is My Command, pp. 209–226. Morgan Kaufmann Publishers Inc., 2001. find
  25. Maclaurin, Dougal, Duvenaud, David, and Adams, Ryan P. Gradient-based Hyperparameter Optimization through Reversible Learning. In Proceedings of the International Conference on Machine Learning (ICML), 2015. find
  26. Manna, Zohar and Waldinger, Richard J. Toward automatic program synthesis. Communications of the ACM, 14(3): 151–165, 1971. find
  27. Neelakantan, Arvind, Le, Quoc V, and Sutskever, Ilya. Neural Programmer: Inducing latent programs with gradient descent. In Proceedings of the International Conference on Learning Representations (ICLR), 2015a. find
  28. Neelakantan, Arvind, Vilnis, Luke, Le, Quoc V, Sutskever, Ilya, Kaiser, Lukasz, Kurach, Karol, and Martens, James. Adding Gradient Noise Improves Learning for Very Deep Networks. arXiv preprint arXiv:1511.06807, 2015b. find
  29. Nordin, Peter. Evolutionary Program Induction of Binary Machine Code and its Applications. PhD thesis, der Universitat Dortmund am Fachereich Informatik, 1997. find
  30. Reed, Scott and de Freitas, Nando. Neural programmer-interpreters. In Proceedings of the International Conference on Learning Representations (ICLR), 2015. find
  31. Roy, Subhro and Roth, Dan. Solving General Arithmetic Word Problems. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1743–1752, 2015.
  32. Roy, Subhro, Vieira, Tim, and Roth, Dan. Reasoning about quantities in natural language. Transactions of the Association for Computational Linguistics (TACL), 3: 1–13, 2015. find
  33. Siegelmann, Hava T. Neural Programming Language. In Proceedings of the Twelfth AAAI National Conference on Artificial Intelligence, pp. 877–882, 1994. find
  34. Solar-Lezama, Armando, Rabbah, Rodric, Bodı́k, Rastislav, and Ebcioğlu, Kemal. Programming by Sketching for Bit-streaming Programs. In Proceedings of Programming Language Design and Implementation (PLDI), pp. 281–294, 2005. find
  35. Solar-Lezama, Armando, Tancau, Liviu, Bodik, Rastislav, Seshia, Sanjit, and Saraswat, Vijay. Combinatorial Sketching for Finite Programs. In ACM Sigplan Notices, volume 41, pp. 404–415, 2006. find
  36. Sutskever, Ilya, Vinyals, Oriol, and Le, Quoc V. Sequence to Sequence Learning with Neural Networks. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), pp. 3104–3112, 2014.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bosnjak-2016-programming-differentiable-forth-interpreter/