When scripts in untyped languages grow into large programs, maintaining them becomes difficult. A lack of types in typical scripting languages means that programmers 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 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. Initial experiments with the implementation suggest that Typed Scheme naturally accommodates the programming style of the underlying scripting language, at least for the first few thousand lines of ported code.  Categories and Subject Descriptors Recently, under the heading of "scripting languages", a variety of new languages have become popular, and even pervasive, in weband systems-related fields. Due to their popularity, programmers often create scripts that then grow into large applications. Most scripting languages are untyped and have a flexible semantics that makes programs concise. Many programmers find these attributes appealing and use scripting languages for these reasons. Programmers are also beginning to notice, however, that untyped scripts are difficult to maintain over the long run. The lack of types means a loss of design information that programmers must recover every time they wish to change existing code. Both the Perl community (Tang 2007) and the JavaScript community (ECMA International 2007) are implicitly acknowledging this problem with the 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. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. POPL'08, January 7-12, 2008 In the meantime, industry faces the problem of porting existing application systems from untyped scripting languages to the typed world. Based on our own experience, we have proposed a theoretical model for this conversion process and have shown that partial conversions can benefit from type-safety properties to the desired extent (Tobin-Hochstadt and Felleisen 2006). The key assumption behind our work is the existence of an explicitly typed version of the scripting language, with the same semantics as the original language, so that values can freely flow back and forth between typed and untyped modules. In other words, we imagine that programmers can simply add type annotations to a module and thus introduce a certain amount of type-safety into the program. At first glance, such an assumption seems unrealistic. Programmers in untyped languages often loosely mix and match reasoning from various type disciplines when they write scripts. Worse, an inspection of code suggests they also include flow-oriented reasoning, distinguishing types for variables depending on prior operations. In short, untyped scripting languages permit programs that appear difficult to type-check with existing type systems. To demonstrate the feasibility of our approach, we have designed and implemented Typed Scheme, an explicitly typed version of PLT Scheme. We have chosen PLT Scheme for two reasons. On one hand, PLT Scheme is used as a scripting language by a large number of users. It also comes with a large body of code, with contributions ranging from scripts to libraries to large operating-system like programs. On the other hand, the language comes with macros, a powerful extension mechanism (Flatt 2002) . Macros place a significant constraint on the design and implementation of Typed Scheme, since supporting macros requires typechecking a language with a user-defined set of syntactic forms. We are able to overcome this difficulty by integrating the type checker with the macro expander. Indeed, this approach ends up greatly facilitating the integration of typed and untyped modules. As envisioned (Tobin-Hochstadt and Felleisen 2006) , this integration makes it easy to turn portions of a multi-module program into a partially typed yet still executable program. Here we report on the novel type system, which combines the idea of occurrence typing with subtyping, recursive types, polymorphism and a modicum of inference. We first present a formal model of the key aspects of occurrence typing and prove it to be type-sound. Later we describe how to scale this calculus into a fullfledged, typed version of PLT Scheme and how to implement it. Finally, we give an account of our preliminary experience, adding types to thousands of lines of untyped Scheme code. Our experiments seem promising and suggest that converting untyped scripts into well-typed programs is feasible. 395
A prominent example is the work on typed Scheme REF .
The design and implementation of typed scheme
POPL '08
Computer Science