research-article

A functional reformulation of UnCAL graph-transformations: or, graph transformation as graph reduction

Authors:

Kazutaka Matsuda,

Kazuyuki AsadaAuthors Info & Claims

PEPM 2017: Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

Pages 71 - 82

https://doi.org/10.1145/3018882.3018883

Published: 02 January 2017 Publication History

Abstract

This paper proposes FUnCAL, a functional redesign of the graph transformation language UnCAL. A large amount of graph-structured data are widely used, including biological database, XML with IDREFs, WWW, and UML diagrams in software engineering. UnCAL is a language designed for graph transformations, i.e., extracting a subpart of a graph data and converting it to a suitable form, as what XQuery does for XMLs. A distinguished feature of UnCAL is its semantics that respects bisimulation on graphs; this enables us to reason about UnCAL graph transformations as recursive functions, which is useful for reasoning as well as optimization. However, there is still a gap to apply the program-manipulation techniques studied in the programming language literature directly to UnCAL programs, due to some special features in UnCAL, especially markers. In this paper, following the observation that markers can be emulated by tuples and λ-abstractions, we transform UnCAL programs to a restricted class of usual (thus, marker-free) functional ones. By this translation, we can reason, analyze or optimize UnCAL programs as usual functional programs. Moreover, we introduce a type system for showing that a small modification to the usual lazy semantics is enough to run well-typed functional programs as finite-graph transformations in a terminating way.

References

[1]

Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, and Janet L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68–88, 1997.

[2]

Zena M. Ariola and Stefan Blom. Cyclic lambda calculi. In TACS, volume 1281 of LNCS, pages 77–106. Springer, 1997.

Digital Library

[3]

Zena M. Ariola and Jan Willem Klop. Equational term graph rewriting. Fundam. Inform., 26(3/4):207–240, 1996.

Digital Library

[4]

Jean Bézivin, Bernhard Rumpe, Andy Schürr, and Laurence Tratt. Model transformations in practice workshop. In MoDELS Satellite Events, volume 3844 of LNCS, pages 120–127. Springer, 2005.

Digital Library

[5]

Peter Buneman, Susan Davidson, Gerd Hillebrand, and Dan Suciu. A query language and optimization techniques for unstructured data. In SIGMOD, pages 505–516. ACM, 1996.

Digital Library

[6]

Peter Buneman, Susan B. Davidson, Mary F. Fernandez, and Dan Suciu. Adding structure to unstructured data. In ICDT, volume 1186 of LNCS, pages 336–350. Springer, 1997.

Digital Library

[7]

Peter Buneman, Mary F. Fernandez, and Dan Suciu. UnQL: A query language and algebra for semistructured data based on structural recursion. VLDB J., 9(1):76–110, 2000.

Digital Library

[8]

Mariano P. Consens and Alberto O. Mendelzon. GraphLog: a visual formalism for real life recursion. In PODS, pages 404–416. ACM Press, 1990.

Digital Library

[9]

Bruno C. d. S. Oliveira and William R. Cook. Functional programming with structured graphs. In ICFP, pages 77–88. ACM, 2012.

Digital Library

[10]

Agostino Dovier, Carla Piazza, and Alberto Policriti. An efficient algorithm for computing bisimulation equivalence. Theoretical Computer Science, 311(1):221 – 256, 2004.

Digital Library

[11]

Martin Erwig. Graph algorithms = iteration + data structures? the structure of graph algorithms and a corresponding style of programming. In WG, volume 657 of LNCS, pages 277–292. Springer, 1992.

Digital Library

[12]

Martin Erwig. Inductive graphs and functional graph algorithms. J. Funct. Program., 11(5):467–492, 2001.

Digital Library

[13]

Leonidas Fegaras and Tim Sheard. Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space). In POPL, pages 284–294, 1996.

Digital Library

[14]

Sebastian Fischer, Oleg Kiselyov, and Chung-chieh Shan. Purely functional lazy non-deterministic programming. In ICFP, pages 11–22, 2009.

