Abstract
Separation of concerns is difficult to achieve in the implementation of a programming language interpreter. We argue that evaluator concerns (i.e., those implementing the operational semantics of the language) are, in particular, difficult to separate from the runtime concerns (e.g., memory and stack management) that support them. This precludes the former from being reused and limits variability in the latter.
In this paper, we present the Game environment for composing customized interpreters from a reusable evaluator and different variants of its supporting runtime. To this end, Game offers a language for specifying the evaluator according to the generic programming methodology. Through a transformation into defunctionalized monadic style, the Game toolchain generates a generic abstract machine in which the sequencing of low-level interpretational steps is parameterized. Given a suitable instantiation of these parameters for a particular runtime, the toolchain is able to inject the runtime into the generic abstract machine such that a complete interpreter is generated.
To validate our approach, we port the prototypical Scheme evaluator to Game and compose the resulting generic abstract machine with several runtimes that vary in their automatic memory management as well as their stack discipline.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abelson, H., Sussman, G.J., Sussman, J.: Structure and Interpretation of Computer Programs, 2nd edn. MIT Press/McGraw-Hill, Cambridge (1996)
Ager, M.S., Biernacki, D., Danvy, O., Midtgaard, J.: A functional correspondence between evaluators and abstract machines. In: Proc. of the 5th ACM SIGPLAN Intl. Conf. on Principles and Practice of Declaritive Programming, PPDP 2003, pp. 8–19. ACM, New York (2003)
Clinger, W.D., Hartheimer, A.H., Ost, E.M.: Implementation strategies for first-class continuations. Higher Order Symbol. Comput. 12, 7–45 (1999)
Danvy, O.: Defunctionalized interpreters for programming languages. In: Proc. of the 13th ACM SIGPLAN Intl. Conf. on Functional Programming, ICFP 2008, pp. 131–142. ACM, New York (2008)
Diehl, S., Sestoft, P.: Abstract machines for programming language implementation. Future Gener. Comput. Syst. 16, 739–751 (2000)
Anton Ertl, M., Gregg, D.: The structure and performance of efficient interpreters. Journal of Instruction-Level Parallelism 5, 1–25 (2003)
Ganz, S.E., Friedman, D.P., Wand, M.: Trampolined style. In: Proc. of the Fourth ACM SIGPLAN Intl. Conf. on Functional Programming, ICFP 1999, pp. 18–27. ACM, New York (1999)
Graunke, P., Findler, R.B., Krishnamurthi, S., Felleisen, M.: Automatically restructuring programs for the web. In: Proc. of the 16th IEEE Intl. Conf. on Automated Software Engineering, ASE 2001, p. 211. IEEE Computer Society, Washington, DC (2001)
Hanson, C.: Efficient stack allocation for tail-recursive languages. In: Proc. of the 1990 ACM Conf. on LISP and Functional Programming, LFP 1990, pp. 106–118. ACM, New York (1990)
Herzeel, C., Costanza, P.: Dynamic parallelization of recursive code: part 1: managing control flow interactions with the continuator. In: Proc. of the ACM Intl. Conf. on Object Oriented Programming Systems Languages and Applications, OOPSLA 2010, pp. 377–396. ACM, New York (2010)
Liang, S., Hudak, P., Jones, M.: Monad transformers and modular interpreters. In: Proc. of the 22nd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL 1995, pp. 333–343. ACM, New York (1995)
Nielsen, L.R.: A selective cps transformation. Electr. Notes Theor. Comput. Sci. 45, 311–331 (2001)
Reynolds, J.C.: Definitional interpreters for higher-order programming languages. In: Proc. of the ACM Annual Conf., ACM 1972, vol. 2, pp. 717–740. ACM, New York (1972)
Rigo, A., Pedroni, S.: Pypy’s approach to virtual machine construction. In: Companion to the 21st ACM SIGPLAN Symp. on Object-Oriented Programming Systems, Languages, and Applications, OOPSLA 2006, pp. 944–953. ACM, New York (2006)
Rompf, T., Maier, I., Odersky, M.: Implementing first-class polymorphic delimited continuations by a type-directed selective cps-transform. In: Proc. of the 14th ACM SIGPLAN Intl. Conf. on Functional Programming, ICFP 2009, pp. 317–328. ACM, New York (2009)
Schrijvers, T., Peyton Jones, S., Chakravarty, M., Sulzmann, M.: Type checking with open type functions. In: Proc. of the 13th ACM SIGPLAN Intl. Conf. on Functional Programming, ICFP 2008, pp. 51–62. ACM, New York (2008)
Snyder, M., Frisby, N., Kimmell, G., Alexander, P.: Writing Composable Software with InterpreterLib. In: Bergel, A., Fabry, J. (eds.) SC 2009. LNCS, vol. 5634, pp. 160–176. Springer, Heidelberg (2009)
Talpin, J.-P., Jouvelot, P.: The type and effect discipline. Inf. Comput. 111, 245–296 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Timbermont, S., De Roover, C., D’Hondt, T. (2012). Constructing Customized Interpreters from Reusable Evaluators Using Game . In: Gschwind, T., De Paoli, F., Gruhn, V., Book, M. (eds) Software Composition. SC 2012. Lecture Notes in Computer Science, vol 7306. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30564-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-30564-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30563-4
Online ISBN: 978-3-642-30564-1
eBook Packages: Computer ScienceComputer Science (R0)