Abstract
This article describes SCHISM: a self-applicable partial evaluator for a first order subset of Scheme. SCHISM takes place in the framework of mixed computation, and is situated along the line of the MIX project at the University of Copenhagen. The goal is automatically to generate compilers from interpreters by self-application and we have done this with an extensible and directly executable first order subset of Scheme.
SCHISM is an open-ended partial evaluator with a syntactic extension mechanism (macro-functions written in full Scheme). Furthermore, the set of primitives is extensible without any modification of the system.
Partial evaluation of functional languages relies on the treatment of function calls. We have chosen to use annotations for driving SCHISM to eliminate a call (unfold it) or to keep it residual (specialize it). They are local to each function rather than to each function call. This solves the problem of multiple calls to the same function with different patterns of static and dynamic arguments. Usually two pitfalls are possible in such a case: either to make all of these calls residual and specialize the function exponentially; or to eliminate the calls systematically and possibly start an infinite unfolding. Both are avoided by the use of a filter expression attached to functions. These filters drive SCHISM.
In this article we first describe our first order Scheme both with its abstract syntax and informally. Then we analyze the possibilities raised by keeping annotations local to each function. Finally we propose a partial solution to the open problem of reusing the store: the idea is to distinguish compile time and run time in the interpreter itself. In the end some conclusions and issues are proposed.
Chapter PDF
Similar content being viewed by others
Keywords
Bibliography
Aho, A. V., Sethi, R. and Ullman J. D. Compilers: Principles, Techniques and Tools, Addison-Wesley [1986]
Bondorf A. Towards a Self-Applicable Partial Evaluator for Term Rewriting Systems, North Holland Publ. proceedings of the Workshop on Partial Evaluation and Mixed Computation, Denmark [1987]
Consel C., Deutsch A., Dumeur R. and Fekete J-D. Skim Reference Manual, Rapport Technique 86/09 Université de Paris 8, France [1986]
Diku, University of Copenhagen The Mix System User's Guide Version 3.0 Diku internal report, University of Copenhagen, Denmark [1987]
Ershov, A. P. Mixed Computation: Potential Applications and Problems for Study, Theoretical Computer Science 18 (41–67) [1982]
Emanuelson, P. and Haraldsson A. On Compiling Embedded Languages in Lisp, Lisp Conference, Standford, California, (208–215) [1980]
Futamura, Y. Partial Evaluation of Computation Process — an Approach to a Compiler-Compiler, Systems, Computers, Controls 2, 5 (45–50) [1971]
Futamura, Y. Partial Computation of Programs, In E. Goto et al (eds.): RIMS Symposia on Software Science and Engineering, Kyoto, Japan. Lecture Notes in Computer Science 147, 1983, (1–35) [1982]
Gordon, M. J. C. The Denotational Description of Programming Languages, Springer-Verlag [1979]
Jones, N. D., P. Sestoft, and H. Søndergaard An Experiment in Partial Evaluation: the Generation of a Compiler Generator, Rewriting Techniques and Applications, Dijon, France. Lecture Notes in Computer Science 202, (124–140) Springer-Verlag [1985]
Jones, N. D., P. Sestoft, and H. Søndergaard Mix: a Self-Applicable Partial Evaluator for Experiments in Compiler Generation, Diku Report 87/08, University of Copenhagen, Denmark [1987]
Kleene, S. C. Introduction to Metamathematics, Van Nostrand [1952]
Kohlbecker, E. E. Syntactic Extensions in the Programming Language Lisp, PH. D. thesis, Technical Report No 199, Indiana University, Bloomington, Indiana [1986]
Lombardi, L. A. Incremental Computation, Advances in Computers 8 (ed. F. L. Alt and Rubinoff), Academic Press, (247–333) [1967]
Rees, J. and W. Clinger (eds.) Revised3 Report on the Algorithmic Language Scheme, SIGPLAN Notices 21, 12, (37–79) [1986]
Schmidt, D. A. Denotational Semantics: a Methodology for Language Development, Allyn and Bacon, Inc. [1986]
Sestoft, P. The Structure of a Self-Applicable Partial Evaluator, Diku report 85/11, University of Copenhagen, Denmark. [1985].
Steele G. L. Jr. Rabbit: a Compiler for Scheme, MIT AIL TR 474, Cambridge, Mass. [1978]
Steele G. L. Jr. Common Lisp, Digital Press [1984]
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
CONSEL, C. (1988). New insights into partial evaluation: the SCHISM experiment. In: Ganzinger, H. (eds) ESOP '88. ESOP 1988. Lecture Notes in Computer Science, vol 300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-19027-9_16
Download citation
DOI: https://doi.org/10.1007/3-540-19027-9_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19027-1
Online ISBN: 978-3-540-38941-5
eBook Packages: Springer Book Archive