Document Open Access Logo

Transient Typechecks Are (Almost) Free

Authors Richard Roberts , Stefan Marr , Michael Homer , James Noble

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECOOP.2019.5.pdf
  • Filesize: 0.56 MB
  • 28 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Software and its engineering → Just-in-time compilers
  • Software and its engineering → Object oriented languages
  • Software and its engineering → Interpreters
Keywords
  • dynamic type checking
  • gradual types
  • optional types
  • Grace
  • Moth
  • object-oriented programming

Metrics

Abstract

Transient gradual typing imposes run-time type tests that typically cause a linear slowdown. This performance impact discourages the use of type annotations because adding types to a program makes the program slower. A virtual machine can employ standard just-in-time optimizations to reduce the overhead of transient checks to near zero. These optimizations can give gradually-typed languages performance comparable to state-of-the-art dynamic languages, so programmers can add types to their code without affecting their programs' performance.

Cite As Get BibTex

Richard Roberts, Stefan Marr, Michael Homer, and James Noble. Transient Typechecks Are (Almost) Free. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECOOP.2019.5

Author Details

Richard Roberts
  • School of Engineering and Computer Science, Victoria University of Wellington, New Zealand
Stefan Marr
  • School of Computing, University of Kent, UK
Michael Homer
  • School of Engineering and Computer Science, Victoria University of Wellington, New Zealand
James Noble
  • School of Engineering and Computer Science, Victoria University of Wellington, New Zealand

Funding

This work is supported by the Royal Society of New Zealand Marsden Fund.

