An abstract syntax tree (AST) interpreter is a simple and natural way to implement a programming language. However, it is also considered the slowest approach because of the high overhead of virtual method dispatch. Language implementers therefore define bytecodes to speed up interpretation, at the cost of introducing inflexible and hard to maintain bytecode formats. We present a novel approach to implementing AST interpreters in which the AST is modified during interpretation to incorporate type feedback. This tree rewriting is a general and powerful mechanism to optimize many constructs common in dynamic programming languages. Our system is implemented in Java and uses the static typing and primitive data types of Java elegantly to avoid the cost of boxed representations of primitive values in dynamic programming languages.
%0 Conference Paper
%1 Wurthinger:2012:SelfOptAST
%A Würthinger, Thomas
%A Wöß, Andreas
%A Stadler, Lukas
%A Duboscq, Gilles
%A Simon, Doug
%A Wimmer, Christian
%B Proceedings of the 8th Dynamic Languages Symposium
%D 2012
%K AST Interpreter Java Truffle
%P 73--82
%R 10.1145/2384577.2384587
%T Self-Optimizing AST Interpreters
%U http://www.christianwimmer.at/Publications/Wuerthinger12a/
%X An abstract syntax tree (AST) interpreter is a simple and natural way to implement a programming language. However, it is also considered the slowest approach because of the high overhead of virtual method dispatch. Language implementers therefore define bytecodes to speed up interpretation, at the cost of introducing inflexible and hard to maintain bytecode formats. We present a novel approach to implementing AST interpreters in which the AST is modified during interpretation to incorporate type feedback. This tree rewriting is a general and powerful mechanism to optimize many constructs common in dynamic programming languages. Our system is implemented in Java and uses the static typing and primitive data types of Java elegantly to avoid the cost of boxed representations of primitive values in dynamic programming languages.
%@ 978-1-4503-1564-7
@inproceedings{Wurthinger:2012:SelfOptAST,
abstract = {An abstract syntax tree (AST) interpreter is a simple and natural way to implement a programming language. However, it is also considered the slowest approach because of the high overhead of virtual method dispatch. Language implementers therefore define bytecodes to speed up interpretation, at the cost of introducing inflexible and hard to maintain bytecode formats. We present a novel approach to implementing AST interpreters in which the AST is modified during interpretation to incorporate type feedback. This tree rewriting is a general and powerful mechanism to optimize many constructs common in dynamic programming languages. Our system is implemented in Java and uses the static typing and primitive data types of Java elegantly to avoid the cost of boxed representations of primitive values in dynamic programming languages.},
acmid = {2384587},
added-at = {2012-10-17T12:26:35.000+0200},
author = {Würthinger, Thomas and Wöß, Andreas and Stadler, Lukas and Duboscq, Gilles and Simon, Doug and Wimmer, Christian},
biburl = {https://www.bibsonomy.org/bibtex/24e1140d14d242f7e300d85478582d14a/gron},
booktitle = {Proceedings of the 8th Dynamic Languages Symposium},
doi = {10.1145/2384577.2384587},
interhash = {161620261807eb2e79ba17123d532078},
intrahash = {4e1140d14d242f7e300d85478582d14a},
isbn = {978-1-4503-1564-7},
keywords = {AST Interpreter Java Truffle},
location = {Tucson, Arizona, USA},
month = {October},
numpages = {10},
pages = {73--82},
series = {DLS'12},
timestamp = {2016-05-31T14:57:26.000+0200},
title = {Self-Optimizing AST Interpreters},
url = {http://www.christianwimmer.at/Publications/Wuerthinger12a/},
year = 2012
}