1.1 Programming in Logic

Logic Programming is a style of programming in which programs take the form of sets of sentences in the language of Symbolic Logic. Programs written in this style are called logic programs. The language in which these programs are written is called logic programming language. And a computer system that manages the creation and execution of logic programs is called a logic programming system.

1.2 Logic Programs as Runnable Specifications

Logic Programming is often said to be declarative or descriptive and contrasts with the imperative or prescriptive approach to programming associated with traditional programming languages.

In imperative / prescriptive programming, the programmer provides a detailed operational program for a system in terms of internal processing details (such as data types and variable assignments). In writing such programs, programmers typically take into account information about the intended application areas and goals of their programs, but that information is rarely recorded in the resulting programs, except in the form of non-executable comments.

In declarative / descriptive programming, programmers explicitly encode information about the application area and the goals of the program, but they do not specify internal processing details, leaving it to the systems that execute those programs to decide on those details on their own.

As an intuitive example of this distinction, consider the task of programming a robot to navigate from one point in a building to a second point. A typical imperative program would direct the robot to move forward a certain amount (or until its sensors indicated a suitable landmark); it would then tell the robot to turn and move forward again; and so forth until the robot arrives at the destination. By contrast, a typical declarative program would consist of a map and an indication of the starting and ending points on the map and would leave it to the robot to decide how to proceed.

A logic program is a type of declarative program in that it describes the application area of the program and the goals the programmer would like to achieve. It focusses on what is true and what is wanted rather than how to achieve the desired goals. In this respect, a logic program is more of a specification than an implementation.

Logic Programming is practical because there are well-known mechanical techniques for executing logic programs and/or producing traditional programs that achieve the same results. For this reason, logic programs are sometimes called runnable specifications.

1.3 Advantages of Logic Programming

Logic programs are typically easier to create and easier to modify than traditional programs. Programmers can get by with little or no knowledge of the capabilities and limitations of the systems executing those programs, and they do not need to choose specific methods of achieving their programs' goals.

Logic programs are more composable than traditional programs. In writing logic programs, programmers do not need to make arbitrary choices. As a result, logic programs can be combined with each other more easily than traditional programs where unnecessary arbitrary choices can conflict.

Logic programs are also more agile than traditional programs. A system executing a logic program can readily adapt to unexpected changes to its assumptions and/or its goals. Once again consider the robot described in the preceding section. If a robot running a logic program learns that a corridor is unexpectedly closed, it can choose a different corridor. If the robot is asked to pick up and deliver some goods along the way, it can combine routes to accomplish both tasks without having to accomplish them individually.

Finally, logic programs are more versatile than traditional programs - they can be used for multiple purposes, often without modification. Suppose we have a table of parents and children. Now, imagine that we are given definitions for standard kinship relations. For example, we are told that a grandparent is the parent of a parent. That single definition can be used as the basis for multiple traditional programs. (1) We can use it to build a program that computes whether one person is the grandparent of a second person. (2) We can use the definition to write a program to compute a person's grandparents. (3) We can use it to compute the grandchildren of a given person. (4) And we can use it to compute a table of grandparents and grandchildren. In traditional programming, we would write different programs for each of these tasks, and the definition of grandparent would not be explicitly encoded in any of these programs. In Logic Programming, the definition can be written just once, and that single definition can be used to accomplish all four tasks.

As another example of this (due to John McCarthy), consider the fact that, if two objects collide, they typically make a noise. This fact about the world can be used in designing programs for various purposes. (1) If we want to wake someone else, we can bang two objects together. (2) If we want to avoid waking someone, we would be careful not to let things collide. (3) If we see two cars come close in the distance and we hear a bang, we can conclude that they had collided. (4) If we see two cars come close together but we do not hear anything, we might guess that they did not collide.

1.4 Applications of Logic Programming

Logic Programming can be used fruitfully in almost any application area. However, it has special value in application areas characterized by large numbers of definitions and constraints and rules of action, especially where those definitions and constraints and rules come from multiple sources or where they are frequently changing. The following are a few application areas where Logic Programming has proven particularly useful.

Database Systems. By conceptualizing database tables as sets of simple sentences, it is possible to use Logic in support of database systems. For example, the language of Logic can be used to define virtual views of data in terms of explicitly stored tables; it can be used to encode constraints on databases; it can be used to specify access control policies; and it can be used to write update rules.

Logical Spreadsheets / Worksheets. Logical spreadsheets (sometimes called worksheets) generalize traditional spreadsheets to include logical constraints as well as traditional arithmetic formulas. Examples of such constraints abound. For example, in scheduling applications, we might have timing constraints or restrictions on who can reserve which rooms. In the domain of travel reservations, we might have constraints on adults and infants. In academic program sheets, we might have constraints on how many courses of varying types that students must take.

Data Integration. The language of Logic can be used to relate the concepts in different vocabularies and thereby allow users to access multiple, heterogeneous data sources in an integrated fashion, giving each user the illusion of a single database encoded in his own vocabulary.

Enterprise Management. Logic Programming has special value in expressing and implementing business rules of various sorts. Internal business rules include enterprise policies (e.g. expense approval) and workflow (who does what and when). External business rules include the details of contracts with other enterprises, configuration and pricing rules for company products, and so forth.

Computational Law. Computational Law is the branch of Legal Informatics concerned with the representation of rule and regulations in computable form. Encoding laws in computable form enables automated legal analysis and the creation of technology to make that analysis available to citizens, and monitors and enforcers, and legal professionals.

General Game Playing. General game players are systems able to accept descriptions of arbitrary games at runtime and able to use such descriptions to play those games effectively without human intervention. In other words, they do not know the rules until the games start. Logic Programming is widely used in General Game Playing as the preferred way to formalize game descriptions.

1.5 Basic Logic Programming

Over the years, various types of Logic Programming have been explored (Basic Logic Programming, Classic Logic Programming, Transaction Logic Programming, Constraint Logic Programming, Disjunctive Logic Programming, Answer Set Programming, Inductive Logic Programming, etc.). Along with these different types of Logic Programming, a variety of logic programming languages have been developed (e.g. Datalog, Prolog, Epilog, Golog, Progol, LPS, etc.). In this volume, we concentrate on Basic Logic Programming, a variant of Transaction Logic Programming; and we use Epilog in writing our examples.

In Basic Logic Programming, we model the states of an application as sets of simple facts (called datasets), and we write rules to define abstract views of the facts in datasets. We model changes to state as primitive updates to our datasets, i.e. sets of additions and deletions of facts, and we write rules of a different sort to define compound actions in terms of primitive updates.

Epilog (the language we use in this volume) is closely related to Datalog and Prolog. Their syntaxes are almost identical. And the three languages are nicely ordered in terms of expressiveness - with Datalog being a subset of Prolog and Prolog being a subset of Epilog. For the sake of simplicity, we use the syntax of Epilog throughout this course, and we talk about the Epilog interpreter and compiler. Thus, when we mention Datalog in what follows, we are referring to the Datalog subset of Epilog; and, when we mention Prolog, we are referring to the Prolog subset of Epilog.

As we shall see, all three of these languages (Datalog and Prolog and Epilog) are less expressive than the languages associated with more complex forms of Logic Programming (such as Disjunctive Logic Programming and Answer Set Programming). While these restrictions limit what we can say in these languages, the resulting programs are computationally better behaved and, in most cases, more practical than programs written in more expressive languages. Moreover, due to these restrictions, Datalog and Prolog and Epilog are easy to understand; and, consequently, they have pedagogical value as an introduction to more complex Logic Programming languages.

In keeping with our emphasis on Basic Logic Programming, the material of the course is divided into five units. In this unit, Unit 1, we give an overview of Logic Programming and Basic Logic Programming, and we introduce datasets. In Unit 2, we talk about queries and updates. In Unit 3, we talk about view definitions. In Unit 4, we concentrate on operation definitions. And, in Unit 5, we talk about variations, i.e. other forms of Logic Programming.

Historical Notes

In the mid 1950s, computer scientists began to concentrate on the development of high-level programming languages. As a contribution to this effort, John McCarthy suggested the language of Symbolic Logic as a candidate, and he articulated the ideal of declarative programming. He gave voice to these ideas in a seminal paper, published in 1958, which describes a type of system that he called an advice taker.

"The main advantage we expect the advice taker to have is that its behavior will be improvable merely by making statements to it, telling it about its ... environment and what is wanted from it. To make these statements will require little, if any, knowledge of the program or the previous knowledge of the advice taker."

The idea of declarative programming caught the imaginations of subsequent researchers - notably Bob Kowalski, one of the fathers of Logic Programming, and Ed Feigenbaum, the inventor of Knowledge Engineering. In a paper written in 1974, Feigenbaum gave a forceful restatement of McCarthy's ideal.

"The potential use of computers by people to accomplish tasks can be 'one-dimensionalized' into a spectrum representing the nature of the instruction that must be given the computer to do its job. Call it the what-to-how spectrum. At one extreme of the spectrum, the user supplies his intelligence to instruct the machine with precision exactly how to do his job step-by-step. ... At the other end of the spectrum is the user with his real problem. ... He aspires to communicate what he wants done ... without having to lay out in detail all necessary subgoals for adequate performance."

The development of Logic Programming in its present form can be traced to subsequent debates about declarative versus procedural representations of knowledge in the Artificial Intelligence community.

Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky and Seymour Papert. Although it was based on the proof methods of logic, Planner, developed at MIT, was the first language to emerge within the proceduralist paradigm. Planner featured pattern-directed invocation of procedural plans from goals (i.e. goal-reduction or backward chaining) and from assertions (i.e. forward chaining). The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman, Eugene Charniak and Terry Winograd. It was used to implement Winograd's natural-language understanding program SHRDLU, which was a landmark at that time.

Advocates of declarative representations were centered at Stanford (associated with John McCarthy, Bertram Raphael, and Cordell Green) and in Edinburgh (associated with John Alan Robinson, Pat Hayes, and Robert Kowalski). Hayes and Kowalski tried to reconcile the logic-based declarative approach to knowledge representation with Planner's procedural approach. In 1973, Hayes developed an equational language, Golux, in which different procedures could be obtained by altering the behavior of a theorem prover. Kowalski, on the other hand, developed SLD resolution, a variant of SL-resolution, and showed how it treats implications as goal-reduction procedures. Kowalski collaborated with Colmerauer in Marseille, who developed these ideas in the design of the programming language Prolog, which was implemented in the summer and autumn of 1972. The first Prolog program, also written in 1972 and implemented in Marseille, was a French question-answering system. The use of Prolog as a practical programming language was given great momentum by the development of a compiler by David Warren in Edinburgh in 1977.