Document Open Access Logo

On Solving Solved Problems

Author Sebastian Erdweg

PDF
Thumbnail PDF

File

OASIcs.EVCS.2023.10.pdf
  • Filesize: 371 kB
  • 6 pages

Document Identifiers

Author Details

Sebastian Erdweg
  • Johannes Gutenberg-Universität Mainz, Germany

Acknowledgements

The idea for this essay occurred during the preparation for the "Discussion with Experts" session on the Specification and Implementation of Type Systems that Eelco Visser and I moderated at ECOOP 2021. One of the points we had put up for discussion was: Are type systems the new "solved problem that isn’t solved"? I want to thank the reviewers for helping me to get the historical facts straight and André Pacak for feedback on draft of this paper.

Cite AsGet BibTex

Sebastian Erdweg. On Solving Solved Problems. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 10:1-10:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/OASIcs.EVCS.2023.10

Abstract

Some problems are considered solved by the research community. But are they really and does that mean we should stop investigating them? In this essay, I argue that "solved" problems often only appear solved on the surface, while fundamental open research problems lurk below the surface. It requires dedicated researchers to discover those open problems by applying the existing solutions and putting them to the test.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parsing
  • Theory of computation → Program analysis
Keywords
  • Research Methodology
  • Parsing
  • Type Checking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ali Afroozeh, Mark van den Brand, Adrian Johnstone, Elizabeth Scott, and Jurgen J. Vinju. Safe specification of operator precedence rules. In Software Language Engineering - 6th International Conference, SLE 2013, Indianapolis, IN, USA, October 26-28, 2013. Proceedings, volume 8225 of Lecture Notes in Computer Science, pages 137-156. Springer, 2013. Google Scholar
  2. Alfred V. Aho, Stephen C. Johnson, and Jeffrey D. Ullman. Deterministic parsing of ambiguous grammars. Commun. ACM, 18(8):441-452, 1975. URL: https://doi.org/10.1145/360933.360969.
  3. Maartje de Jonge, Lennart C. L. Kats, Eelco Visser, and Emma Söderberg. Natural and flexible error recovery for generated modular language environments. ACM Transactions on Programming Languages and Systems, 34(4):15, 2012. URL: https://doi.org/10.1145/2400676.2400678.
  4. Luis Eduardo de Souza Amorim, Sebastian Erdweg, Guido Wachsmuth, and Eelco Visser. Principled syntactic code completion using placeholders. In Tijs van der Storm, Emilie Balland, and Dániel Varró, editors, Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, Amsterdam, The Netherlands, October 31 - November 1, 2016, pages 163-175. ACM, 2016. Google Scholar
  5. Luís Eduardo de Souza Amorim, Michael J. Steindorfer, Sebastian Erdweg, and Eelco Visser. Declarative specification of indentation rules: a tooling perspective on parsing and pretty-printing layout-sensitive languages. In Proceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2018, Boston, MA, USA, November 05-06, 2018, pages 3-15. ACM, 2018. Google Scholar
  6. Luis Eduardo de Souza Amorim, Michael J. Steindorfer, and Eelco Visser. Deep priority conflicts in the wild: a pilot study. In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2017, Vancouver, BC, Canada, October 23-24, 2017, pages 55-66. ACM, 2017. URL: https://doi.org/10.1145/3136014.3136020.
  7. Luis Eduardo de Souza Amorim, Michael J. Steindorfer, and Eelco Visser. Towards zero-overhead disambiguation of deep priority conflicts. Programming Journal, 2(3):13, 2018. URL: https://doi.org/10.22152/programming-journal.org/2018/2/13.
  8. Luis Eduardo de Souza Amorim and Eelco Visser. Multi-purpose syntax definition with SDF3. In Frank S. de Boer and Antonio Cerone, editors, Software Engineering and Formal Methods - 18th International Conference, SEFM 2020, Amsterdam, The Netherlands, September 14-18, 2020, Proceedings, volume 12310 of Lecture Notes in Computer Science, pages 1-23. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-58768-0_1.
  9. Jay Earley. Ambiguity and precedence in syntax description. Acta Informatica, 4:183-192, 1974. URL: https://doi.org/10.1007/BF00288747.
  10. Sebastian Erdweg, Oliver Bracevac, Edlira Kuci, Matthias Krebs, and Mira Mezini. A co-contextual formulation of type rules and its application to incremental type checking. In Jonathan Aldrich and Patrick Eugster, editors, Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 880-897. ACM, 2015. URL: https://doi.org/10.1145/2814270.2814277.
  11. Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. Layout-sensitive generalized parsing. In Software Language Engineering, 5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers, volume 7745 of Lecture Notes in Computer Science, pages 244-263. Springer, 2012. Google Scholar
  12. Jan Heering, P. R. H. Hendriks, Paul Klint, and J. Rekers. The syntax definition formalism SDF - reference manual. ACM SIGPLAN Notices, 24(11):43-75, 1989. URL: https://doi.org/10.1145/71605.71607.
  13. Lennart C. L. Kats and Eelco Visser. 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, October 17-21, 2010, Reno/Tahoe, Nevada, USA, pages 444-463. ACM, 2010. Google Scholar
  14. Paul Klint and Eelco Visser. Using filters for the disambiguation of context-free grammars. In Proc. ASMICS Workshop on Parsing Theory, pages 1-20. Milan, Italy, 1994. Google Scholar
  15. Edlira Kuci, Sebastian Erdweg, Oliver Bracevac, Andi Bejleri, and Mira Mezini. A co-contextual type checker for featherweight java. In 31st European Conference on Object-Oriented Programming, ECOOP 2017, June 19-23, 2017, Barcelona, Spain, volume 74 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ECOOP.2017.18.
  16. Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. A theory of name resolution. In Jan Vitek, editor, 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, volume 9032 of Lecture Notes in Computer Science, pages 205-231. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46669-8_9.
  17. André Pacak and Sebastian Erdweg. 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, pages 197-201. ACM, 2019. URL: https://doi.org/10.1145/3357766.3359534.
  18. André Pacak, Sebastian Erdweg, and Tamás Szabó. A systematic approach to deriving incremental type checkers. Proc. ACM Program. Lang., 4(OOPSLA):127:1-127:28, 2020. URL: https://doi.org/10.1145/3428195.
  19. Daniel A. A. Pelsmaeker, Hendrik van Antwerpen, Casper Bach Poulsen, and Eelco Visser. Language-parametric static semantic code completion. Proc. ACM Program. Lang., 6(OOPSLA1), April 2022. URL: https://doi.org/10.1145/3527329.
  20. Hendrik van Antwerpen and Eelco Visser. Scope states: Guarding safety of name resolution in parallel type checkers. In Anders Møller and Manu Sridharan, editors, 35th European Conference on Object-Oriented Programming, ECOOP 2021, July 11-17, 2021, Aarhus, Denmark (Virtual Conference), volume 194 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ECOOP.2021.1.
  21. Eelco Visser. A case study in optimizing parsing schemata by disambiguation filters. In Sandiway Fong, editor, International Workshop on Parsing Technologies, IWPT 1997, Boston, MA, USA, September 17-20, 1997, pages 210-224, 1997. URL: https://aclanthology.org/1997.iwpt-1.24/.
  22. Eelco Visser. Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam, September 1997. Google Scholar
  23. Guido Wachsmuth, Gabriël Konat, Vlad A. Vergu, Danny M. Groenewegen, and Eelco Visser. A language independent task engine for incremental name and type analysis. In Martin Erwig, Richard F. Paige, and Eric Van Wyk, editors, Software Language Engineering - 6th International Conference, SLE 2013, Indianapolis, IN, USA, October 26-28, 2013. Proceedings, volume 8225 of Lecture Notes in Computer Science, pages 260-280. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-02654-1_15.
  24. Aron Zwaan, Hendrik van Antwerpen, and Eelco Visser. Incremental type-checking for free: Using scope graphs to derive incremental type-checkers. Proc. ACM Program. Lang., 6(OOPSLA2), October 2022. URL: https://doi.org/10.1145/3563303.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact