Alessandro Dal Palù Dip. di Matematica, Università di Parma (Italy)
Paolo Torroni DEIS, Università di Bologna (Italy)
Abstract
In this paper we give a summary of our recent survey of practical applications of Logic Programming in Italy. The survey covers a 25 year time-span. Information was mainly gathered via current and past members of the Italian Logic Programming Association GULP. The survey demonstrated that Logic Programming successfully evolved and quickly adapted to new challenges offered by a notable variety of application areas.
Introduction
Logic Programming (LP) is one of these areas in Computer Science subject to indefatigable cross fire. On one side, because it is programming, it is regarded by hard core logicians as something impure. On the other side, because it is logic after all, it causes serious allergies to hard core programmers, who abhor anything which is not procedural, and generally get disturbed by too many parentheses. So it seems to be our destiny to have to fight a battle on two fronts. We all love to show how clever we are with birds and penguins, but sometimes we also need to show that LP languages can also be used to solve concrete problems. So is life.
For this reason, we have recently been invited by Agostino and Enrico to run a survey of practical LP applications. The survey was to be published in a volume collecting 25 years of LP experiences in Italy, and it is currently in press [7]. Our work was mainly based on bibliographic search and on a questionnaire, which we sent to current and past members of the Italian Associations for Logic Programming GULP and Artificial Intelligence AIxIA and to other possibly interested individuals, who had been involved in projects dealing with LP. The answers to our poll gave us a non exhaustive, but significant collection of projects and experiences, often described with passion and enthusiasm. In a short time span, we received more than 50 different applications, and we ended up with so much material that we were forced to operate a selection.
That was actually the first work to survey LP applications in Italy in 25 years. Exhaustiveness was not our aim. In particular, we restricted this survey to applications developed in Italy. Even if these are only a fraction of the international panorama, they represent a significant body of work. Besides, our resources did not permit us to run a more accurate investigation of industrial applications. Nevertheless, we managed to put together a very rich selection of experiences, and at the same time to keep the scope of this overview as broad as possible.
Although our presentation is mainly thematic, and only marginally historical, it is interesting to note the extent to which applications domains have increased in the last 25 years.
In the early days, applications of LP especially focussed on a little number of domains, such as robotics. However, industry was very much interested in this new, promising way of thinking.
The mid 90s witnessed a change in the impact of LP into industries. Even if, e.g., Constraint Logic Programming started to be employed as an effective tool to solve complex and industrial problems, applications were being developed as stand-alone projects rather than integrated in the production line mainstream. Programmers were not familiar with Prolog and thus it was difficult to estimate costs and performances of projects that included LP critical components. Often the choice was then to move to traditional technologies. Finally, LP was a tool developed and used by researchers and little low-level programming skills were transferred to students [12].
In the latest 15 years, the scenario evolved and expanded widely. The scope of LP application domains has steadily increased to conquer new grounds. We are witnessing the birth and rise of new application domains, alongside the evolution of older application domains in which LP had been present since the 80s, addressed with renewed vigor motivated by more modern LP-based solutions. Probably, LP technologies are now ripe and stakeholders ready for their adoption. We can rely on more efficient algorithms, on the achievements of CLP, on more powerful machines, and on a better understanding of the their theoretical underpinnings. Another reason why there are so many academic LP applications in Italy nowadays may be that, recently, funding agencies privilege applied research projects rather than basic research. This happens both at the National level, and at the European level, where most of Italian research is seeking funding.
On the downside, comparatively little Prolog is used for applications – despite the availability of many implementations of it. Like it used to be, 15 years ago, only a few companies use Prolog. However, from the LP education point of view, the situation has improved since 1995. In 2007, GULP ran another survey, to evaluate the extent of computational logic teaching at Italian universities. It turns out that nowadays declarative programming is being taught in 20 out of 94 Italian universities in around 50 courses, at various levels in computer science and engineering curricula. Some of these courses have been running for as long as 20 years. In 80% of the cases, the syllabus includes practical lab sessions that teach students how to use SWI Prolog, SICStus, ECLiPSe or other Prolog engines, Answer Set Programming (ASP) solvers such as DLV, SAT solvers and model checkers.
There are two drawbacks of our investigation that we could not handle with our resources. The first one is that older applications are more difficult to dig and for this reason our report appears to be biased towards more recent ones. Some information about the early applications of LP in Italy can be found in [12]. The other drawback is that potentially many industrial applications are left out, since we had no means to reach projects that are completely independent from academia. Considering also the relevant number of students graduated with (at least) the basics of LP, it is reasonable to imagine a number of independent solutions that we are not aware of. Even if strongly biased by our poll method, it is our belief that in the years the number of industrial applications has not dramatically increased. We can also observe the lack of an organized and international developer’s network that is often a necessary condition for technology transfer and dissemination in the industrial and commercial entourage.
Selected applications
We propose here only a selection of applications. We invite the interested reader to refer to the extended version [7], which contains larger and more detailed descriptions.
Robotics.
In the early days, LP in Italy was in tight connection with research on Robotics. The first Prolog installation dates back in 1974, when Pagello (Politecnico di Milano); and his colleagues at the University of Padova started developing Prolog applications for planning in robotic environments, addressing the automatic generation of action sequences for robotic mechanical assembly. LP would provide the tools needed to design more easily a higher level planning system to automatically generate lower level instructions for the robot. The results of this line of research could be tested on a Cartesian manipulator.
Knowledge Management.
There are several successful industrial exploitations of the DLV [9] ASP system developed by Leone and colleagues at the University of Calabria. Two spin-off companies, Exeura srl and DLVSYSTEM srl, use DLV for Knowledge Management. DLVSYSTEM srl licenses and maintains DLV. Exeura instead offers three industrial products: OntoDLV (ontology management and reasoning system), OLEX (document classification system), and HiLeX (information extraction). DLV has also been applied at CERN for knowledge manipulation on large databases; in the context of E-Tourism and Automatic Itinerary Search, and in Team Building applications. Also based on DLV, INFOMIX is an information integration application capable of dealing with incomplete and inconsistent data, built in cooperation with RODAN systems, a commercial DBMS developer. An overview of such applications is given by Leone in [10].
Figure 1: OntoDLV interface
Business processes and choreographies.
The EU-funded SOCS produced a computational logic model for the description, analysis and verification of global and open societies of heterogeneous logic based agents. The methods developed by SOCS, especially the CIFF [11] and SCIFF [1] languages and proof-procedures, have been applied to a variety of domains, including normative, recommendation systems, ambient intelligence, business process interaction, medical guidelines, Web service choreographies, agent-oriented requirements engineering, argumentation, contract modeling and monitoring, hybrid systems. A subset of SCIFF is at the base of the CLIMB framework for business process and choreography specification, verification and analysis.
Figure 2: Illustration of SCIFF uses, taken from the CLIMB home page
Electronic marketplaces.
The ARGUGRID project proposes e-business applications of LP-based argumentation agents. Its methods support the decision-making of intelligent agents, representing buyers and sellers of products in electronic marketplaces. ARGUGRID developed several LP-based argumentation engines, including MARGO for electronic auction selection, CaSAPI for service provider selection and MoDiSo for legal dispute resolution.
Figure 3: Snapshot of the eAuction decision tool, built on top of MARGO
Agent-based applications.
Since 1999, Costantini & al. develops the DALI platform [4]. It is a general-purpose and agent-oriented logical language implemented in SICStus Prolog. DALI has been used for industrial applications and is patent pending. Since 1998, Omicini et al. (Bologna, Cesena campus) work on the TuCSoN service infrastructure for the coordination and communication among independent and concurrent software components. TuCSoN is used in a number of applications, ranging from Agent Coordination Context, interaction space, system biology, to workflow management system prototype for virtual organizations and pervasive smart environments. Recently, Mascardi et al (Genova) implemented a MAS prototype [13] for Ansaldo STS, that monitors processes running in a railway signalling plant, detects functioning anomalies, and provides support to the early notification of problems to the Command and Control System Assistance. The MAS is implemented with DCaseLP, a multi-language prototyping environment (see also [2])
Natural Language Processing.
An important NLP project was developed since 2004, by Bos (La Sapienza) [5] to map syntactic structures produced by a parser to first-order languages. The system designed is based on syntactic and semantic formalisms from theoretical linguistics and on a wide-coverage Combinatory Categorial Grammar (CCG) parser. The resulting open-domain QA system is well suited to analyze large amounts of text containing a potential answer.
Bioinformatics.
The COLA project [6] started in 2003 by Dal Palù (Parma), Dovier and Fogolari (Udine), and Pontelli (New Mexico State University), addresses the problem of protein tertiary structure prediction by modeling a spatial environment and an objective function to be optimized. The problem translates into a CSP, where constraints are derived from physical properties of the molecules, and a set of heuristics that explore the search space effectively are studied.
Figure 4: Constraint satisfaction for Bioinformatics
E-Learning.
In 2007, Gennari and Mich (Bolzano) started developing an educational Web-based tool called LODE for teaching learning-impaired children [8]. On the server side, a first prototype of LODE used the ECLiPSe CLP system to generate exercises and to check their temporal consistency.
Figure 5: Snapshot of the LODE interface
Health Care.
The SINDI (Secure and INDependent LIving) system offers advanced tools for monitoring dynamical, clinical and physical parameters since 2007. It offers medical professionals the tools to prevent the verification of potential events that may limit the autonomy of the patients. The system is made of a wireless sensor network, an interface with the patient and a Reasoning Component based on non monotonic reasoning, focusing on situation assessment and evaluation of the patient’s risk status (by comparing gathered data and clinical knowledge base). Moreover the reasoner depicts possible future scenarios, as prevention and feedback output, based on the current risk status. The latest version is currently under experimentation at the Monza Hospital.
Figure 6: Snapshot of the SINDI system
Conclusions
The sample applications reviewed above and the other ones we surveyed in our extended article [7] emphasize many collaborations between research groups and industrial and commercial partners. This makes us believe that now time is ripe for pushing the adoption of LP outside of academic entourage. Exeura srl is a successful example of a company that is actually doing business and providing services with LP technology. There are many collaborations and projects with Public Administrations, such as municipalities and hospitals, that rely on LP and extensions. The main obstacles to LP adoptions, such as lack of LP-education and problems of efficiency and integration, seem to have been overcome in many cases.
Programming methodologies and environments, debugging techniques, friendly interfaces did not evolve significantly compared to those of other popular imperative languages. However, these issues are confined to the production of LP-based solutions and do not affect the quality of the solutions themselves.
We can observe that the current trend is to develop competitive LP-based solutions for hard problems. This requires a solid background, education and high programming skills. In the perspective of market globalization and considering the constant increase in the number of new and complex applications, a demand for such high quality profiles is not necessarily a negative and penalizing aspect. We believe, instead, that competencies in declarative programming will become even more valuable in the next years.
References
[1] M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello, and P. Torroni.
Verifiable agent interaction in abductive logic programming: The SCIFF framework. ACM Trans. Comput. Log., 9(4), 2008.
[2] M. Baldoni, C. Baroglio, V. Mascardi, A. Omicini, and P. Torroni.
Agents, multi-agent systems and declarative programming: What, when,
where, why, who, how? In A 25-Year Perspective on Logic Programming.
Achievements of the Italian Association for Logic Programming, GULP,
LNCS 6125, pages 199–224, 2010.
[3] R. Bisiani, D. Merico, A. Mileo, and S. Pinardi. A logical approach
to home healthcare with intelligent sensor-network support. The Comp. J.
Adv. Access, 2009.
[4] S. Costantini and A. Tocchio. The dali logic programming
agent-oriented language. In J. J. Alferes and J. A. Leite, editors, JELIA,
LNCS 3229, pages 685–688, 2004.
[5] J. R. Curran, S. Clark, and J. Bos. Linguistically motivated
large-scale NLP with C&C and Boxer. In ACL, pages 29–32, 2007.
[6] A. Dal Palù, A. Dovier, and E. Pontelli. A constraint solver for
discrete lattices, its parallelization, and application to protein structure
prediction. Softw. Pract. Exper., 37(13):1405–1449, 2007.
[7] A. Dal Palù and P. Torroni. 25 years of applications of logic
programming in italy. In A 25-Year Perspective on Logic Programming.
Achievements of the Italian Association for Logic Programming, GULP,
LNCS 6125, pages 298–325, 2010.
[8] R. Gennari and O. Mich. LODE: A logic-based e-learning tool for deaf
children. Tech Rep KRDB07-3, University of Bolzano, 2007.
[9] G. Grasso, S. Iiritano, N. Leone, and F. Ricca. Some DLV
applications for knowledge management. In LPNMR, pages 591–597, 2009.
[10] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and
F. Scarcello. The DLV system for knowledge representation and reasoning.
ACM Trans. Comput. Logic, 7(3):499–562, 2006.
[11] P. Mancarella, G. Terreni, F. Sadri, F. Toni, and U. Endriss. The
CIFF proof procedure for abductive logic programming with constraints:
Theory, implementation and experiments. Theory and Practice of Logic
Programming, 9:691–750, 2009.
[12] M. Martelli. Constraint logic programming: Theory and applications.
In M. Sessa, editor, 1985 – 1995: Ten years of Logic Programming in Italy,
pages 137–166. Palladio, Salerno, Italy, 1995.
[13] V. Mascardi, D. Briola, M. Martelli, R. Caccia, and C. Milani.
Monitoring and diagnosing railway signalling with logic-based distributed
agents. In CISIS’08, volume 53 of LNCS, pages 108–115, 2009.
[14] A. Omicini and F. Zambonelli. Coordination of mobile information
agents in TuCSoN. Internet Research: El. Networking Appl. and Policy,
8(5):400–413, 1998.