A Domain-Specific Language for Building Self-Optimizing AST Interpreters

Christian Humer, Christian Wimmer, Christian Wirth, Andreas Wöß, Thomas Würthinger: A Domain-Specific Language for Building Self-Optimizing AST Interpreters. In Proceedings of the International Conference on Generative Programming: Concepts and Experiences, pages 123–132. ACM Press, 2014. doi:10.1145/2775053.2658776

Download as PDF
© ACM, 2014.

Abstract

Self-optimizing AST interpreters dynamically adapt to the provided input for faster execution. This adaptation includes initial tests of the input, changes to AST nodes, and insertion of guards that ensure assumptions still hold. Such specialization and speculation is essential for the performance of dynamic programming languages such as JavaScript. In traditional procedural and object-oriented programming languages it can be tedious to write self-optimizing AST interpreters, as those languages fail to provide constructs that would specifically support that.

This paper introduces a declarative domain-specific language (DSL) that greatly simplifies writing self-optimizing AST interpreters. The DSL supports specialization of operations based on types of the input and other properties. It can then use these specializations directly or chain them to represent the operation with the minimum amount of code possible. The DSL significantly reduces the complexity of expressing specializations for those interpreters. We use it in our high-performance implementation of JavaScript, where 274 language operations have an average of about 4 and a maximum of 190 specializations. In addition, the DSL is used in implementations of Ruby, Python, R, and Smalltalk.