Digital Library

[15]

Andrew J. Gill, John Launchbury, and Simon L. Peyton Jones. A short cut to deforestation. In FPCA, pages 223–232, 1993.

Digital Library

[16]

Lars Grunske, Leif Geiger, and Michael Lawley. A graphical specification of model transformations with triple graph grammars. In ECMDA-FA, volume 3748 of LNCS, pages 284–298. Springer, 2005.

Digital Library

[17]

Makoto Hamana. Initial algebra semantics for cyclic sharing tree structures. Logical Methods in Computer Science, 6(3), 2010.

[18]

Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, and Keisuke Nakano. Bidirectionalizing graph transformations. In ICFP, pages 205–216. ACM, 2010.

Digital Library

[19]

Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, Keisuke Nakano, and Isao Sasano. Marker-directed optimization of UnCAL graph transformations. In LOPSTR, volume 7225 of LNCS, pages 123–138. Springer, 2011.

Digital Library

[20]

Soichiro Hidaka, Kazuyuki Asada, Zhenjiang Hu, Hiroyuki Kato, and Keisuke Nakano. Structural recursion for querying ordered graphs. In ICFP, pages 305–318, 2013.

Digital Library

[21]

Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, and Keisuke Nakano. GRoundTram: An integrated framework for developing well-behaved bidirectional model transformations. Progress in Informatics, (10):131–148, 2013.

Digital Library

[22]

Kazuhiro Inaba, Soichiro Hidaka, Zhenjiang Hu, Hiroyuki Kato, and Keisuke Nakano. Graph-transformation verification using monadic second-order logic. In PPDP, pages 17–28. ACM, 2011.

Digital Library

[23]

Jean-Baptiste Jeannin, Dexter Kozen, and Alexandra Silva. Cocaml: Programming with coinductive types. http://www.cs.cornell. edu/~kozen/Papers/cocaml.pdf, 2013.

[24]

Thomas Johnsson. Efficient graph algorithms using lazy monolithic arrays. J. Funct. Program., 8(4):323–333, 1998.

Digital Library

[25]

Frédéric Jouault and Jean Bézivin. KM3: A DSL for metamodel specification. In FMOODS, volume 4037 of LNCS, pages 171–185. Springer, 2006.

Digital Library

[26]

David J. King and John Launchbury. Structuring depth-first search algorithms in haskell. In POPL, pages 344–354, 1995.

Digital Library

[27]

John Launchbury. A natural semantics for lazy evaluation. In POPL, pages 144–154, 1993.

Digital Library

[28]

Lambert G. L. T. Meertens. Paramorphisms. Formal Asp. Comput., 4 (5):413–424, 1992.

Digital Library

[29]

Erik Meijer, Maarten M. Fokkinga, and Ross Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In FPCA, volume 523 of LNCS, pages 124–144. Springer, 1991.

Digital Library

[30]

Robin Milner. Communicating and mobile systems - the Pi-calculus. Cambridge University Press, 1999. ISBN 978-0-521-65869-0.

Digital Library

[31]

Keiko Nakata and Masahito Hasegawa. Small-step and big-step semantics for call-by-need. J. Funct. Program., 19(6):699–722, 2009.

Digital Library

[32]

Susumu Nishimura and Atsushi Ohori. Parallel functional programming on recursively defined data via data-parallel recursion. J. Funct. Program., 9(4):427–462, 1999.

Digital Library

[33]

Susumu Nishimura, Atsushi Ohori, and Keishi Tajima. An equational object-oriented data model and its data-parallel query language. In OOPSLA, pages 1–17, 1996.

Digital Library

[34]

Atsushi Ohori and Isao Sasano. Lightweight fusion by fixed point promotion. In POPL, pages 143–154. ACM, 2007.

Digital Library

[35]

Yannis Papakonstantinou, Hector Garcia-Molina, and Jennifer Widom. Object exchange across heterogeneous information sources. In ICDE, pages 251–260. IEEE Computer Society, 1995.

Digital Library

[36]

Morten Heine Sørensen, Robert Glück, and Neil D. Jones. A positive supercompiler. J. Funct. Program., 6(6):811–838, 1996.

[37]

William W. Tait. Intensional interpretations of functionals of finite type I. Journal of Symbolic Logic, 32(2):198–212, June 1967.

[38]

Hiroshi Unno, Naoshi Tabuchi, and Naoki Kobayashi. Verification of tree-processing programs via higher-order model checking. In APLAS, volume 6461 of LNCS, pages 312–327. Springer, 2010.

Digital Library

[39]

Yijun Yu, Yu Lin, Zhenjiang Hu, Soichiro Hidaka, Hiroyuki Kato, and Lionel Montrieux. Maintaining invariant traceability through bidirectional transformations. In ICSE, pages 540–550, 2012.

Digital Library

Cited By

Mishina HUeda K(2024)Introducing Quantification into a Hierarchical Graph Rewriting LanguageLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_13(220-239)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71294-4_13
Sano JYamamoto NUeda K(2023)Type Checking Data Structures More Complex than TreesJournal of Information Processing10.2197/ipsjjip.31.11231(112-130)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.112
Sano JUeda K(2023)Implementing the $$\lambda _{GT}$$ Language: A Functional Language with Graphs as First-Class DataGraph Transformation10.1007/978-3-031-36709-0_14(263-277)Online publication date: 12-Jul-2023
https://doi.org/10.1007/978-3-031-36709-0_14
Show More Cited By

Index Terms

A functional reformulation of UnCAL graph-transformations: or, graph transformation as graph reduction

Recommendations

Precise Semantics of EMF Model Transformations by Graph Transformation
MoDELS '08: Proceedings of the 11th international conference on Model Driven Engineering Languages and Systems

Model transformation is one of the key activities in model-driven software development. An increasingly popular technology to define modeling languages is provided by the Eclipse Modeling Framework (EMF). Several EMF model transformation approaches have ...
Graph transformation with time
Special issue on the first international conference on graph transformation (ICGT 2002)

Following TER nets, an approach to the modeling of time in high-level Petri nets, we propose a model of time within (attributed) graph transformation systems where logical clocks are represented as distinguished node attributes. Corresponding axioms for ...
Formal foundation of consistent EMF model transformations by algebraic graph transformation

Model transformation is one of the key activities in model-driven software development. An increasingly popular technology to define modeling languages is provided by the Eclipse Modeling Framework (EMF). Several EMF model transformation approaches have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM 2017: Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

January 2017

124 pages

ISBN:9781450347211

DOI:10.1145/3018882

Program Chairs:
Ulrik Schultz
University of Southern Denmark
,
Jeremy Yallop
University of Cambridge, UK

Copyright © 2017 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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Japan Society for the Promotion of Science

Conference

POPL '17

Sponsor:

SIGPLAN

POPL '17: The 44th Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 16 - 17, 2017

Paris, France

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
127
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mishina HUeda K(2024)Introducing Quantification into a Hierarchical Graph Rewriting LanguageLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_13(220-239)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71294-4_13
Sano JYamamoto NUeda K(2023)Type Checking Data Structures More Complex than TreesJournal of Information Processing10.2197/ipsjjip.31.11231(112-130)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.112
Sano JUeda K(2023)Implementing the $$\lambda _{GT}$$ Language: A Functional Language with Graphs as First-Class DataGraph Transformation10.1007/978-3-031-36709-0_14(263-277)Online publication date: 12-Jul-2023
https://doi.org/10.1007/978-3-031-36709-0_14
Matsuda KWang M(2018)Embedding invertible languages with binders: a case of the FliPpr languageACM SIGPLAN Notices10.1145/3299711.324275853:7(158-171)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3299711.3242758
Matsuda KWang MWu N(2018)Embedding invertible languages with binders: a case of the FliPpr languageProceedings of the 11th ACM SIGPLAN International Symposium on Haskell10.1145/3242744.3242758(158-171)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3242744.3242758

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents