Article

Transformation of structure-shy programs: applied to XPath queries and strategic functions

Authors:

Joost VisserAuthors Info & Claims

PEPM '07: Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

Pages 11 - 20

https://doi.org/10.1145/1244381.1244385

Published: 15 January 2007 Publication History

Abstract

Various programming languages allow the construction of structure-shy programs. Such programs are defined generically for many different datatypes and only specify specific behavior for a few relevant subtypes. Typical examples are XML query languages that allow selection of subdocuments without exhaustively specifying intermediate element tags. Other examples are languages and libraries for polytypic or strategic functional programming and for adaptive object-oriented programming.

In this paper, we present an algebraic approach to transformation of declarative structure-shy programs, in particular for strategic functions and XML queries. We formulate a rich set of algebraic laws, not just for transformation of structure-shy programs, but also for their conversion into structure-sensitive programs and vice versa. We show how subsets of these laws can be used to construct effective rewrite systems for specialization, generalization, and optimization of structure-shy programs. We present a type-safe encoding of these rewrite systems in Haskell which itself uses strategic functional programming techniques.

References

[1]

A. Alimarine and S. Smetsers. Optimizing generic functions. In D. Kozen, editor, Mathematics of Program Construction, volume 3125 of LNCS, pages 16--31. Springer, 2004.

[2]

A. Alimarine and S. Smetsers. Improved fusion for optimizing generics. In M. V. Hermenegildo and D. Cabeza, editors, Proc. 7th Int. Symp. Practical Aspects of Declarative Languages, volume 3350 of LNCS, pages 203--218. Springer, 2005.

Digital Library

[3]

J. W. Backus. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Commun. ACM, 21(8):613--641, 1978.

Digital Library

[4]

D. Che, K. Aberer, and T. Özsu. Query optimization in XML structured-document databases. The VLDB Journal, 15(3):263--289, 2006.

Digital Library

[5]

A. Cunha, J. N. Oliveira, and J. Visser. Type-safe two-level data transformation. In J. Misra, T. Nipkow, and E. Sekerinski, editors, Proc. Formal Methods, 14th Int. Symp. Formal Methods Europe, volume 4085 of LNCS, pages 284--299. Springer, 2006.

Digital Library

[6]

A. Cunha and J. Sousa Pinto. Point-free program transformation. Fundam. Inform., 66(4):315--352, 2005.

Digital Library

[7]

A. Cunha, J. Sousa Pinto, and J. Proença. A framework for point-free program transformation. In A. Butterfield, C. Grelck, and F. Huch, editors, Selected papers 17th Int. Workshop on Implementation and Application of Functional Languages, volume 4015 of LNCS, pages 1--18. Springer, 2006.

Digital Library

[8]

A. Cunha and J. Visser. Strongly typed rewriting for coupled software transformation. In M. Fernandez and R. Lämmel, editors, Proc. 7th Int. Workshop on Rule-Based Programming (RULE 2006), ENTCS. Elsevier, 2006. To appear.

[9]

J. Gibbons. Calculating functional programs. In R. Backhouse et al., editors, Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, volume 2297 of LNCS, chapter 5, pages 148--203. Springer, 2002.

Digital Library

[10]

R. Hinze, A. Löh, and B. C. d. S. Oliveira. "Scrap your boilerplate" reloaded. In M. Hagiya and P. Wadler, editors, Proc. Functional and Logic Programming, 8th Int. Symp., volume 3945 of LNCS, pages 13--29. Springer, 2006.

Digital Library

[11]

S. Holdermans, J. Jeuring, A. Löh, and A. Rodriguez. Generic views on data types. In Tarmo Uustalu, editor, Proc. 8th Int. Conf. Mathematics of Program Construction, volume 4014 of LNCS, pages 209--234. Springer, 2006.

Digital Library

[12]

R. Lämmel. Typed Generic Traversal With Term Rewriting Strategies. Journal of Logic and Algebraic Programming, 54, 2003.

[13]

