Trace Typing: An Approach for Evaluating Retrofitted Type Systems

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

TL;DR

This paper introduces "trace typing," a novel framework for automatically and quantitatively evaluating different type system designs for dynamically-typed languages. By analyzing execution traces, it significantly reduces the effort needed to assess the impact of type system features on large codebases, helping developers prioritize design choices.

What Problem Does This Paper Address?

Dynamically-typed languages like JavaScript are incredibly popular, but they lack the safety nets of static typing. Retrofitting type systems onto these languages aims to improve safety, productivity, and performance. However, designing these type systems is tricky: adding more features can increase complexity and implementation effort. Developers need a way to understand the real-world impact of different type system features (like union types or parametric polymorphism) on existing code before committing to a full implementation. Manually evaluating these features is a massive undertaking, often leading to design decisions based on intuition rather than data.

Methods

The core innovation is trace typing. Here's how it works:

  1. Execution Tracing: The target program is executed with instrumented code to generate a detailed "trace" of its dynamic behavior. This trace essentially unrolls loops and inlines calls, simplifying the program's structure.
  2. Type Ascription: The framework infers precise types for all values and variables within this trace.
  3. Type Merging: This is where the type system design comes in. Different "merge strategies" are applied to coarsen the precise trace types into types that reflect the source-level type system being evaluated. For example, a merge strategy might decide how to handle a variable that holds both a number and an object – should it be a union type, or a type error?
  4. Type Checking: The merged types are then used to type-check the trace. The number of type errors reported serves as a quantitative metric for how well the evaluated type system variant handles the observed program behavior.

This approach is novel because it shifts the burden from complex static analysis of the source code to a simpler analysis of dynamic traces, drastically reducing implementation effort for evaluating type system variants.

Datasets

The authors evaluated their framework on nine popular npm packages for Node.js, totaling over 50,000 lines of code. These benchmarks represent a variety of JavaScript programming styles, including utility libraries, parsers, code generators, and a compiler. They also used a separate driver program to exercise these benchmarks.

Key Insights and Ideas

  • Empirical Design Decisions: Trace typing provides a data-driven way to make design decisions about type system features, moving beyond intuition and anecdotal evidence.
  • Effort Reduction: Analyzing traces is significantly simpler than building full static type checkers, making it feasible to evaluate multiple type system variants.
  • Quantifying Feature Usefulness: The framework can answer questions like "How often are union types actually needed?" or "How pervasive is the need for parametric polymorphism?" by looking at error counts.
  • Discovering Tag Tests: The technique can automatically identify "tag tests" (checks that narrow down union types), providing insights into how developers actually use these features in practice.

Key Results

  • Union Types: While union types generally reduced error counts, the reduction was relatively small in their experiments, potentially explaining why they weren't an initial feature in TypeScript.
  • Parametric Polymorphism: The inclusion of parametric polymorphism (via T.poly) consistently reduced error counts compared to a "base" system, highlighting its importance for core routines and data structure manipulation.
  • Fixed Object Layout: Experiments with a stricter type system enforcing fixed object layout showed that many of its restrictions were not overly burdensome in practice, with a low number of property write errors.
  • Tag Test Analysis: They identified six major classes of narrowing checks, with typeof and instanceof being common. Non-local type guards were rare.

Limitations and Future Work

  • Assumption of Type Correctness: The accuracy of error locations generated by trace typing can be reduced if the input programs are not mostly type correct.
  • Over-approximations: Like any static analysis, trace typing can involve over-approximations, meaning a design that yields fewer errors in the framework might not perfectly translate to fewer errors in a full static checker.
  • Synthetic Type Systems: For highly synthetic type systems (like intersection types used as a limit study), the inferred types might not perfectly match what a human developer would write.
  • Future Work: The authors suggest extending the framework to other dynamically typed languages, adding more metadata to traces for richer experimentation (e.g., alias types), and exploring more sophisticated type system features like computed property accesses and unsound union elimination.

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}},
  booktitle = {Ecoop},
  year = {2016},
  doi = {10.4230/lipics.ecoop.2016.1},
}
Figure