References

  1. Martín Abadi, Luca Cardelli, Benjamin C. Pierce, and Gordon D. Plotkin. Dynamic Typing in a Statically Typed Language. ACM Trans. Program. Lang. Syst., 13(2):237-268, 1991. URL: http://dx.doi.org/10.1145/103135.103138.
  2. Amal Ahmed, Robert Bruce Findler, Jeremy G. Siek, and Philip Wadler. Blame for all. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 201-214, 2011. URL: http://dx.doi.org/10.1145/1926385.1926409.
  3. Esteban Allende, Oscar Callaú, Johan Fabry, Éric Tanter, and Marcus Denker. Gradual typing for Smalltalk. Sci. Comput. Program., 96:52-69, 2014. URL: http://dx.doi.org/10.1016/j.scico.2013.06.006.
  4. Edd Barrett, Carl Friedrich Bolz-Tereick, Rebecca Killick, Sarah Mount, and Laurence Tratt. Virtual Machine Warmup Blows Hot and Cold. Proc. ACM Program. Lang., 1(OOPSLA):52:1-52:27, October 2017. Google Scholar
  5. Spenser Bauman, Carl Friedrich Bolz, Robert Hirschfeld, Vasily Kirilichev, Tobias Pape, Jeremy G. Siek, and Sam Tobin-Hochstadt. Pycket: a tracing JIT for a functional language. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, ICFP 2015, Vancouver, BC, Canada, September 1-3, 2015, pages 22-34, 2015. URL: http://dx.doi.org/10.1145/2784731.2784740.
  6. Spenser Bauman, Carl Friedrich Bolz-Tereick, Jeremy Siek, and Sam Tobin-Hochstadt. Sound Gradual Typing: Only Mostly Dead. Proc. ACM Program. Lang., 1(OOPSLA):54:1-54:24, October 2017. Google Scholar
  7. Michael Bayne, Richard Cook, and Michael D. Ernst. Always-available static and dynamic feedback. In Proceedings of the 33rd International Conference on Software Engineering (ICSE), pages 521-530, 2011. Google Scholar
  8. Gavin M. Bierman, Martín Abadi, and Mads Torgersen. Understanding TypeScript. In ECOOP 2014 - Object-Oriented Programming - 28th European Conference, Uppsala, Sweden, July 28 - August 1, 2014. Proceedings, pages 257-281, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44202-9_11.
  9. Andrew P. Black, Kim B. Bruce, Michael Homer, and James Noble. Grace: the absence of (inessential) difficulty. In Onward! '12: Proceedings 12th SIGPLAN Symp. on New Ideas in Programming and Reflections on Software, pages 85-98, New York, NY, 2012. ACM. Google Scholar
  10. Andrew P. Black, Norman C. Hutchinson, Eric Jul, and Henry M. Levy. The development of the Emerald programming language. In Proceedings of the Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III), San Diego, California, USA, 9-10 June 2007, pages 1-51, 2007. URL: http://dx.doi.org/10.1145/1238844.1238855.
  11. Bard Bloom, John Field, Nathaniel Nystrom, Johan Östlund, Gregor Richards, Rok Strniša, Jan Vitek, and Tobias Wrigstad. Thorn: Robust, Concurrent, Extensible Scripting on the JVM. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 117-136, 2009. Google Scholar
  12. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. Tracing the Meta-level: PyPy’s Tracing JIT Compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, ICOOOLPS '09, pages 18-25. ACM, 2009. Google Scholar
  13. Carl Friedrich Bolz, Lukas Diekmann, and Laurence Tratt. Storage Strategies for Collections in Dynamically Typed Languages. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA'13, pages 167-182. ACM, 2013. Google Scholar
  14. Carl Friedrich Bolz and Laurence Tratt. The Impact of Meta-Tracing on VM Design and Implementation. Science of Computer Programming, 98:408-424, February 2013. Google Scholar
  15. John Tang Boyland. The Problem of Structural Type Tests in a Gradual-Typed Language. In FOOL, 2014. Google Scholar
  16. Gilad Bracha. Pluggable Type Systems. OOPSLA Workshop on Revival of Dynamic Languages, October 2004. Google Scholar
  17. Gilad Bracha and David Griswold. Stongtalk: Typechecking Smalltalk in a Production Environment. In OOPSLA, 1993. Google Scholar
  18. Gilad Bracha, Peter von der Ahé, Vassili Bykov, Yaron Kashai, William Maddox, and Eliot Miranda. Modules as Objects in Newspeak. In European Conference on Object-Oriented Programming (ECOOP), volume 6183 of Lecture Notes in Computer Science, pages 405-428. Springer, 2010. Google Scholar
  19. Kim Bruce, Andrew Black, Michael Homer, James Noble, Amy Ruskin, and Richard Yannow. Seeking Grace: a new object-oriented language for novices. In Proceedings 44th SIGCSE Technical Symposium on Computer Science Education, pages 129-134. ACM, 2013. Google Scholar
  20. Craig Chambers, David Ungar, and Elgin Lee. An Efficient Implementation of SELF a Dynamically-Typed Object-Oriented Language Based on Prototypes. In Proceedings on Object-Oriented Programming Systems, Languages and Applications, OOPSLA'89, pages 49-70. ACM, October 1989. Google Scholar
  21. Maxime Chevalier-Boisvert and Marc Feeley. Interprocedural Type Specialization of JavaScript Programs Without Type Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016), volume 56 of LIPIcs, pages 7:1-7:24. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2016.7.
  22. Benjamin Chung, Paley Li, Francesco Zappa Nardelli, and Jan Vitek. KafKa: gradual typing for objects. In 32nd European Conference on Object-Oriented Programming, ECOOP 2018, July 16-21, 2018, Amsterdam, The Netherlands, pages 12:1-12:24, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2018.12.
  23. Daniel Clifford, Hannes Payer, Michael Stanton, and Ben L. Titzer. Memento Mori: Dynamic Allocation-site-based Optimizations. In Proceedings of the 2015 International Symposium on Memory Management, ISMM '15, pages 105-117. ACM, 2015. Google Scholar
  24. Benoit Daloze, Stefan Marr, Daniele Bonetta, and Hanspeter Mössenböck. Efficient and Thread-Safe Objects for Dynamically-Typed Languages. In Proceedings of the 2016 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA'16, pages 642-659. ACM, 2016. Google Scholar
  25. Ulan Degenbaev, Jochen Eisinger, Manfred Ernst, Ross McIlroy, and Hannes Payer. Idle Time Garbage Collection Scheduling. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'16, pages 570-583. ACM, 2016. Google Scholar
  26. M. Furr, J.-H. An, J. Foster, and M.J. Hicks. Static type inference for Ruby. In Symposium on Applied Computation, pages 1859-1866, 2009. Google Scholar
  27. Adele Goldberg and David Robson. Smalltalk-80: The Language and its Implementation. Addison-Wesley, 1983. Google Scholar
  28. Ben Greenman and Matthias Felleisen. A spectrum of type soundness and performance. PACMPL, 2(ICFP):71:1-71:32, 2018. URL: http://dx.doi.org/10.1145/3236766.
  29. Ben Greenman and Zeina Migeed. On the Cost of Type-Tag Soundness. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'18, pages 30-39. ACM, 2018. Google Scholar
  30. Ben Greenman, Asumu Takikawa, Max S. New, Daniel Feltey, Robert Bruce Findler, Jan Vitek, and Matthias Felleisen. How to evaluate the performance of gradual type systems. Journal of Functional Programming, 29:45, 2019. URL: http://dx.doi.org/10.1017/S0956796818000217.
  31. Christian Humer, Christian Wimmer, Christian Wirth, Andreas Wöß, and Thomas Würthinger. A Domain-Specific Language for Building Self-Optimizing AST Interpreters. In Proceedings of the 13th International Conference on Generative Programming: Concepts and Experiences, GPCE '14, pages 123-132. ACM, 2014. URL: http://dx.doi.org/10.1145/2658761.2658776.
  32. Urs Hölzle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches. In ECOOP '91: European Conference on Object-Oriented Programming, volume 512 of LNCS, pages 21-38. Springer, 1991. URL: http://dx.doi.org/10.1007/BFb0057013.
  33. Ralph E. Johnson. Type-Checking Smalltalk. In Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'86), Portland, Oregon, USA, Proceedings., pages 315-321, 1986. URL: http://dx.doi.org/10.1145/28697.28728.
  34. Timothy Jones. Classless Object Semantics. PhD thesis, Victoria University of Wellington, 2017. Google Scholar
  35. Timothy Jones, Michael Homer, James Noble, and Kim Bruce. Object Inheritance Without Classes. In 30th European Conference on Object-Oriented Programming (ECOOP 2016), volume 56, pages 13:1-13:26, 2016. Google Scholar
  36. Andre Kuhlenschmidt, Deyaaeldeen Almahallawi, and Jeremy G. Siek. Efficient Gradual Typing. CoRR, abs/1802.06375, 2018. URL: http://arxiv.org/abs/1802.06375.
  37. Ole Lehrmann Madsen, Birger Møller-Pedersen, and Kristen Nygaard. Object-Oriented Programming in the BETA Programming Language. Addison-Wesley, 1993. Google Scholar
  38. Stefan Marr. SOMns: a newspeak for concurrency research. https://github.com/smarr/SOMns, 2018. Google Scholar
  39. Stefan Marr. ReBench: Execute and Document Benchmarks Reproducibly, June 2019. Version 1.0rc2. URL: http://dx.doi.org/10.5281/zenodo.3242039.
  40. Stefan Marr, Benoit Daloze, and Hanspeter Mössenböck. Cross-Language Compiler Benchmarking - Are We Fast Yet? In Proceedings of the 12th Symposium on Dynamic Languages, DLS'16, pages 120-131. ACM, November 2016. Google Scholar
  41. Stefan Marr and Stéphane Ducasse. Tracing vs. Partial Evaluation: Comparing Meta-Compilation Approaches for Self-Optimizing Interpreters. In Proceedings of the 2015 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA '15, pages 821-839. ACM, October 2015. Google Scholar
  42. Fabian Muehlboeck and Ross Tate. Sound Gradual Typing is Nominally Alive and Well. Proc. ACM Program. Lang., 1(OOPSLA):56:1-56:30, October 2017. Google Scholar
  43. Francisco Ortin, Miguel Garcia, and Seán McSweeney. Rule-based program specialization to optimize gradually typed code. Knowledge-Based Systems, 2019. URL: http://dx.doi.org/10.1016/j.knosys.2019.05.013.
  44. Aaron Pang, Craig Anslow, and James Noble. What Programming Languages Do Developers Use? A Theory of Static vs Dynamic Language Choice. In 2018 IEEE Symposium on Visual Languages and Human-Centric Computing, VL/HCC 2018, Lisbon, Portugal, October 1-4, 2018, pages 239-247, 2018. URL: http://dx.doi.org/10.1109/VLHCC.2018.8506534.
  45. Gregor Richards, Ellen Arteca, and Alexi Turcotte. The VM Already Knew That: Leveraging Compile-time Knowledge to Optimize Gradual Typing. Proc. ACM Program. Lang., 1(OOPSLA):55:1-55:27, October 2017. Google Scholar
  46. Gregor Richards, Francesco Zappa Nardelli, and Jan Vitek. Concrete Types for TypeScript. In 29th European Conference on Object-Oriented Programming, ECOOP 2015, July 5-10, 2015, Prague, Czech Republic, pages 76-100, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2015.76.
  47. Richard Roberts, Stefan Marr, Michael Homer, and James Noble. Toward Virtual Machine Adaption Rather than Reimplementation. In MoreVMs'17: 1st International Workshop on Workshop on Modern Language Runtimes, Ecosystems, and VMs at <Programming> 2017, 2017. Presentation. Google Scholar
  48. Jeremy G. Siek and Walid Taha. Gradual typing for functional languages. In Seventh Workshop on Scheme and Functional Programming, volume Technical Report TR-2006-06, pages 81-92. University of Chicago, September 2006. Google Scholar
  49. Jeremy G. Siek and Walid Taha. Gradual Typing for Objects. In ECOOP 2007 - Object-Oriented Programming, 21st European Conference, Berlin, Germany, July 30 - August 3, 2007, Proceedings, pages 2-27, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73589-2_2.
  50. Jeremy G. Siek, Michael M. Vitousek, Matteo Cimini, and John Tang Boyland. Refined Criteria for Gradual Typing. In Thomas Ball, Rastislav Bodik, Shriram Krishnamurthi, Benjamin S. Lerner, and Greg Morrisett, editors, 1st Summit on Advances in Programming Languages (SNAPL 2015), volume 32 of Leibniz International Proceedings in Informatics (LIPIcs), pages 274-293. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  51. Jeremy G. Siek, Michael M. Vitousek, Matteo Cimini, Sam Tobin-Hochstadt, and Ronald Garcia. Monotonic References for Efficient Gradual Typing. In European Symposium on Programming (ESOP), pages 432-456, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46669-8_18.
  52. Jeremy G. Siek and Philip Wadler. Threesomes, with and without blame. In Proceedings of the 37th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010, Madrid, Spain, January 17-23, 2010, pages 365-376, 2010. URL: http://dx.doi.org/10.1145/1706299.1706342.
  53. Vincent St-Amour, Sam Tobin-Hochstadt, and Matthias Felleisen. Optimization coaching: optimizers learn to communicate with programmers. In Proceedings of the 27th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2012, part of SPLASH 2012, Tucson, AZ, USA, October 21-25, 2012, pages 163-178, 2012. URL: http://dx.doi.org/10.1145/2384616.2384629.
  54. G.L. Steele. Common Lisp the Language. Digital Press, 1990. Google Scholar
  55. Nataliia Stulova, José F. Morales, and Manuel V. Hermenegildo. Reducing the Overhead of Assertion Run-time Checks via Static Analysis. In Proceedings of the 18th International Symposium on Principles and Practice of Declarative Programming, PPDP'16, pages 90-103. ACM, 2016. Google Scholar
  56. Asumu Takikawa, Daniel Feltey, Ben Greenman, Max S. New, Jan Vitek, and Matthias Felleisen. Is Sound Gradual Typing Dead? In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'16, pages 456-468. ACM, 2016. Google Scholar
  57. Asumu Takikawa, T. Stephen Strickland, Christos Dimoulas, Sam Tobin-Hochstadt, and Matthias Felleisen. Gradual typing for first-class classes. In Proceedings of the 27th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2012, part of SPLASH 2012, Tucson, AZ, USA, October 21-25, 2012, pages 793-810, 2012. URL: http://dx.doi.org/10.1145/2384616.2384674.
  58. The Clean. Vehicle. Flying Nun Records, FN147, 1990. Google Scholar
  59. Sam Tobin-Hochstadt and Matthias Felleisen. The design and implementation of Typed Scheme. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008, pages 395-406, 2008. URL: http://dx.doi.org/10.1145/1328438.1328486.
  60. Michael M. Vitousek, Andrew M. Kent, Jeremy G. Siek, and Jim Baker. Design and evaluation of gradual typing for Python. In DLS'14, Proceedings of the 10th ACM Symposium on Dynamic Languages, part of SPLASH 2014, Portland, OR, USA, October 20-24, 2014, pages 45-56, 2014. URL: http://dx.doi.org/10.1145/2661088.2661101.
  61. Michael M. Vitousek, Jeremy G. Siek, and Avik Chaudhuri. Optimizing and Evaluating Transient Gradual Typing. CoRR, abs/1902.07808, 2019. URL: http://arxiv.org/abs/1902.07808.
  62. Michael M. Vitousek, Cameron Swords, and Jeremy G. Siek. Big Types in Little Runtime: Open-world Soundness and Collaborative Blame for Gradual Type Systems. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL'17, pages 762-774. ACM, 2017. Google Scholar
  63. Philip Wadler and Robert Bruce Findler. Well-Typed Programs Can't Be Blamed. In European Symposium on Programming Languages and Systems (ESOP), pages 1-16, 2009. Google Scholar
  64. Preston Tunnell Wilson, Ben Greenman, Justin Pombrio, and Shriram Krishnamurthi. The Behavior of Gradual Types: A User Study. In Dynamic Language Symposium (DLS), 2018. Google Scholar
  65. 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 Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, PPPJ'14, pages 133-144. ACM, 2014. Google Scholar
  66. 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 Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'17, pages 662-676. ACM, 2017. Google Scholar
  67. 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 Proceedings of the 2013 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, Onward! 2013, pages 187-204. ACM, 2013. Google Scholar
  68. Thomas Würthinger, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Doug Simon, and Christian Wimmer. Self-Optimizing AST Interpreters. In Proceedings of the 8th Dynamic Languages Symposium, DLS'12, pages 73-82, October 2012. URL: http://dx.doi.org/10.1145/2384577.2384587.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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