Abstract
An adaptive program is an object-oriented program which is abstracted over the particular class structure. This abstraction fosters software reuse, because programmers can concentrate on specifying how to process the objects which are essential to their application. The compiler of an adaptive program takes care of actually locating the objects. The adaptive programmer merely writes a traversal specification decorated with actions. The compiler instantiates the specification with the actual class structure and generates code that traverses a collection of objects, performing visits and actions according to the specification. Earlier work on adaptive programming merely stated but never verified that compilation of adaptive programs is nothing but partial evaluation. We employ an algebraic framework based on derivatives of traversal specifications to develop an interpretive semantics of adaptive programming. This semantics is naturally staged in up to three stages. Compilation can be achieved using a standard partial evaluator. Slight changes in the binding-time properties yield several variants of the compiler, by trading compile-time computations for run-time computations.
Chapter PDF
Similar content being viewed by others
References
Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, and Janet Wiener. The Lorel query language for semistructured data. Journal of Digital Libraries, 1(1):68–88, 1997. 276
Serge Abiteboul and Victor Vianu. Regular path queries with constraints. In PODS’ 97. Proceedings of the Sixteenth ACM SIG-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 122–133, Tucson, Arizona, May 1997. ACM Press. 276
Paul L. Bergstein. Object-preserving class transformations. In OOPSLA’91, ACM SIGPLAN Sixth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 299–313. ACM, November 1991. SIGPLAN Notices (26)11. 267
Gerard Berry and Ravi Sethi. From regular expressions to deterministic automata. Theoretical Computer Science, 48:117–126, 1986. 277
W. Brown, R. Malveau, H. McCormick, and T. Mowbray. AntiPatterns: Refactoring Software, Architectures, and Projects in Crisis.John Wiley and Sons, 1998. 265
Janusz A. Brzozowski. Derivatives of regular expressions. Journal of the ACM, 11(4):481–494, 1964. 277
John H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, 1971. 277
Martin Fowler. Refactoring: Improving the Design of Existing Code. Addison-Wesley, 1999. 265
John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages and computation. Addison-Wesley, 1979. 277
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993. 265, 273
Richard Kelsey, William Clinger, and Jonathan Rees. Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7–105, 1998. Also appears in ACM SIGPLAN Notices 33(9), September 1998. Available electronically as http://www.neci.nj.nec.com/homepages/kelsey/r5rs.ps.gz. 265, 272
Michael Kifer, Wong Kim, and Yehoshua Sagiv. Querying object oriented databases. In Michael Stonebraker, editor, Proceedings of the SIGMOD International Conference on Management of Data, volume 21 of SIGMOD Record, pages 393–402, New York, NY, USA, June 1992. ACM Press. 276
Donald Ervin Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2:127–145, 1968. 277, 278
Donald Ervin Knuth. Semantics of context-free languages. Mathematical Systems Theory, 5:95–96, 1971. Correction to [13]. 277
Karl J. Lieberherr. Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns. PWS Publishing Company, Boston, 1996. 264, 265, 276
Karl J. Lieberherr and Boaz Patt-Shamir. Traversals of object structures: Specification and efficient implementation. Technical Report NU-CCS-97-15, College of Computer Science, Northeastern University, Boston, MA, July 1997. 264, 267, 269, 274, 276
W. Opdyke. Refactoring Object-Oriented Frameworks. PhD thesis, University of Illinois at Urbana-Champain, 1992. 265
Jens Palsberg, Boaz Patt-Shamir, and Karl Lieberherr. A new approach to compiling adaptive programs. Science of Computer Programming, 29(3):303–326, September 1997. 264, 265, 267, 269, 276
Jens Palsberg, Cun Xiao, and Karl Lieberherr. Efficient implementation of adaptive software. ACM Transactions on Programming Languages and Systems, 17(2):264–292, March 1995. 264, 265, 267, 270, 271, 276
S._Doaitse Swierstra, P.R. Azero Alocer, and João Saraiava. Designing and implementing combinator languages. In Doaitse Swierstra, Pedro Henriques, and José Oliveira, editors, Advanced Functional Programming, Third International School, AFP’98, volume 1608 of LNCS-Tutorial, pages 150–206. Springer-Verlag, 1999. 277
Peter Thiemann. Towards partial evaluation of full Scheme. In Gregor Kiczales, editor, Reflection’96, pages 95–106, San Francisco, CA, USA, April 1996. 274
Peter Thiemann. The PGG System—User Manual. Universitßt Freiburg, Freiburg, Germany, February 1999. Available from ftp://ftp.informatik.uni-freiburg.de/iif/thiemann/pgg/. 265, 273
Peter Thiemann. An algebraic foundation for adaptive programming. In Jerzy Tiuryn, editor, Foundations of Software Science and Computation Structures, FOSSACS 2000, Lecture Notes in Computer Science, Berlin, Germany, March 2000. Springer-Verlag. Extended version available from http://www.informatik.uni-freiburg.de/thiemann/papers/adaptive-lncs.ps.gz. 265, 273, 277
Jan Van den Bussche and Gottfried Vossen. An extension of path expressions to simplify navigation in object-oriented queries. In Proc. of Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), volume 760 of Lecture Notes in Computer Science, pages 267–282, 1993. 276
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Thiemann, P. (2000). Compiling Adaptive Programs by Partial Evaluation. In: Watt, D.A. (eds) Compiler Construction. CC 2000. Lecture Notes in Computer Science, vol 1781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46423-9_18
Download citation
DOI: https://doi.org/10.1007/3-540-46423-9_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67263-0
Online ISBN: 978-3-540-46423-5
eBook Packages: Springer Book Archive