article

Transforming interpreters into inverse interpreters by partial evaluation

Authors:

Takuya HashimotoAuthors Info & Claims

ACM SIGPLAN Notices, Volume 38, Issue 10

Pages 10 - 19

https://doi.org/10.1145/966049.777391

Published: 07 June 2003 Publication History

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

[1]

S. M. Abramov and R. Glück. Combining semantics with non-standard interpreter hierarchies. In S. Kapoor and S. Prasad, editors, Foundations of Software Technology and Theoretical Computer Science. Proceedings, LNCS 1974, pages 201--213. Springer-Verlag,2000.]]

Digital Library

[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]

S. M. Abramov and R. Glück. Principles of inverse computation and the universal resolving algorithm. In T. A. Mogensen, D. Schmidt, and H. I. Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation, LNCS 2566, pages 269--295. Springer-Verlag, 2002.]]

Digital Library

[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]

E. Albert and G. Vidal. The narrowing-driven approach to functional logic program specialization. New Generation Computing, 20(1):3--26, 2002.]]

Digital Library

[6]

A. Bondorf. Automatic autoprojection of higher order recursive equations. Science of Computer Programming,17(1 .3):3--34, 1991.]]

Digital Library

[7]

A. Bondorf. Similix 5.0 Manual. DIKU, University of Copenhagen, Denmark, 1993. Included in the Similix distribution, 82 pages.]]

[8]

A. Bondorf and O. Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming,16:151--195, 1991.]]

Digital Library

[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]

E. W. Dijkstra. Program inversion. In F. L. Bauer and M. Broy, editors, Program Construction: International Summer School, LNCS 69, pages 54--57. Springer-Verlag, 1978.]]

Digital Library

[13]

R.Glück and A. V. Klimov. Occam's razor in metacomputation: the notion of a perfect process tree. In P. Cousot, M. Falaschi,G.Filé, and A. Rauzy, editors, Static Analysis. Proceedings, LNCS 724, pages 112--123. Springer-Verlag, 1993.]]

Digital Library

[14]

R.Glück and M. H. Sorensen. Partial deduction and driving are equivalent. In M. Hermenegildo and J. Penjam, editors, Programming Language Implementation and Logic Programming.Proceedings, LNCS 844, pages 165--181. Springer-Verlag, 1994.]]

Digital Library

[15]

M. Hanus. The integration of functions into logic programming: from theory to practice. Journal of Logic Programming,19&20: 583--628, 1994.]]

[16]

J. Hatcliff. An introduction to online and offline partial evaluation using a simple flowchart language. In J. Hatcliff, T. Mogensen, and P. Thiemann, editors, Partial Evaluation.Practice and Theory, LNCS 1706, pages 20--82. Springer-Verlag, 1999.]]

Digital Library

[17]

N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.]]

Digital Library

[18]

J. Jorgensen. Generating a compiler for a lazy language by partial evaluation. In Conference Record of the Nighteenth Symposium on Principles of Programming Languages, pages 258--268. ACM Press, 1992.]]

Digital Library

[19]

J. Jorgensen. Similix: a self-applicable partial evaluator for scheme. In J.Hatcliff, T. Mogensen, and P. Thiemann, editors, Partial Evaluation. Practice and Theory, LNCS 1706, pages 83--107. Springer-Verlag, 1999.]]

Digital Library

[20]

S. Katsumata and A. Ohori. Proof-directed de-compilation of Java bytecode. In D. Sands, editor, Programming Languages and Systems. Proceedings, LNCS 2028, pages 352--366. Springer-Verlag, 2001.]]

Digital Library

[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]

S.-C. Mu and R. Bird. Inverting functions as folds. In E. A. Boiten and B. Möller, editors, Mathematics of Program Construction. Proceedings, LNCS 2386, pages 209--232. Springer-Verlag, 2002.]]

Digital Library

[23]

A. P. Nemytykh and V. A. Pinchuk. Program transformation with metasystem transitions: experiments with a supercompiler. In D.Bjorner, M. Broy, and I. V. Pottosin, editors, Perspectives of System Informatics. Proceedings, LNCS 1181, pages 249--260. Springer-Verlag, 1996.]]

Digital Library

[24]

