Trace Typing: An Approach for Evaluating Retrofitted Type Systems (Extended Version)

Esben Andreasen, Colin S. Gordon, Satish Chandra, Manu Sridharan, Frank Tip, Koushik Sen

Abstract

Retrofitting static type systems onto dynamic languages like JavaScript, Python, and PHP has become a common practice to improve code maintainability and catch errors early. However, designing these systems is often an ad-hoc process driven by intuition rather than empirical data. This paper presents Trace Typing, a novel data-driven framework that allows language designers to quantitatively evaluate proposed type system features on large, existing codebases without the overhead of building full compilers or manually annotating code.

Introduction: The Challenge of Retrofitted Types

Designing a type system for a dynamic language involves a difficult trade-off: a simple system may reject valid idiomatic patterns, while a complex one is hard to implement and use. Traditionally, evaluating a new feature—such as intersection types or polymorphism—requires implementing it in a production compiler and manually annotating thousands of lines of code. This high barrier to entry means design decisions are frequently based on anecdotes. Trace Typing addresses this by providing a "preview" of how a proposed system would perform, turning type system design into an empirical science.

The Trace Typing Framework

The core of the Trace Typing approach is a four-phase pipeline that leverages execution traces to simulate the behavior of a candidate type system.

Overview of the Trace Typing framework, illustrating the pipeline from program execution to error detection.
  1. Trace Collection: The target program is executed with representative inputs to record a detailed "unrolled" trace of every variable operation and function call.
  2. Initial Type Ascription: The framework ascribes types based on observed runtime values (e.g., a value of 42 is typed as Number).
  3. Type Merging: This is the central innovation. Designers define merge strategies that simulate the proposed type system. For instance, if a variable holds different types at different points, a "Union" strategy merges them into a union type, while a "Subtyping" strategy might seek a common ancestor.
  4. Type Checking: The framework re-evaluates the trace against these merged types. If a merged type lacks a property required by an operation in the trace, a type error is recorded.

By using linear, concrete traces, this framework provides a realistic lower bound on the errors a static checker would encounter, significantly simplifying the evaluation of complex features like parametric polymorphism.

Experimental Evaluation

The authors evaluated Trace Typing on nine popular npm packages, including underscore, esprima, and the typescript compiler itself, totaling over 52,000 lines of code. The framework processed the entire suite across six different type system configurations in less than 15 minutes, demonstrating its efficiency for rapid design iteration.

Key Results and Insights

  • The Impact of Intersections: The experiments revealed that "intersection" configurations (modeling overloaded functions) significantly reduced error counts. This suggests that JavaScript developers rely heavily on functions that change behavior based on input types.
  • Utility of Union Types: While union types reduced error counts, the reduction was surprisingly small in several benchmarks. This provides empirical support for why early versions of TypeScript were viable even before full union type support.
  • Object Layout Stability: Using the framework to validate a strict type system (SJS), the authors found that most real-world JavaScript objects maintain a fixed shape after initialization, supporting the viability of stricter object models.
  • Tag Test Discovery: The tool automatically identified 164 "tag tests" (type guards). It found that while complex boolean combinations are common, "non-local" guards—where the check is far from the usage—are rare.

Limitations and Future Work

Trace Typing is subject to dynamic sampling bias; it only analyzes executed code paths. Furthermore, it assumes the input program is mostly correct; actual runtime bugs might be interpreted as type system limitations. Future work includes extending the framework to other dynamic languages like Python and Ruby, and incorporating more metadata to evaluate advanced features like alias types.

Conclusion

Trace Typing offers a scalable, empirical method for evaluating retrofitted type systems. By shifting from anecdotal design to data-driven analysis, it enables language designers to make informed decisions about which features provide the most value to developers.

Summary updated

BibTeX
@inproceedings{andreasen2016trace,
  author = {Esben Andreasen and Colin S. Gordon and Satish Chandra and Manu Sridharan and Frank Tip and Koushik Sen},
  title = {{Trace Typing: An Approach for Evaluating Retrofitted Type Systems (Extended Version)}},
  booktitle = {Ecoop},
  year = {2016},
  doi = {10.4230/lipics.ecoop.2016.1},
}
Figure