Abstract
Earlier work has shown that partial evaluation of a self-interpreter with respect to an input program can be used to effect program transformation. This talk shows that this technique, augmented by a preliminary abstract interpretation, can yield, among many other transformations:
-
• Safe, efficient execution of programs in an unsafe language, and
-
• A change in program style, from one list representation to another
Further, partial evaluation can be viewed as an on-line polyvariant abstract interpretation, augmented by code generation. This view generalizes conventional projection-based partial evaluation in the direction of Turchin's supercompilation.
This research was partially supported by the Danish DART project.
Preview
Unable to display preview. Download preview PDF.
References
Samson Abramsky and Chris Rankin, editors. Abstract Interpretation of Declarative Languages. Ellis Horwood, 1987.
Charles Consel and Olivier Danvy, Partial evaluation of pattern matching in strings. Information Processing Letters, 30, pp. 79–86, January 1989.
Patrick Cousot and Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Fourth ACM Symposium on Principles on Programming Languages, pp. 238–252, New York: ACM Press, 1977.
Andrei P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18, pp. 41–67, 1982.
Robert Glück and Andrei V. Klimov, Occam's razor in metacomputation: the notion of a perfect process tree. In Static analysis Proceedings, eds. P. Cousot, M. Falaschi, G. Filé, G. Rauzy. Lecture Notes in Computer Science 724, pp. 112–123, Springer-Verlag, 1993.
C.V. Hall, Using Hindley-Milner type inference to optimise list representation. In ACM Conference on Lisp and Functional Programming, pp. 162–172, ACM Press, 1994.
Neil D. Jones, C.K. Gomard, P. Sestoft, Partial Evaluation and Automatic Program Generation, Prentice Hall International Series in Computer Science, 1993.
Neil D. Jones and Flemming Nielson, Abstract interpretation: a semantics-based tool for program analysis, 122 pages. In Handbook of Logic in Computer Science, Oxford University Press, 1995.
Neil D Jones and Steven S Muchnick, Complexity of flow analysis, inductive assertion synthesis, and a language due to Dijkstra, pages 380–393. In Program Flora Analysis: Theory and Applications, Prentice-Hall, 1981.
Neil D. Jones, Automatic program specialization: A re-examination from basic principles, in D. Bjørner, A.P. Ershov, and N.D. Jones (eds.), Partial Evaluation and Mixed Computation, pp. 225–282, Amsterdam: North-Holland, 1988.
N. D. Jones, The Essence of Program Transformation by Partial Evaluation and Driving, in Logic, Language and Computation, a Festschrift in honor of Satoru Takasu, edited by Masahiko Sato N. D. Jones, Masami Hagiya, pages 206–224, S-V, April 1994.
Donald E. Knuth, James H. Morris, and Vaughan R. Pratt, Fast pattern matching in strings, SIAM Journal of Computation, 6(2), pp. 323–350, 1977.
Shao, Z., J.H. Reppy, A.W.Appel, Unrolling lists. In ACM Conference on Lisp and Functional Programming, pp. 185–195, ACM Press, 1994.
V.F. Turchin, ‘The concept of a supercompiler,’ ACM Transactions on Programming Languages and Systems, 8(3):292–325, July 1986 *** DIRECT SUPPORT *** A0008C44 00011
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jones, N.D. (1997). Combining abstract interpretation and partial evaluation (brief overview). In: Van Hentenryck, P. (eds) Static Analysis. SAS 1997. Lecture Notes in Computer Science, vol 1302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032761
Download citation
DOI: https://doi.org/10.1007/BFb0032761
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63468-3
Online ISBN: 978-3-540-69576-9
eBook Packages: Springer Book Archive