Chapter 1    General Introduction

``Prolog'' stands for ``Programming in Logic.'' It is the most widely available general-purpose language for doing logic programming. Since the earliest days of digital computers, researchers have been interested in computational logic or automated theorem proving. The goal there is to get the computer to help search for particularly hard proofs, using the computer's practically infinite patience to supplement the logician's insight. Logic programming was born when researchers in computational logic discovered that certain approaches to deduction made sense as a general-purpose programming language. For example, consider the following fragment of Prolog code. 
true_sentence( Sentence ) :- 
    syntactic_analysis( Sentence, Structure ), 
    meaning( Structure, LogicalForm ), 
    value( LogicalForm, true ).
This can be read logically as stating that for all Sentence, if a syntactic analysis of Sentence is Structure and furthermore LogicalForm is a meaning that can be associated with Structure, and furthermore the value of LogicalForm is true, then Sentence is a true sentence. As such it could be an axiom in a logical theory designed to characterize the true sentences of German, for instance.

It also has a procedural interpretation. In this interpretation, true_sentence, is the name of a procedure with one parameter, named Sentence. The procedure true_sentence is then defined in terms of other procedures---syntactic_analysis, meaning, and value---which it calls. We would then think of the variables Structure and LogicalForm as local variables of the procedure.

So logic programs have both a logical (usually called declarative) interpretation and also a procedural one. Even better, those interpretations coincide. This means that it does not matter whether you view a Prolog program as a set of axioms and Prolog itself as a deductive engine for deriving valid consequences of those axioms, or you view a Prolog program as a set of procedures, and Prolog itself as an interpreter to handle procedure-calling and parameter-passing. You can look at a program from whichever angle best suits your purpose at the time. This is very useful because, in general, at the beginning of a long and complex programming project you are likely to be more interested in the logic of the problem you have set out to solve, but later on as the project progresses you will become more interested in solving the problem efficiently, so details of the procedure by which the problem is solved will become more important.

The organization of the course reflects this progression from concern for correctness to concern for speed. In the first part of the course, we will focus on learning how to write logically correct recursive definitions of data types and relations over these data types. This is tricky enough, without worrying about efficiency at all! Then, in the second part of the course, once we have gotten accustomed to writing recursive programs, we will begin to focus on issues related to the procedural interpretation of logic programs.

This neat division of topics into Logic and Control cannot be absolute, of course. We are here to learn about a programming language, not about logic or automated theorem proving, and some issues of control will concern us right from the start. In particular, Prolog is a powerful programming language, and, as with any other programming language, it is possible to write programs that do not halt, but instead run on forever (or until we interrupt them). So even at the very start we will be concerned with some procedural details of Prolog, just so we can be sure that we are writing programs that will indeed halt before the end of the world. Also, some knowledge of Prolog's procedural interpretation is necessary to debug programs that don't do what you think you told them to do. When things go wrong, it is often useful to be able to work out with pencil and paper just what steps the Prolog interpreter is going through when it runs your faulty program, and, obviously, you need to know what those steps will be to do this.

(Of course, some programs simply cannot be guaranteed to halt for all inputs. Assuming that the program, whose top level was given at the beginning of this introduction, were correctly implemented, can you think of an input for it for which it might not halt?)

This document was translated from LATEX by HEVEA.