Abstract
In recent works, we have proposed a general framework for lazy functional logic programming with algebraic polymorphic types, i.e., parametric datatypes whose data constructors fulfill a given set of equational axioms. The aim of this paper is to investigate implementation techniques for an extended instance of this framework, namely, lazy functional logic programming with multisets and constraints. We consider a language (named Seta) which supports a polymorphic datatype Mset(α) along with specific constraints for multisets: strict equality (already present in the general framework), disequality, membership and non-membership. We describe a quite readable Prolog-based implementation which can be executed on top of any Prolog system that provides the ability to solve simple arithmetic constraints.
This research has been partially supported by the the Spanish National Project TIC95-0433-C03-01 “CPD” and the Esprit BRA Working Group EP-22457 “CCLII”.
Preview
Unable to display preview. Download preview PDF.
References
Antoy S., Echahed R., Hanus M.: A Needed Narrowing Strategy. In Proc. POPL'94, pp. 268–279, 1994.
Arenas-Sánchez P., Gil-Luezas A., López-Fraguas F.J.: Combining Lazy Narrowing with Disequality Constraints. In Proc. PLILP'94, Springer LNCS 844, pp. 385–399, 1994.
Arenas-Sánchez P., Rodríguez-Artalejo M.: A Semantic Framework for Functional Logic Programming with Algebraic Polymorphic Types. In Proc. TAPSOFT'97, Springer LNCS 1214, pp. 453–464, 1997.
Arenas-Sánchez P., Rodríguez-Artalejo M.: A Lazy Narrowing Calculus for Functional Logic Programming with Algebraic Polymorphic Types. In Proc. ILPS'97, the MIT Press, pp. 53–69, 1997.
Banâtre, J.P. and Le Métayer, D.: The Gamma model and its discipline of programming. Science of Computer Programming 15, pp. 55–77, 1990.
Caballero-Roldán R., Sánchez-Hernández J., López-Fraguas F.J: User's Manual for TOY. Tech. Rep. SIP 97/57, Universad Complutense de Madrid, 1997.
Cheong P.H., Fribourg, L.:Implementation of Narrowing: The Prolog-Based Approach. In Apt, de Bakker, Rutten (eds), Logic Programming languages: constraints, functions and objects, the MIT Press, pp. 1–20, 1993.
Damas L., Milner R.: Principal type schemes for functional programs. In Proc. POPL'82, pp. 207–212, 1982.
Dovier A., Rossi G.: Embedding Extensional Finite Sets in CLP. In Proc. ILPS'93, the MIT Press, pp. 540–556, 1993.
González-Moreno J.C., Hortalá-González T., López-Fraguas F.J, Rodríguez-Artalejo M.: A Rewriting Logic for Declarative Programming. In Proc. ESOP'96, Springer LNCS 1058, pp. 156–172, 1996. Full version available as TR DIA95/10, http://mozart.sip.ucm.es
Große G., Hölldobler J., Schneeberger J., Sigmund U., Thielscher M.: Equational Logic Programming, Actions, and Change. In Proc. ICLP'92, the MIT Press, pp. 177–191, 1992.
Hanus M.: The Integration of Functions into Logic Programming. A Survey. JLP (19:20). Special issue Ten Years of Logic Programming, pp. 583–628, 1994.
Holzbaur C.: OFAI clp(Q,R) Manual., Edition 1.3.3., Austrian Research Institute for Artificial Intelligence, Vienna, TR-95-09, 1995.
Jayaraman B., Plaisted D.A.: Programming with Equations, Subsets, and Relations. In Proc. ICLP'89, Vol. 2, the MIT Press, pp. 1051–1068, 1989.
Jouannaud J.P., Kirchner C.: Solving Equations in Abstract Algebras: A Rule-Based Survey of Unification. In J.L. Lassez and G. Plotking (eds.), Computational Logic, Essays in Honor of Alan Robinson. The MIT Press, pp. 257–321, 1991.
Legèard B.: Programmation en Logique avec Contraintes sur les Ensembles, Multiensembles et Séquences. Utilisation en prototypage de logiciels. PhD thesis, Université de Franche-Comté, 1994.
Loogen R., López-Fraguas F.J., Rodríguez-Artalejo M.: A Demand Driven Computation Strategy for Lazy Narrowing. In Proc. PLILP'93, Springer LNCS 714, pp 184–200, 1993.
Marriott, K.: Constraint multiset grammars. In Proc. IEEE Symposium on Visual Languages, IEEE Computer Society Press, pp. 118–125, 1994.
Martí-Oliet N., Meseguer J.: Action and Change in Rewriting Logic. In R. Pareschi & B. Fronhöfer (eds.). Theoretical Approaches to Dynamic Worlds in Computer Science and Artificial Intelligence. Cambridge M.P., 1995.
Reddy U.: Narrowing as the Operational Semantics of Functional Languages. In Proc. IEEE Symposium on Logic Programming, pp. 138–151, 1985.
Sicstus Prolog User's Manual. Programming Systems Group. Swedish Institute of Computer Science, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arenas-Sánchez, P., López-Fraguas, F.J., Rodríguez-Artalejo, M. (1998). Embedding multiset constraints into a lazy functional logic language. In: Palamidessi, C., Glaser, H., Meinke, K. (eds) Principles of Declarative Programming. ALP PLILP 1998 1998. Lecture Notes in Computer Science, vol 1490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056631
Download citation
DOI: https://doi.org/10.1007/BFb0056631
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65012-6
Online ISBN: 978-3-540-49766-0
eBook Packages: Springer Book Archive