UCL - Département d'Ingénierie Informatique

Implementation of logic languages

Vision

Is it possible to implement a logic language as easily as writing a WAM-based Prolog, such that the language's performance rivals imperative languages? Each of these two conditions can be satisfied separately. First, it is very easy to build a logic programming system based on the technology of the Warren Abstract Machine (WAM). The performance of such a system will be an order of magnitude less than that of imperative language implementations. Second, it is possible for a logic language to approach imperative language performance. Constructive proofs of this have been given by the Aquarius and Parma systems. However, achieving this performance level requires a quite complex implementation. Can the simplicity of the first approach be combined with the performance of the second? Finding a positive answer to this question will catalyze a quantum leap in performance in all existing logic language implementations.

References

Logical State Threads: a tool for writing large Prolog programs

Logical State Threads is a package for SICStus Prolog and compatible systems that simplifies the development of large Prolog programs. A beta version has been released in January 1997. The package was designed by Andreas Kagedal, Peter Van Roy and Bruno Dumant, and written mostly by Andreas Kagedal. The package subsumes the Wild_Life and Extended DCG packages (see next item). It is a cleaned up version of the Wild_Life package for Prolog. It includes powerful operators for scoping and composition of accumulators. This makes it especially useful for the practical development of large, applicative ("pure") programs in Prolog. Please contact Andreas Kagedal (andka@cs.arizona.edu) or Peter Van Roy for more information.
Extended DCG's: Declarative programming with state. The Logical State Threads are based on this work.

The state-of-the-art in logic programming implementation (1994)

Constructive proofs that Prolog can execute as fast as C: Peter Van Roy's Ph.D. dissertation (1990), Andrew Taylor's Ph.D. dissertation (1991).
Issues in Implementing Logic Languages, May 1994, École de Printemps (Spring School), Châtillon sur Seine, France. Includes a first approach towards resolving the research question posed above.
1983-1993: The Wonder Years of Sequential Prolog Implementation (450K), May/July 1994, Journal of Logic Programming. A survey of implementation technology and systems since the WAM. Includes summaries of Aquarius (Van Roy's system) and Parma (Taylor's system).

Record constraints in Oz

Integrating Efficient Records into Concurrent Constraint Programming (170K). This article tells how record constraints were added to the DFKI Oz system.
Draft documentation on open feature structures (record constraints) (240K), including how to implement LIFE's psi-terms in Oz.
DFKI Oz 2.0 is a programming system designed for applications that require complex symbolic computations, organization into multiple agents, and soft real-time control.

Implementation of LIFE, a successor to Prolog

High performance implementation of Prolog

Aquarius Prolog is one of the world's highest performance Prolog systems. It rivals imperative language performance (i.e., good C compilers) on a significant set of programs. In its current state, the system has a full complement of built-ins (Quintus-compatible), is available free with full source code, but is no longer being maintained.

Aquarius Prolog.
User Manual (790K).
Foundation of Aquarius Prolog: Peter Van Roy's Ph.D. dissertation.