Labelled Variables in Logic Programming: A First Prototype in tuProlog

Abstract

We present the rst prototype of Labelled tuProlog, an extension of tuProlog exploiting labelled variables to enable a sort of multiparadigm / multi-language programming aimed at pervasive systems.

Motivation

To face the challenges of today pervasive system, which are inherently complex, distributed, situated [ 7 ] and intelligent, suitable models and technologies are required to e ectively support distributed situated intelligence. To this end, in this paper we investigate a logic programming (LP) extension based on labelled variables, and test it by means of a prototype rooted in the tuProlog system [ 3, 9 ], called Labelled tuProlog. Our general aim is to de ne a unique blend of LP and labelled variables { a sort of multi-paradigm and multi-language programming framework for a distributed environment { where diverse computational models can be tailored to the local needs of situated systems by means of suitable labelled variables systems, and work together against the common LP background according to the original tuProlog aim [ 3 ].

Our work builds upon the general notion of label de ned by Gabbay [ 4 ], and adopts the techniques introduced by Holzbaur [ 6 ] to develop a generalisation of LP where labels are exploited to de ne computations in domain-speci c contexts, while retaining the conventional syntax of LP. More generally, our work moves from the observation that pervasiveness of today systems requires awareness of the environment as well as the ability of reacting to changes. This mandates for models promoting system intelligence, and for technologies making it possible to spread intelligence wherever needed. While logic-based approaches are natural candidates for intelligent systems, a pure LP approach seems not to t the needs of situated systems. Instead, a hybrid approach would make it possible to exploit LP for what it is most suited { symbolic computation {, while possibly delegating other aspects (such as situated computations) to other languages, or to other levels of computation. This is precisely where the notion of labelled variables can be of help: by enabling some parts of the computation to be expressed at a separate level, while retaining the general coherence of the LP approach.

Being light-weight, intentionally designed around a minimal core, and Javabased, tuProlog is an ideal candidate to support the above goal|distributing situated intelligence while supporting labelled-variable-based computations.

While several works exists in this area { such as [ 8, 1 ] { they mostly focus onto speci c scenarios and sorts of systems|e.g. modal logic, deductive systems, fuzzy systems, etc. Instead, our model aims at providing a general-purpose mechanism that could t several relevant context-speci c systems, while seamlessly rooted in the LP framework.

While in our rst prototype labels are only applied to variables { and not generally to formulas like in Gabbay [ 4 ] { the proposed notion of label is already general enough to capture Holzbaur's attribute variables [ 6 ], opening the way towards the expressiveness and the computational power of Constraint Logic Programming (CLP) [ 10, 5 ]|which is why the two case studies presented below assume CLP as the reference label domain. 2

The Labelled Variables Model in Logic Programming

A Labelled Variables Model for Logic Programming is de ned by: { a set of basic labels b1,. . . , bn, each with the form of a logic term, which represent entities in the domain of labels ; { a set of labels, each de ned as a set of basic labels|i.e., li = fb1i; ::; bnig; { a labelling association hv; li, associating label l to variable v: as a convenient shortcut, such association can be written as vl; { a combining function fL, synthesising a new label from two given ones, combining the two labels according to some scenario-speci c criteria. The uni cation of two labelled variables is represented by the extended tuple (true/false, , label) where true/false represents the existence of an answer, represents the most general substitution, and label represents the new label associated to the uni ed variables de ned by the combining function fL. Figure 1 reports the uni cation rules for two generic terms T1 and T2: to lighten the notation, unde ned elements in the tuple are omitted|i.e., labels or substitutions that do not exist/do not apply in a particular situation. Since, by design, only variables can be labelled here, the only case to be added to the standard uni cation table is represented by labelled variables.

While this choice clearly con nes the impact of labelling, keeping the label computational model well separate from the LP one, it is also too restrictive in practice: in fact, application scenarios often need to express some relevant properties via by suitable terms, so that they can in uence the label computation. For this purpose, we introduce the notion of label-interpreted terms, as a set of semantically-relevant terms in the domain of labels, along with a pre-processing phase, where each label-interpreted term is intercepted and replaced with an anonymous variable labelled with that term. In this way, any special term in the domain of label can be treated normally by the fL combining function, with no need to change the basic model above. 3

Prototype in tuProlog

In this Section we apply our model in the context of the tuProlog system, designing a tuProlog extension that enables users to de ne their own labelled applications for their speci c domains of interest. 3.1

System architecture

Since tuProlog is Java-based, a language extension can be provided both as a Prolog meta-level or library, or via suitable Java methods [ 3 ]. We support both ways, de ning rst a Prolog-language level to denote labelled variables, then two language extensions (Prolog-based and Java-based) to be used in alterative to denote the labelled application (Subsection 3.2).

Moreover, practical reasons suggest to avoid the proliferation of anonymous variables in the pre-processing phase, since they would pollute the name space and make the code less readable: for this reason, the prototype adopts a language shortcut to specify the label of a term directly, with no need to actually replace terms with unbound variables explicitly. However, this is just a linguistic extension { not a model extension {, thus leaving the model properties untouched. 3.2

The language extension

In order to enable users to de ne their labelled application, a suitable set of Prolog predicates / Java methods is introduced to let users de ne: (i) the label/variable association; (ii) the function fL that speci es under which conditions two labels unify in the selected domain, returning the new label associated with the uni ed term; (iii) a shortcut for the pre-processing transformation, moving label-interpreted terms to the label world, making them labels of unde ned variables. For the sake of brevity, we show here how to express the three entities just on the Prolog side only|the Java side being conceptually identical. { the label/variable association is expressed by the label associate(+Var, +Term ) predicate, which associates variable Var to label Term ; as a further convenience, the °/2 in x operator is also provided for the same purpose. { the function fL is expressed by the label generate(+Label1, +Label2, -Label3 ) predicate, which encodes how to build a new label from two given ones. { the pre-processing phase is embedded in the label interpret(+Label, +Term ) helper predicate, which succeeds if Term can potentially be unied with the label Label in the label world, or fails otherwise. Only if the check succeeds, the labelled variable is actually uni ed with the term. 4

Case studies

In the following we present two application examples: Interval CLP [ 2 ] and Dress Selection based on colour-match rules. There, gures show both the syntax (left), and the prototype screenshot (right), which sometimes di ers due to the current implementation shortcuts, as discussed below.

4.1 Interval CLP

In this application scenario, variables are labelled with their admissible numeric interval|that is, X°[A,B] means that X can span over the range [A::B]. Uni cation succeeds if two numeric intervals overlap, in which case the intersected interval is the newly-computed label. Being speci c of the application scenario, the behaviour is de ned by the fL function.

In the code in Figure 2 (top), labelled variable Y is uni ed with labelled variable X: the operation succeeds (X/Y), with both variables receiving the new label [ 2,3 ]. Conversely, in the subsequent case the uni cation fails, because the intersected interval is empty.

In the third case, three aspects are worth highlighting. First of all, an explicit uni cation is needed to link an unlabelled logic variable (X) to a labelled variable (X°[ 2,5 ]). The second aspect concerns the last term: because the shortcut notation Z°plus(X,Y) is not yet supported by the prototype, the uni cation with a new (possibly anonymous) variable must be made explicit (Z= °plus(X,Y)). This is why an auxiliary variable (T) is introduced|but Z could have been reused in alternative, as above. Finally, plus(X,Y) is an example of a label-interpreted term (whose meaning is obvious) requiring pre-processing. 4.2

Dress Selection

Here, the goal is to select from the wardrobe all the shirts that respect some given colour constraints: the domain of labels includes then shirts and their colours.

The predicate shirt(Colour,Description ) represents a shirt with of colour Colour , expressed in terms of its RGB composition { a triple like rgb(Red,Green,Blue ) {, synthetically described by Description . This means that in standard LP the knowledge representation would include facts like shirt(rgb(255,255,255), amy white blouse), and alike.

In the labelled context, however, the objective is to move relevant information to the domain of labels. Since labels can only be attached to variables, a di erent knowledge representation is adopted, where Colour is seen as a labelled variable, having the rgb/3 term above as its label. Accordingly, the wardrobe content representation is as follows: shirt(Argb(255,240,245), pink blouse). shirt(Brgb(255,222,173), yellow tshirt). shirt(Crgb(119,136,153), army tshirt). shirt(Drgb(188,143,143), periwinkle blouse).

shirt(Ergb(255,245,238), cream blouse).

To obtain all the shirts in the wardrobe, a query such as

?- shirt(Colour, Description) would obviously generate all the possible solutions in backtracking (Figure 3, top). By suitable exploiting labelled variables, however, the query can be re ned by de ning a target colour in the goal, and exploiting the combining function to get only the dresses whose dress colour is \similar enough" to the target.

To this end, two RGB colours c1 = rgb(r1; g1; b1) and c2 = rgb(r2; g2; b2) are considered similar { so, the corresponding labels unify { if their distance is below a given threshold. For the sake of concreteness, we assume the threshold to be 100, and the colour distance to be normalised and computed as a distance in a 3D Euclidean space.

The fL function, checking whether two given labels (c1=target colour and c2=dress colour ) are to be considered as similar, can be de ned as: fL(c1; c2) = (c2 if distance(c1; c2)

threshold 2 [0::100] fg if distance(c1; c2) > threshold 2 [0::100] During the uni cation of the two labelled variables whose label represent the target colour and the dress colour, the following steps are performed: if the dress colour is similar to the target colour, the returned label is dress colour | that is, the colour of the selected shirt; if, instead, the two colours are not similar, the empty label is returned, causing the uni cation process to fail.

Now let us look for all the shirts similar to the papaya colour : assuming a normalised similarity threshold of 30 (max is 100), the system returns just three solutions (Figure 3, bottom) instead of the ve available in un unconstrained world (Figure 3, top), thus actually pruning the solution tree.

References

1. Alsinet , T. , Chesn~evar, C.I. , Godo , L. , Simari , G.R.: A logic programming framework for possibilistic argumentation: Formalization and logical properties . Fuzzy Sets and Systems 159 ( 10 ), 1208 { 1228 ( 2008 )

2. Benhamou , F. : Interval constraint logic programming . In: Podelski, A . (ed.) Constraint Programming: Basics and Trends, LNCS , vol. 910 , pp. 1 { 21 . Springer ( 1995 )

3. Denti , E. , Omicini , A. , Ricci , A. : Multi-paradigm Java-Prolog integration in tuProlog . Science of Computer Programming 57 ( 2 ), 217 {250 (Aug 2005 )

4. Gabbay , D.M. : Labelled Deductive Systems , Volume 1 . Clarendon Press, Oxford Logic Guides 33 ( Sep 1996 )

5. Gavanelli , M. , Rossi , F. : Constraint logic programming . In: Dovier, A. , Pontelli , E. (eds.) A 25-year Perspective on Logic Programming, LNCS , vol. 6125 , pp. 64 { 86 . Springer ( 2010 )

6. Holzbaur , C. : Metastructures vs. attributed variables in the context of extensible uni cation . In: Bruynooghe, M. , Wirsing , M. (eds.) Programming Language Implementation and Logic Programming, LNCS , vol. 631 , pp. 260 { 268 . Springer ( 1992 )

7. Mariani , S. , Omicini , A. : Coordinating activities and change: An event-driven architecture for situated MAS . Engineering Applications of Arti cial Intelligence 41 , 298 {309 (May 2015 )

8. Russo , A. : Generalising propositional modal logic using labelled deductive systems . In: Baader, F. , Schulz , K.U. (eds.) Frontiers of Combining Systems, Applied Logic Series , vol. 3 , pp. 57 { 73 . Springer ( 1996 )

9. tuProlog: Home page . http://tuprolog.unibo.it/

10. Van Hentenryck, P.: Constraint logic programming . The Knowledge Engineering Review 6 , 151 {194 (Sep 1991 )