Abstract
We present the design of a compiler for a functional logic programming language and discuss the compiler’s implementation. The source program is abstracted by a constructor based graph rewriting system obtained from a functional logic program after syntax desugaring, lambda lifting and similar transformations provided by a compiler’s front-end. This system is non-deterministic and requires a specialized normalization strategy. The target program consists of 3 procedures that execute graph replacements originating from either rewrite or pull-tab steps. These procedures are deterministic and easy to encode in an ordinary programming language. We describe the generation of the 3 procedures, discuss the correctness of our approach, highlight some key elements of an implementation, and benchmark the performance of a proof-of-concept. Our compilation scheme is elegant and simple enough to be presented in one page.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Antoy, S.: Definitional Trees. In: Kirchner, H., Levi, G. (eds.) ALP 1992. LNCS, vol. 632, pp. 143–157. 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, pp. 16–30. Springer, Heidelberg (1997)
Antoy, S.: Constructor-based conditional narrowing. In: Proc. of the 3rd International Conference on Principles and Practice of Declarative Programming (PPDP 2001), Florence, Italy, pp. 199–206. ACM (September 2001)
Antoy, S.: Evaluation strategies for functional logic programming. Journal of Symbolic Computation 40(1), 875–903 (2005)
Antoy, S.: Programming with narrowing. Journal of Symbolic Computation 45(5), 501–522 (2010)
Antoy, S.: On the correctness of pull-tabbing. TPLP 11(4-5), 713–730 (2011)
Antoy, S., Hanus, M.: Overlapping Rules and Logic Variables in Functional Logic Programs. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 87–101. Springer, Heidelberg (2006)
Antoy, S., Hanus, M.: Set functions for functional logic programming. In: Proceedings of the 11th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP 2009), Lisbon, Portugal, pp. 73–82 (September 2009)
Antoy, S., Hanus, M.: Functional logic programming. Comm. of the ACM 53(4), 74–85 (2010)
Antoy, S., Hanus, M., Liu, J., Tolmach, A.: A Virtual Machine for Functional Logic Computations. In: Grelck, C., Huch, F., Michaelson, G.J., Trinder, P. (eds.) IFL 2004. LNCS, vol. 3474, pp. 108–125. Springer, Heidelberg (2005)
Brassel, B.: Implementing Functional Logic Programs by Translation into Purely Functional Programs. PhD thesis, Christian-Albrechts-Universität zu Kiel (2011)
Braßel, B., Fischer, S., Huch, F.: Declaring Numbers. Electron. Notes Theor. Comput. Sci. 216, 111–124 (2008)
Braßel, B., Hanus, M., Peemöller, B., Reck, F.: KiCS2: A New Compiler from Curry to Haskell. In: Kuchen, H. (ed.) WFLP 2011. LNCS, vol. 6816, pp. 1–18. Springer, Heidelberg (2011)
Braßel, B., Huch, F.: On a Tighter Integration of Functional and Logic Programming. In: Shao, Z. (ed.) APLAS 2007. LNCS, vol. 4807, pp. 122–138. Springer, Heidelberg (2007)
Braßel, B., Huch, F.: The Kiel Curry System KiCS. In: Seipel, D., Hanus, M., Wolf, A. (eds.) INAP/WLP 2007. LNCS, vol. 5437, pp. 195–205. Springer, Heidelberg (2009)
Caballero, R., Sánchez, J. (eds.): TOY: A Multiparadigm Declarative Language, version 2.3.1 (2007), http://toy.sourceforge.net
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
Echahed, R., Janodet, J.C.: Admissible graph rewriting and narrowing. In: Proceedings of the Joint International Conference and Symposium on Logic Programming, Manchester, pp. 325–340. MIT Press (June 1998)
Fischer, S., Kiselyov, O., Chieh Shan, C.: Purely functional lazy nondeterministic programming. J. Funct. Program. 21(4-5), 413–465 (2011)
Fokkink, W., van de Pol, J.: Simulation as a Correct Transformation of Rewrite Systems. In: Privara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 249–258. Springer, Heidelberg (1997)
González Moreno, J.C., López Fraguas, F.J., Hortalá González, M.T., Rodríguez Artalejo, M.: An approach to declarative programming based on a rewriting logic. The Journal of Logic Programming 40, 47–87 (1999)
Hanus, M.: The integration of functions into logic programming: From theory to practice. Journal of Logic Programming 19&20, 583–628 (1994)
Hanus, M.: Efficient Translation of Lazy Functional Logic Programs into Prolog. In: Proietti, M. (ed.) LOPSTR 1995. LNCS, vol. 1048, pp. 252–266. Springer, Heidelberg (1996)
Hanus, M.: Functional logic programming: From theory to Curry. Technical report, Christian-Albrechts-Universität Kiel (2005), http://www.informatik.uni-kiel.de/~mh/publications/reports/
Hanus, M. (ed.): Curry: An Integrated Functional Logic Language, Vers. 0.8.2 (2006), http://www-ps.informatik.uni-kiel.de/currywiki/
Hanus, M.: Multi-paradigm Declarative Languages. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 45–75. Springer, Heidelberg (2007)
Hanus, M.: Flatcurry: An intermediate representation for Curry programs (2008), http://www.informatik.uni-kiel.de/~curry/flat/
Hanus, M. (ed.): PAKCS 1.9.1: The Portland Aachen Kiel Curry System (2008), http://www.informatik.uni-kiel.de/~pakcs
Hanus, M.: KiCS2 benchmarks (2011), http://www-ps.informatik.uni-kiel.de/kics2/benchmarks/
Hanus, M., Sadre, R.: An abstract machine for Curry and its concurrent implementation in Java. Journal of Functional and Logic Programming 1999(Special Issue 1), 1–45 (1999)
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)
López-Fraguas, F.J., de Dios-Castro, J.: Extra variables can be eliminated from functional logic programs. Electron. Notes Theor. Comput. Sci. 188, 3–19 (2007)
Lux, W.: An abstract machine for the efficient implementation of Curry. In: Kuchen, H. (ed.) Workshop on Functional and Logic Programming, Arbeitsbericht No. 63. Institut für Wirtschaftsinformatik, Universität Münster (1998)
Ocaml (2004), http://caml.inria.fr/ocaml/index.en.html
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)
Warren, D.H.D.: Higher-order extensions to PROLOG: are they needed? Machine Intelligence 10, 441–454 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Antoy, S., Peters, A. (2012). Compiling a Functional Logic Language: The Basic Scheme . In: Schrijvers, T., Thiemann, P. (eds) Functional and Logic Programming. FLOPS 2012. Lecture Notes in Computer Science, vol 7294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29822-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-29822-6_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29821-9
Online ISBN: 978-3-642-29822-6
eBook Packages: Computer ScienceComputer Science (R0)