Mimir:Draft6 Chapter5

From Openitware
Jump to: navigation, search

Back to Table of Contents


Contents

Chapter 5: Logic Programming

"If you want to gather honey, don't kick over the beehive."

In this chapter you will learn:

  1. Logic Programming Paradigm
  2. Prolog Programming Language


The Logic Paradigm

Logic Programming: is a type of programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain.

Major logic programming language families include Prolog, Answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

H :- B1, …, Bn.

and are read declaratively as logical implications:

H if B1 and … and Bn.

H is called the head of the rule and B1, …, Bn is called the body. Facts are rules that have no body, and are written in the simplified form:

H.

In the simplest case in which H, B1, …, Bn are all atomic formulae, these clauses are called definite clauses or Horn clauses. However, there exist many extensions of this simple case, the most important one being the case in which conditions in the body of a clause can also be negations of atomic formulae. Logic programming languages that include this extension have the knowledge representation capabilities of a non-monotonic logic.

In ASP and Datalog, logic programs have only a declarative reading, and their execution is performed by means of a proof procedure or model generator whose behavior is not meant to be under the control of the programmer. However, in the Prolog family of languages, logic programs also have a procedural interpretation as goal-reduction procedures:

to solve H, solve B1, and ... and solve Bn.

Consider, for example, the following clause:

fallible(X) :- human(X).

based on an example used by Terry Winograd, to illustrate the programming language Planner. As a clause in a logic program, it can be used both as a procedure to test whether X is fallible by testing whether X is human, and as a procedure to find an X that is fallible by finding an X that is human. Even facts have a procedural interpretation. For example, the clause:

human(Socrates).

can be used both as a procedure to show that socrates is human, and as a procedure to find an X that is human by "assigning" Socrates to X.

The declarative reading of logic programs can be used by a programmer to verify their correctness. Moreover, logic-based program transformation techniques can also be used to transform logic programs into logically equivalent programs that are more efficient. In the Prolog family of logic programming languages, the programmer can also use the known problem-solving behavior of the execution mechanism to improve the efficiency of programs.

Datalog

Datalog is a truly declarative logic programming language that syntactically is a subset of Prolog. It is often used as a query language for deductive databases. Datalog has found new applications in data integration, information extraction, networking, program analysis, security, and cloud computing. Unlike in Prolog, statements of a Datalog program can be stated in any order. Furthermore, Datalog queries on finite sets are guaranteed to terminate, so Datalog does not have Prologs cut operator. This makes Datalog a truly declarative language. Query evaluation with Datalog is based on first order logic. Some widely used database systems include ideas and algorithms developed for Datalog.

It is also used in many fields that require logic programming including networking, cloud computing, deductive database design, information extraction, and program analysis. Datalog is usually implemented in, or interpreted using, other programming languages. Open source Datalog implementations exist for Java, C++, Lua, Python, Prolog, Clojure, and Racket, and commercial Datalog implementations are also available.

  • Database programmers like Datalog for its simplicity. As a simple declarative logic-based language, Datalog relies on a conventional clause format. In a declarative language, the user enters the items that they want to find and then the system takes over, finding values that comply with the user's request.
  • Like other types of query systems, a Datalog query involves setting up a command-based premise. For example, many simpler Datalog queries consist of an object and a set of modifiers or constraints in parentheses. The simple syntax allows administrators to quickly learn how to get the results they need from the database. However, as with other systems, Datalog users have to deal with the emergence of raw or unstructured data sets in a database technology. In other words, whereas databases of the past tended to have strict "table" data formats, today's databases may have much more abstracted information that has to be queried and handled in a different way.

Examples

Example of a Datalog program:

parent(bill, mary).
parent(mary, john).

These two lines define two facts, i.e. things that always hold. They can be intuitively understood as: the parent of mary is bill and the parent of john is mary.

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

These two lines describe the rules that define the ancestor relationship. A rule consists of two main parts separated by the :- symbol. The part to the left of this symbol is the head of the rule, the part to the right is the body. A rule is read (and can be intuitively understood) as <head> if it is known that <body>. Uppercase letters stand for variables. Hence in the example, the first rule can be read as X is the ancestor of Y, if it is known that X is the parent of Y. The second rule can be read as X is the ancestor of Y, if it is known that X is the parent of some Z, and Z is the ancestor of Y. The ordering of the clauses is irrelevant in Datalog in contrast to Prolog which depends on the ordering of clauses for computing the result of the query call.

