Article

Compiling a functional logic language: the basic scheme

Authors:

Arthur PetersAuthors Info & Claims

FLOPS'12: Proceedings of the 11th international conference on Functional and Logic Programming

Pages 17 - 31

https://doi.org/10.1007/978-3-642-29822-6_5

Published: 23 May 2012 Publication History

Abstract

We present the design of a compiler for a functional logic programming language and discuss the compiler's implementation. The <em>source</em> 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 <em>target</em> 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.

References

[1]

Antoy, S.: Definitional Trees. In: Kirchner, H., Levi, G. (eds.) ALP 1992. LNCS, vol. 632, pp. 143-157. Springer, Heidelberg (1992)

Digital Library

[2]

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)

Digital Library

[3]

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)

Digital Library

[4]

Antoy, S.: Evaluation strategies for functional logic programming. Journal of Symbolic Computation 40(1), 875.903 (2005)

Digital Library

[5]

Antoy, S.: Programming with narrowing. Journal of Symbolic Computation 45(5), 501.522 (2010)

Digital Library

[6]

Antoy, S.: On the correctness of pull-tabbing. TPLP 11(4-5), 713.730 (2011)

[7]

Antoy, S., Hanus, M.: Overlapping Rules and Logic Variables in Functional Logic Programs. In: Etalle, S., Truszczynski, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 87.101. Springer, Heidelberg (2006)

Digital Library

[8]

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)

Digital Library

[9]

Antoy, S., Hanus, M.: Functional logic programming. Comm. of the ACM 53(4), 74.85 (2010)

Digital Library

[10]

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)

Digital Library

[11]

Brassel, B.: Implementing Functional Logic Programs by Translation into Purely Functional Programs. PhD thesis, Christian-Albrechts-Universität zu Kiel (2011)

[12]

Braßel, B., Fischer, S., Huch, F.: Declaring Numbers. Electron. Notes Theor. Comput. Sci. 216, 111.124 (2008)

Digital Library

[13]

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)

Digital Library

[14]

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)

Digital Library

[15]

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)

[16]

Caballero, R., Sánchez, J. (eds.): TOY: A Multiparadigm Declarative Language, version 2.3.1 (2007), http://toy.sourceforge.net

[17]

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

[18]

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)

Digital Library

[19]

Fischer, S., Kiselyov, O., Chieh Shan, C.: Purely functional lazy nondeterministic programming. J. Funct. Program. 21(4-5), 413.465 (2011)

Digital Library

[20]

Fokkink, W., van de Pol, J.: Simulation as a Correct Transformation of Rewrite Systems. In: Privara, I., Ru.zi.cka, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 249.258. Springer, Heidelberg (1997)

Digital Library

[21]

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)

[22]

Hanus, M.: The integration of functions into logic programming: From theory to practice. Journal of Logic Programming 19&20, 583.628 (1994)

[23]

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)

Digital Library

[24]

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/

[25]

Hanus, M. (ed.): Curry: An Integrated Functional Logic Language, Vers. 0.8.2 (2006), http://www-ps.informatik.uni-kiel.de/currywiki/

[26]

Hanus, M.: Multi-paradigm Declarative Languages. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 45-75. Springer, Heidelberg (2007)

Digital Library

[27]

Hanus, M.: Flatcurry: An intermediate representation for Curry programs (2008), http://www.informatik.uni-kiel.de/~curry/flat/

[28]

Hanus, M. (ed.): PAKCS 1.9.1: The Portland Aachen Kiel Curry System (2008), http://www.informatik.uni-kiel.de/~pakcs

[29]

Hanus, M.: KiCS2 benchmarks (2011), http://www-ps.informatik.uni-kiel.de/kics2/benchmarks/

[30]

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)

[31]

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)

Digital Library

[32]

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)

Digital Library

[33]

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)

Digital Library

[34]

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)

[35]

Ocaml (2004), http://caml.inria.fr/ocaml/index.en.html

[36]

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)

Digital Library

[37]

Warren, D. H. D.: Higher-order extensions to PROLOG: are they needed? Machine Intelligence 10, 441-454 (1982)

Cited By

Antoy SJost A(2015)Compiling Collapsing Rules in Certain Constructor SystemsRevised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 952710.1007/978-3-319-27436-2_4(57-72)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27436-2_4
Antoy SJost APeña RSchrijvers T(2013)Are needed redexes really needed?Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming10.1145/2505879.2505881(61-71)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1145/2505879.2505881

Compiling a functional logic language: the basic scheme
1. Theory of computation
  1. Semantics and reasoning

Recommendations

Compiling a functional language
LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming

This paper summarizes my experience in implementing a compiler for a functional language. The language is ML(1) [Milner 84] and the compiler was first implemented in 1980 as a personal project when I was a postgraduate student at the University of ...
Compiling a reflective language using MetaOCaml
GPCE 2014: Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences

A reflective language makes the language semantics open to user programs and allows them to access, extend, and modify it from within the same language framework. Because of its high flexibility and expressiveness, it can be an ideal platform for ...
Compiling the graphical functional language PROGRAPH
SIGSMALL '85: Proceedings of the 1985 ACM SIGSMALL symposium on Small systems

The imperative style of standard programming languages is not appropriate for many modern computing tasks involving manipulation of symbols and complex structures. These applications require higher level declarative languages such as Lisp and Prolog. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

FLOPS'12: Proceedings of the 11th international conference on Functional and Logic Programming

May 2012

331 pages

ISBN:9783642298219

Editors:
Tom Schrijvers
Dept. of Applied Mathematics and Computer Science, Ghent University, Krijgslaan 281 S9 WE02, Ghent, Belgium
,
Peter Thiemann
Dept. of Computer Science, University of Freiburg, Georges-Köhler-Allee 106, Freiburg, Germany

Sponsors

Kobe University: Kobe University
JSSST: Japan Society for Software Science & Technology

In-Cooperation

AAFS: Asian Association for Foundation of Software
ALP: Assoc for Logic Programming
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 May 2012

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Antoy SJost A(2015)Compiling Collapsing Rules in Certain Constructor SystemsRevised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 952710.1007/978-3-319-27436-2_4(57-72)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27436-2_4
Antoy SJost APeña RSchrijvers T(2013)Are needed redexes really needed?Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming10.1145/2505879.2505881(61-71)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1145/2505879.2505881

View Options

View options

Media

Figures

Other

Tables

View Table of Contents