R. Lämmel. Scrap your boilerplate with XPath-like combinators, 15 July 2006. Draft, 6 pages, Accepted as short paper at POPL 2007.

Digital Library

[14]

R. Lämmel and S. Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. ACM SIGPLAN Notices, 38(3):26--37, March 2003. Proc. ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI 2003).

Digital Library

[15]

R. Lämmel, E. Visser, and J. Visser. Strategic programming meets adaptive programming. In AOSD '03: Proc. 2nd Int. Conf. Aspect-Oriented Software Development, pages 168--177. ACM Press, 2003.

Digital Library

[16]

R. Lämmel, E. Visser, and J. Visser. The Essence of Strategic Programming. Available at http://www.cwi.nl/~ralf, 2003.

[17]

R. Lämmel and J. Visser. Typed Combinators for Generic Traversal. In Proc. Practical Aspects of Declarative Programming PADL 2002, volume 2257 of LNCS, pages 137--154. Springer, January 2002.

Digital Library

[18]

R. Lämmel and J. Visser. A Strafunski Application Letter. In V. Dahl and P. Wadler, editors, Proc. of Practical Aspects of Declarative Programming (PADL'03), volume 2562 of LNCS, pages 357--375. Springer, January 2003.

Digital Library

[19]

K. Lieberherr, B. Patt-Shamir, and D. Orleans. Traversals of object structures: Specification and efficient implementation. ACM Trans. Program. Lang. Syst., 26(2):370--412, 2004.

Digital Library

[20]

Karl J. Lieberherr. Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns. PWS Publishing Company, 1996.

Digital Library

[21]

S. Peyton Jones, G. Washburn, and S. Weirich. Wobbly types: type inference for generalised algebraic data types. Technical Report MS-CIS-05-26, Univ. of Pennsylvania, July 2004.

[22]

F. Reig. Generic proofs for combinator-based generic programs. In H.-W. Loidl, editor, Trends in Functional Programming, volume 5, pages 17--32. Intellect, 2006.

[23]

Alexandra Silva and Joost Visser. Strong types for relational databases. In Proc. ACM SIGPLAN workshop on Haskell, pages 25--36. ACM Press, 2006.

Digital Library

[24]

E. Visser. Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5. In A. Middeldorp, editor, Rewriting Techniques and Applications, volume 2051 of LNCS, pages 357--361. Springer, May 2001.

Digital Library

[25]

E. Visser and Z. Benaissa. A core language for rewriting. Electr. Notes Theor. Comput. Sci., 15, 1998.

[26]

J. Visser. Visitor combination and traversal control. ACM SIGPLAN Notices, 36(11):270--282, 2001. Proc. ACM Conf. on Object-Oriented Programming Systems, Languages, and Applications.

Digital Library

[27]

J. Visser. Generic Traversal over Typed Source Code Representations. PhD thesis, University of Amsterdam, 2003.

[28]

M. de Vries. Specializing type-indexed values by partial evaluation. Master's thesis, Rijksuniversiteit Groningen, 2004.

[29]

W3C. XML path language (XPath) 2.0, W3C candidate recommendation, June, 8, 2006.

[30]

S. Weirich. RepLib: a library for derivable type classes. In Proc. ACM SIGPLAN workshop on Haskell, pages 1--12. ACM Press, 2006.

Digital Library

Cited By

Qin XO’Connor Lvan Glabbeek RHöfner PKammar OSteuwer M(2024)Shoggoth: A Formal Foundation for Strategic RewritingProceedings of the ACM on Programming Languages10.1145/36332118:POPL(61-89)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3633211
Caruccio LPolese GTortora G(2016)Synchronization of Queries and Views Upon Schema EvolutionsACM Transactions on Database Systems10.1145/290372641:2(1-41)Online publication date: 11-May-2016
https://dl.acm.org/doi/10.1145/2903726
Cunha JFernandes JMendes JSaraiva J(2015)Embedding, Evolution, and Validation of Model-Driven SpreadsheetsIEEE Transactions on Software Engineering10.1109/TSE.2014.236114141:3(241-263)Online publication date: 1-Mar-2015
https://doi.org/10.1109/TSE.2014.2361141
Show More Cited By

Index Terms

Transformation of structure-shy programs: applied to XPath queries and strategic functions
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages
2. Theory of computation
  1. Logic
  2. Semantics and reasoning

Recommendations

Transformation of structure-shy programs with application to XPath queries and strategic functions

Various programming languages allow the construction of structure-shy programs. Such programs are defined generically for many different datatypes and only specify specific behavior for a few relevant subtypes. Typical examples are XML query languages ...
Comparison of two XML query languages from the perspective of learners

Two XML query languages were tested for intuitivity, learnability and memorability. The languages differ with relation to the query structures like the use of variables, iterators and reference to attributes. One of the languages, XQuery, is a ...
A church-style intermediate language for MLF

MLF is a type system that seamlessly merges ML-style implicit but second-class polymorphism with System-F explicit first-class polymorphism. We present xMLF, a Church-style version of MLF with full type information that can easily be maintained during ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '07: Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

January 2007

180 pages

ISBN:9781595936202

DOI:10.1145/1244381

Conference Chairs:
G. Ramalingam,
Eelco Visser

Copyright © 2007 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PEPM07

Sponsor:

SIGPLAN

PEPM07: Partial Evaluation and Program Manipulation

January 15 - 16, 2007

Nice, France

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
185
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Qin XO’Connor Lvan Glabbeek RHöfner PKammar OSteuwer M(2024)Shoggoth: A Formal Foundation for Strategic RewritingProceedings of the ACM on Programming Languages10.1145/36332118:POPL(61-89)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3633211
Caruccio LPolese GTortora G(2016)Synchronization of Queries and Views Upon Schema EvolutionsACM Transactions on Database Systems10.1145/290372641:2(1-41)Online publication date: 11-May-2016
https://dl.acm.org/doi/10.1145/2903726
Cunha JFernandes JMendes JSaraiva J(2015)Embedding, Evolution, and Validation of Model-Driven SpreadsheetsIEEE Transactions on Software Engineering10.1109/TSE.2014.236114141:3(241-263)Online publication date: 1-Mar-2015
https://doi.org/10.1109/TSE.2014.2361141
LäMmel RThompson SKaiser M(2013)Programming errors in traversal programs over structured dataScience of Computer Programming10.1016/j.scico.2011.11.00678:10(1770-1808)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.scico.2011.11.006
Alves TSilva PVisser J(2012)Constraint-aware Schema TransformationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2012.11.008290(3-18)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.entcs.2012.11.008
Cunha JVisser JAlves TSaraiva J(2011)Type-safe evolution of spreadsheetsProceedings of the 14th international conference on Fundamental approaches to software engineering: part of the joint European conferences on theory and practice of software10.5555/1987434.1987453(186-201)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987434.1987453
Mametjanov AWinter VLämmel RBrabrand CWyk E(2011)More precise typing of rewrite strategiesProceedings of the Eleventh Workshop on Language Descriptions, Tools and Applications10.1145/1988783.1988786(1-8)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.1145/1988783.1988786
Ikeda YNishimura SKhoo SSiek J(2011)Calculating tree navigation with symmetric relational zipperProceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation10.1145/1929501.1929521(101-110)Online publication date: 24-Jan-2011
https://dl.acm.org/doi/10.1145/1929501.1929521
Kaiser MLämmel RPorto ALópez-Fraguas F(2009)An Isabelle/HOL-based model of stratego-like traversal strategiesProceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming10.1145/1599410.1599423(93-104)Online publication date: 7-Sep-2009
https://dl.acm.org/doi/10.1145/1599410.1599423
Lämmel RPorto ALópez-Fraguas F(2009)Scrap your boilerplateProceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming10.1145/1599410.1599412(7-12)Online publication date: 7-Sep-2009
https://dl.acm.org/doi/10.1145/1599410.1599412
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.

Figures

Tables

Media

View Table of Conten