research-article

Cast insertion strategies for gradually-typed objects

Authors:

Esteban Allende,

Éric TanterAuthors Info & Claims

DLS '13: Proceedings of the 9th symposium on Dynamic languages

Pages 27 - 36

https://doi.org/10.1145/2508168.2508171

Published: 28 October 2013 Publication History

Abstract

Gradual typing enables a smooth and progressive integration of static and dynamic typing. The semantics of a gradually-typed program is given by translation to an intermediate language with casts: runtime type checks that control the boundaries between statically- and dynamically-typed portions of a program. This paper studies the performance of different cast insertion strategies in the context of Gradualtalk, a gradually-typed Smalltalk. We first implement the strategy specified by Siek and Taha, which inserts casts at call sites. We then study the dual approach, which consists in performing casts in callees. Based on the observation that both strategies perform well in different scenarios, we design a hybrid strategy that combines the best of each approach. We evaluate these three strategies using both micro- and macro-benchmarks. We also discuss the impact of these strategies on memory, modularity, and inheritance. The hybrid strategy constitutes a promising cast insertion strategy for adding gradual types to existing dynamically-typed languages.

References

[1]

R. Cartwright, M. Fagan, Soft typing, in: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, PLDI '91, 1991, pp. 278--292.

Digital Library

[2]

G. Bracha, D. Griswold, Strongtalk: Typechecking Smalltalk in a production environment, in: Proceedings of the 8th International Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA 95), ACM Press, Washington, D.C., USA, 1993, pp. 215--230, aCM SIGPLAN Notices, 28(10).

Digital Library

[3]

G. Bracha, Pluggable type systems, in: OOPSLA Workshop on Revival of Dynamic Languages, 2004, pp. 1--6.

[4]

K. Knowles, C. Flanagan, Hybrid type checking, ACM Transactions on Programming Languages and Systems 32 (2) (2010) Article n.6.

Digital Library

[5]

S. Tobin-Hochstadt, Typed Scheme: From Scripts to Programs, Ph.D. thesis, Northeastern University (Jan. 2010).

[6]

M. Furr, Combining static and dynamic typing in Ruby, Ph.D. thesis, University of Maryland (2009).

[7]

A. Rastogi, A. Chaudhuri, B. Hosmer, The ins and outs of gradual type inference, in: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL 2012), ACM Press, Philadelphia, USA, 2012, pp. 481--494.

Digital Library

[8]

J. Siek, W. Taha, Gradual typing for functional languages, in: Proceedings of the Scheme and Functional Programming Workshop, 2006, pp. 81--92.

[9]

J. Siek, W. Taha, Gradual typing for objects, in: E. Ernst (Ed.), Proceedings of the 21st European Conference on Object-oriented Programming (ECOOP 2007), no. 4609 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, 2007, pp. 2--27.

Digital Library

[10]

A. Goldberg, D. Robson, Smalltalk-80: The Language and its Implementation, Addison-Wesley, 1983.

Digital Library

[11]

P. Wadler, R. B. Findler, Well-typed programs can't be blamed, in: ESOP 2009, pp. 1--16.

Digital Library

[12]

C. Saito, A. Igarashi, hrefhttp://doi.acm.org/10.1145/1640089.1640109Self type constructors, in: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, OOPSLA '09, ACM, New York, NY, USA, 2009, pp. 263--282.href http://dx.doi.org/10.1145/1640089.1640109pathdoi:10.1145/1640089.1640109. http://doi.acm.org/10.1145/1640089.1640109

Digital Library

[13]

R. B. Findler, M. Felleisen, Contracts for higher-order functions, in: Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming, ACM Press, Pittsburgh, PA, USA, 2002, pp. 48--59.

Digital Library

[14]

J. Siek, R. Garcia, W. Taha, Exploring the design space of higher-order casts, in: ESOP 2009, pp. 17--31.

Digital Library

[15]

B. C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, USA, 2002.

Digital Library

[16]

L. Ina, A. Igarashi, Gradual typing for generics, in: Proceedings of the 26th ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA 2011), ACM Press, Portland, Oregon, USA, 2011, pp. 609--624.

Digital Library

[17]

S. Tobin-Hochstadt, M. Felleisen, Logical types for untyped languages, in: Proceedings of the 15th ACM SIGPLAN Conference on Functional Programming (ICFP 2010), ACM Press, Baltimore, Maryland, USA, 2010, pp. 117--128.

Digital Library

[18]

A. Guha, C. Saftoiu, S. Krishnamurthi, Typing local control and state using flow analysis, in: G. Barthe (Ed.), Proceedings of the 20th European Symposium on Programming (ESOP 2011), Vol. 6602 of Lecture Notes in Computer Science, Springer-Verlag, 2011, pp. 256--275.

