Rule-based program specialization to optimize gradually typed code

Abstract

Both static and dynamic typing provide different benefits to the programmer. Statically typed languages support earlier type error detection and more opportunities for compiler optimizations. Dynamically typed languages facilitate the development of runtime adaptable applications and rapid prototyping. Since both approaches provide benefits, gradually typed languages support both typing approaches in the very same programming language. Gradual typing has been an active research field in the last years, turning out to be a strong influence on commercial languages. However, one important drawback of gradual typing is the runtime performance cost of the additional type checks performed at runtime. In this article, we propose a rule-based program specialization mechanism to provide significant performance optimizations of gradually typed code. Our system gathers dynamic type information of the application by simulating its execution. That type information is used to optimize the generated code, reducing the number of type checks performed at runtime. Moreover, program specialization allows the early detection of compile-time type errors, providing static type safety. To ensure the correctness of the proposed approach, we prove its soundness and efficiency properties. The specialization system has been implemented as part of a full-fledged programming language, measuring the runtime performance gain. The generated code performs significantly better than the state-of-the-art techniques to optimize dynamically typed code. Unlike the existing approaches, our system does not consume additional memory resources at runtime, because program specialization is performed statically. Program specialization involves an average compilation time increase from 2% to 11.75%.