Logic Programming in Space-Time: The Case of Situatedness in LPaaS Roberta Calegari∗ , Giovanni Ciatto∗ , Stefano Mariani† , Enrico Denti∗ , Andrea Omicini∗ ∗ Department of Computer Science and Engineering (DISI) A LMA M ATER S TUDIORUM–Università di Bologna, Italy Email: roberta.calegari@unibo.it, giovanni.ciatto@unibo.it, enrico.denti@unibo.it, andrea.omicini@unibo.it † Department of Sciences and Methods for Engineering (DISMI) Università degli Studi di Modena e Reggio Emilia, Italy Email: stefano.mariani@unimore.it Abstract—Situatedness is a fundamental requirement for to- However, technology advancements and the emergence of day’s complex software systems, as well as for the computational the Internet of Intelligent Things context [11], [12] are dras- models and programming languages used to build them. Spatial tically changing such a scenario, eventually enabling LP to and temporal situatedness, in particular, are essential features for AI, enabling actors of the system to take autonomous decisions unveil its full potential in real-world applications. Along this contextual to the space-time they live in. To support spatio- line, in this paper we extend the Logic Programming as a temporal awareness in distributed pervasive systems, we adopt Service (LPaaS) approach, intended as the natural evolution of the standpoint of Logic Programming (LP) by focussing on the distributed LP in pervasive systems, towards spatio-temporal Logic Programming as a Service (LPaaS) approach, promoting awareness, to promote the distribution of situated intelligence. the distribution of situated intelligence. Accordingly, we provide an interpretation about what it means to make LP span across Accordingly, in Section II we introduce LPaaS focussing space and time, then we extend the LPaaS model and architecture on the most relevant features for context-aware domains, then towards spatio-temporal situatedness, by identifying a set of (Section III) we discuss spatio-temporal issues for LP and suitably-expressive spatio-temporal primitives. LPaaS, and (Section IV) we identify a suitably-expressive set Index Terms—LPaaS, Situatedness, Logic Programming, SOA, of spatio-temporal primitives. A case study is presented in space-time programming Section V, and conclusions are drawn in Section VI. I. I NTRODUCTION II. BACKGROUND : LPAA S KEY FEATURES The widespread diffusion of mobile and wearable technolo- LPaaS [13], [14] is the evolution of LP in parallel, concur- gies, along with the pervasiveness of the Internet, opens the rent, distributed scenarios according to the Service-Oriented way towards a wide range of distributed, location- and context- Architecture (SOA) paradigm [15], concretising the micro- aware applications, where both the system’s goals and its intelligence vision in terms of micro-services. computational behaviour depend on the users’ position in the This perspective emphasises the role of situatedness, already space [1], [2], [3], [4], and on time passing by. brought along by distribution in itself. The resolution process There, one of the main technical challenges is to design and [16] remains a staple in LPaaS, yet it is re-contextualised develop context-aware services that anticipate users’ situation, according to the situated nature of the specific LP service. proactively serve their information needs, and personalise Thus, given the precise spatial, temporal, and general con- suggestions, starting from the agreement that most cognitive text within which the service is operating when the resolution processes are contextual in that they depend on the environ- process starts, the process follows the usual rules of resolution. ment inside which they are carried on [5], [6]. Contextual in- At the same time, this context is exactly what can make res- formation such as location, time, activity, physical conditions, olution come up with different solutions to the same queries: and social interaction, in fact, is acknowledged to generate indeed, the situatedness of the resolution process (Section IV) trustworthy and accurate reasoning and recommendations [7]. is the first novelty of the LPaaS approach. Logic Programming (LP) can play a key role by enabling the The second novelty concerns interaction with the clients widespread diffusion of distributed intelligence. Nevertheless, of the LP service. In classical LP, interactions are necessarily although LP languages and technologies represent a natural stateful: users set the logic theory, define the goal, then ask candidate for injecting intelligence within computational sys- for solutions, iteratively. This implies that the LP engine is tems [8], and despite the many practical applications developed expected i) to store the logic theory, ii) to memorise the goal over the years – see [9], [10] for a survey –, the adoption of under demonstration, and iii) to track how many solutions have LP in pervasive contexts has been historically hindered by been already provided: altogether, this information composes technological obstacles like efficiency and integration issues, the state of the LP engine. as well as by some cultural resistance towards LP-based In LPaaS, instead, interactions are mainly stateless: coher- approaches outside the academy. ently with the SOA approach, the LP service instance that 63 serves each request may be different each time, e.g. due to the In principle, the resolution process could also span and redundancy of the distributed software components to improve move over time and space. Leaving the full discussion to availability and reliability of the LP service. Each client query Subsection III-B and III-C, intuitively, moving back in time (interaction) should then be self-contained, so that it does not means to ask the LPaaS service the solution of a given goal matter which specific service instance actually responds. at a certain moment in the past, whereas moving forward in Another key feature is the possibility of choosing between time either means to ask to “predict” the solutions that could dynamic or static knowledge bases (KBs): from the client become available in the future, or to wait until they become viewpoint, a static KB is immutable, while a dynamic KB can provable. Analogously, moving in space in either direction evolve during the service lifetime due to assertion/retraction means to consider a different region of validity associated to of clauses. This implies that clauses in a dynamic KB have a the logic theory, providing solutions that are situated (hold lifetime, representing mutable knowledge about the world. true) in a given region of space—and only provable therein. The last key novelty regards the software engineering pro- cess: since LPaaS embraces the SOA perspective and its most B. The Temporal Dimension recent evolutions, such as the micro-services paradigm and the Being situated in time means that the temporal context when Web of Things perspective, LPaaS is both built as a micro- the LP service is executed may affect its properties, compu- service and exploits micro-services for its inner architecture. tations, and interactions with clients. Since reconstructing a LPaaS functionalities are made available as a standardised global notion of time in pervasive systems is either unfeasible RESTful web service, exploiting technologies such as JSON, or non-trivial, each LP service should be supposed to operate JWT, and Docker for the sake of interoperability, and a fully on its own local time—that is, computing deadlines, leasing automated continuous integration/delivery pipeline for an agile times, and the like according to its local perception of time. development and deployment (details in [17]). Also, it is worth emphasising that the notion of time assumed in LPaaS is not bound to a specific definition of time, but III. LP IN S PACE -T IME : THE LPAA S P ERSPECTIVE is related to each step of the computation in the resolution A. LP in Space-Time process—which may be unrelated to physical time. Time can affects both computations, leading to time- Making LP aware of space-time essentially means making dependant computations, and the temporal validity of logic the resolution process sensitive i) to the passing of time, and theories, thus of all the individual facts and clauses therein, ii) to the topology of space—that is, aware of the existence of whose validity can be collectively bound to a given time different points in time/space and of the possibility of moving horizon—i.e., being true up to a certain instant in time, between them. Fig. 1 illustrates this idea by representing LP and no longer since then. Computation requests may then approaches in a bidimensional time/space chart. arbitrarily restrict the temporal scope of the expected solutions, In classical LP, a goal is basically proven against a logic specifying the temporal bounds of the logical facts and clauses theory that is considered true independently of space and to consider as valid while proving a goal. time—that is, regardless of when and where the resolution Subsection IV-A discusses the specific LPaaS API dedicated process takes place. LPaaS promotes a broader vision: the to managing temporal aspects, as reported by TABLE I. resolution process becomes sensitive to the time and space dimension. Hence, a goal is demonstrated against a logic C. The Spatial Dimension theory that is considered true within a (possibly open) interval Being situated in space means that the spatial context where of time, and within a region of space. the LP service is executing may affect its properties, compu- tations, and the way it interacts with clients. Intentionally, we do not focus on the structure of space, such as whether there is a global coordinate system shared by all LPaaS instances, or each LPaaS server has its own local one, and which metrics of distance to adopt, etc.: it only matters that the LPaaS service has a notion of locality which situates it in space. The region of validity is then to be considered local to the service, as represented by the server container. For instance, in the following we consider the notion of neighbourhood – intended as the collection of the LPaaS services sufficiently close to each other – without specifying how such a notion is technically computed and maintained. Analogously to Subsection III-B, the notion of space and its properties, such as topology, may be exploited to design space- dependant computations, and affect LPaaS properties such as logic theories, individual facts, and clauses—whose validity Fig. 1. LPaaS in the space-time. can be collectively bound to a given region in space. Requests 64 may then arbitrarily restrict the spatial scope of the expected Here, w.r.t. Fig. 1, we actually are moving the dot along solutions—that is, explicitly specify the spatial bounds to be the time dimension, affecting the resolution process, thus its considered as valid while proving a given goal. outcomes. Furthermore, the query to the server could specify In this perspective, LPaaS is capable of interacting with not a timestamp, that is an instant in time, but rather a temporal its surroundings to contact the other LPaaS services in the interval. With respect to Fig. 1, each instant in the interval neighbourhood, that can represent the same knowledge but would be considered by the resolution process, adding the with a different local truth—depending on their location. corresponding solutions to the solution list. This possibility Subsection IV-B discusses the specific LPaaS API dedicated is left as a future work and not included in the current version to managing these aspects, as reported by TABLE I. of LPaaS API—TABLE I. IV. S PATIO -T EMPORAL S ITUATEDNESS IN LPAA S B. The Spatial Dimension LPaaS provides an application-level API to exploit the built- Yet again, some of the issues described in Subsection III-C in situatedness of both the service and clients as discussed in affect the resolution process, while some other pertain only to Section III, enabled and supported by the service container. the way clients interact with the service. Client-Server Interaction: Since the service container is A. The Temporal Dimension physically located somewhere, the LPaaS server inherently has Of all the issues described in Subsection III-B, some affect a notion of its own location: so, specifying its surroundings the resolution process, other pertain only to the way clients amounts basically at specifying the “width” of such a region, interact with the service. according to some (custom) metric. Alternatively, we might Client-Server Interaction: Temporal situatedness is basi- be interested in specifying a region from another, different cally implied by distribution per se: moving information in position—i.e., the client’s own one. a network takes time, thus aspects such as expiration of The key point is that LPaaS can explore its surroundings requests, obsolescence of logic theories, and timeliness of to discover other LPaaS instances, representing different lo- replies need to be taken into account when designing a dis- cal knowledge, and forward to them the query looking for tributed LP service. To this end, LPaaS introduces a family of expanding the solutions it found by itself. The primitive solve predicates with a specific within(Time) argument solveNeighborhood/2: (intended as server-side local time) for the resolution, thus solveNeighborhood(-SList, region(?Pos, +Distance)) preventing the server from being indefinitely busy: if the associates the inference process to a region centred in Pos – resolution process does not complete within the given time, if omitted, the server position is considered – and distance the request is cancelled, and a failure response is returned to specified by Distance; the resulting list of solutions is the client. returned in SList. The client could also ask for a stream of solutions, as it Intentionally, the precise syntax of the region terms (Pos is likely the case in IoT scenarios when exploiting sensors or and Distance) is left unspecified, so that it can be general monitoring processes: this is why solve can also take an enough to cover the widest range of possible interpretations: every(Time) argument, meaning that each new solution Distance, in particular, could be a physical distance in should be returned not faster than every Time milliseconds. meters, leading to a circular region, or the maximum number Note that, w.r.t. Fig. 1, here we are not “moving the dot” of hops in a network, leading to a region of virtually any along the time dimension: rather, we are simply letting clients shape, etc. Indeed, the specific language to be used for the configure their interactions with the LPaaS service along the space description is an open research aspect, hence outside temporal dimension—namely, when they want a solution. the scope of this paper. Resolution process: To capture the time-bounded validity of Similarly to the time case, the client could also open a theories, each axiom in the LPaaS knowledge base is decorated stream of solutions across space: this could be interpreted, for with a time interval. When a new resolution process starts, the instance, as widening/narrowing the region to be considered logic theory used for the resolution includes only the axioms at each cycle of the resolution process (Fig. 2). Syntax valid at the Timestamp provided in the client query. solveNeighborhood(-SList,region(?Pos,+Distance,+Span)) This timestamp can span both in the past and in the future. The first means to ask for solutions that were valid in the fits the purpose: the extra Span argument specifies how much past, while the second opens intriguing possibilities about to widen/narrow the considered range at each cycle. As above, “reasoning on the future”. An appealing perspective could the precise syntax of Span is left intentionally unspecified. be to postpone the resolution process until future information Last but not least, in dynamic KBs time and space could inter- becomes available, or to ask for some sort of prediction to vene together, leading to a family of solveNeighborhood some intelligent “oracle”. This may imply the ability to track primitives (TABLE I). the history of modifications to the logic theory, in order to Along this line, fascinating possibilities come from con- guess its future state. This fascinating perspective would make sidering moving regions as streams of solutions bound to the LPaaS service ultimately behave as a prediction model spatial constraints, possibly evolving over time. This implies trained on the evolution of the logic theory. that time and space are considered together, as inseparable 65 dimensions—in fact, moving in space takes time, and the V. C ASE STUDY notion of stream implies some notion of time. (This is not As a scenario to conceptually validate the LPaaS approach part of the current LPaaS API in TABLE I.) to spatial awareness here proposed, let us consider the case Resolution process: Distribution per se constitutes a of a user looking for a parking spot in proximity of a metro premise to spatial situatedness: each LP instance runs on a station in London (Fig. 3). different device, on a different network host, accessing the The standard, non-spatial query (Fig. 3, (a)) would be just to different computational and network resources that are locally ask the nearest LPaaS metro service if there is a free parking available. Moreover, since LP services encapsulate their logic slot at the region covered by the logic theory of that station. theory, the locally-gathered knowledge affects the result. In the case of a negative answer, one could just proceed to C. Infrastructural Aspects: Mobility another metro service and re-ask the same query there. Spatial queries, instead, make it possible to expand the Besides the kind of mobility shown in Fig. 1, where the LP query to a region of space. Since the domain refers to metro engine conceptually moves in time and space, another kind stations, it seems reasonable to assume as “distance” the of mobility stems from use cases in mobile computing and number of stations between the LPaaS server station and pervasive systems. the parking station, possibly restricted to a single metro Generally speaking, mobile computing deals with systems line (i.e. black line only). For instance, distance(1,_) in which either software or devices need to move to ac- includes the stations adjacent to the server on any line, while complish their tasks, whereas pervasive computing deals with distance(1,black) includes the adjacent stations on the application scenarios in which computing devices are densely black line only. scattered in the physical world—and, possibly, moving. Start- In Fig. 3, (b) we assume that the user is close to the Elephant ing from this consideration, LPaaS aims at dealing with both and Castle station. In the spatial solve: physical (mobile hosts) and logical (code migration) mobility, solveAllNeighborhood ((station_with_parking(X), so as to support distributed location-aware computation. n_free_place(X,N)), S, region(_, distance(1,_)). As a first step towards a full-fledged perception of the goal time/space dimensions, mobility captures the idea that both station_with_parking(X), n_free_places(X,N) the LPaaS server and clients could move over the network: time and space are perceived to maintain the client/server looks for possible parkings in a region defined as at most one connections, i.e. somehow to “reroute” the server solutions to station away (region(_, distance(1,_))), retrieving the clients despite their movement, but have no impact on the the number N of free places. The service replies with a resolution process itself—that is, on the provided solutions. parking near the X=’London Bridge’ station, with N=5 Accordingly, mobile clients may request LP services from free places, reachable in one step on the black line. different locations at each request, possibly while moving, If the distance is restricted to a given line, i.e. brown as in which means that the LP service should be able to identify Fig. 3 (c), the answer is different—in this case, no solution. and track clients to reply to the correct network address. The Conversely, if the region is expanded to two stations of distance (Fig. 3 (d)), three parking spots will be found: issue must be resolved at the infrastructural level, via some X/‘London Bridge’, N/5, distance(1,black) middleware layer that possibly supports some notion of com- X/‘Canada Water’, N/2, distance(2,’black - grey’) munication session enabling users to consistently interact with X/‘Charing Cross’, N/0, distance(2,brown) the LPaaS service regardless of their mobility—there including the latter, unfortunately, with no free places. possible disconnections, reconnections, or IP changes. More complex scenarios could be envisioned—for instance, a user could ask the service the number of expected free places, possibly based on some prediction algorithm or analysing the history of the knowledge in each parking. VI. C ONCLUSION Pervasive and situated systems of any sort are increas- ingly demanding intelligence to be scattered throughout the computational devices populating the physical environment— as clearly demonstrated by IoT scenarios like smart homes, personal healthcare assistants, energy grids, etc. The LPaaS approach aims at fitting such a challenging context by introducing a standard interface that is general enough to account for both stateful and stateless services, with both static and dynamic knowledge bases, in a configurable and customisable way. The distinguishing feature of LPaaS is to support the spatio-temporal awareness, thus allowing for the Fig. 2. The solveNeighborhood primitive spanning over time and space. distribution of situated intelligence where and when needed. 66 Fig. 3. Examples of LPaaS queries exploiting spatial situatedness. The paper provides an interpretation of what it means to [10] M. Martelli, “Constraint logic programming: Theory and applications,” let LP span across space and time, and discusses the LPaaS in 1985-1995: Ten years of Logic Programming in Italy, M. Sessa, Ed., 1995, pp. 137–166. model and architecture extensions towards spatio-temporal [11] Y. Leng and L. Zhao, “Novel design of intelligent internet-of-vehicles situatedness, by identifying a suitably-expressive set of spatio- management system based on cloud-computing and internet-of-things,” temporal primitives. A real application scenario is discussed, in Electronic and Mechanical Engineering and Information Technology (EMEIT), 2011 International Conference on, vol. 6. IEEE, 2011, pp. highlighting the potential of such an approach, and showing 3190–3193. how taking the space around either the client or the server [12] Y. Chen and H. Hu, “Internet of intelligent things and robot as a service,” into account opens the chance to opportunistically federate LP Simulation Modelling Practice and Theory, vol. 34, pp. 159–171, 2013. [13] R. Calegari, E. Denti, S. Mariani, and A. Omicini, “Logic program- engines by need as a form of dynamic service composition. ming as a service in multi-agent systems for the Internet of Things,” Of course, this is not the end of the story: many im- International Journal of Grid and Utility Computing, In press. provements can be devised in several directions, starting from [14] ——, “Logic Programming as a Service (LPaaS): Intelligence for the IoT,” in 2017 IEEE 14th International Conference on Networking, building a specialised logic-oriented middleware, dealing with Sensing and Control (ICNSC 2017), G. Fortino, M. Zhou, Z. Lukszo, heterogeneous platforms, as well as with distribution, life- A. V. Vasilakos, F. Basile, C. Palau, A. Liotta, M. P. Fanti, A. Guerrieri, cycle, interoperation, and coordination of multiple, situated and A. Vinci, Eds. IEEE, May 2017, pp. 72–77. [Online]. Available: http://ieeexplore.ieee.org/document/8000070/ Prolog engines is a goal for our future research, aimed at [15] T. Erl, Service-Oriented Architecture: Concepts, Technology, exploring the full potential of logic-based technologies in the and Design. Upper Saddle River, NJ, USA: Prentice context of IoT scenarios and applications. Hall / Pearson Education International, 2005. [Online]. Available: http://www.pearson.com/us/higher-education/program/ Erl-Service-Oriented-Architecture-Concepts-Technology-and-Design/ R EFERENCES PGM137253.html [16] J. A. Robinson, “A machine-oriented logic based on the resolution [1] J. Beal, D. Pianini, and M. Viroli, “Aggregate programming for the principle,” Journal of the ACM, vol. 12, no. 1, pp. 23–41, Jan. 1965. Internet of Things,” IEEE Computer, vol. 48, no. 9, pp. 22–30, Sep. [Online]. Available: http://dl.acm.org/citation.cfm?id=321253 2015. [Online]. Available: http://ieeexplore.ieee.org/xpl/articleDetails. [17] R. Calegari, G. Ciatto, S. Mariani, E. Denti, and A. Omicini, “Micro- jsp?arnumber=7274429 intelligence for the IoT: SE challenges and practice in LPaaS,” in [2] M. Hazas, J. Scott, and J. Krumm, “Location-aware computing comes 2018 IEEE International Conference on Cloud Engineering (IC2E 208). of age,” Computer, vol. 37, no. 2, pp. 95–97, Feb. 2004. [Online]. IEEE Computer Society, 17–20 Apr. 2018, pp. 292–297. Available: http://ieeexplore.ieee.org/document/1266301/ [3] T. E. Starner, “Wearable computers: no longer science fiction,” IEEE Pervasive Computing, vol. 1, no. 1, pp. 86–88, Jan. 2002. [Online]. Available: http://ieeexplore.ieee.org/document/993148/ [4] R. Scoble and S. Israel, The Age of Context. Patrick Brewster Press, Apr. 2014. [5] F. Giunchiglia, “Contextual reasoning,” Epistemologia, special issue on I Linguaggi e le Macchine, vol. 16, pp. 345–364, 1993. [6] I. Uddin, A. Rakib, H. M. U. Haque, and P. C. Vinh, “Modeling and reasoning about preference-based context-aware agents over heteroge- neous knowledge sources,” Mobile Networks and Applications, vol. 23, no. 1, pp. 13–26, 2018. [7] N. Y. Asabere, “Towards a viewpoint of context-aware recommender systems (cars) and services,” International Journal of Computer Science and Telecommunications, vol. 4, no. 1, pp. 10–29, 2013. [8] J. Brownlee, Clever algorithms: nature-inspired programming recipes. Jason Brownlee, 2011. [9] A. D. Palù and P. Torroni, “25 years of applications of logic programming in Italy,” in A 25-year Perspective on Logic Programming, A. Dovier and E. Pontelli, Eds. Springer, 2010, pp. 300–328. [Online]. Available: http://link.springer.com/10.1007/978-3-642-14309-0 14 67 TABLE I LPAA S C LIENT I NTERFACE . DYNAMIC KNOWLEDGE BASE Stateless Stateful getServiceConfiguration(-ConfigList) getTheory(-Theory, ?Timestamp) getGoals(-GoalList) isGoal(+Goal) setGoal(template(+Template)) setGoal(index(+Index)) solve(+Goal, -Solution, ?Timestamp) solve(-Solution, ?Timestamp) solveN(+Goal, +NSol, -SList, ?TimeStamp) solveN(+N, -SolutionList, ?TimeStamp) solveAll(+Goal, -SList, ?TimeStamp) solveAll(-SolutionList, ?TimeStamp) solve(+Goal, -Solution, within(+Time), ?TimeStamp) solve(-Solution, within(+Time), ?TimeStamp) solveN(+Goal, +NSol, -SList, within(+Time), ?TimeStamp) solveN(+NSol, -SList, within(+Time), ?TimeStamp) solveAll(+Goal, -SList, within(+Time), ?TimeStamp) solveAll(-SList, within(+Time), ?TimeStamp) 68 solveAfter(+Goal, +AfterN, -Solution, ?TimeStamp) solveNAfter(+Goal, +AfterN, +NSol, -SList, ?TimeStamp) solveAllAfter(+Goal, +AfterN, -SList, ?TimeStamp) solve(-Solution, every(+Time), ?TimeStamp) solveN(+N, -SList, every(+Time), ?TimeStamp) solveAll(-SList, every(+Time), ?TimeStamp) pause() resume() solveNeighborhood(+Goal, -Solution, region(?P, +Space), ?TimeS) solveNeighborhood(-Solution, region(?P, +Space), ?TimeS) solveNNeighborhood(+Goal, +N, -SList, region(?P, +Space), ?TimeS) solveNNeighborhood(+N, -SList, region(?P, +Space), ?TimeS) solveAllNeighborhood(+Goal, -SList, region(?P, +Space), ?TimeS) solveAllNeighborhood(-SList, region(?P, +Space), ?TimeS) solveNeighborhood(+Goal, -Solution, region(?P, +Space, +Span), ?TimeS) solveNeighborhood(-Solution, region(?P, +Space, +Span), ?TimeS) solveNNeighborhood(+Goal, +N, -SList, region(?P, +Space, +Span), ?TimeS) solveNNeighborhood(+N, -SList, region(?P, +Space, +Span), ?TimeS) solveAllNeighborhood(+Goal, -SList, region(?P, +Space, +Span), ?TimeS) solveAllNeighborhood(-SList, region(?P, +Space, +Span), ?TimeS) reset() close() The table reports only methods operating on a dynamic KB that take an additional Timestamp argument, expressing the required time validity; static KB methods are analogous without the Timestamp parameter.