Document Open Access Logo

Scopes and Frames Improve Meta-Interpreter Specialization

Authors Vlad Vergu, Andrew Tolmach , Eelco Visser

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECOOP.2019.4.pdf
  • Filesize: 0.79 MB
  • 30 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Software and its engineering → Interpreters
Keywords
  • Definitional interpreters
  • partial evaluation

Metrics

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

Abstract

DynSem is a domain-specific language for concise specification of the dynamic semantics of programming languages, aimed at rapid experimentation and evolution of language designs. To maintain a short definition-to-execution cycle, DynSem specifications are meta-interpreted. Meta-interpretation introduces runtime overhead that is difficult to remove by using interpreter optimization frameworks such as the Truffle/Graal Java tools; previous work has shown order-of-magnitude improvements from applying Truffle/Graal to a meta-interpreter, but this is still far slower than what can be achieved with a language-specific interpreter. In this paper, we show how specifying the meta-interpreter using scope graphs, which encapsulate static name binding and resolution information, produces much better optimization results from Truffle/Graal. Furthermore, we identify that JIT compilation is hindered by large numbers of calls between small polymorphic rules and we introduce rule cloning to derive larger monomorphic rules at run time as a countermeasure. Our contributions improve the performance of DynSem-derived interpreters to within an order of magnitude of a handwritten language-specific interpreter.

Cite As Get BibTex

Vlad Vergu, Andrew Tolmach, and Eelco Visser. Scopes and Frames Improve Meta-Interpreter Specialization. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 4:1-4:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECOOP.2019.4

Author Details

Vlad Vergu
  • Delft University of Technology, Delft, The Netherlands
Andrew Tolmach
  • Portland State University, Portland, OR, USA
Eelco Visser
  • Delft University of Technology, Delft, The Netherlands

Funding

This research was partially funded by the NWO VICI Language Designer’s Workbench project (639.023.206) and by a gift from the Oracle Corporation.

Acknowledgements

We thank the anonymous reviewers for their feedback on previous versions of this paper, and we thank Laurence Tratt for his guidance on obtaining reliable runtime measurements and analyzing the resulting time series.

