The Design and Implementation of Typed Scheme: From Scripts to Programs
By Sam Tobin-Hochstadt, Matthias Felleisen. 2011
288 citations recorded by the source corpus.
When scripts in untyped languages grow into large programs, maintaining them becomes difficult. A lack of explicit type annotations in typical scripting languages forces programmers to must (re)discover critical pieces of design information every time they wish to change a program. This analysis step both slows down the maintenance process and may even introduce mistakes due to the violation of undiscovered invariants. This paper presents Typed Scheme, an explicitly typed extension of PLT Scheme, an untyped scripting language. Its type system is based on the novel notion of occurrence typing, which we formalize and mechanically prove sound. The implementation of Typed Scheme additionally borrows elements from a range of approaches, including recursive types, true unions and subtyping, plus polymorphism combined with a modicum of local inference. The formulation of occurrence typing naturally leads to a simple and expressive version of predicates to describe refinement types. A Typed Scheme program can use these refinement types to keep track of arbitrary classes of values via the type system. Further, we show how the Typed Scheme type system, in conjunction with simple recursive types, is able to encode refinements of existing datatypes, thus expressing both proposed variations of refinement types.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Program Analysis & Verification, Software Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Arjun Guha
- Ming-Ho Yee
- Erik Krogh Kristensen
- Anders Møller
- Jeffrey S. Foster
- Jens Palsberg
- Zeina Migeed
- Yusuke Miyazaki
In Computational Theory and Mathematics
- Arjun Guha
- Ming-Ho Yee
- Jens Palsberg
- Zeina Migeed
- Yusuke Miyazaki
- Atsushi Igarashi
- Taro Sekiyama
- Matteo Cimini
In Information Systems
- Arjun Guha
- Ming-Ho Yee
- Erik Krogh Kristensen
- Anders Møller
- Jeffrey S. Foster
- Shriram Krishnamurthi
- Milod Kazerounian
- Claudiu Saftoiu
In Program Analysis & Verification
- Arjun Guha
- Ming-Ho Yee
- Erik Krogh Kristensen
- Anders Møller
- Jeffrey S. Foster
- Jens Palsberg
- Zeina Migeed
- Yusuke Miyazaki
In Software Engineering
- Anders Møller
- Erik Krogh Kristensen
- Arjun Guha
- Ming-Ho Yee
- Jeffrey S. Foster
- Milod Kazerounian
- Matteo Cimini
- Ronald Garcia
Citations in the corpus
- Do Machine Learning Models Produce TypeScript Types that Type Check? (2023, methodology): “This makes it possible to add static types to a large program incrementally, and slowly reap the benefits of static typing without requiring a complete rewrite of an existing codebase at once [22, 46, 48].”
- Principal Type Schemes for Gradual Programs (2015, methodology): “(e.g. (Bierman et al. 2010; Gronski et al. 2006; Swamy et al. 2014; Tobin-Hochstadt and Felleisen 2008; Wrigstad et al. 2010)) Among the proposed foundations for such languages, gradual typing , due to Siek and Taha (2006) has been used to integrate dynamic checks into a variety of type structures,…”
- TeJaS: retrofitting type systems for JavaScript (2013, background): “Such reasoning about the predicates implied by the return values of functions is known as occurrence typing [23].”
- The ins and outs of gradual type inference (2012, methodology): “, via occurrence typing [22], gradual typing [16, 17], hybrid typing [8], and like typing [26].”
- Profile-guided static typing for dynamic scripting languages (2009, methodology): “Evolutionary Programming and Gradual Typing in ECMAScript 4 (Tutorial), November 2007.”
- Gradual typing with unification-based inference (2008, background): “Tobin-Hochstadt and Felleisen [51, 52] developed a system that provides convenient inter-language migration between dynamic and static languages on a per-module basis.”
- Sound, heuristic type annotation inference for Ruby (2020, background): “Many researchers have explored ways to add static types to dynamic languages [3, 4, 15, 19, 29, 31, 36, 37], to help programmers find and prevent type errors.”
- Practical Optional Types for Clojure (2016, methodology): “These include TypeScript [19] and Flow [11] for JavaScript, Hack [10] for PHP, and mypy [15] for Python among the optional systems, and Typed Racket [23], Reticulated Python [25], and GradualTalk [1] among gradually-typed systems.”
- Inference and Evolution of TypeScript Declaration Files (2017, background): “Other languages, such as typed dialects of Python [23,10], Scheme [21], Clojure [5], Ruby [12], and Flow for JavaScript[7], have similar challenges with types and cross-language library interoperability, though not (yet) at the same scale as TypeScript.”
- Dynamic type inference for gradual Hindley–Milner typing (2018, background): “There has been much work to integrate static and dynamic typing in a single programming language [Abadi et al. 1991; Bracha and Griswold 1993; Cartwright and Fagan 1991; Flanagan and Felleisen 1999; Siek and Taha 2006; Thatte 1990; Tobin-Hochstadt and Felleisen 2008].”
- What is decidable about gradual types? (2019, methodology): “Gradual typing has found practical application in Typed Racket [Tobin-Hochstadt and Felleisen 2008], TypeScript [Bierman et al. 2014], Reticulated Python [Vitousek et al. 2014], and others.”
- An analysis of the dynamic behavior of JavaScript programs (2010, background): “Other dynamic languages such as Scheme have had recent success introducing gradual typing systems [25], but they have stopped short of type checking object-oriented extensions (implemented by macros in Scheme).”
- SimTyper: sound type inference for Ruby using type equality prediction (2021, background): “…the benefits of static typing while preserving the flexibility of the language [Aiken et al. 1994; Cartwright and Fagan 1991; Flanagan and Felleisen 1997; Kazerounian et al. 2019; Lerner et al. 2013; Ren and Foster 2016; Siek and Taha 2006; Tobin-Hochstadt and Felleisen 2008; Vitousek et al. 2014].”
- Design and evaluation of gradual typing for python (2014, methodology): “We could possibly achieve some kind of static typing by introducing sum types into the language, or by using the occurrence typing of Tobin-Hochstadt and Felleisen [34].”
- The ruby type checker (2013, background): “Similarly, gradual type systems [12] like those for Scheme [15] and Thorn [6] pair a dynamically typed language with a sister, statically typed language.”