Program transformation with metasystem transitions: Experiments with a supercompiler | SpringerLink
Skip to main content
Springer Nature Link
Log in

Program transformation with metasystem transitions: Experiments with a supercompiler

  • Conference paper
  • First Online:
Perspectives of System Informatics (PSI 1996)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1181))

Abstract

Turchin's supercompilation is a program transformation technique for functional languages. A supercompiler is a program which can perform a deep transformation of programs using a principle which is similar to partial evaluation.

In the present paper we use a supercompiler, which V.F. Turchin and we have described in [22], [23]. The aim of our investigation has been to show, what deep changes (w.r.t. run time) in the programs can be achieved by supercompilation.

In [21] V.F. Turchin presented a method to improve the transformational power of supercompilation without modifying the transformation system. We use this idea to show both the power of the method and abilities of our supercompiler. Our examples include a generation of both one-step unfolding and instantiations, lazy evaluation, inverse evaluation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abramov S.M., Metavychisleniya i logicheskoe programmirovanie (Metacomputation and logic programming). Programmirovanie, 3:31–44, 1991. (in Russian).

    Google Scholar 

  2. Burstall R. M., J. Darlington. A Transformation System for Developing Recursive Programs. In Journal of the ACM. Vol. 24, No.1,pp. 44–67, 1977.

    Google Scholar 

  3. Ershov, A.P. On the essence of compilation, In: E.J.Neuhold (Ed.) Formal Description of Programming Concepts, pp.391–420, North-Holland, 1978.

    Google Scholar 

  4. Futamura, Y., Partial evaluation of computation process — an approach to compiler compiler. Systems, Computers, Controls, 2, 5 (1971) pp. 45–50.

    Google Scholar 

  5. Jones N., Sestoft P., Sondergaard H., An experiment in partial evaluation: the generation of a compiler generator. In: Jouannaud J.-P. (Ed.) Rewriting Techniques and Applications, Dijon, France, LNCS 202, Springer, 1985.

    Google Scholar 

  6. Glück R. and Turchin V., Experiments with a Self-applicable Supercompiler, CCNY Technical Report, 1989.

    Google Scholar 

  7. Glück R., Towards multiple self-application. In: Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pp. 309–320, New Haven, Connecticut, ACM Press, 1991.

    Google Scholar 

  8. Glück R., Jørgensen J., Generating optimizing specializers. In: IEEE International Conference on Computer Languages, Toulose, France, IEEE Computer Society Press, 1994.

    Google Scholar 

  9. Knuth D.E., Morris J.H., Pratt V.R., Fast Pattern Matching in Strings. In SIAM Journal of Computer, 6(2) pp. 323–350, 1977

    Google Scholar 

  10. Nemytykh A., Fast Pattern Matching in Strings by Program Transformation in preparation

    Google Scholar 

  11. Nemytykh A., Pinchuk V., Transformation Programs to Decrease Run Time in preparation

    Google Scholar 

  12. Nemytykh A., Pinchuk V., Inversing of functional programs by metasystem transitions in preparation

    Google Scholar 

  13. Nemytykh A., Pinchuk V., Interpretive layers in metasystem transitions. In: ftp.botik.ru (name: anonymous, pwd: YourSecondName), path: pub/local/scp, 1995.

    Google Scholar 

  14. Pettorossi A. and Proietti M., Transformation of logic programs: Foundations and Techniques, Istituto di analisi dei sistemi ed informatica, R. 369, Novembre 1993, Italy.

    Google Scholar 

  15. Romanenko A., Inversion and Metacomputation. Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Yale University, 1991, USA pp. 12–22.

    Google Scholar 

  16. Turchin V. F., Klimov A. V. et al, Bazisnyi Refal i yego realizalsiya na vychislitel'nykh mashinakh. (Basic Refal and its implementation on computers) GOSSTROY SSSR, TsNIPIASS, Moscow, 1977 (in Russian).

    Google Scholar 

  17. Turchin, V.F. The Language Refal, the Theory of Compilation and Metasystem Analysis, Courant Computer Science Report #20, New York University, 1980.

    Google Scholar 

  18. Turchin, V.F. The concept of a supercompiler, ACM Transactions on Programming Languages and Systems, 8, pp. 292–325, 1986.

    Google Scholar 

  19. Turchin, V.F. The Algorithm of Generalization in the Supercopmiler, In ACM Partial Evaluation and Mixed Computation. Eds. A.P. Ershov, D. Bjorner, N.D. Jones North-Holland, 1988.

    Google Scholar 

  20. Turchin V., Refal-5, Programming Guide and Reference Manual, New England Publishing Co., 1989.

    Google Scholar 

  21. Turchin V.F., Program Transformation with Metasystem Transitions, J. of Functional Programming, 3(3) 283–313, 1993.

    Google Scholar 

  22. Turchin V., Nemytykh, A. Metavariables: Their implementation and use in Program Transformation, Technical Report CSc. TR 95-012, City College of the City University of New York, 1995.

    Google Scholar 

  23. Turchin V., Nemytykh A., Pinchuk V., A Self-Applicable Supercompiler, to appear in Proceedings of PEPM, Dagstuhl, 1996.

    Google Scholar 

  24. Wadler P. Deforestation Programs to Eliminate Trees. TCS., 73: 231–248, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Program Systems Institute, Pereslavl-Zalesski, 152140, Yaroslavl Region, Russia

    Andrei P. Nemytykh & Victoria A. Pinchuk

Authors
  1. Andrei P. Nemytykh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Victoria A. Pinchuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Dines Bjørner Manfred Broy Igor V. Pottosin

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nemytykh, A.P., Pinchuk, V.A. (1996). Program transformation with metasystem transitions: Experiments with a supercompiler. In: Bjørner, D., Broy, M., Pottosin, I.V. (eds) Perspectives of System Informatics. PSI 1996. Lecture Notes in Computer Science, vol 1181. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62064-8_21

Download citation

  • DOI: https://doi.org/10.1007/3-540-62064-8_21

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-62064-8

  • Online ISBN: 978-3-540-49637-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics