The last two decades have witnessed the development and application of numerous logic programming systems based on Prolog. While these systems demonstrate both the power and praticality of logic programming, deficiencies in Prolog's SLD evaluation mechanism have limited the full exploitation of the logic programming paradigm. For instance, SLD's susceptability to infinite looping and redundant subcomputations render Prolog unsuitable as a query language for deductive databases. Prolog's weak termination properties have rendered its negation as failure rule inadequate for non-monotonic reasoning.
Tabulation methods in logic programming address these shortcomings. The past ten years of research in tabulation methods have produced major theoretical and practical advancements --- so much so that one can now claim that from a computational viewpoint tabled logic programming has tightly integrated logic programming, deductive databases and non-monotonic reasoning. Consequently, a number of applications that were beyond the reach of Prolog-based logic programming systems have now been made feasible. Examples include parsing of automatically generated grammars, dataflow and other types of program analyses, automated verification of correctness of program properties, and certain non-monotonic reasoning applications --- such as hierarchical reasoning and reasoning about actions --- which stem from the addition of explicit negation to the default negation of the well-founded semantics.
This tutorial will present a three-part survey of the developments in tabled logic programming. The theoretical foundations of tabled logic programming will constitute the first part. Techniques for implementing high-performance tabulation methods will be covered in the second part. New applications will be surveyed in the last part.
Mercury is a new logic programming language that breaks with the traditions of the field in two respects. First, the language has no no-logical constructs; even I/O is implemented in a declarative fashion. This gives the language a useful declarative semantics, which makes it much easier to apply existing theory (about program analysis, transformation, parallelization etc.) to Mercury programs. Second, the language has strong type, mode and determinism systems. These systems allow the Mercury compiler to detect a large fraction of program errors and to generate very fast yet compact code.
We will discuss the reasons for our language design decisions, and show how these decisions affect the implementation. In the process, we will give an introduction to Mercury, including features such as higher-order predicates and functions.