Datalog distinguishes between extensional predicate symbols (defined by facts) and intensional predicate symbols (defined by rules).[9] In the example above, ancestor is an intensional predicate symbol, and parent is extensional. Predicates may also be defined by facts and rules, and therefore neither can be purely extensional nor intensional. Any Datalog program can be rewritten into an equivalent program without such predicate symbols with duplicate roles.

?- ancestor(bill,X).

The query above asks for all that bill is ancestor of, and would return mary and john when posed against a Datalog system containing the facts and rules described above.

Free software/Open source

Written in Name Try it online External Database Description Licence
In Java IRIS<ref>Template:Citation.</ref> yes<ref>IRIS demo</ref> IRIS extends Datalog with function symbols, built-in predicates, locally stratified or un-stratified logic programs (using the well-founded semantics), unsafe rules and XML schema data types (GNU LGPL v2.1).
Jena a Semantic Web framework which includes a Datalog implementation as part of its general purpose rule engine, which provides OWL and RDFS support.<ref>Template:Cite web</ref> (Apache v2)
SociaLite<ref>Template:CitationTemplate:Dead link.</ref> SociaLite is a datalog variant for large-scale graph analysis developed in Stanford (Apache v2)
Graal<ref>Template:Citation.</ref> Graal is a Java toolkit dedicated to querying knowledge bases within the framework of existential rules, aka Datalog+/-. (CeCILL v2.1)
In C XSB A logic programming and deductive database system for Unix and MS Windows with tabling giving Datalog-like termination and efficiency, including incremental evaluation<ref>The XSB System, Version 3.7.x, Template:Citation.</ref> (GNU LGPL).
In C++ Coral<ref>Template:Citation.</ref> A deductive database system written in C++ with semi-naïve datalog evaluation. Developed 1988-1997. (custom licence, free for non-commercial use).
Inter4QL<ref>Template:Citation.</ref> an open-source command-line interpreter of Datalog-like 4QL query language implemented in C++ for Windows, Mac OS X and Linux. Negation is allowed in heads and bodies of rules as well as in recursion (GNU GPL v3).
RDFox<ref>Template:Citation.</ref> RDF triple store with Datalog reasoning. Implements the FBF algorithm for incremental evaluation. (custom licence, free for non-commercial use<ref>Template:Citation.</ref>)
Souffle<ref>Template:Citation.</ref> an open-source Datalog-to-C++ compiler converting Datalog into high-performance, parallel C++ code, specifically designed for complex Datalog queries over large data sets as e.g. encountered in the context of static program analysis (UPL v1.0)
In Python pyDatalog 11 dialects of SQL adds logic programming to python's toolbox. It can run logic queries on databases or python objects, and use logic clauses to define the behavior of python classes. (GNU LGPL)
In Ruby bloom / bud A Ruby DSL for programming with data-centric constructs, based on the Dedalus extension of Datalog which adds a temporal dimension to the logic. (BSD 3-Clause)
In Lua Datalog<ref>Template:Citation.</ref> yes<ref>Template:Citation, (compiled to JavaScript).</ref> a lightweight deductive database system. (GNU LGPL).
In Prolog DES<ref>Template:Citation.</ref> an open-source implementation to be used for teaching Datalog in courses (GNU LGPL).
In Clojure Cascalog Hadoop a Clojure library for querying data stored on Hadoop clusters (Apache).
Clojure Datalog a contributed library implementing aspects of Datalog (Eclipse Public License 1.0).
Datascript in-memory Immutable database and Datalog query engine that runs in the browser (Eclipse Public License 1.0).
In Racket Datalog for Racket<ref>Template:Citation.</ref> (GNU LGPL).
Datafun<ref>Template:Citation.</ref> Generalized Datalog on Semilattices (GNU LGPL).
In Tcl tclbdd<ref>Template:Cite conferenceTemplate:Dead link</ref> Implementation based on binary decision diagrams. Built to support development of an optimizing compiler for Tcl. (BSD).
In Haskell Dyna<ref>Template:Citation.</ref> Dyna is a declarative programming language for statistical AI programming. The language is based on Datalog, supports both forward and backward chaining, and incremental evaluation. (GNU AGPLv3).
In other or unknown languages bddbddb<ref>Template:Citation.</ref> an implementation of Datalog done at Stanford University. It is mainly used to query Java bytecode including points-to analysis on large Java programs (GNU LGPL).
ConceptBase<ref>Template:Citation.</ref> a deductive and object-oriented database system based on a Datalog query evaluator. It is mainly used for conceptual modeling and metamodeling (FreeBSD-style license). Prolog, Java.

Non-free software

  • Datomic is a distributed database designed to enable scalable, flexible and intelligent applications, running on new cloud architectures. It uses Datalog as the query language.
  • DLV is a commercial Datalog extension that supports disjunctive head clauses.
  • FoundationDB provides a free-of-charge database binding for pyDatalog, with a tutorial on its use.
  • Leapsight Semantic Dataspace (LSD) is a distributed deductive database that offers high availability, fault tolerance, operational simplicity, and scalability. LSD uses Leaplog (a Datalog implementation) for querying and reasoning and was create by Leapsight.
  • LogicBlox, a commercial implementation of Datalog used for web-based retail planning and insurance applications.
  • .QL, a commercial object-oriented variant of Datalog created by Semmle.
  • SecPAL a security policy language developed by Microsoft Research.
  • Stardog is a graph database, implemented in Java. It provides support for RDF and all OWL 2 profiles providing extensive reasoning capabilities, including datalog evaluation.
  • StrixDB: a commercial RDF graph store, SPARQL compliant with Lua API and Datalog inference capabilities. Could be used as httpd (Apache HTTP Server) module or standalone (although beta versions are under the Perl Artistic License 2.0).

Answer Set Programming

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming.In a more general sense, ASP includes all applications of answer sets to knowledge representation[1][2] and the use of Prolog-style query evaluation for solving problems arising in these applications.

The language we will focus on and give examples for will be "Prolog".

Prolog

Is a general-purpose logic programming language associated with artificial intelligence and computational linguistics.

  • Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations.
  • The language was first conceived by a group around Alain Colmerauer in Marseille, France, in the early 1970's and the first Prolog system was developed in 1972 by Colmerauer with Philippe Roussel.
  • Prolog was one of the first logic programming languages, and remains the most popular among such languages today, with several free and commercial implementations available. The language has been used for theorem proving, expert systems, type inference systems, and automated planning, as well as its original intended field of use, natural language processing.
  • Modern Prolog environments support creating graphical user interfaces, as well as administrative and networked applications.

Prolog is well-suited for specific tasks that benefit from rule-based logical queries such as searching databases, voice control systems, and filling templates.

Basic Features of Prolog

Facts

Facts are statements that describe object properties or relations between objects. Let us imagine we want to encode that Ulysses, Penelope, Telemachus, Achilles, and others are characters of Homer’s Iliad and Odyssey. This translates into Prolog facts ended with a period:

character(priam, iliad).
character(hecuba, iliad).
character(achilles, iliad).
character(agamemnon, iliad).
character(patroclus, iliad).
character(hector, iliad).
character(andromache, iliad).
character(rhesus, iliad).
character(ulysses, iliad).
character(menelaus, iliad).
character(helen, iliad).
character(ulysses, odyssey).
character(penelope, odyssey).
character(telemachus, odyssey).
character(laertes, odyssey).
character(nestor, odyssey).
character(menelaus, odyssey).
character(helen, odyssey).
character(hermione, odyssey).

Such a collection of facts, and later, of rules, makes up a database. It transcribes the knowledge of a particular situation into a logical format. Adding more facts to the database, we express other properties, such as the gender of characters:

% Male characters     % Female characters
male(priam).          female(hecuba).
male(achilles).       female(andromache).
male(agamemnon).      female(helen).
male(patroclus).      female(penelope).
male(hector).
male(rhesus).
male(ulysses).
male(menelaus).
male(telemachus).
male(laertes).
male(nestor).

You can also look at relationships between characters such as parentage:

% Fathers                  % Mothers
father(priam, hector).     mother(hecuba, hector).
father(laertes,ulysses).   mother(penelope,telemachus).
father(atreus,menelaus).   mother(helen, hermione).
father(menelaus, hermione).
father(ulysses, telemachus).

Finally, would we wish to describe kings of some cities and their parties, this would be done as:

king(ulysses, ithaca, achaean).
king(menelaus, sparta, achaean).
king(nestor, pylos, achaean).
king(agamemnon, argos, achaean).
king(priam, troy, trojan).
king(rhesus, thrace, trojan).

From these examples, we understand that the general form of a Prolog fact is: relation(object1, object2, ..., objectn).

Symbols or names representing objects, such as ulysses and penelope, are called atoms. Atoms are normally strings of letters, digits, or underscores “_”, and begin with a lowercase letter.

An atom can also be a string beginning with an uppercase letter or including white spaces, but it must be enclosed between quotes.

Thus ’Ulysses’ or ’Pallas Athena’ are legal atoms. In logic, the name of the symbolic relation is the predicate, the objects object1, object2, ..., objectn involved in the relation are the arguments, and the number n of the arguments is the arity. Traditionally, a Prolog predicate is indicated by its name and arity: predicate/arity, for example, character/2, king/3.

Terms

In Prolog, all forms of data are called terms. The constants, i.e., atoms or numbers, are terms. The fact king(menelaus, sparta, achaean) is a compound term or a structure, that is, a term composed of other terms – subterms. The arguments of this compound term are constants. They can also be other compound terms, as in:

character(priam, iliad, king(troy, trojan)).
character(ulysses, iliad, king(ithaca, achaean)).
character(menelaus, iliad, king(sparta, achaean)).

Where the arguments of the predicate character/3 are two atoms and a compound term. It is common to use trees to represent compound terms. The nodes of a tree are then equivalent to the factors of a term.

Figure below shows examples of this.

caption

Syntactically, a compound term consists of a functor – the name of the relation – and arguments. The leftmost functor of a term is the principal functor. A same principal functor with a different arty corresponds to different predicates: character/3 is thus different from character/2. A constant is a special case of a compound term with no arguments and an arity of 0.

The constant abc can thus be referred to as abc/0.

Queries

A query is a request to prove or retrieve information from the database, for example, if a fact is true. Prolog answers yes if it can prove it, meaning that the fact is in the database, or no if it cannot, meaning the fact is not in the database. The question Is Ulysses a male? corresponds to the query:

caption

This has a positive answer. A same question with Penelope would give:

?- male(penelope).
No

This returns 'no' because this fact is not in the database. The expressions male(ulysses) or male(penelope) are goals to prove. The previous queries consisted of single goals. Some questions require more goals, such as is Menelaus a male and is he the king of Sparta and an Achaean?, which translates into:

?- male(menelaus), king(menelaus, sparta, achaean).
Yes

Where “,” is the conjunction operator. It indicates that Prolog has to prove both goals. The simple queries have one goal to prove, while the compound queries are a conjunction of two or more goals:

?- G1, G2, G3, ..., Gn.

Prolog proves the whole query by proving that all the goals G1 ...Gn are true.

Logical Variables

The logical variables are the last kind of Prolog terms. Syntactically, variables begin with an uppercase letter, for example, X, Xyz, or an underscore “_”. Logical variables stand for any term; constants, compound terms, and other variables.

A term containing variables such as character(X, Y) can unify with a compatible fact, such as character(penelope, odyssey), with the substitutions X = penelope and Y = odyssey. When a query term contains variables, the Prolog resolution algorithm searches terms in the database that unify with it. It then substitutes the variables to the matching arguments.

Variables enable users to ask questions such as What are the characters of the Odyssey?

caption

Or What is the city and the party of king Menelaus? etc.

?- king(menelaus, X, Y). X = sparta, Y = achaean
?- character(menelaus, X, king(Y, Z)). X = iliad, Y = sparta, Z = achaean
?- character(menelaus, X, Y). X = iliad, Y = king(sparta, achaean)

When there are multiple solutions, Prolog considers the first fact to match the query in the database. The user can type “;” to get the next answers until there is no more solution. For example:

caption

Shared Variables

Goals in a conjunctive query can share variables. This is useful to constrain arguments of different goals to have a same value. To express the question Is the king of Ithaca also a father? in Prolog, we use the conjunction of two goals king(X, ithaca, Y) and father(X, Z), where the variable X is shared between goals:

?- king(X, ithaca, Y), father(X, Z).
X = ulysses, Y = achaean, Z = telemachus

In this query, we are not interested by the name of the child although Prolog responds with Z = telemachus. We can indicate to Prolog that we do not need to know the values of Y and Z using anonymous variables. We then replace Y and Z with the symbol “_”, which does not return any value:

?- king(X, ithaca, _), father(X, _).
X = ulysses

Data Types in Prolog

To sum up, every data object in Prolog is a term. Terms divide into atomic terms, variables, and compound terms (see Figure below).

caption

Syntax of terms may vary according to Prolog implementations. You should consult reference manuals for their specific details.

Here is a list of simplified conventions from Standard Prolog (Deransart et al. 1996):

  • Atoms are sequences of letters, numbers, and/or underscores beginning with a lowercase letter, as ulysses, iSLanD3, king_of_Ithaca.
  • Some single symbols, called solo characters, are atoms: ! ;
  • Sequences consisting entirely of some specific symbols or graphic characters are atoms: + - * / ˆ < = > ˜ : . ? @ # $ & \ ‘
  • Any sequence of characters enclosed between single quotes is also an atom, as ’king of Ithaca’.

A quote within a quoted atom must be double quoted: ’I”m’

  • Numbers are either decimal integers, as -19, 1960, octal integers when preceded by 0o, as 0o56, hexadecimal integers when preceded by 0x, as 0xF4, or binary integers when preceded by 0b, as 0b101.
  • Floating-point numbers are digits with a decimal point, as 3.14, -1.5. They may contain an exponent, as 23E-5 (23 10−5) or -2.3e5 (2.3 10−5).
  • The ASCII numeric value of a character x is denoted 0’x, as 0’a (97), 0’b (98), etc.
  • Variables are sequences of letters, numbers, and/or underscores beginning with an uppercase letter or the underscore character.
  • Compound terms consist of a functor, which must be an atom, followed immediately by an opening parenthesis, a sequence of terms separated by commas, and a closing parenthesis.

Finally, Prolog uses two types of comments:

  • Line comments go from the “%” symbol to the end of the line:
% This is a comment 
  • Multiline comments begin with a “/*” and end with a “*/”:
/* 
this is a comment
*/

Rules

Rules enable us to derive a new property or relation from a set of existing ones. For instance, the property of being the son of somebody corresponds to either the property of having a father and being a male, or having a mother and being a male. Accordingly, the Prolog predicate son(X, Y) corresponds either to conjunction male(X), father(Y, X), or to male(X), mother(Y, X). Being a son admits thus two definitions that are transcribed as two Prolog rules:

son(X, Y) :- father(Y, X), male(X).
son(X, Y) :- mother(Y, X), male(X).

More formally, rules consist of a term called the head, followed by symbol “:-”, read if, and a conjunction of goals. They have the form:

HEAD :- G1, G2, G3, ... Gn.

Where the conjunction of goals is the body of the rule. The head is true if the body is true. Variables of a rule are shared between the body and the head. Rules can be queried just like facts:

?- son(telemachus, Y).
Y = ulysses;
Y = penelope;
No

Rules are a flexible way to deduce new information from a set of facts. The parent/2 predicate is another example of a family relationship that is easy to define using rules. Somebody is a parent if s/he is either a mother or a father:

parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).

Rules can call other rules as with grandparent/2. A grandparent is the parent of a parent and is defined in Prolog as:

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

Where Z is an intermediate variable shared between goals. It enables us to find the link between the grandparent and the grandchild, a mother or a father. We can generalize the grandparent/2 predicate and write ancestor/2. We use two rules, one of them being recursive:

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

This latter pattern is quite common of Prolog rules. One or more rules express a general case using recursion. Another set of rules or facts describes simpler conditions without recursion. They correspond to boundary cases and enable the recursion to terminate.

A query about the ancestors of Hermione yields:

?- ancestor(X, hermione).
X= menelaus;
X = helen;
X = atreus;
No

Facts and rules are also called clauses. A predicate is defined by a set of clauses with the same principal functor and arity. Facts are indeed special cases of rules: rules that are always true and relation(X, Y) is equivalent to relation(X, Y) :- true, where true/0 is a built-in predicate that always succeeds. Most Prolog implementations require clauses of the same name and arity to be grouped together.

In the body of a rule, the comma “,” represents a conjunction of goals. It is also possible to use a disjunction with the operator “;”. Thus:

A :-
B
;
C.

is equivalent to

A :- B.
A :- C.

However, “;” should be used scarcely because it impairs somewhat the legibility of clauses and programs. The latter form is generally better.

Running a Program

The set of facts and rules of a file makes up a Prolog text or program. To run it and use the information it contains, a Prolog system has to load the text and add it to the current database in memory. Once Prolog is launched, it displays a prompt symbol “?-” and accepts commands from the user. Ways to load a program are specific to each Prolog implementation. A user should look them up in the reference manual because the current standard does not define them. There are, however, two commands drawn from the Edinburgh Prolog tradition (Pereira 1984) implemented in most systems: consult/1 and reconsult/1.

The predicate consult/1 loads a file given as an argument and adds all the clauses of the file to the current database in memory:

?- consult(file_name).

file_name must be an atom as, for example,

?- consult(’odyssey.pl’).

It is also possible to use the shortcut:

?- [file_name].

to load one file, for example,

?- [’odyssey.pl’].

or more files:

?- [file1, file2].

The predicate reconsult/1 is a variation of consult. Usually, a programmer writes a program, loads it using consult, runs it, debugs it, modifies the program, and reloads the modified program until it is correct. While consult adds the modified clauses to the old ones in the database, reconsult updates the database instead. It loads the modified file and replaces clauses of existing predicates in the database by new clauses contained in the file. If a predicate is in the file and not in the database, reconsult simply adds its clauses. In some Prolog systems, reconsult does not exist, and consult discards existing clauses to replace them by the new definition from the loaded file. Once a file is loaded, the user can run queries.

The listing/0 built-in predicate displays all the clauses in the database, and listing/1, the definition of a specific predicate.

The listing/1 argument format is either Predicate or Predicate/Arity:

?- listing(character/2).
character(priam, iliad).
character(hecuba, iliad).
character(achilles, iliad).
...

A program can also include directives, i.e., predicates to run at load time.

A directive is a rule without a head: a term or a conjunction of terms with a “:-” symbol to its left-hand side:

:- predicates_to_execute.

Directives are run immediately as they are encountered. If a directive is to be executed once the program is completely loaded, it must occur at the end of the file. Finally, halt/0 quits Prolog.

Syntax

A program, or database, in Prolog consists of one or more predicates; each predicate consists of one or more clauses. A clause is a base clause if it is unconditionally true, that is, it has no "if part. <program> ::= <predicate> | <program><predicate>

<predicate> ::= <clause> | <predicate><clause>

<clause> ::= <base clause> | <nonbase clause>

Two clauses belong to the same predicate if they have the same functor (name) and the same arity (number of arguments). Thus, mother(jane) and mother(jane, jim) are different predicates. <base clause> ::= <structure> .

<nonbase clause> ::= <structure> :- <structures> .

<structures> ::= <structure> | <structure> , <structures>

A structure is a functor followed by zero or more arguments; the arguments are enclosed in parentheses and separated by commas. There must be no space between the functor and the opening parenthesis! If there are no arguments, the parentheses are omitted. <structure> ::= <name> | <name> ( <arguments> )

<arguments> ::= <argument> | <argument> , <arguments>

Programming in Prolog

In Prolog, loading code is referred to as consulting. Prolog can be used interactively by entering queries at the Prolog prompt ?-. If there is no solution, Prolog writes no. If a solution exists then it is printed. If there are multiple solutions to the query, then these can be requested by entering a semicolon ;. There are guidelines on good programming practice to improve code efficiency, readability and maintainability.

Some Simple Prolog Clauses:

likes(mary,food).
likes(mary,wine).
likes(john,wine).
likes(john,mary).

The following queries yield the specified answers.

| ?- likes(mary,food). 
yes.
| ?- likes(john,wine). 
yes.
| ?- likes(john,food). 
no.
How do you add the following facts?
  1. John likes anything that Mary likes
  2. John likes anyone who likes wine
  3. John likes anyone who likes themselves

Typing in a Prolog program

Firstly, we want to type in a Prolog program and save it in a file, so, using a basic text editor such as Notepad++ or WordPad type in the following program:

likes(mary,food).
likes(mary,wine).
likes(john,wine).
likes(john,mary).
Try to get this exactly as it is
  • Don't add in any extra spaces or punctuation with the commands.
  • Don't use any capital letters - not even for people's names.
  • Make sure there's at least one fully blank line at the end of the program.
  • Don't forget the full-stops (the period at the end of each line): these are very important to Prolog.

Once you have typed this in, save it as intro.pl (Prolog files usually end with ".pl", just as Java files end with ".java" and python end with ".py").

Starting Prolog

If you are using SWI-Prolog launch the program. If you are using a command prompt type 'prolog' Either way, you should get something like the following on screen:

caption

Prolog is now running and waiting for you to type in some commands.

Loading the Program:

Writing programs in Prolog is a cycle involving

  1. Write/Edit the program in a text-editor
  2. Save the program in the text editor
  3. Tell Prolog to read in the program
  4. If Prolog gives you errors, go back to step 1 and fix them
  5. Test it - if it doesn't do what you expected, go back to step 1

We've done the first two of these, so now we need to load the program into Prolog.

The program has been saved as "filename.pl", so in your prolog window select:

File -> Consult,
load filename.pl 

wherever you just saved it. This tells Prolog to read in the file called filename.pl

you should do this every time you change your program in the text editor.

(Note, you can also do this by simply double clicking the filename.pl file. This will relaunch prolog with this "knowledge base" loaded.)


Running a query


We can now ask Prolog about some of the information it has just read in. Type in the following (and don't forget the full-stop at the end: Prolog won't do anything until it sees a full-stop)...

?      likes(mary,food). 

When you do this you should get

caption

At this point you should hit the semicolon key.

This tells the computer you wish to see any additional facts pertaining to your query.

Since there aren't any, it quits and returns "false." Indicating that there is no more information to report..

Repeat this process for each of the following.
?      likes(john,chess). 
?      likes(john,food). 

Notice that predicates and objects in Prolog are both done in lowercase letters. For objects, this is the opposite of what we were to do in Predicate Logic. Unfortunately, the opposite is also true for variables. Variables must begin with capital letters in prolog. Type in the following. Remember to hit the ; key after each response until you see no more responses.

?      likes(john,What). 
?      likes(mary,What). 
?      likes(Who,food). 
?      likes(Who,wine). 

Next, we are going to edit our knowledge base again so we need to quit prolog. To do this type:

?  halt.

(Of course, you can also just quit SWI-Prolog)

The Rules

The program we wrote in the last tutorial was a fairly small one containing few facts. Thus, it doesn't make much sense to add very many rules, but to get you started consider the following:

?     John likes anything that Mary likes 

In predicate logic this would read:

likes(Mary,something) ⇒ likes(John,something).

In prolog we write this:

likes(john,X) :-  likes(mary,X).

Notice three things that will mess you up with prolog.
  1. The implication symbol is :-
  2. We reverse the antecedent and the consequent. The consequent always comes first in prolog.
  3. The capitalization is also "backwards." Objects start with lowercase and variables start with upper case.


Add this rule you your knowledge base using your text editor. Test the impact of this rule by reloading and resubmitting the following queries against it:

?      likes(john,What). 
?      likes(mary,What). 
?      likes(Who,food). 
?      likes(Who,wine).


Let's try one more idea. Let's say that two people like each other if they share the same hobby. That is:

likes(P1,P2) :-
    hobby(P1,H),
    hobby(P2,H).

I did two things differently here. First, I took the rule and divided it out over several lines for ease of reading. Prolog has no problems with this. It knows that as long as it hasn't seen the period yet that the rule isn't over. The second is that this rule has two parts to the antecedent (remember, that we are backwards from what we are use to and those are things to the "right" of the implication symbol) that are conjoined together. In prolog the conjunction symbol (AND) is a comma.

hobby(john,cooking).
hobby(john,games).
hobby(tim,cooking).
hobby(helen,games).

You might be tempted to put the simple predicates from hobby up at the top with the predicates from likes, but if you don't do this correctly prolog will complain. Prolog wants you to keep all similar rules together. Thus, we have to have it look like it appears below:

caption

Now reload prolog, reload this file [intro]. and then make the query:

likes(john,What).

The first couple probably make sense, but in the middle you suddenly see that john likes himself (and more than once).

caption

Where does that come from? This is a little bit funny at first, but look at our rule again. It says that P1 likes P2 whenever we can find a rule that says P1 likes a certain hobby and that P2 likes the same hobby. The problem is, prolog starts binding variables to known rules and eventually discovers that hobby(john,cooking) means P1 = john and H= cooking. But then hobby(john,cooking) can also mean P2= john and H=cooking. Thus, likes(P1,P2) yields likes(john,john). Prolog isn't "smart enough" (this isn't really a sense of dumb, but a design feature in prolog) to recognize that maybe it shouldn't allow that. Instead we have to be explicit here. We need to let prolog know that P1 shouldn't be the same as P2. We do this by adding one more line to the likes/hobby rule:

caption

Resave this, rerun prolog and reload intro and you should get much better results.

Summary

A quick summary of the chapter should go here

Problem Sets

1. Slightly more complicated family tree.


                             James I
                                |
                                |
               +----------------+-----------------+
               |                                  |
            Charles I                          Elizabeth
               |                                  |
               |                                  |
    +----------+------------+                     |
    |          |            |                     |
Catherine   Charles II   James II               Sophia
                                                  |
                                                  |
                                                  |
                                               George I

Here are the resultant clauses:


 male(james1).
 male(charles1).
 male(charles2).
 male(james2).
 male(george1).

 female(catherine).
 female(elizabeth).
 female(sophia).

 parent(charles1, james1).
 parent(elizabeth, james1).
 parent(charles2, charles1).
 parent(catherine, charles1).
 parent(james2, charles1).
 parent(sophia, elizabeth).
 parent(george1, sophia).


Here is how you would formulate the following queries:

  • Was George I the parent of Charles I?
 Query: parent(charles1, george1). 
  • Who was Charles I's parent?
 Query: parent(charles1,X). 
  • Who were the children of Charles I?
 Query: parent(X,charles1). 

Now try expressing the following rules:

    M is the mother of X if she is a parent of X and is female 
    F is the father of X if he is a parent of X and is male 
    X is a sibling of Y if they both have the same parent. 

Furthermore add rules defining:

    "sister", "brother", 
    "aunt", "uncle", 
    "grandparent", "cousin" 

2. Recursion: Towers of Hanoi


The 3-disk setup is like this:


          |        |         |
         xxx       |         |
        xxxxx      |         |
       xxxxxxx     |         |
    _________________________________
    

Here's a sample:

% move(N,X,Y,Z) - move N disks from peg X to peg Y, with peg Z being the
%                 auxilliary peg
%
% Strategy:
% Base Case: One disc - To transfer a stack consisting of 1 disc from 
%    peg X to peg Y, simply move that disc from X to Y 
% Recursive Case: To transfer n discs from X to Y, do the following: 
        Transfer the first n-1 discs to some other peg X 
        Move the last disc on X to Y 
        Transfer the n-1 discs from X to peg Y
    move(1,X,Y,_) :-  
        write('Move top disk from '), 
        write(X), 
        write(' to '), 
        write(Y), 
        nl. 
    move(N,X,Y,Z) :- 
        N>1, 
        M is N-1, 
        move(M,X,Z,Y), 
        move(1,X,Y,_), 
        move(M,Z,Y,X).  

- note the use of "anonymous" variables _

Here is what happens when Prolog solves the case N=3.

    ?-  move(3,left,right,center). 
    Move top disk from left to right 
    Move top disk from left to center 
    Move top disk from right to center 
    Move top disk from left to right 
    Move top disk from center to left 
    Move top disk from center to right 
    Move top disk from left to right 
    yes

3. An example using lists:

(a) length of a list

size([],0).
size([H|T],N) :- size(T,N1), N is N1+1.

% or size([_|T],N) :- size(T,N1), N is N1+1.

| ?- size([1,2,3,4],N).
N = 4
yes
| ?- size([bill,ted,ming,pascal,nat,ron],N).
N = 6
yes
| ?- size([a, [b, c, d], e, [f | g], h], N).
N = 5
yes


(b) summing elements of a list of numbers

sumlist([],0).
ssumlist([H|T],N) :- sumlist(T,N1), N is N1+H.

(c) list membership

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

(d) reversing a list

reverse(List, Reversed) :-
         reverse(List, [], Reversed).
reverse([], Reversed, Reversed).
reverse([Head|Tail], SoFar, Reversed) :-
         reverse(Tail, [Head|SoFar], Reversed).
| ?- myreverse([a,b,c,d],X).
X = [d,c,b,a];     <- note semicolon (more solns?)
no
| ?- myreverse([a,b,c,d],[d,b,c,a]).
no
| ?- myreverse([a,b,c,d],[d,c,b,a]).
yes
  • note difference between reverse/2 and reverse/3
  • reverse/3 probably should be called reverseHelper or something else for clarity.

Top of Page - Prev Chapter - Next Chapter