Digital Library

[19]

N. Schärli, S. Ducasse, O. Nierstrasz, A. Black, Traits: Composable units of behavior, in: L. Cardelli (Ed.), Proceedings of the 17th European Conference on Object-Oriented Programming (ECOOP 2003), no. 2743 in Lecture Notes in Computer Science, Springer-Verlag, Darmstadt, Germany, 2003, pp. 248--274.

[20]

D. Malayeri, J. Aldrich, Integrating nominal and structural subtyping, in: J. Vitek (Ed.), Proceedings of the 22nd European Conference on Object-oriented Programming (ECOOP 2008), no. 5142 in Lecture Notes in Computer Science, Springer-Verlag, Paphos, Cyprus, 2008, pp. 260--284.

Digital Library

[21]

D. Malayeri, J. Aldrich, Is structural subtyping useful? an empirical study, in: ESOP 2009, pp. 95--111.

Digital Library

[22]

D. Doligez, A. Frisch, J. Garrigue, D. Rémy, J. Vouillon, The OCaml system release 3.12, Institut National de Recherche en Informatique et en Automatique, http://caml.inria.fr/pub/docs/manual-ocaml/index.html (Jul 2011).

[23]

É. P. F. de Lausanne (EPFL), Scala, http://www.scala-lang.org.

[24]

L. Cardelli, Type systems, in: A. B. Tucker (Ed.), The Computer Science and Engineering Handbook, CRC Press, 1997, Ch. 103, pp. 2208--2236.

[25]

O. Callaú, É. Tanter, Programming with ghosts, IEEE Software 30 (1) (2013) 74--80.

Digital Library

[26]

R. Wolff, R. Garcia, É. Tanter, J. Aldrich, Gradual typestate, in: M. Mezini (Ed.), Proceedings of the 25th European Conference on Object-oriented Programming (ECOOP 2011), Vol. 6813 of Lecture Notes in Computer Science, Springer-Verlag, Lancaster, UK, 2011, pp. 459--483.

Digital Library

[27]

G. Bracha, The strongtalk type system for smalltalk, http://www.bracha.org/nwst.html.

[28]

R. Smit, Pegon, http://sourceforge.net/projects/pegon/.

[29]

S. Tobin-Hochstadt, V. St-Amour, The typed racket guide, http://docs.racket-lang.org/ts-guide/.

[30]

I. Figueroa, É. Tanter, N. Tabareau, A practical monadic aspect weaver, in: Proceedings of the 11th Workshop on Foundations of Aspect-Oriented Languages (FOAL 2012), ACM Press, Potsdam, Germany, 2012, pp. 21--26.

Digital Library

[31]

R. E. Johnson, Type-checking smalltalk, SIGPLAN Not. 21 (11) (1986) 315--321.

Digital Library

[32]

R. E. Johnson, J. O. Graver, L. W. Zurawski, Ts: an optimizing compiler for smalltalk, SIGPLAN Not. 23 (11) (1988) 18--26.

Digital Library

[33]

J. O. Graver, R. E. Johnson, A type system for smalltalk, in: POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1990, pp. 136--150.

Digital Library

[34]

N. Haldiman, M. Denker, O. Nierstrasz, Practical, pluggable types for a dynamic language, Comput. Lang. Syst. Struct. 35 (1) (2009) 48--62.

Digital Library

[35]

F. Pluquet, A. Marot, R. Wuyts, Fast type reconstruction for dynamically typed programming languages, in: DLS '09: Proceedings of the 5th symposium on Dynamic languages, 2009, pp. 69--78.

Digital Library

[36]

D. Ancona, M. Ancona, A. Cuni, N. D. Matsakis, Rpython: a step towards reconciling dynamically and statically typed oo languages, in: Proceedings of the 2007 symposium on Dynamic languages, DLS '07, 2007, pp. 53--64.

Digital Library

[37]

C. Anderson, S. Drossopoulou, P. Giannini, Towards type inference for javascript, in: A. P. Black (Ed.), Proceedings of the 19th European Conference on Object-Oriented Programming (ECOOP 2005), no. 3586 in Lecture Notes in Computer Science, Springer-Verlag, Glasgow, UK, 2005, pp. 428--452.

Digital Library

[38]

T. Wrigstad, F. Zappa Nardelli, S. Lebresne, J. Östlund, J. Vitek, Integrating typed and untyped code in a scripting language, in: POPL 2010, pp. 377--388.

Digital Library

[39]

D. Herman, A. Tomb, C. Flanagan, Space-efficient gradual typing, Higher-Order and Sympolic Computation 23 (2) (2010) 167--189.

Digital Library

