2016 · 32 citations · 22 references
ComputingComputer ScienceCompilersProgramming LanguagesSoftware EngineeringAbstract Syntax TreesCompiler ConstructionData-flow AnalysisType CheckingType SystemsConstraint-based Type CheckingRecursive TypesStatic CompilationStatic Type CheckingSubtypingType AnalysisType InferenceWorkarounds
We present a type system and inference algorithm for a rich subset of JavaScript equipped with objects, structural subtyping, prototype inheritance, and first-class methods. The type system supports abstract and recursive objects, and is expressive enough to accommodate several standard benchmarks with only minor workarounds. The invariants enforced by the types enable an ahead-of-time compiler to carry out optimizations typically beyond the reach of static compilers for dynamic languages. Unlike previous inference techniques for prototype inheritance, our algorithm uses a combination of lower and upper bound propagation to infer types and discover type errors in all code, including uninvoked functions. The inference is expressed in a simple constraint language, designed to leverage off-the-shelf fixed point solvers. We prove soundness for both the type system and inference algorithm. An experimental evaluation showed that the inference is powerful, handling the aforementioned benchmarks with no manual type annotation, and that the inferred types enable effective static compilation.
22
Principal type-schemes for functional programs
Robin Milner · 1982 · 1.1K citations
An analysis of the dynamic behavior of JavaScript programs
Gregor Richards, Sylvain Lebresne, Brian R. Burg et al. · 2010 · 356 citations
Object-oriented type inference
Jens Palsberg, Michael I. Schwartzbach · 1991 · 305 citations · Full text
Complete Type Inference for Simple Objects
Mitchell Wand · Logic in Computer Science · 1987 · 211 citations