A functorial framework for constraint normal logic programming

Paqui Lucio

Fernando Orejas

Edelmira Pasarella

Elvira Pino

pp. 555-577

in: Kokichi Futatsugi, Jean-Pierre Jouannaud, José Meseguer (eds), Algebra, meaning, and computation, Berlin, Springer, 2006

Abstract

The semantic constructions and results for definite programs do not extend when dealing with negation. The main problem is related to a well-known problem in the area of algebraic specification: if we fix a constraint domain as a given model, its free extension by means of a set of Horn clauses defining a set of new predicates is semicomputable. However, if the language of the extension is richer than Horn clauses its free extension (if it exists) is not necessarily semicomputable. In this paper we present a framework that allows us to deal with these problems in a novel way. This framework is based on two main ideas: a reformulation of the notion of constraint domain and a functorial presentation of our semantics. In particular, the semantics of a logic program P is defined in terms of three functors: (({mathcal {OP}}_{P},{mathcal {ALG}}_{P},{mathcal {LOG}}_{P})) that apply to constraint domains and provide the operational, the least fixpoint and the logical semantics of P, respectively. The idea is that the application of ({mathcal {OP}}_{P}) to a specific constraint solver, provides the operational semantics of P that uses this solver; the application of ({mathcal {ALG}}_{P}) to a specific domain, provides the least fixpoint of P over this domain; and the application of ({mathcal {LOG}}_{P}) to a theory of constraints provides the logic theory associated to P. We prove that these three functors are in some sense equivalent.