S. Thibault, C. Consel, J. L. Lawall, R. Marlet, and G. Muller. Static and dynamic program compilation by interpreter specialization. Higher-Order and Symbolic Computation, 13(3):161--178, 2000.]]

Digital Library

Cited By

Glück RYokoyama T(2022)Reversible Computing from a Programming Language PerspectiveTheoretical Computer Science10.1016/j.tcs.2022.06.010Online publication date: Dec-2022
https://doi.org/10.1016/j.tcs.2022.06.010
Axelsen HGlück R(2016)On reversible Turing machines and their function universalityActa Informatica10.1007/s00236-015-0253-y53:5(509-543)Online publication date: 27-Jan-2016
https://doi.org/10.1007/s00236-015-0253-y
Niwa MNishida NSakai M(2013)Improving Determinization of Grammar Programs for Program InversionLogic-Based Program Synthesis and Transformation10.1007/978-3-642-38197-3_11(155-175)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38197-3_11
Show More Cited By

Index Terms

Transforming interpreters into inverse interpreters by partial evaluation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Interpreters
      2. Preprocessors
    2. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory
  2. Semantics and reasoning
    1. Program semantics

Recommendations

Transforming interpreters into inverse interpreters by partial evaluation
PEPM '03: Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation

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 ...
Definitional Interpreters for Higher-Order Programming Languages

Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that are themselves written in a programming language based on the lambda calculus (i.e., an applicative language ...
Definitional interpreters for higher-order programming languages
ACM '72: Proceedings of the ACM annual conference - Volume 2

Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters which are themselves written in a programming language based on the lambda calculus (i.e., an applicative language ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 38, Issue 10

Proceedings of the ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP 2003) and workshop on partial evaluation and semantics-based program manipulation (PEPM 2003)

October 2003

331 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/966049

Issue’s Table of Contents

PEPM '03: Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation
June 2003
100 pages
ISBN:1581136676
DOI:10.1145/777388
Program Chair:
Michael Leuschel
University of Southampton, UK

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2003

Published in SIGPLAN Volume 38, Issue 10

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
394
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Glück RYokoyama T(2022)Reversible Computing from a Programming Language PerspectiveTheoretical Computer Science10.1016/j.tcs.2022.06.010Online publication date: Dec-2022
https://doi.org/10.1016/j.tcs.2022.06.010
Axelsen HGlück R(2016)On reversible Turing machines and their function universalityActa Informatica10.1007/s00236-015-0253-y53:5(509-543)Online publication date: 27-Jan-2016
https://doi.org/10.1007/s00236-015-0253-y
Niwa MNishida NSakai M(2013)Improving Determinization of Grammar Programs for Program InversionLogic-Based Program Synthesis and Transformation10.1007/978-3-642-38197-3_11(155-175)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38197-3_11
Glück RKawabe M(2019)A Method for Automatic Program Inversion Based on LR(0) ParsingFundamenta Informaticae10.5555/2370162.237016666:4(367-395)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2370162.2370166
Glück RKawabe M(2019)A Method for Automatic Program Inversion Based on LR(0) ParsingFundamenta Informaticae10.5555/1227189.122719366:4(367-395)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/1227189.1227193
Axelsen HGlück R(2019)On reversible Turing machines and their function universalityActa Informatica10.1007/s00236-015-0253-y53:5(509-543)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/s00236-015-0253-y
Glück R(2009)An experiment with the fourth Futamura projectionProceedings of the 7th international Andrei Ershov Memorial conference on Perspectives of Systems Informatics10.1007/978-3-642-11486-1_12(135-150)Online publication date: 15-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-11486-1_12
Mogensen T(2007)Report on an Implementation of a Semi-inverterPerspectives of Systems Informatics10.1007/978-3-540-70881-0_28(322-334)Online publication date: 2007
https://doi.org/10.1007/978-3-540-70881-0_28
Mogensen T(2006)Report on an implementation of a semi-inverterProceedings of the 6th international Andrei Ershov memorial conference on Perspectives of systems informatics10.5555/1760700.1760730(322-334)Online publication date: 27-Jun-2006
https://dl.acm.org/doi/10.5555/1760700.1760730
Glück RKawabe M(2005)Revisiting an automatic program inverter for LispACM SIGPLAN Notices10.1145/1071221.107122240:5(8-17)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1145/1071221.1071222
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents