Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-14T03:44:04.207Z Has data issue: false hasContentIssue false
  • English
  • Français

How to evaluate the performance of gradual type systems

Part of: JFP Research Articles

Published online by Cambridge University Press:  20 February 2019

BEN GREENMAN Open the ORCID record for BEN GREENMAN [Opens in a new window] ,
ASUMU TAKIKAWA ,
MAX S. NEW ,
DANIEL FELTEY ,
ROBERT BRUCE FINDLER ,
JAN VITEK  and
MATTHIAS FELLEISEN
BEN GREENMAN*
Affiliation:
Northeastern University, Boston, MA, USA (e-mail: benjaminlgreenman@gmail.com)
ASUMU TAKIKAWA
Affiliation:
Northeastern University, Boston, MA, USA Igalia, San Francisco, CA, USA (e-mail: asumu@simplyrobot.org)
MAX S. NEW
Affiliation:
Northeastern University, Boston, MA, USA (e-mail: maxsnew@gmail.com)
DANIEL FELTEY
Affiliation:
Northeastern University, Boston, MA, USA Northwestern University, Chicago, IL, USA (e-mail: daniel.feltey@eecs.northwestern.edu)
ROBERT BRUCE FINDLER
Affiliation:
Northwestern University, Chicago, IL, USA (e-mail: robby@eecs.northwestern.edu)
JAN VITEK
Affiliation:
Northeastern University, Boston, MA, USA Czech Technical University, Prague, Czech Republic (e-mail: j.vitek@neu.edu)
MATTHIAS FELLEISEN
Affiliation:
Northeastern University, Boston, MA, USA (e-mail: matthias@ccs.neu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A sound gradual type system ensures that untyped components of a program can never break the guarantees of statically typed components. This assurance relies on runtime checks, which in turn impose performance overhead in proportion to the frequency and nature of interaction between typed and untyped components. The literature on gradual typing lacks rigorous descriptions of methods for measuring the performance of gradual type systems. This gap has consequences for the implementors of gradual type systems and developers who use such systems. Without systematic evaluation of mixed-typed programs, implementors cannot precisely determine how improvements to a gradual type system affect performance. Developers cannot predict whether adding types to part of a program will significantly degrade (or improve) its performance. This paper presents the first method for evaluating the performance of sound gradual type systems. The method quantifies both the absolute performance of a gradual type system and the relative performance of two implementations of the same gradual type system. To validate the method, the paper reports on its application to 20 programs and 3 implementations of Typed Racket.

Type
Regular Paper
Information
Journal of Functional Programming , Volume 29 , 2019 , e4
Copyright
© Cambridge University Press 2019 

References

Aiken, A., Wimmers, E. L. & Lakshman, T. K. (1994) Soft Typing with conditional types. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 163–173.Google Scholar
Allende, E., Callaú, O., Fabry, J., Tanter, É. & Denker, M. (2013) Gradual typing for Smalltalk. Sci. Comput. Program.96(1), 52–69.Google Scholar
Anderson, C., Giannini, P. & Drossopoulou, S. (2005) Toward type inference for JavaScript. In Proceedings of European Conference Object-Oriented Programming, pp. 428–452.Google Scholar
Bauman, S., Bolz, C. F., Hirschfield, R., Kirilichev, V., Pape, T., Siek, J. G. & Tobin-Hochstadt, S. (2015) Pycket: A tracing JIT for a functional language. In Proceedings of ACM International Conference on Functional Programming, pp. 22–34.Google Scholar
Bauman, S., Tobin-Hochstadt, S., Siek, J. G. & Bolz-Tereick, J. G. (2017) Sound gradual typing: Only mostly dead. In Proceedings of the ACM on Programming Languages. 1(OOPSLA), pp. 54:1–54:24.Google Scholar
Bloom, B., Field, J., Nystrom, N., Östlund, J., Richards, G., Strniša, R., Vitek, J. & Wrigstad, T. (2009) Thorn: Robust, concurrent, extensible scripting on the JVM. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, pp. 117–136.Google Scholar
Cartwright, R. & Fagan, M. (1991) Soft typing. In Proceedings of ACM Conference on Programming Language Design and Implementation, pp. 278–292.Google Scholar
Consel, C. (1988) New insights into partial evaluation: The SCHISM experiment. In Proceedings of European Symposium on Programming, pp. 236–246.Google Scholar
Curtsinger, C. & Berger, E. (2013) Stabilizer: Statistically sound performance evaluation. In Proceedings of ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 219–228.Google Scholar
Dimoulas, C., Tobin-Hochstadt, S. & Felleisen, M. (2012) Complete monitors for behavioral contracts. In Proceedings of European Symposium on Programming, pp. 214–233.Google Scholar
Fieller, E. C. (1957) Some problems in interval estimation. J. R. Stat. Soc.16(2), 175–185.Google Scholar
Flanagan, C., Flatt, M., Krishnamurthi, S., Weirich, S. & Felleisen, M. (1996) Catching bugs in the web of program invariants. In Proceedings of ACM Conference on Programming Language Design and Implementation, pp. 23–32.Google Scholar
Flatt, M. (2016) Bindings as sets of scopes. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 705–717.Google Scholar
Franz, Volker H. (2007) Ratios: A short guide to confidence limits and proper use. Unpublished Manuscript. https://arxiv.org/abs/0710.2024.Google Scholar
Furr, M., (David) An, J.-H., Foster, J. S. & Hicks, M. (2009) Static type inference for Ruby. In Proceedings of Symposium on Applied Computing, pp. 1859–1866.Google Scholar
Gallesio, E. & Serrano, M. (1995) Bigloo: A portable and optimizing compiler for strict functional languages. In Proceedings of International Static Analysis Symposium, pp. 366–381.Google Scholar
Garcia, R. (2013) Calculating threesomes, with blame. In Proceedings of ACM International Conference on Functional Programming, pp. 417–428.Google Scholar
Garcia, R. & Cimini, M. (2015) Principal type schemes for gradual programs. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 303–315.Google Scholar
Garcia, R., Clark, A. M. & Tanter, É. (2016) Abstracting gradual typing. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 429–442.Google Scholar
Greenberg, M. (2015) Space-efficient manifest contracts. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 181–194.Google Scholar
Greenberg, M. (2016) Space-efficient latent contracts. arXiv:1604.02474v4. Accessed 2018-12-03.Google Scholar
Greenman, B. & Felleisen, M. (2018) A spectrum of type soundness and performance. In Proceedings of the ACM on Programming Languages. 2(ICFP), pp. 71:1–71:32.Google Scholar
Greenman, B. & Migeed, Z. (2018) On the cost of type-tag soundness. In Proceedings of ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, pp. 30–39.CrossRefGoogle Scholar
Gu, D., Verbrugge, C. & Gagnon, E. (2005) Code layout as a source of noise in JVM performance. Stud. Inform. Univers.4(1), 83–99.Google Scholar
Henglein, F. (1992) Global tagging optimization by type inference. In Proceedings of ACM Symposium on LISP and Functional Programming, pp. 205–215.Google Scholar
Henglein, F. & Rehof, J. (1995) Safe polymorphic type inference for a dynamically typed language: Translating scheme to ML. In Proceedings of ACM International Conference on Functional Programming Languages and Computer Architecture, pp. 192–203.Google Scholar
Herman, D., Tomb, A. & Flanagan, C. (2010) Space-efficient gradual typing. Higher Order Symb. Comput. 23(2), 167–189.CrossRefGoogle Scholar
Jagannathan, S. & Wright, A. K. (1995) Effective flow analysis for avoiding run-time checks. In Proceedings of International Static Analysis Symposium, pp. 207–224.CrossRefGoogle Scholar
Knowles, K., Tomb, A., Gronski, J., Freund, S. N. & Flanagan, C. (2007) Sage: Unified Hybrid Checking for First-Class Types, General Refinement Types, and Dynamic (Extended Report).Google Scholar
Lemonnier, E. (2006) Pluto: Or how to make Perl juggle with billions. Forum on Free and Open Source Software (FREENIX). Available at: http://erwan.lemonnier.se/talks/pluto.html. Accessed 2018-12-03.Google Scholar
Matthews, J. & Findler, R. B. (2009) Operational semantics for multi-language programs. Trans. Program. Lang. Syst. 31(3), 12:1–12:44.Google Scholar
Moon, D. A. (1974) MACLISP Reference Manual. Massachusetts Institute of Technology.Google Scholar
Mytkowicz, T., Diwan, A., Hauswirth, M. & Sweeney, P. F. (2009) Producing wrong data without doing anything obviously wrong. In Proceedings of ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 265–276.Google Scholar
Neyman, J. (1937) Outline of a theory of statistical estimation based on the classical theory of probability. Philos. Trans. R. Soc. Lond.236(767), 333–380.Google Scholar
Nguyen, L. C. (2014) Tough Behavior in Repeated Bargaining Game. A Computer Simulation Study. Master in Economics dissertation, University of Trento.Google Scholar
Nguyen, P., Tobin-Hochstadt, S., & Van Horn, D. (2014) Soft Contract Verification. In Proceedings of ACM International Conference on Functional Programming, pp. 139–152.Google Scholar
Rastogi, A., Swamy, N., Fournet, C., Bierman, G. & Vekris, P. (2015) Safe & efficient gradual typing for TypeScript. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 167–180.Google Scholar
Ren, B. M. & Foster, J. S. (2016) Just-in-time static type checking for dynamic languages. In Proceedings of ACM Conference on Programming Language Design and Implementation, pp. 462–476.Google Scholar
Richards, G., Nardelli, F. Z. & Vitek, J. (2015) Concrete types for TypeScript. In Proceedings of European Conference on Object-Oriented Programming, pp. 76–100.Google Scholar
Siek, J. G. & Taha, W. (2006) Gradual typing for functional languages. In Proceedings of Scheme and Functional Programming Workshop, University of Chicago, TR-2006-06, 2006.Google Scholar
Siek, J. G., Thiemann, P. & Wadler, P. (2015a) Blame and coercion: Together again for the first time. In Proceedings ACM Conference on Programming Language Design and Implementation, pp. 425–435.Google Scholar
Siek, J. G. & Vachharajani, M. (2008) Gradual typing with unification-based inference. In Proceedings of Dynamic Languages Symposium, Article 7.Google Scholar
Siek, J. G., Vitousek, M. M., Cimini, M., Tobin-Hochstadt, S. & Garcia, R. (2015b) Monotonic references for efficient gradual typing. In Proceedings of European Symposium on Programming, pp. 432–456.Google Scholar
Siek, J. G. & Wadler, P. (2010) Threesomes, with and without blame. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 365–376.Google Scholar
St-Amour, V., Andersen, L. & Felleisen, M. (2015) Feature-specific profiling. In Proceedings of International Conference on Compiler Construction, pp. 49–68.CrossRefGoogle Scholar
Steele, G. L. (1990) Common Lisp the Language, 2nd ed. Digital Press.Google Scholar
Strickland, T. S., Tobin-Hochstadt, S. & Felleisen, M. (2009) Practical variable-arity polymorphism. In Proceedings of European Symposium on Programming, pp. 32–46.Google Scholar
Strickland, T. S., Tobin-Hochstadt, S., Findler, R. B. & Flatt, M. (2012) Chaperones and impersonators: Run-time support for reasonable interposition. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, pp. 943–962.Google Scholar
Suzuki, N. (1981) Inferring types in smalltalk. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 187–199.Google Scholar
Takikawa, A., Feltey, D., Dean, E., Findler, R. B., Flatt, M., Tobin-Hochstadt, S. & Felleisen, M. (2015) Towards practical gradual typing. In Proceedings of European Conference on Object-Oriented Programming, pp. 4–27.Google Scholar
Takikawa, A., Feltey, D., Greenman, B., New, M. S., Vitek, J. & Felleisen, M. (2016) Is sound gradual typing dead? In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 456–468.Google Scholar
Takikawa, A., Strickland, T. S., Dimoulas, C., Tobin-Hochstadt, S. & Felleisen, M. (2012) Gradual typing for first-class classes. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, pp. 793–810.Google Scholar
Takikawa, A., Strickland, T. S. & Tobin-Hochstadt, S. (2013) Constraining delimited control with contracts. In Proceedings of European Symposium on Programming, pp. 229–248.Google Scholar
Tobin-Hochstadt, S. & Felleisen, M. (2006) Interlanguage migration: From scripts to programs. In Proceedings of Dynamic Languages Symposium, pp. 964–974.Google Scholar
Tobin-Hochstadt, S. & Felleisen, M. (2008) The design and implementation of typed scheme. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 395–406.Google Scholar
Tobin-Hochstadt, S., Felleisen, M., Findler, R. B., Flatt, M., Greenman, B., Kent, A. M., St-Amour, V., Strickland, T. S. & Takikawa, A. (2017) Migratory typing: Ten years later. In Proceedings of Summit on Advances in Programming Languages, pp. 17:1–17:17.Google Scholar
Vitousek, M. M., Kent, A., Siek, J. G. & Baker, J. (2014) Design and evaluation of gradual typing for Python. In Proceedings of Dynamic Languages Symposium, pp. 45–56.CrossRefGoogle Scholar
Vitousek, M. M., Swords, C. & Siek, J. G. (2017) Big types in little runtime: Open-world soundness and collaborative blame for gradual type systems. In Proceedings of ACM Symposium on Principles of Programming Languages, pp. 762–774.Google Scholar
Wolff, R., Garcia, R., Tanter, É & Aldrich, J. (2011) Gradual typestate. In Proceedins of European Conference on Object-Oriented Programming, pp. 459–483.Google Scholar
Supplementary material: Link

Video abstract for the paper _How_to_Evaluate_the_Performace_of_Gradual_Type_Systems

Greenman Supplementary Video https://www.youtube.com/watch?v=7d6iJdSRFtQ&feature=youtu.be
Link
Submit a response

Discussions

No Discussions have been published for this article.