WG211/M16Siek

Jeremy Siek: Compiling gradually typed languages for efficiency

Gradual typing combines static and dynamic typing in the same program. One would hope that the performance in a gradually typed language would range from being similar to that of a dynamically typed language to that of a statically typed language. Existing implementations of gradually typed languages have not achieved this goal due to overheads associated with runtime casts, some research reports as much as 100x slowdown for partially typed programs. Runtime casts are necessary to ensure sound interoperability between static and dynamic regions. In this talk I present a compiler, Schml, that serves as a framework for exploring implementation strategies for gradual typing. The design space has many variables with different possible choices: the cast semantics, the blame tracking strategy, and the runtime representation of casted values.

We evaluate the performance of the operations on functions and mutable references in two different implementations. The first is the traditional type-based casts with functional representation of function casts and the second is space-efficient coercions with hybrid representation of function casts. Our evaluation methodology determines the overheads in the fully statically-typed code, in the fully dynamically-typed code, and in the partially-typed code. Our preliminary finds are quite promising for the coercion-based implementation: a statically typed quicksort is within 50% of C, a dynamically typed quicksort is 2x slower than Gambit, and a partially typed quicksort is in between. The traditional type-based version often does better than the coercion-based version, but sometimes does catistrophically worse, which is to be expected.