References

  1. Nada Amin and Tiark Rompf. Collapsing towers of interpreters. Proceedings of the ACM on Programming Languages, 2(POPL), 2018. URL: http://dx.doi.org/10.1145/3158140.
  2. Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Google Scholar
  3. Edd Barrett, Carl Friedrich Bolz-Tereick, Rebecca Killick, Sarah Mount, and Laurence Tratt. Virtual machine warmup blows hot and cold. Proceedings of the ACM on Programming Languages, 1(OOPSLA), 2017. URL: http://dx.doi.org/10.1145/3133876.
  4. Carl Friedrich Bolz. Meta-Tracing Just-in-Time Compilation for RPython. PhD thesis, Heinrich Heine University Düsseldorf, 2014. URL: http://d-nb.info/1057957054.
  5. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. Tracing the meta-level: PyPy’s tracing JIT compiler. In Ian Rogers, editor, Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, ICOOOLPS 2009, Genova, Italy, July 6, 2009, pages 18-25. ACM, 2009. URL: http://dx.doi.org/10.1145/1565824.1565827.
  6. Carl Friedrich Bolz and Laurence Tratt. The impact of meta-tracing on VM design and implementation. Science of Computer Programming, 98:408-421, 2015. URL: http://dx.doi.org/10.1016/j.scico.2013.02.001.
  7. Martin Churchill, Peter D. Mosses, Neil Sculthorpe, and Paolo Torrini. Reusable Components of Semantic Specifications. Transactions on Aspect-Oriented Software Development, 12:132-179, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46734-3_4.
  8. Olivier Danvy and René Vestergaard. Semantics-Based Compiling: A Case Study in Type-Directed Partial Evaluation. In Herbert Kuchen and S. Doaitse Swierstra, editors, Programming Languages: Implementations, Logics, and Programs, 8th International Symposium, PLILP 96, Aachen, Germany, September 24-27, 1996, Proceedings, volume 1140 of Lecture Notes in Computer Science, pages 182-197. Springer, 1996. Google Scholar
  9. Sebastian Erdweg, Tijs van der Storm, Markus Völter, Laurence Tratt, Remi Bosman, William R. Cook, Albert Gerritsen, Angelo Hulshout, Steven Kelly, Alex Loh, Gabriël Konat, Pedro J. Molina, Martin Palatnik, Risto Pohjonen, Eugen Schindler, Klemens Schindler, Riccardo Solmi, Vlad A. Vergu, Eelco Visser, Kevin van der Vlist, Guido Wachsmuth, and Jimi van der Woning. Evaluating and comparing language workbenches: Existing results and benchmarks for the future. Computer Languages, Systems & Structures, 44:24-47, 2015. URL: http://dx.doi.org/10.1016/j.cl.2015.08.007.
  10. Matthias Felleisen, Robby Findler, and Matthew Flatt. Semantics Engineering with PLT Redex. MIT Press, 2009. Google Scholar
  11. Matthias Felleisen and Robert Hieb. The Revised Report on the Syntactic Theories of Sequential Control and State. Theoretical Computer Science, 103(2):235-271, 1992. Google Scholar
  12. Yoshihiko Futamura. Partial Evaluation of Computation Process - An Approach to a Compiler-Compiler. Higher-Order and Symbolic Computation, 12(4):381-391, 1999. URL: http://www.springerlink.com/content/l46w6q3720n57607/.
  13. Yoshihiko Futamura. Partial Evaluation of Computation Process, Revisited. Higher-Order and Symbolic Computation, 12(4):377-380, 1999. Google Scholar
  14. Christian Humer, Christian Wimmer, Christian Wirth, Andreas Wöß, and Thomas Würthinger. A domain-specific language for building self-optimizing AST interpreters. In Ulrik Pagh Schultz and Matthew Flatt, editors, Generative Programming: Concepts and Experiences, GPCE'14, Vasteras, Sweden, September 15-16, 2014, pages 123-132. ACM, 2014. URL: http://dx.doi.org/10.1145/2658761.2658776.
  15. Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial evaluation and automatic program generation. Prentice Hall international series in computer science. Prentice Hall, 1993. Google Scholar
  16. Gilles Kahn. Natural Semantics. In Franz-Josef Brandenburg, Guy Vidal-Naquet, and Martin Wirsing, editors, STACS 87, 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, Germany, February 19-21, 1987, Proceedings, volume 247 of Lecture Notes in Computer Science, pages 22-39. Springer, 1987. Google Scholar
  17. Lennart C. L. Kats and Eelco Visser. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In William R. Cook, Siobhán Clarke, and Martin C. Rinard, editors, Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, pages 444-463, Reno/Tahoe, Nevada, 2010. ACM. URL: http://dx.doi.org/10.1145/1869459.1869497.
  18. Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, and Robby Findler. Run your research: on the effectiveness of lightweight mechanization. In John Field and Michael Hicks, editors, Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, pages 285-296. ACM, 2012. URL: http://dx.doi.org/10.1145/2103656.2103691.
  19. Stefan Marr, Benoit Daloze, and Hanspeter Mössenböck. Cross-language compiler benchmarking: are we fast yet? In Roberto Ierusalimschy, editor, Proceedings of the 12th Symposium on Dynamic Languages, DLS 2016, Amsterdam, The Netherlands, November 1, 2016, pages 120-131. ACM, 2016. URL: http://dx.doi.org/10.1145/2989225.2989232.
  20. Stefan Marr and Stéphane Ducasse. Tracing vs. partial evaluation: comparing meta-compilation approaches for self-optimizing interpreters. In Jonathan Aldrich and Patrick Eugster, editors, Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, part of SPLASH 2015, Pittsburgh, PA, USA, October 25-30, 2015, pages 821-839. ACM, 2015. URL: http://dx.doi.org/10.1145/2814270.2814275.
  21. Peter D. Mosses. Compiler Generation Using Denotational Semantics. In Antoni W. Mazurkiewicz, editor, Mathematical Foundations of Computer Science 1976, 5th Symposium, Gdansk, Poland, September 6-10, 1976, Proceedings, volume 45 of Lecture Notes in Computer Science, pages 436-441. Springer, 1976. Google Scholar
  22. Peter D. Mosses. Modular structural operational semantics. Journal of Logic and Algebraic Programming, 60-61:195-228, 2004. URL: http://dx.doi.org/10.1016/j.jlap.2004.03.008.
  23. Peter D. Mosses and Mark J. New. Implicit Propagation in Structural Operational Semantics. Electronic Notes in Theoretical Computer Science, 229(4):49-66, 2009. URL: http://dx.doi.org/10.1016/j.entcs.2009.07.073.
  24. Pierre Neron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. A Theory of Name Resolution with extended Coverage and Proofs. Technical Report TUD-SERG-2015-001, Software Engineering Research Group. Delft University of Technology, January 2015. Extended version of ESOP 2015 paper "A Theory of Name Resolution". Google Scholar
  25. 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: http://dx.doi.org/10.1007/978-3-662-46669-8_9.
  26. Lawrence C. Paulson. A Semantics-Directed Compiler Generator. In POPL, pages 224-233, 1982. Google Scholar
  27. Gordon D. Plotkin. A structural approach to operational semantics. Journal of Logic and Algebraic Programming, 60-61:17-139, 2004. Google Scholar
  28. Casper Bach Poulsen, Pierre Néron, Andrew P. Tolmach, and Eelco Visser. Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics. In Shriram Krishnamurthi and Benjamin S. Lerner, editors, 30th European Conference on Object-Oriented Programming, ECOOP 2016, July 18-22, 2016, Rome, Italy, volume 56 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2016.20.
  29. Casper Bach Poulsen, Arjen Rouvoet, Andrew P. Tolmach, Robbert Krebbers, and Eelco Visser. Intrinsically-typed definitional interpreters for imperative languages. Proceedings of the ACM on Programming Languages, 2(POPL), 2018. URL: http://dx.doi.org/10.1145/3158104.
  30. Grigore Rosu and Traian-Florin Serbanuta. An overview of the K semantic framework. Journal of Logic and Algebraic Programming, 79(6):397-434, 2010. URL: http://dx.doi.org/10.1016/j.jlap.2010.03.012.
  31. Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, and Rok Strnisa. Ott: Effective tool support for the working semanticist. Journal of Functional Programming, 20(1):71-122, 2010. URL: http://dx.doi.org/10.1017/S0956796809990293.
  32. Hendrik van Antwerpen, Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. A constraint language for static semantic analysis based on scope graphs. In Martin Erwig and Tiark Rompf, editors, Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, pages 49-60. ACM, 2016. URL: http://dx.doi.org/10.1145/2847538.2847543.
  33. Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, and Eelco Visser. Scopes as types. Proceedings of the ACM on Programming Languages, 2(OOPSLA), 2018. URL: http://dx.doi.org/10.1145/3276484.
  34. Vlad A. Vergu, Pierre Néron, and Eelco Visser. DynSem: A DSL for Dynamic Semantics Specification. In Maribel Fernández, editor, 26th International Conference on Rewriting Techniques and Applications, RTA 2015, June 29 to July 1, 2015, Warsaw, Poland, volume 36 of LIPIcs, pages 365-378. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.RTA.2015.365.
  35. Vlad A. Vergu and Eelco Visser. Specializing a meta-interpreter: JIT compilation of Dynsem specifications on the Graal VM. In Eli Tilevich and Hanspeter Mössenböck, editors, Proceedings of the 15th International Conference on Managed Languages & Runtimes, ManLang 2018, Linz, Austria, September 12-14, 2018. ACM, 2018. URL: http://dx.doi.org/10.1145/3237009.3237018.
  36. Eelco Visser, Guido Wachsmuth, Andrew P. Tolmach, Pierre Néron, Vlad A. Vergu, Augusto Passalaqua, and Gabriël Konat. A Language Designer’s Workbench: A One-Stop-Shop for Implementation and Verification of Language Designs. In Andrew P. Black, Shriram Krishnamurthi, Bernd Bruegge, and Joseph N. Ruskiewicz, editors, Onward! 2014, Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, part of SPLASH '14, Portland, OR, USA, October 20-24, 2014, pages 95-111. ACM, 2014. URL: http://dx.doi.org/10.1145/2661136.2661149.
  37. Andreas Wöß, Christian Wirth, Daniele Bonetta, Chris Seaton, Christian Humer, and Hanspeter Mössenböck. An object storage model for the truffle language implementation framework. In Joanna Kolodziej and Bruce R. Childers, editors, 2014 International Conference on Principles and Practices of Programming on the Java Platform Virtual Machines, Languages and Tools, PPPJ '14, Cracow, Poland, September 23-26, 2014, pages 133-144. ACM, 2014. URL: http://dx.doi.org/10.1145/2647508.2647517.
  38. Thomas Würthinger, Christian Wimmer, Christian Humer, Andreas Wöß, Lukas Stadler, Chris Seaton, Gilles Duboscq, Doug Simon, and Matthias Grimmer. Practical partial evaluation for high-performance dynamic language runtimes. In Albert Cohen 0001 and Martin T. Vechev, editors, Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017, pages 662-676. ACM, 2017. URL: http://dx.doi.org/10.1145/3062341.3062381.
  39. Thomas Würthinger, Christian Wimmer, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Christian Humer, Gregor Richards, Doug Simon, and Mario Wolczko. One VM to rule them all. In Antony L. Hosking, Patrick Th. Eugster, and Robert Hirschfeld, editors, ACM Symposium on New Ideas in Programming and Reflections on Software, Onward! 2013, part of SPLASH '13, Indianapolis, IN, USA, October 26-31, 2013, pages 187-204. ACM, 2013. URL: http://dx.doi.org/10.1145/2509578.2509581.
  40. Thomas Würthinger, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Doug Simon, and Christian Wimmer. Self-optimizing AST interpreters. In Alessandro Warth, editor, Proceedings of the 8th Symposium on Dynamic Languages, DLS '12, Tucson, AZ, USA, October 22, 2012, pages 73-82. ACM, 2012. URL: http://dx.doi.org/10.1145/2384577.2384587.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact