Section 1.5 Logic Programming
73
S e c t I o n 1 . 5 logiC pRogR amming
The programming languages with which you are probably familiar, such as C++
or Java, are known as procedural languages. Much of the content of a program
written in a procedural language consists of instructions to carry out the algorithm the programmer believes will solve the problem at hand. The programmer, therefore, is telling the computer how to solve the problem in a step-by-step
fashion.
Some programming languages, rather than being procedural, are declarative
languages or descriptive languages. A declarative language is based on predicate logic; such a language comes equipped with its own rules of inference. A
program written in a declarative language consists only of statements— actually
predicate wffs—that are declared as hypotheses. Execution of a declarative program allows the user to pose queries, asking for information about possible
conclusions that can be derived from the hypotheses. After obtaining the user’s
query, the language turns on its “inference engine” and applies its rules of inference to the hypotheses to see which conclusions fit the user’s query. The
program, remember, contains only the hypotheses, not any explicit instructions
as to what steps to perform in what order. The inference engine of the language
acts behind the scenes, so to speak, to construct a proof sequence. It is the mechanical nature of applying inference rules that makes this “automated theorem
proving” possible.
Prolog
The programming language Prolog, which stands for PROgramming in LOGic,
is a declarative programming language. The set of declarations that constitutes
a Prolog program is also known as a prolog database. Items in a Prolog database take on one of two forms, known in Prolog as facts and rules. (Prolog rules,
however, are just another kind of fact and should not be confused with a rule of
inference.)
prolog facts allow predicates to be defined by stating which items in some
domain of interpretation satisfy the predicates. As an example, suppose we wish to
create a Prolog program that describes food chains in a given ecological region. We
might begin with a binary predicate eat. We then describe the predicate by giving
the pairs of elements in the domain that make eat true. Thus we might have the facts
eat(bear, fish)
eat(bear, fox)
eat(deer, grass)
in our database. (The exact details of Prolog statements vary from one Prolog
implementation to another, so in this section we are only giving the spirit of the
language by using a Prolog-like pseudocode.) Here “bear,” “fish,” “fox,” “deer,”
and “grass” are constants because they represent specific elements in the domain.
Because the domain itself is never specified except by describing predicates, at
this point we may take the domain to consist of “bear,” “fish,” “fox,” “deer,” and
73
S e c t I o n 1 . 5 logiC pRogR amming
The programming languages with which you are probably familiar, such as C++
or Java, are known as procedural languages. Much of the content of a program
written in a procedural language consists of instructions to carry out the algorithm the programmer believes will solve the problem at hand. The programmer, therefore, is telling the computer how to solve the problem in a step-by-step
fashion.
Some programming languages, rather than being procedural, are declarative
languages or descriptive languages. A declarative language is based on predicate logic; such a language comes equipped with its own rules of inference. A
program written in a declarative language consists only of statements— actually
predicate wffs—that are declared as hypotheses. Execution of a declarative program allows the user to pose queries, asking for information about possible
conclusions that can be derived from the hypotheses. After obtaining the user’s
query, the language turns on its “inference engine” and applies its rules of inference to the hypotheses to see which conclusions fit the user’s query. The
program, remember, contains only the hypotheses, not any explicit instructions
as to what steps to perform in what order. The inference engine of the language
acts behind the scenes, so to speak, to construct a proof sequence. It is the mechanical nature of applying inference rules that makes this “automated theorem
proving” possible.
Prolog
The programming language Prolog, which stands for PROgramming in LOGic,
is a declarative programming language. The set of declarations that constitutes
a Prolog program is also known as a prolog database. Items in a Prolog database take on one of two forms, known in Prolog as facts and rules. (Prolog rules,
however, are just another kind of fact and should not be confused with a rule of
inference.)
prolog facts allow predicates to be defined by stating which items in some
domain of interpretation satisfy the predicates. As an example, suppose we wish to
create a Prolog program that describes food chains in a given ecological region. We
might begin with a binary predicate eat. We then describe the predicate by giving
the pairs of elements in the domain that make eat true. Thus we might have the facts
eat(bear, fish)
eat(bear, fox)
eat(deer, grass)
in our database. (The exact details of Prolog statements vary from one Prolog
implementation to another, so in this section we are only giving the spirit of the
language by using a Prolog-like pseudocode.) Here “bear,” “fish,” “fox,” “deer,”
and “grass” are constants because they represent specific elements in the domain.
Because the domain itself is never specified except by describing predicates, at
this point we may take the domain to consist of “bear,” “fish,” “fox,” “deer,” and