Daniel A. A. Pelsmaeker
Casper Bach Poulsen
Eelco Visser
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Code completion is an editor service in IDEs that proposes code fragments for the user to insert at the caret position in their code. Code completion should be sound and complete. It should be sound, such that it only proposes fragments that do not violate the syntactic and static semantic rules of the language. It should be complete, such that it proposes all valid fragments so that code completion can be used to construct all programs. To realize soundness and completeness, code completion should be informed by the language definition. In practice, the implementation of code completion is an additional effort in the implementation of a language.
In this paper, we develop a framework for language-parametric semantic code completion for statically typed programming languages based on their specification of syntax and static semantics, realizing the implementation of a code completion editor service with minimal additional effort. The framework builds on the SDF3 syntax definition formalism and the Statix static semantics specification language. The algorithm reinterprets the static semantics definition to find sound expansions of predicates and solutions to name resolution queries in scope graphs. This allows a search strategy to explore the solution space and synthesize completion proposals. The implementation of the strategy language and code completion algorithm extend the implementation of the Statix solver, and can be used for any language defined in Statix. We demonstrate soundness and completeness of the completion proposal synthesis, and evaluate its performance.
Supplemental Material
Available for Download
zip
oopsla22main-p98-p-archive.zip (114 KB)
Appendices accompanying the "Language-Parametric Static Semantic Code Completion" paper.
- Andrew W. Appel. 2002. Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press. isbn:0-521-82060-XGoogle Scholar
- Muhammad Asaduzzaman, Chanchal K. Roy, Kevin A. Schneider, and Daqing Hou. 2014. Context-Sensitive Code Completion Tool for Better API Usability. In 30th IEEE International Conference on Software Maintenance and Evolution, Victoria, BC, Canada, September 29 - October 3, 2014. IEEE, 621–624. isbn:978-0-7695-5303-0 https://doi.org/10.1109/ICSME.2014.110 Google ScholarDigital Library
- Muhammad Asaduzzaman, Chanchal K. Roy, Kevin A. Schneider, and Daqing Hou. 2016. A Simple, Efficient, Context-sensitive Approach for Code Completion. Journal of Software Maintenance, 28, 7 (2016), 512–541. https://doi.org/10.1002/smr.1791 Google ScholarDigital Library
- Edwin Brady. 2013. Idris, a general-purpose dependently typed programming language: Design and implementation. Journal of Functional Programming, 23, 5 (2013), 552–593. https://doi.org/10.1017/S095679681300018X Google ScholarCross Ref
- Marcel Bruch, Martin Monperrus, and Mira Mezini. 2009. Learning from examples to improve code completion systems. In Proceedings of the 7th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2009, Amsterdam, The Netherlands, August 24-28, 2009, Hans van Vliet and Valérie Issarny (Eds.). ACM, 213–222. isbn:978-1-60558-001-2 https://doi.org/10.1145/1595696.1595728 Google ScholarDigital Library
- Luis Eduardo de Souza Amorim, Sebastian Erdweg, Guido Wachsmuth, and Eelco Visser. 2016. Principled syntactic code completion using placeholders. In Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, Amsterdam, The Netherlands, October 31 - November 1, 2016, Tijs van der Storm, Emilie Balland, and Dániel Varró (Eds.). ACM, 163–175. isbn:978-1-4503-4447-0 https://doi.org/10.1145/2997364.2997374 Google ScholarDigital Library
- Luis Eduardo de Souza Amorim and Eelco Visser. 2020. Multi-purpose Syntax Definition with SDF3. In Software Engineering and Formal Methods - 18th International Conference, SEFM 2020, Amsterdam, The Netherlands, September 14-18, 2020, Proceedings, Frank S. de Boer and Antonio Cerone (Eds.) (Lecture Notes in Computer Science, Vol. 12310). Springer, 1–23. isbn:978-3-030-58768-0 https://doi.org/10.1007/978-3-030-58768-0_1 Google ScholarDigital Library
- Sebastian Erdweg, Tijs van der Storm, and Yi Dai. 2014. Capture-Avoiding and Hygienic Program Transformations. In ECOOP 2014 - Object-Oriented Programming - 28th European Conference, Uppsala, Sweden, July 28 - August 1, 2014. Proceedings, Richard Jones (Ed.) (Lecture Notes in Computer Science, Vol. 8586). Springer, 489–514. isbn:978-3-662-44201-2 https://doi.org/10.1007/978-3-662-44202-9_20 Google ScholarDigital Library
- Martin Fowler. 2005. Language Workbenches: The Killer-App for Domain Specific Languages? http://www.martinfowler.com/articles/languageWorkbench.htmlGoogle Scholar
- Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. 2017. Program Synthesis. Foundations and Trends in Programming Languages, 4, 1-2 (2017), 1–119. https://doi.org/10.1561/2500000010 Google ScholarCross Ref
- Vincent J. Hellendoorn, Sebastian Proksch, Harald C. Gall, and Alberto Bacchelli. 2019. When code completion fails: a case study on real-world completions. In Proceedings of the 41st International Conference on Software Engineering, ICSE 2019, Montreal, QC, Canada, May 25-31, 2019, Gunter Mussbacher, Joanne M. Atlee, and Tevfik Bultan (Eds.). IEEE / ACM, 960–970. https://dl.acm.org/citation.cfm?id=3339625Google ScholarDigital Library
- Jetbrains. 2021. Jetbrains MPS. http://jetbrains.com/mps/Google Scholar
- Lennart C. L. Kats and Eelco Visser. 2010. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, William R. Cook, Siobhán Clarke, and Martin C. Rinard (Eds.). ACM, Reno/Tahoe, Nevada. 444–463. isbn:978-1-4503-0203-6 https://doi.org/10.1145/1869459.1869497 Google ScholarDigital Library
- Paul Klint, Tijs van der Storm, and Jurgen J. Vinju. 2009. RASCAL: A Domain Specific Language for Source Code Analysis and Manipulation. In Ninth IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM 2009, Edmonton, Alberta, Canada, September 20-21, 2009. IEEE Computer Society, 168–177. isbn:978-0-7695-3793-1 https://doi.org/10.1109/SCAM.2009.28 Google ScholarDigital Library
- Paul Klint, Tijs van der Storm, and Jurgen J. Vinju. 2010. EASY Meta-Programming with Rascal. Leveraging the Extract-Analyze-SYnthesize Paradigm for Meta-Programming. In Proceedings of the 3rd International Summer School on Generative and Transformational Techniques in Software Engineering (GTTSE’09) (LNCS). Springer. to appearGoogle Scholar
- Paul Klint, Tijs van der Storm, and Jurgen J. Vinju. 2019. Rascal, 10 Years Later. In 19th International Working Conference on Source Code Analysis and Manipulation, SCAM 2019, Cleveland, OH, USA, September 30 - October 1, 2019. IEEE, 139. isbn:978-1-7281-4937-0 https://doi.org/10.1109/SCAM.2019.00023 Google ScholarCross Ref
- Fredrik Lindblad and Marcin Benke. 2004. A Tool for Automated Theorem Proving in Agda. In Types for Proofs and Programs, International Workshop, TYPES 2004, Jouy-en-Josas, France, December 15-18, 2004, Revised Selected Papers, Jean-Christophe Filliâtre, Christine Paulin-Mohring, and Benjamin Werner (Eds.) (Lecture Notes in Computer Science, Vol. 3839). Springer, 154–169. isbn:3-540-31428-8 https://doi.org/10.1007/11617990_10 Google ScholarDigital Library
- Justin Lubin, Nick Collins, Cyrus Omar, and Ravi Chugh. 2020. Program sketching with live bidirectional evaluation. Proceedings of the ACM on Programming Languages, 4, ICFP (2020), https://doi.org/10.1145/3408991 Google ScholarDigital Library
- Linghui Luo, Julian Dolby, and Eric Bodden. 2019. MagpieBridge: A General Approach to Integrating Static Analyses into IDEs and Editors (Tool Insights Paper). In 33rd European Conference on Object-Oriented Programming, ECOOP 2019, July 15-19, 2019, London, United Kingdom, Alastair F. Donaldson (Ed.) (LIPIcs, Vol. 134). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. isbn:978-3-95977-111-5 https://doi.org/10.4230/LIPIcs.ECOOP.2019.21 Google ScholarCross Ref
- Conor McBride. 2000. Dependently typed functional programs and their proofs. Ph. D. Dissertation. University of Edinburgh, UK. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.561753 British Library, EThOSGoogle Scholar
- Conor McBride. 2004. Epigram: Practical Programming with Dependent Types. In Advanced Functional Programming, 5th International School, AFP 2004, Tartu, Estonia, August 14-21, 2004, Revised Lectures, Varmo Vene and Tarmo Uustalu (Eds.) (Lecture Notes in Computer Science, Vol. 3622). Springer, 130–170. isbn:3-540-28540-7 https://doi.org/10.1007/11546382_3 Google ScholarDigital Library
- Conor McBride and James McKinna. 2004. The view from the left. Journal of Functional Programming, 14, 1 (2004), 69–111. https://doi.org/10.1017/S0956796803004829 Google ScholarDigital Library
- Ulf Norell. 2007. Towards a practical programming language based on dependent type theory. Ph. D. Dissertation. Department of Computer Science and Engineering, Chalmers University of Technology. SE-412 96 Göteborg, Sweden.Google Scholar
- Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. 2015. A Theory of Name Resolution. In Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings, Jan Vitek (Ed.) (Lecture Notes in Computer Science, Vol. 9032). Springer, 205–231. isbn:978-3-662-46668-1 https://doi.org/10.1007/978-3-662-46669-8_9 Google ScholarCross Ref
- Cyrus Omar, Ian Voysey, Ravi Chugh, and Matthew A. Hammer. 2019. Live functional programming with typed holes. Proceedings of the ACM on Programming Languages, 3 (2019), https://dl.acm.org/citation.cfm?id=3290327Google Scholar
- Cyrus Omar, Ian Voysey, Michael Hilton, Jonathan Aldrich, and Matthew A. Hammer. 2017. Hazelnut: a bidirectionally typed structure editor calculus. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, Giuseppe Castagna and Andrew D. Gordon (Eds.). ACM, 86–99. isbn:978-1-4503-4660-3 http://dl.acm.org/citation.cfm?id=3009900Google Scholar
- André Pacak and Sebastian Erdweg. 2019. Generating incremental type services. In Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2019, Athens, Greece, October 20-22, 2019, Oscar Nierstrasz, Jeff Gray, and Bruno C. D. S. Oliveira (Eds.). ACM, 197–201. isbn:978-1-4503-6981-7 https://doi.org/10.1145/3357766.3359534 Google ScholarDigital Library
- Rohan Padhye, Koushik Sen, and Paul N. Hilfinger. 2019. ChocoPy: A Programming Language for Compilers Courses. In Proceedings of the 2019 ACM SIGPLAN Symposium on SPLASH-E (SPLASH-E 2019). Association for Computing Machinery, New York, NY, USA. isbn:9781450369893 https://doi.org/10.1145/3358711.3361627 Google ScholarDigital Library
- Daniel A. A. Pelsmaeker, Hendrik van Antwerpen, Casper Bach Poulsen, and Eelco Visser. 2022. Artifact for "Language-Parametric Static Semantic Code Completion". https://doi.org/10.5281/zenodo.6367565 Google ScholarDigital Library
- Daniël A. A. Pelsmaeker, Hendrik van Antwerpen, and Eelco Visser. 2019. Towards Language-Parametric Semantic Editor Services Based on Declarative Type System Specifications (Brave New Idea Paper). In 33rd European Conference on Object-Oriented Programming, ECOOP 2019, July 15-19, 2019, London, United Kingdom, Alastair F. Donaldson (Ed.) (LIPIcs, Vol. 134). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. isbn:978-3-95977-111-5 https://doi.org/10.4230/LIPIcs.ECOOP.2019.26 Google ScholarCross Ref
- Daniel Perelman, Sumit Gulwani, Thomas Ball, and Dan Grossman. 2012. Type-directed completion of partial expressions. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, Beijing, China - June 11 - 16, 2012, Jan Vitek, Haibo Lin, and Frank Tip (Eds.). ACM, 275–286. isbn:978-1-4503-1205-9 https://doi.org/10.1145/2254064.2254098 Google ScholarDigital Library
- Rascal. 2021. TypePal: Name and Type Analysis Made Easy. http://docs.rascal-mpl.org/unstable/TypePalGoogle Scholar
- Veselin Raychev, Martin T. Vechev, and Eran Yahav. 2014. Code completion with statistical language models. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, Michael F. P. O’Boyle and Keshav Pingali (Eds.). ACM, 44. isbn:978-1-4503-2784-8 https://doi.org/10.1145/2594291.2594321 Google ScholarDigital Library
- Arjen Rouvoet, Hendrik van Antwerpen, Casper Bach Poulsen, Robbert Krebbers, and Eelco Visser. 2020. Knowing when to ask: sound scheduling of name resolution in type checkers derived from declarative specifications. Proceedings of the ACM on Programming Languages, 4, OOPSLA (2020), https://doi.org/10.1145/3428248 Google ScholarDigital Library
- Isao Sasano and Kwanghoon Choi. 2021. A text-based syntax completion method using LR parsing. In Proceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM@POPL 2021, Virtual Event, Denmark, January 18-19, 2021, Sam Lindley and Torben Æ. Mogensen (Eds.). ACM, 32–43. isbn:978-1-4503-8305-9 https://doi.org/10.1145/3441296.3441395 Google ScholarDigital Library
- Max Schäfer, Torbjörn Ekman, and Oege de Moor. 2008. Sound and extensible renaming for Java. In Proceedings of the 23rd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2008, October 19-23, 2008, Nashville, TN, USA, Gail E. Harris (Ed.). ACM, 277–294. isbn:978-1-60558-215-3 https://doi.org/10.1145/1449764.1449787 Google ScholarDigital Library
- Armando Solar-Lezama. 2009. The Sketching Approach to Program Synthesis. In Programming Languages and Systems, 7th Asian Symposium, APLAS 2009, Seoul, Korea, December 14-16, 2009. Proceedings, Zhenjiang Hu (Ed.) (Lecture Notes in Computer Science, Vol. 5904). Springer, 4–13. isbn:978-3-642-10671-2 https://doi.org/10.1007/978-3-642-10672-9_3 Google ScholarDigital Library
- Friedrich Steimann, Marcus Frenkel, and Markus Voelter. 2017. Robust projectional editing. In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2017, Vancouver, BC, Canada, October 23-24, 2017, Benoît Combemale, Marjan Mernik, and Bernhard Rumpe (Eds.). ACM, 79–90. isbn:978-1-4503-5525-4 https://doi.org/10.1145/3136014.3136034 Google ScholarDigital Library
- Michael Steindorfer. 2017. Efficient Immutable Collections. Ph. D. Dissertation. Universiteit van Amsterdam.Google Scholar
- Emma Söderberg and Görel Hedin. 2011. Building semantic editors using JastAdd: tool demonstration. In Language Descriptions, Tools and Applications, LDTA 2011, Saarbrücken, Germany, March 26-27, 2011. Proceeding, Claus Brabrand and Eric Van Wyk (Eds.). ACM, 11. isbn:978-1-4503-0665-2 https://doi.org/10.1145/1988783.1988794 Google ScholarDigital Library
- Hendrik van Antwerpen, Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. 2016. A constraint language for static semantic analysis based on scope graphs. In Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, Martin Erwig and Tiark Rompf (Eds.). ACM, 49–60. isbn:978-1-4503-4097-7 https://doi.org/10.1145/2847538.2847543 Google ScholarDigital Library
- Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, and Eelco Visser. 2018. Scopes as types. Proceedings of the ACM on Programming Languages, 2, OOPSLA (2018), https://doi.org/10.1145/3276484 Google ScholarDigital Library
- Eelco Visser, Zine-El-Abidine Benaissa, and Andrew P. Tolmach. 1998. Building Program Optimizers with Rewriting Strategies. In Proceedings of the third ACM SIGPLAN international conference on Functional programming, Matthias Felleisen, Paul Hudak, and Christian Queinnec (Eds.). ACM, Baltimore, Maryland, United States. 13–26. https://doi.org/10.1145/289423.289425 Google ScholarDigital Library
- Xtext Team. 2021. Xtext. https://www.eclipse.org/Xtext/Google Scholar
Index Terms
- Language-parametric static semantic code completion
Recommendations
Principled syntactic code completion using placeholders
SLE 2016: Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language EngineeringPrincipled syntactic code completion enables developers to change source code by inserting code templates, thus increasing developer efficiency and supporting language exploration. However, existing code completion systems are ad-hoc and neither ...
Code Completion from Abbreviated Input
ASE '09: Proceedings of the 24th IEEE/ACM International Conference on Automated Software EngineeringAbbreviation Completion is a novel technique to improve the efficiency of code-writing by supporting code completion of multiple keywords based on non-predefined abbreviated input -- a different approach from conventional code completion that finds one ...
Code completion of multiple keywords from abbreviated input
Abbreviation Completion is a novel technique to improve the efficiency of code-writing by supporting code completion of multiple keywords based on non-predefined abbreviated input--a different approach from conventional code completion that finds one ...
Comments