Implementing Contexts in Logic Programming

   page       BibTeX_logo.png   
Enrico Denti, Evelina Lamma, Paola Mello, Antonio Natali, Andrea Omicini
Evelina Lamma, Paola Mello (eds.)
3rd International Workshop on Extensions of Logic Programming (ELP'92), pages 145–170
Tecnoprint Bologna, Bologna, Italy
February 1992

The concept of context and contextual programming has been recently introduced in the logic programming field in order to enrich logic languages with general purpose concepts and mechanisms to structure programs, to support quick prototyping techniques and to promote the design and development of open, extensible software components.

The key-idea of contextual logic programming is to allow programmers to introduce the software components they need not only in a static way, but also dynamically, by composition of primitive, unalterable objects, called units, which are collections of clauses. The main goal is to give a uniform language support to fundamental concepts in knowledge-based applications, such as inheritance, viewpoints, evolving knowledge, etc.

A context is intended here as an abstraction that can be interpreted in two ways: at programming-level, it can be viewed as a dynamically configured software component; at implementation-level, it works like a structured environment, supporting a number of different binding mechanisms, each related to a specific high-level component architecture. In particular, the eager binding mechanism allows users to define software components according to conservative architectures, while lazy binding supports evolving, open architectures.

Contexts have been deeply studied in the last years both from the semantic and the implementative side.
In the following two related works, we describe our main results concerning the implementation of the context abstraction as an extension of Prolog. In particular, three main approaches have been considered, which can be summarized as follows:

  • Prolog-based approach: it exploits two well known techniques for implementing extensions of logic programming:
    • translating contextual programs into standard Prolog;
    • meta-intepretation;
  • WAM-based approach: it consists of extending the standard Warren Abstract Machine with a minimal set of features to support contexts;
  • Program representation-based approach: it exploits the program representation and the predicate addressing mechanism of a modular Prolog programming system, in order to implement contexts in the same way ordinary modules are.

The main goal of the first work is to discuss and compare the first two approaches by considering both methodological and performance aspects.

In order to achieve comparable performance results, a simulator of the VLSI Prolog coprocessor has been used. Two versions of such a simulator have been employed, the first supporting standard Prolog (i.e. implementing the standard WAM), the second supporting the S-WAM. Since both machines share the same set of micro-coded instruction, this set has been used as unit of measure. Reliable measures of computational costs can also be achieved, since the execution time of each micro-instruction is known.
The work shows, as it can be expected, that the WAM-based approach gives the better performance results. However, these results are considerably different (in favour of the Prolog-based approach) in the case of partial evaluation of completely configured contextual goals.

The main goal of the second work is to describe the third implementation approach, assuming as host environment the SICStus Prolog system. This approach (called CSM, i.e. Contexts as SICStus Modules) allowed us to achieve the following important results:

  • contexts are now supported by an efficient, widely used and well-supported Prolog system;
  • the implementation of contexts does introduce neither semantic distortion nor computational overhead with respect to standard (SICStus) Prolog programs;
  • both eager and late binding policies are implemented with the same (very low) computational cost. The main computational cost is now related to the context creation operation, which is however rather limited, since context creation is always obtained in an incremental way, without restarting from scratch.

Since CSM is based on a completely different predicate addressing scheme and operating environment, no quantitative performance comparison is immediately possible with the previous approaches. In any case, it is worth to note that the last solution can be considered as complementary with respect to the S-WAM design. In particular, while the stack-based S-WAM context representation provides automatic memory management in case of context deallocation, the CSM approach delegates such a problem to the user, by allowing, on the other side, the system programmer to exploit context memoization techniques.

In conclusion, far from stating the ultimate word in a field still open to significative improvements, our work shows that contextual logic programming paradigm can be effectively used also in industrial environments to face several of the most critical problems of modern software engineering.

reference talk
page_white_powerpointImplementing Contexts in Logic Programming (ELP'92, 26/02/1992) — Andrea Omicini (Enrico Denti, Evelina Lamma, Paola Mello, Antonio Natali, Andrea Omicini)
origin event
works as
reference publication for talk
page_white_powerpointImplementing Contexts in Logic Programming (ELP'92, 26/02/1992) — Andrea Omicini (Enrico Denti, Evelina Lamma, Paola Mello, Antonio Natali, Andrea Omicini)