Arthur Nunes-Harwitt
ABSTRACT
An interpreter is a concise definition of the semantics of a programming language and is easily implemented. A compiler is more difficult to construct, but the code that it generates runs faster than interpreted code. This paper introduces rules for staging an interpreter so that it generates a compiler. An extended example suggests the utility of the technique. The rules are described formally and correctness is discussed. Finally, this technique is compared to staging and partial evaluation.
- L. Birkedal, M. Welinder. Hand-Writing Program Generator Generators. Programming Language Implementation and Logic Programming, Springer, 1994. Google Scholar
Digital Library
- R. M. Bustall, J. Darlington. A Transformation System for Developing Recursive Programs. Journal of the ACM, Vol. 24, No. 1, 44--67, 1977. Google ScholarDigital Library
- C. Consel. A Tour of Schism: A Partial Evaluation System for Higher-Order Applicative Languages. Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, 145--154, 1993. Google ScholarDigital Library
- C. Consel. New Insights into Partial Evaluation: The Schism Experiment. Lecture Notes in Computer Science, Vol. 300, 236--246, Springer-Verlag, 1988. Google ScholarDigital Library
- O. Danvy, H. K. Rohde. On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation. Information Processing Letters, Vol. 99, No. 4, 158--162, 2006. Google ScholarDigital Library
- O. Danvy and R. Vestergaard. Semantics Based Compiling: A Case Study in Type Directed Partial Evaluation. Eighth International Symposium on Programming Language Implementation and Logic Programming, 182--497, 1996. Google ScholarDigital Library
- M. Feeley, G. LaPalme. Using Closures for Code Generation. Computer Language, Vol. 12, No. 1, 47--66, 1987. Google ScholarDigital Library
- Y. Futamura. Partial Evaluation of Computation Process -- An Approach to a Compiler-Compiler. Systems, Computers, Controls, Vol. 2, No. 5, 45--50, 1971.Google Scholar
- C. A. Gunter. Semantics of Programming Languages: Structures and Techniques. MIT Press, 1992. Google ScholarDigital Library
- N. D. Jones. Personal Communication, 2013.Google Scholar
- N. D. Jones, C. K. Gomard, P. Sestoft, L. O. Andersen, T. Mogensen. Partial Evaluation and Automatic Program Generation. Prentice Hall International, 1993. Google ScholarDigital Library
- U. Jørring, W. L. Scherlis. Compilers and Staging Transformations. Symposium on Principles of Programming Languages, 86--96, 1986. Google ScholarDigital Library
- R. Kelsey, W. Clinger, J. Rees editors. Revised5 Report on the Algorithmic Language Scheme. ACM SIGPLAN Notices, Vol. 33, No. 9, 26--76, 1998. Google ScholarDigital Library
- E. Moggi, W. Taha, Z. Benaissa, T. Sheard. An Idealized MetaML: Simpler, and More Expressive. Proeedings of the European Symposium on Programming, 193--207, 1999. Google ScholarDigital Library
- A. Nanevski, F. Pfenning. Staged Computation with Names and Necessity. Journal of Functional Programming, Vol. 15, No. 6, 893--939, 2005. Google ScholarDigital Library
- J. E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press, 1981. Google ScholarDigital Library
- W. Taha. Multi-Stage Programming: Its Theory and Applications. PhD thesis, Oregon Graduate Institute of Science and Technology, Hillsboro, Oregon, USA, 1999. Google ScholarDigital Library
- P. J. Thiemann. Cogen in Six Lines. ACM SIGPLAN Notices, Vol. 31, No. 6. ACM, 1996. Google ScholarDigital Library
- P. J. Thiemann. The PGG system--user manual. 2000.Google Scholar
- F. Turbak, D. Gifford, M. A. Sheldon. Design Concepts in Programming Languages. MIT Press, 2008. Google ScholarDigital Library
Index Terms
- Eager Evaluation Isn't Eager Enough A Transformation Based Approach to Semantics-Directed Code Generation
Recommendations
From Naïve to Norvig On Deriving a PROLOG Compiler
ILC '14: Proceedings of ILC 2014 on 8th International Lisp ConferenceAn interpreter is a concise definition of the semantics of a programming language and is easily implemented. A compiler is more difficult to construct, but the code that it generates runs faster than interpreted code. This paper introduces rules to ...
A Surprisingly Simple Lua Compiler
SBLP '21: Proceedings of the 25th Brazilian Symposium on Programming LanguagesDynamically-typed programming languages are often implemented using interpreters, which offer several advantages in terms of portability and flexibility of the implementation. However, as a language matures and its programs get bigger, programmers may ...
Towards a jitting VM for prolog execution
PPDP '10: Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programmingMost Prolog implementations are implemented in low-level languages such as C and are based on a variation of the WAM instruction set, which enhances their performance but makes them hard to write. In addition, many of the more dynamic features of Prolog ...
Comments