Transforming interpreters into inverse interpreters by partial evaluation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transforming interpreters into inverse interpreters by partial evaluation

Full text

Pdf (196 KB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation table of contents

San Diego, California, USA

Pages: 10 - 19

Year of Publication: 2003

ISBN:1-58113-667-6

Also published in ...

Authors

Robert Glück	Waseda University, Tokyo, Japan
Youhei Kawada	Waseda University, Tokyo, Japan
Takuya Hashimoto	Waseda University, Tokyo, Japan

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 26, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/777388.777391 What is a DOI?

ABSTRACT

The experiments in this paper apply the idea of prototyping programming language tools from robust semantics: we used a partial evaluator (Similix) to turn interpreters into inverse interpreters. This way we generated inverse interpreters for several small languages including interpreters for Turing machines, an applied lambda calculus, a flowchart language, and a subset of Java bytecode. Limiting factors of online partial evaluation were the polyvariant specialization scheme with its lack of generalization;advantages were the availability of higher-order values to specialize a breadth-first tree traversal.This application of self-applicable partial evaluation is different from the classical Futamura projections that tell us how to translate a program by specialization of an interpreter.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sergei M. Abramov , Robert Glück, Combining Semantics with Non-standard Interpreter Hierarchies, Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, p.201-213, December 13-15, 2000
	2	S. M. Abramov and R. Gl ück. From standard to non-standard semantics by semantics modifiers. International Journal of Foundations of Computer Science, 12(2):171--211, 2001.
	3	Sergei Abramov , Robert Glück, Principles of inverse computation and the Universal resolving algorithm, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	4	S. M. Abramov and R. Glück. The universal resolving algorithm and its correctness: inverse computation in a functional language. Science of Computer Programming, 43(2-3):193--229, 2002.
	5	Elvira Albert , Germán Vidal, The narrowing-driven approach to functional logic program specialization, New Generation Computing, v.20 n.1, p.3-26, January 2002
	6	Anders Bondorf, Automatic autoprojection of higher order recursive equations, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
	7	A. Bondorf. Similix 5.0 Manual. DIKU, University of Copenhagen, Denmark, 1993. Included in the Similix distribution, 82 pages.
	8	Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991 [doi>10.1016/0167-6423(91)90002-F ]
	9	A. Bondorf and J. Jorgensen. Efficient analyses for realistic off-line partial evaluation. Journal of Functional Programming, 11:315--346, 1993.
	10	A. Bondorf and J. Palsberg. Generating action compilers by partial evaluation. Journal of Functional Programming, 6(2):269--298, 1996.
	11	N. H. Christensen and R. Glück. On the equivalence of online and offine partial evaluation. Manuscript, DIKU, Department of Computer Science, University of Copenhagen, 2001.
	12	Edsger W. Dijkstra, Program Inversion, Program Construction, International Summer Schoo, p.54-57, July 26-August 06, 1978
	13	Robert Glück , Andrei V. Klimov, Occam's Razor in Metacompuation: the Notion of a Perfect Process Tree, Proceedings of the Third International Workshop on Static Analysis, p.112-123, September 22-24, 1993
	14	Robert Glück , Morten Heine Sørensen, Partial Deduction and Driving are Equivalent, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.165-181, September 14-16, 1994
	15	M. Hanus. The integration of functions into logic programming: from theory to practice. Journal of Logic Programming,19&20: 583--628, 1994.
	16	John Hatcliff, An Introduction to Online and Offline Partial Evaluation using a Simple Flowchart Language, Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School, p.20-82, June 29-July 10, 1998
	17	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	18	Jesper Jørgensen, Generating a compiler for a lazy language by partial evaluation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-268, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143220]
	19	Jesper Jørgensen, SIMILIX: A Self-Applicable Partial Evaluator for Scheme, Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School, p.83-107, June 29-July 10, 1998
	20	Shin-ya Katsumata , Atsushi Ohori, Proof-Directed De-compilation of Low-Level Code, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.352-366, April 02-06, 2001
	21	J. McCarthy. The inversion of functions defined by Turing machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 177--181. Princeton University Press, 1956.
	22	Shin-Cheng Mu , Richard S. Bird, Inverting Functions as Folds, Proceedings of the 6th International Conference on Mathematics of Program Construction, p.209-232, July 08-10, 2002
	23	Andrei P. Nemytykh , Victoria A. Pinchuk, Program Transformation with Metasystem Transitions: Experiments with a Supercompiler, Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics, p.249-260, June 25-28, 1996
	24	Scott Thibault , Charles Consel , Julia L. Lawall , Renaud Marlet , Gilles Muller, Static and Dynamic Program Compilation by Interpreter Specialization, Higher-Order and Symbolic Computation, v.13 n.3, p.161-178, Sept. 2000 [doi>10.1023/A:1010078412711 ]

CITED BY 2

	Robert Glück , Masahiko Kawabe, A Method for Automatic Program Inversion Based on LR(0) Parsing, Fundamenta Informaticae, v.66 n.4, p.367-395, December 2005
	Robert Glück , Masahiko Kawabe, Revisiting an automatic program inverter for Lisp, ACM SIGPLAN Notices, v.40 n.5, p.8-17, May 2005