=Paper=
{{Paper
|id=Vol-1485/paper5
|storemode=property
|title=Labelled Variables in Logic Programming: A First Prototype in tuProlog
|pdfUrl=https://ceur-ws.org/Vol-1485/paper5.pdf
|volume=Vol-1485
|dblpUrl=https://dblp.org/rec/conf/aiia/CalegariDO15
}}
==Labelled Variables in Logic Programming: A First Prototype in tuProlog==
https://ceur-ws.org/Vol-1485/paper5.pdf
Labelled Variables in Logic Programming:
A First Prototype in tuProlog
Roberta Calegari, Enrico Denti, and Andrea Omicini
Dipartimento di Informatica, Scienza e Ingegneria (DISI)
Alma Mater Studiorum–Università di Bologna, Italy
{roberta.calegari, enrico.denti, andrea.omicini}@unibo.it
Abstract. We present the first prototype of Labelled tuProlog, an ex-
tension of tuProlog exploiting labelled variables to enable a sort of multi-
paradigm / multi-language programming aimed at pervasive systems.
1 Context & Motivation
To face the challenges of today pervasive system, which are inherently complex,
distributed, situated [7] and intelligent, suitable models and technologies are re-
quired to effectively support distributed situated intelligence. To this end, in this
paper we investigate a logic programming (LP) extension based on labelled vari-
ables, and test it by means of a prototype rooted in the tuProlog system [3, 9],
called Labelled tuProlog. Our general aim is to define 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 la-
belled 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 defined by Gabbay [4], and
adopts the techniques introduced by Holzbaur [6] to develop a generalisation of
LP where labels are exploited to define computations in domain-specific 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 fit 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 Java-
based, tuProlog is an ideal candidate to support the above goal—distributing
situated intelligence while supporting labelled-variable-based computations.
2 Calegari, Denti & Omicini
While several works exists in this area – such as [8, 1] – they mostly focus onto
specific 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 fit several relevant context-specific systems, while seamlessly rooted
in the LP framework.
While in our first 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 defined 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 defined as a set of basic labels—i.e., li = {b1i , .., bni };
– a labelling association hv, li, associating label l to variable v: as a convenient
shortcut, such association can be written as v l ;
– a combining function fL , synthesising a new label from two given ones,
combining the two labels according to some scenario-specific criteria.
The unification 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 as-
sociated to the unified variables defined by the combining function fL . Figure
1 reports the unification rules for two generic terms T1 and T2 : to lighten the
notation, undefined elements in the tuple are omitted—i.e., labels or substitu-
tions 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
unification table is represented by labelled variables.
Fig. 1. Unification rules summary
Labelled Variables in Logic Programming: A First Prototype 3
While this choice clearly confines 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 prop-
erties via by suitable terms, so that they can influence 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, de-
signing a tuProlog extension that enables users to define their own labelled ap-
plications for their specific 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, defining first 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 exten-
sion – not a model extension –, thus leaving the model properties untouched.
3.2 The language extension
In order to enable users to define their labelled application, a suitable set of
Prolog predicates / Java methods is introduced to let users define: (i) the label/-
variable association; (ii) the function fL that specifies under which conditions
two labels unify in the selected domain, returning the new label associated with
the unified term; (iii) a shortcut for the pre-processing transformation, moving
label-interpreted terms to the label world, making them labels of undefined vari-
ables. 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 infix operator is also provided for the same purpose.
4 Calegari, Denti & Omicini
– 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 uni-
fied with the label Label in the label world, or fails otherwise. Only if the
check succeeds, the labelled variable is actually unified 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, figures show both the syntax (left),
and the prototype screenshot (right), which sometimes differs 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]. Unifi-
cation succeeds if two numeric intervals overlap, in which case the intersected
interval is the newly-computed label. Being specific of the application scenario,
the behaviour is defined by the fL function.
In the code in Figure 2 (top), labelled variable Y is unified with labelled
variable X: the operation succeeds (X/Y), with both variables receiving the new
label [2,3]. Conversely, in the subsequent case the unification fails, because the
intersected interval is empty.
In the third case, three aspects are worth highlighting. First of all, an explicit
unification 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 no-
tation Z°plus(X,Y) is not yet supported by the prototype, the unification with
a new (possibly anonymous) variable must be made explicit (Z= °plus(X,Y)).
Fig. 2. Interval CLP in Labelled tuProlog
? - Y°[1 ,3]= X°[2 ,5].
X / Y °[2 ,3]
yes .
? - Y°[1 ,3]= X°[4 ,5].
no .
? - X°[2 ,5] , Y°[1 ,3] , Z°plus (X , Y ).
Z °[3..8]
yes .
Labelled Variables in Logic Programming: A First Prototype 5
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 different
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 refined
by defining 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 defined as:
(
c2 if distance(c1 , c2 ) ≤ threshold ∈ [0..100]
fL (c1 , c2 ) =
{} if distance(c1 , c2 ) > threshold ∈ [0..100]
During the unification 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 unification process to fail.
6 Calegari, Denti & Omicini
Fig. 3. Colour Constraints in Labelled tuProlog
? - shirt ( Colour , Desc ).
Desc / pink_blouse ;
Desc / yellow_tshirt ;
Desc / army_tshirt ;
Desc / p e r i w i n k l e _ bl ou se ;
Desc / cream_blouse ;
no .
? -shirt ( Colour°rgb (255 ,239 ,213) , Desc ).
Desc / pink_blouse ;
Desc / yellow_tshirt ;
Desc / cream_blouse ;
no .
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 five available in un unconstrained
world (Figure 3, top), thus actually pruning the solution tree.
References
1. Alsinet, T., Chesñevar, C.I., Godo, L., Simari, G.R.: A logic programming frame-
work 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.) Con-
straint 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 extensi-
ble unification. 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 ar-
chitecture for situated MAS. Engineering Applications of Artificial 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)