Modular interpreters with implicit context propagation. (June 2017)

• Record Type: Journal Article
• Authors: Inostroza, Pablo; van der Storm, Tijs
• Is Part Of: Computer languages, systems & structures. Volume 48(2017)
• Page Start: 39
• Page End: 67
• Publication Date: 2017-06
• Subjects: Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2016.08.001
• Languages: English
• ISSNs: 1477-8424

Abstract

Abstract: Modular interpreters are a crucial first step towards component-based language development: instead of writing language interpreters from scratch, they can be assembled from reusable, semantic building blocks. Unfortunately, traditional language interpreters can be hard to extend because different language constructs may require different interpreter signatures. For instance, arithmetic interpreters produce a value without any context information, whereas binding constructs require an additional environment. In this paper, we present a practical solution to this problem based on implicit context propagation. By structuring denotational-style interpreters as Object Algebras, base interpreters can be retroactively lifted into new interpreters that have an extended signature. The additional parameters are implicitly propagated behind the scenes, through the evaluation of the base interpreter. Interpreter lifting enables a flexible style of modular and extensible language development. The technique works in mainstream object-oriented languages, does not sacrifice type safety or separate compilation, and can be easily automated, for instance using macros in Scala or dynamic proxies in Java. We illustrate implicit context propagation using a modular definition of Featherweight Java and its extension to support side-effects, and an extensible domain-specific language for state machines. We finally investigate the performance overhead of lifting by running the DeltaBlue benchmark program in Javascript on top of a modular implementation of LambdaJS and a dedicated micro-benchmark. The results show that lifting makes interpreters roughly twice as slow because of additional call overhead. Further research is needed to eliminate this performance penalty. Abstract : Highlights: We present implicit context propagation as a technique to compose interpreter modules having different context information requirements. Object Algebras provide the necessary extensibility to lift interpreters in order to implicitly propagate context information. Implicit context propagation works in mainstream object-oriented languages, does not sacrifice type safety or separate compilation, and can be easily automated. We illustrate the technique using two case studies and analyze the impact on interpreter performance.