Abstract
We present a high-level transformation scheme to translate lazy functional logic programs into pure Haskell programs. This transformation is based on a recent proposal to efficiently implement lazy non-deterministic computations in Haskell in a monadic style. We build on this work and define a systematic method to transform lazy functional logic programs into monadic programs with explicit sharing. This results in a transformation scheme which produces high-level and flexible target code. For instance, the target code is parametric w.r.t. the concrete evaluation monad. Thus, different monad instances could, for example, define different search strategies (e.g., depth-first, breadth-first, parallel). We formally describe the basic compilation scheme and some useful extensions.
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
Preview
Unable to display preview. Download preview PDF.
References
Antoy, S.: Constructor-based conditional narrowing. In: Proc. of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001), pp. 199–206. ACM Press, New York (2001)
Antoy, S.: Evaluation strategies for functional logic programming. Journal of Symbolic Computation 40(1), 875–903 (2005)
Antoy, S., Braßel, B.: Computing with subspaces. In: Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP 2007), pp. 121–130. ACM Press, New York (2007)
Antoy, S., Hanus, M.: Compiling multi-paradigm declarative programs into Prolog. In: Kirchner, H. (ed.) FroCos 2000. LNCS, vol. 1794, pp. 171–185. Springer, Heidelberg (2000)
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), pp. 73–82. ACM Press, New York (2009)
Antoy, S., Hanus, M.: Functional logic programming. Communications 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)
Braßel, B., Hanus, M., Huch, F.: Encapsulating non-determinism in functional logic computations. Journal of Functional and Logic Programming 2004(6) (2004)
Braßel, B., Huch, F.: The KIEL CURRY system KiCS. In: Seipel, D., Hanus, M., Wolf, A. (eds.) INAP 2007. LNCS, vol. 5437, pp. 195–205. Springer, Heidelberg (2009)
Fischer, S., Kiselyov, O., Shan, C.: Purely functional lazy non-deterministic programming. In: Proceeding of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009), pp. 11–22. ACM, New York (2009)
González-Moreno, J.C., Hortalá-González, M.T., López-Fraguas, F.J., Rodríguez-Artalejo, M.: An approach to declarative programming based on a rewriting logic. Journal of Logic Programming 40, 47–87 (1999)
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., Antoy, S., Braßel, B., Engelke, M., Höppner, K., Koj, J., Niederau, P., Sadre, R., Steiner, F.: PAKCS: The Portland Aachen Kiel Curry System (2010), http://www.informatik.uni-kiel.de/~pakcs/
Hanus, M., Prehofer, C.: Higher-order narrowing with definitional trees. Journal of Functional Programming 9(1), 33–75 (1999)
Hanus, M. (ed.): Curry: An integrated functional logic language, vers. 0.8.2 (2006), http://www.curry-language.org
Hussmann, H.: Nondeterministic algebraic specifications and nonconfluent term rewriting. Journal of Logic Programming 12, 237–255 (1992)
López-Fraguas, F.J., Sánchez-Hernández, J.: TOY: A multiparadigm declarative system. In: Narendran, P., Rusinowitch, M. (eds.) RTA 1999. LNCS, vol. 1631, pp. 244–247. Springer, Heidelberg (1999)
López-Fraguas, F.J., Rodríguez-Hortalá, J., Sánchez-Hernández, J.: Bundles pack tighter than lists. In: Draft Proc. of Trends in Functional Programming, pp. XXIV–1–XXIV–16 (2007)
López-Fraguas, F.J., Rodríguez-Hortalá, J., Sánchez-Hernández, J.: A simple rewrite notion for call-time choice semantics. In: Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP 2007), pp. 197–208. ACM Press, New York (2007)
López-Fraguas, F.J., Rodríguez-Hortalá, J., Sánchez-Hernández, J.: A fully abstract semantics for constructor systems. In: Treinen, R. (ed.) RTA 2009. LNCS, vol. 5595, pp. 320–334. Springer, Heidelberg (2009)
Lux, W., Kuchen, H.: An efficient abstract machine for Curry. In: Beiersdörfer, K., Engels, G., Schäfer, W. (eds.) Informatik 1999 — Annual meeting of the German Computer Science Society (GI), pp. 390–399. Springer, Heidelberg (1999)
Peyton Jones, S. (ed.): Haskell 98 Language and Libraries—The Revised Report. Cambridge University Press, Cambridge (2003)
Wadler, P.: How to replace failure by a list of successes. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 113–128. Springer, Heidelberg (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Braßel, B., Fischer, S., Hanus, M., Reck, F. (2011). Transforming Functional Logic Programs into Monadic Functional Programs. In: Mariño, J. (eds) Functional and Constraint Logic Programming. WFLP 2010. Lecture Notes in Computer Science, vol 6559. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20775-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-20775-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20774-7
Online ISBN: 978-3-642-20775-4
eBook Packages: Computer ScienceComputer Science (R0)