Latent Programmer: Discrete Latent Codes for Program Synthesis

Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, Manzil Zaheer
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:4308-4318, 2021.

Abstract

A key problem in program synthesis is searching over the large space of possible programs. Human programmers might decide the high-level structure of the desired program before thinking about the details; motivated by this intuition, we consider two-level search for program synthesis, in which the synthesizer first generates a plan, a sequence of symbols that describes the desired program at a high level, before generating the program. We propose to learn representations of programs that can act as plans to organize such a two-level search. Discrete latent codes are appealing for this purpose, and can be learned by applying recent work on discrete autoencoders. Based on these insights, we introduce the Latent Programmer (LP), a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language. We evaluate the LP on two domains, demonstrating that it yields an improvement in accuracy, especially on longer programs for which search is most difficult.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-hong21a, title = {Latent Programmer: Discrete Latent Codes for Program Synthesis}, author = {Hong, Joey and Dohan, David and Singh, Rishabh and Sutton, Charles and Zaheer, Manzil}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {4308--4318}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/hong21a/hong21a.pdf}, url = {https://proceedings.mlr.press/v139/hong21a.html}, abstract = {A key problem in program synthesis is searching over the large space of possible programs. Human programmers might decide the high-level structure of the desired program before thinking about the details; motivated by this intuition, we consider two-level search for program synthesis, in which the synthesizer first generates a plan, a sequence of symbols that describes the desired program at a high level, before generating the program. We propose to learn representations of programs that can act as plans to organize such a two-level search. Discrete latent codes are appealing for this purpose, and can be learned by applying recent work on discrete autoencoders. Based on these insights, we introduce the Latent Programmer (LP), a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language. We evaluate the LP on two domains, demonstrating that it yields an improvement in accuracy, especially on longer programs for which search is most difficult.} }
Endnote
%0 Conference Paper %T Latent Programmer: Discrete Latent Codes for Program Synthesis %A Joey Hong %A David Dohan %A Rishabh Singh %A Charles Sutton %A Manzil Zaheer %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-hong21a %I PMLR %P 4308--4318 %U https://proceedings.mlr.press/v139/hong21a.html %V 139 %X A key problem in program synthesis is searching over the large space of possible programs. Human programmers might decide the high-level structure of the desired program before thinking about the details; motivated by this intuition, we consider two-level search for program synthesis, in which the synthesizer first generates a plan, a sequence of symbols that describes the desired program at a high level, before generating the program. We propose to learn representations of programs that can act as plans to organize such a two-level search. Discrete latent codes are appealing for this purpose, and can be learned by applying recent work on discrete autoencoders. Based on these insights, we introduce the Latent Programmer (LP), a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language. We evaluate the LP on two domains, demonstrating that it yields an improvement in accuracy, especially on longer programs for which search is most difficult.
APA
Hong, J., Dohan, D., Singh, R., Sutton, C. & Zaheer, M.. (2021). Latent Programmer: Discrete Latent Codes for Program Synthesis. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:4308-4318 Available from https://proceedings.mlr.press/v139/hong21a.html.

Related Material