P. Arenas Sánchez, F.J. López Fraguas, M. Rodríguez Artalejo
"Embedding Multiset Constraints into a Lazy Functional Logic
Language"
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
$\it Mset}(\alpha)$ along with specific constraints for multisets:
strict equality (already present in the general framework), disequality,
membership and non-membership. $\seta$ turns out to be very expressive for
any kind of problems related to the general idea of multiset rewriting.
SETA's implementation requires a non-trivial combination of lazy
narrowing and unification modulo the equational axioms for multisets.
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.
References
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., Hortalá-González T.,
López-Fraguas F.J., Ullán E. Functional Logic Programming
with Real Numbers. Multi-Paradigm Logic Programming.
Post-Conference Workshops of the Joint Int. Conf. and Symp. on Logic
Programming. Report no. 96-28, pp. 45-58, University of Berlin, 1996.
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.
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.