[40]

J. Siek, P. Wadler, Threesomes, with and without blame, in: POPL 2010, pp. 365--376.

Digital Library

[41]

Proceedings of the 18th European Symposium on Programming Languages and Systems (ESOP 2009), Vol. 5502 of Lecture Notes in Computer Science, Springer-Verlag, York, UK, 2009.

[42]

Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL 2010), ACM Press, Madrid, Spain, 2010.

Cited By

Campora JKhan MChen S(2024)Type-Based Gradual Typing Performance OptimizationProceedings of the ACM on Programming Languages10.1145/36329318:POPL(2667-2699)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632931
Greenman BJhala RDillig I(2022)Deep and shallow types for gradual languagesProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523430(580-593)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523430
SIEK JCHEN T(2021)Parameterized cast calculi and reusable meta-theory for gradually typed lambda calculiJournal of Functional Programming10.1017/S095679682100024131Online publication date: 11-Nov-2021
https://doi.org/10.1017/S0956796821000241
Show More Cited By

Index Terms

Cast insertion strategies for gradually-typed objects
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Cast insertion strategies for gradually-typed objects
DLS '13

Gradual typing enables a smooth and progressive integration of static and dynamic typing. The semantics of a gradually-typed program is given by translation to an intermediate language with casts: runtime type checks that control the boundaries between ...
Interpretations of the gradually-typed lambda calculus
Scheme '12: Proceedings of the 2012 Annual Workshop on Scheme and Functional Programming

Gradual typing is an approach to integrating static and dynamic type checking within the same language [Siek and Taha 2006]. Given the name "gradual typing", one might think that the most interesting aspect is the type system. It turns out that the ...
Gradually Typed Languages Should Be Vigilant!

In gradual typing, different languages perform different dynamic type checks for the same program even though the languages have the same static type system. This raises the question of whether, given a gradually typed language, the combination of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DLS '13: Proceedings of the 9th symposium on Dynamic languages

October 2013

118 pages

ISBN:9781450324335

DOI:10.1145/2508168

Co-chair:
Antony Hosking
Purdue University, USA
,
General Chair:
Patrick Eugster
Purdue University, USA
,
Program Chair:
Carl Friedrich Bolz
Heinrich-Heine-Universität Düsseldorf, Germany

ACM SIGPLAN Notices Volume 49, Issue 2
DLS '13
February 2014
105 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2578856
Editor:
Mark W. Bailey
Hamilton College, Clinton, NY
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '13

Sponsor:

SIGPLAN

SPLASH '13: Conference on Systems, Programming, and Applications: Software for Humanity

October 28, 2013

Indiana, Indianapolis, USA

Acceptance Rates

DLS '13 Paper Acceptance Rate 9 of 22 submissions, 41%;

Overall Acceptance Rate 32 of 77 submissions, 42%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
183
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Campora JKhan MChen S(2024)Type-Based Gradual Typing Performance OptimizationProceedings of the ACM on Programming Languages10.1145/36329318:POPL(2667-2699)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632931
Greenman BJhala RDillig I(2022)Deep and shallow types for gradual languagesProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523430(580-593)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523430
SIEK JCHEN T(2021)Parameterized cast calculi and reusable meta-theory for gradually typed lambda calculiJournal of Functional Programming10.1017/S095679682100024131Online publication date: 11-Nov-2021
https://doi.org/10.1017/S0956796821000241
Greenman BFelleisen MDimoulas C(2019)Complete monitors for gradual typesProceedings of the ACM on Programming Languages10.1145/33605483:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360548
Vitousek MSiek JChaudhuri AMarr SFumero J(2019)Optimizing and evaluating transient gradual typingProceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3359619.3359742(28-41)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3359619.3359742
Greenman BFelleisen M(2018)A spectrum of type soundness and performanceProceedings of the ACM on Programming Languages10.1145/32367662:ICFP(1-32)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236766
Muehlboeck FTate R(2017)Sound gradual typing is nominally alive and wellProceedings of the ACM on Programming Languages10.1145/31338801:OOPSLA(1-30)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133880
Bauman SBolz-Tereick CSiek JTobin-Hochstadt S(2017)Sound gradual typing: only mostly deadProceedings of the ACM on Programming Languages10.1145/31338781:OOPSLA(1-24)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133878
Vitousek MSwords CSiek J(2017)Big types in little runtime: open-world soundness and collaborative blame for gradual type systemsACM SIGPLAN Notices10.1145/3093333.300984952:1(762-774)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009849
Vitousek MSwords CSiek JCastagna GGordon A(2017)Big types in little runtime: open-world soundness and collaborative blame for gradual type systemsProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009849(762-774)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3009837.3009849
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents