Abstract
The implementation of functional logic languages by means of graph rewriting requires a special handling of collapsing rules. Recent advances about the notion of a needed step in some constructor systems offer a new approach to this problem. We present two results: a transformation of a certain class of constructor-based rewrite systems that eliminates collapsing rules, and a rewrite-like relation that takes advantage of the absence of collapsing rules. We formally state and prove the correctness of these results. When used together, these results simplify without any loss of efficiency an implementation of graph rewriting and consequently of functional logic computations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The word “collapse” is overloaded in graph parlance. In this context, its refers to a relation on graphs defined in the cited reference.
References
Alpuente, M., Falaschi, M., Vidal, G.: Partial evaluation of functional logic programs. ACM Trans. Program. Lang. Syst. 20(4), 768–844 (1998)
Antoy, S.: Definitional trees. In: Kirchner, H., Levi, G. (eds.) ALP 1992. LNCS, vol. 632. Springer, Heidelberg (1992)
Antoy, S.: Optimal non-deterministic functional logic computations. In: Hanus, M., Heering, J., Meinke, K. (eds.) ALP 1997 and HOA 1997. LNCS, vol. 1298. Springer, Heidelberg (1997). http://cs.pdx.edu/antoy/homepage/publications/alp97/full.pdf
Antoy, S.: Evaluation strategies for functional logic programming. J. Symb. Comput. 40(1), 875–903 (2005)
Antoy, S.: Programming with narrowing. J. Symb. Comput. 45(5), 501–522 (2010)
Antoy, S., Hanus, M.: Functional logic programming. Comm. ACM 53(4), 74–85 (2010)
Antoy, S., Jost, A.: Are needed redexes really needed? In: Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013, pp. 61–71. ACM, New York (2013)
Antoy, S., Peters, A.: Compiling a functional logic language: The Basic Scheme. In: Schrijvers, T., Thiemann, P. (eds.) FLOPS 2012. LNCS, vol. 7294, pp. 17–31. Springer, Heidelberg (2012)
Ariola, Z.M., Klop, J.W.: Equational term graph rewriting. Fundam. Inf. 26, 207–240 (1996)
Ariola, Z.M., Klop, J.W., Plump, D.: Bisimilarity in term graph rewriting. Inf. Comput. 156(12), 2–24 (2000)
Barendregt, H.P., van Eekelen, M.C.J.D., Glauert, J.R.W., Kennaway, J.R., Plasmeijer, M.J., Sleep, M.R.: Term graph rewriting. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds.) PARLE Parallel Architectures and Languages Europe. Lecture Notes in Computer Science, vol. 259, pp. 141–158. Springer, Heidelberg (1987)
Bezem, M., Klop, J.W., de Vrijer, R.: Term Rewriting Systems. Cambridge University Press, Cambridge (2003)
Clarke, T.J.W., Gladstone, P.J.S., MacLean, C.D., Norman, A.C.: Skim - the s, k, i reduction machine. In: Proceedings of the 1980 ACM Conference on LISP and Functional Programming, LFP 1980, pp. 128–135. ACM, New York (1980)
Echahed, R.: Inductively sequential term-graph rewrite systems. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214. Springer, Heidelberg (2008)
Echahed, R., Janodet, J.C.: On constructor-based graph rewriting systems. Technical Report 985-I, IMAG (1997). ftp://ftp.imag.fr/pub/labo-LEIBNIZ/OLD-archives/PMP/c-graph-rewriting.ps.gz
Fokkink, W., van de Pol, J.: Simulation as a correct transformation of rewrite systems. In: Privara, I., Ružicka, P. (eds.) MFCS 1997. LNCS, vol. 1295. Springer, Heidelberg (1997)
Glauert, J.R.W., Kennaway, R., Papadopoulos, G.A., Sleep, M.R.: Dactl: an experimental graph rewriting language. J. Prog. Lang. 5(1), 85–108 (1997)
Hanus, M.: The integration of functions into logic programming: from theory to practice. J. Log. Program. 19&20, 583–628 (1994)
Hanus, M.: Functional logic programming: from theory to curry. In: Voronkov, A., Weidenbach, C. (eds.) Programming Logics. LNCS, vol. 7797, pp. 123–168. Springer, Heidelberg (2013)
Hanus, M.: PAKCS 1.11.4: The Portland Aachen Kiel Curry System (2014). http://www.informatik.uni-kiel.de/pakcs
Huet, G., Lévy, J.-J.: Computations in orthogonal term rewriting systems, I. In: Lassez, J.-L., Plotkin, G. (eds.) Computational logic.: Essays Honour Alan Robinson, pp. 395–414. MIT Press, Cambridge (1991)
Kamperman, J.F.T., Walters, H.R.: Simulating TRSs by minimal TRSs a simple, efficient, and correct compilation technique. Technical report CS-R9605, CWI (1996)
Kennaway, J.R., Klop, J.K., Sleep, M.R., de Vries, F.J.: The adequacy of term graph rewriting for simulating term rewriting. In: Sleep, M.R., Plasmeijer, M.J., van Eekelen, M.C.J.D. (eds.) Term Graph Rewriting Theory and Practice, pp. 157–169. J. Wiley & Sons, Chichester (1993)
Landin, P.J.: The mechanical evaluation of expressions. Comput. J. 6(4), 308–320 (1964)
Plump, D.: Term graph rewriting. In: Kreowski, H.-J., Ehrig, H., Engels, G., Rozenberg, G., (eds.) Handbook of Graph Grammars, vol. 2, pp. 3–61. World Scientific (1999)
Plump, D.: Essentials of term graph rewriting. Electr. Notes Theor. Comput. Sci. 51, 277–289 (2001)
Sleep, M.R., Plasmeijer, M.J., van Eekelen, M.C.J.D. (eds.): Term Graph Rewriting Theory and Practice. J. Wiley & Sons, Chichester (1993)
Acknowledgments
This material is based upon work partially supported by the National Science Foundation under Grant No. CCF-1317249. Michael Hanus provided valuable comments on a preliminary version of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Antoy, S., Jost, A. (2015). Compiling Collapsing Rules in Certain Constructor Systems. In: Falaschi, M. (eds) Logic-Based Program Synthesis and Transformation. LOPSTR 2015. Lecture Notes in Computer Science(), vol 9527. Springer, Cham. https://doi.org/10.1007/978-3-319-27436-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-27436-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27435-5
Online ISBN: 978-3-319-27436-2
eBook Packages: Computer ScienceComputer Science (R0)