901470 Prolog Pres

Prolog - Prolog - PROgramming in LOGicPROgramming in LOGic

An overview of the Prolog

Language, its structure, uses andits shortcomings!

What is PROLOG?What is PROLOG?

• Prolog is a Declarative or logical Language.Prolog is a Declarative or logical Language.• Prolog takes only facts and rules to arrive at goals.Prolog takes only facts and rules to arrive at goals.• The programmer doesn’t tell it how to solve.The programmer doesn’t tell it how to solve.• For solving logic and decision problems, Prolog is For solving logic and decision problems, Prolog is

ideal.ideal.• Typical applications: AI, Database apps, proving Typical applications: AI, Database apps, proving

theorems, symbolic evaluation (i.e. differentiation).theorems, symbolic evaluation (i.e. differentiation).

How does Prolog work?How does Prolog work?

• Prolog is based on ‘Horn Clauses’Prolog is based on ‘Horn Clauses’• Horn Clauses are a subset of ‘Predicate Horn Clauses are a subset of ‘Predicate

Logic’Logic’• Predicate logic is a way of simply defining Predicate logic is a way of simply defining

how reasoning gets done in logic terms.how reasoning gets done in logic terms.• Predicate Logic is a syntax for easily Predicate Logic is a syntax for easily

reading and writing Logical ideas. reading and writing Logical ideas.

Predicate Logic...Predicate Logic...• To transform an English sentence to Predicate Logic, To transform an English sentence to Predicate Logic,

we remove unnecessary terms.we remove unnecessary terms.• This leaves only the relationship and the entities This leaves only the relationship and the entities

involved, known as arguments.involved, known as arguments.• Ex: A pie is good = good(pie)Ex: A pie is good = good(pie)• The relation is ‘good’, the relation’s argument is ‘pie’.The relation is ‘good’, the relation’s argument is ‘pie’.• In Prolog, we call the relation’s name (e.g. “good”) In Prolog, we call the relation’s name (e.g. “good”)

the ‘Functor’. A relation may include many the ‘Functor’. A relation may include many arguments after the functor.arguments after the functor.

Rules in PrologRules in Prolog• To infer facts from other facts, Prolog uses To infer facts from other facts, Prolog uses

Rules. Rules. • The programmer defines rules similarly to The programmer defines rules similarly to

the facts.the facts.• Ex: Bill likes cars if they are red = Ex: Bill likes cars if they are red =

likes(bill, cars):- red(cars).likes(bill, cars):- red(cars).

• By the way, in prolog, ‘:-’ is pronounced ‘if’.By the way, in prolog, ‘:-’ is pronounced ‘if’.

Prolog QueriesProlog Queries• Based on the Rules and Facts, Prolog can Based on the Rules and Facts, Prolog can

answer questions we ask itanswer questions we ask it• This is known as querying the system.This is known as querying the system.• We may want to ask, “What does ali like?”We may want to ask, “What does ali like?”• In Prolog syntax, we ask: In Prolog syntax, we ask: likes(ali,What).likes(ali,What). Note: capital W on Note: capital W on whatwhat

Let we have the following clauses:Let we have the following clauses:a_kind_of(aa,ship).a_kind_of(aa,ship).a_kind_of(bb,ship).a_kind_of(bb,ship).part_of(aa,jordanian_navy). part_of(aa,jordanian_navy). part_of(bb,jordanian_navy).part_of(bb,jordanian_navy).

part_of(jordanian_navy,jordanian_governpart_of(jordanian_navy,jordanian_government). ment). a_kind_of(jordanian_government,governa_kind_of(jordanian_government,government).ment).color(ship,redcolor(ship,red).).

• Querying the FactsQuerying the Facts

Answer may be:Answer may be:

YES or NOYES or NOExample:Example:

Goal: Goal: a_kind_of(aa,ship).a_kind_of(aa,ship).

YESYES

Goal: Goal: a_kind_of(cc,ship).a_kind_of(cc,ship).

NONO

• Queries with one variable.Queries with one variable.

Example:Example:Goal: Goal: a_kind_of(aa,X).a_kind_of(aa,X).

X=shipX=ship 1 solution1 solution

• Multidirectional QueriesMultidirectional Queries

• MultimatchingMultimatching• (There are more than one solution)(There are more than one solution)

Example:Example:Goal: Goal: a_kind_of(X,ship).a_kind_of(X,ship).

X=aaX=aa X =bbX =bb 2 solution2 solution

Multicondition QueriesMulticondition Queries• (Query has many conditions)(Query has many conditions)• ExampleExample

Color (aa,X).Color (aa,X).no solution………..no solution………..

BUT can find solution by using the following query:BUT can find solution by using the following query:• A_kind_of(aa,Y),color(Y,X)A_kind_of(aa,Y),color(Y,X)• Y=shipY=ship• X=redX=red

Part I - Program Part I - Program StructureStructure

What you’ll need to know about What you’ll need to know about the layout in order to use the layout in order to use Prolog!Prolog!

Putting It Together:Putting It Together:Parts of a Prolog programParts of a Prolog program• All programs written in Prolog All programs written in Prolog

contain at least 4 parts:contain at least 4 parts:• DOMAINSDOMAINS• PREDICATESPREDICATES• CLAUSESCLAUSES• GOALSGOALS

What is DOMAIN?What is DOMAIN?• The section of code where we define The section of code where we define

the legal values for any type that is not the legal values for any type that is not defined as a standard type. This may defined as a standard type. This may include aliasing of types (renaming). include aliasing of types (renaming).

• Domain declarations can also be used Domain declarations can also be used to define structures that are not to define structures that are not defined by the standard domains.defined by the standard domains.

What are PREDICATES?What are PREDICATES?• The PREDICATES section is where we define The PREDICATES section is where we define

predicates to be used in the CLAUSES section predicates to be used in the CLAUSES section and define the domains for their arguments.and define the domains for their arguments.

• Symbolic name of a relationSymbolic name of a relation• We found it best to think of predicate We found it best to think of predicate

declarations as function prototypes. declarations as function prototypes. • Ex: age(string, integer)Ex: age(string, integer)

What are CLAUSESWhat are CLAUSES• Clauses are the heart of the program.Clauses are the heart of the program.• A clause is an instance of a predicate, A clause is an instance of a predicate,

followed by a period.followed by a period.• Clauses are of two types:Clauses are of two types:• FactsFacts• RulesRules

Clause Facts:Clause Facts:• Facts in the CLAUSE section are relations Facts in the CLAUSE section are relations

that are known to be true by the that are known to be true by the programmer. programmer.

• Self standing basis for inferenceSelf standing basis for inference• A property of an object or a relation A property of an object or a relation

between objects.between objects.• Ex: red(car)Ex: red(car)

Clause Rules:Clause Rules:• Used to infer other factsUsed to infer other facts• Property or relation known given the fact Property or relation known given the fact

that some other set of relations are that some other set of relations are known.known.

• Ex: Jane can eat food if it is a vegetable Ex: Jane can eat food if it is a vegetable on the doctor’s list.on the doctor’s list.

• Can_eat(jane, X):- food(X), vegetable(X), Can_eat(jane, X):- food(X), vegetable(X), doc_list(X).doc_list(X).

What are GOALS:What are GOALS:

• Part of program where queries are made.Part of program where queries are made.• Can be singular or compound.Can be singular or compound.• Each part of a compound goal is known Each part of a compound goal is known

as a subgoal. as a subgoal. • To satisfy a compound goal (or query) To satisfy a compound goal (or query)

each subgoal must itself be satisfied by each subgoal must itself be satisfied by the system.the system.

Compound GoalsCompound Goals• Useful when we want to find Conjunction or Useful when we want to find Conjunction or

Disjunction of a number of goals.Disjunction of a number of goals.• Ex: What are the things do Bill Ex: What are the things do Bill andand Cindy both Cindy both

like (in common)?like (in common)?• In Prolog: In Prolog:

likes(bill, What), likes(cindy, What).likes(bill, What), likes(cindy, What).

• Similarly, we use ‘;’ as an OR for system Similarly, we use ‘;’ as an OR for system queries. (Note: AND takes precedence over OR queries. (Note: AND takes precedence over OR in multiple subgoal cases.)in multiple subgoal cases.)

Part II: Syntax and Part II: Syntax and SemanticsSemantics

Making sense of some Prolog Making sense of some Prolog code - much of this is likely code - much of this is likely compiler specific. Variables, compiler specific. Variables, wild card, terms, statement wild card, terms, statement delimiters - facts by ., lists, delimiters - facts by ., lists, compound data objects and compound data objects and functors. AND OR, arithmetic functors. AND OR, arithmetic (integer and real (infix (integer and real (infix notation), order of operations, notation), order of operations, comparison, no loops all comparison, no loops all recursionI/O.recursionI/O.

TermsTerms• Prolog programs are composed of terms.Prolog programs are composed of terms.• Terms are Terms are constantsconstants,, variables variables, or , or structuresstructures. . • ConstantsConstants are names for specific objects or are names for specific objects or

relationships. The two types are Atoms and integers. relationships. The two types are Atoms and integers. The :- symbol is also considered an atom.The :- symbol is also considered an atom.

• Atoms are things which must begin with a lowercase Atoms are things which must begin with a lowercase letter and may be followed by digits, underscores or letter and may be followed by digits, underscores or any case letters. any case letters.

• If needed, an atom may contain anything and be place If needed, an atom may contain anything and be place inside ‘ ’.inside ‘ ’.

VariablesVariables• Variables are any string that begins with Variables are any string that begins with

an uppercase sign or an underscore.an uppercase sign or an underscore.• Variables stand for something that cannot Variables stand for something that cannot

be named at the current time.be named at the current time.• The single ‘_’ is considered the anonymous The single ‘_’ is considered the anonymous

variable. It means don’t care. variable. It means don’t care. • Variables are instantiated (bound to Variables are instantiated (bound to

values) as the program progressesvalues) as the program progresses

Atom and Variable Atom and Variable Examples:Examples:• Atom Examples:Atom Examples: a_boy, peanut, ‘Jack-a_boy, peanut, ‘Jack-

Smith’, i12345.Smith’, i12345.• Not Atoms:Not Atoms: 231as, Jack-Smith, _crack.231as, Jack-Smith, _crack.• Variables Examples:Variables Examples: Answer, X, I_like, Answer, X, I_like,

_Marbles._Marbles.• Not Variables:Not Variables: mother, 3blind_mice.mother, 3blind_mice.

StructuresStructures• Structures represent the atomic proposition of predicate Structures represent the atomic proposition of predicate

calculus. The general form is calculus. The general form is functor(parameter list).functor(parameter list).

• Facts, and relations and rules are considered structures.Facts, and relations and rules are considered structures.• Compound structures – a structure can contain Compound structures – a structure can contain

substructures. E.g. instead ofsubstructures. E.g. instead ofdrives(john,car)drives(john,car)

we could havewe could havedrives(john,car(mercedes))drives(john,car(mercedes))

which can greatly aid readability.which can greatly aid readability.

Arithmetic in PrologArithmetic in Prolog

• Prolog provides built in functions for doing Prolog provides built in functions for doing arithmetic, similar to most major languages.arithmetic, similar to most major languages.

• Provides built in random number generator.Provides built in random number generator.• Integers and reals have standard operations Integers and reals have standard operations

defined (*,/,+,-) defined (*,/,+,-) • In-fix notation is used In-fix notation is used

Arithmetic continuedArithmetic continued

Order of operations (for all types):Order of operations (for all types):1. Parentheses1. Parentheses2. Left to right *, /, div, mod2. Left to right *, /, div, mod3. Left to right +, -3. Left to right +, -

Other Arithmetic Other Arithmetic Functions:Functions:X mod YX mod YReturns the remainder (modulos) of X divided by Y.Returns the remainder (modulos) of X divided by Y.X div YX div YReturns the quotient of X divided by Y.Returns the quotient of X divided by Y.abs(X)abs(X)If X is bound to a positive value val, If X is bound to a positive value val, abs(X)abs(X) returns that value; otherwise, it returns -1 * val. returns that value; otherwise, it returns -1 * val.cos(X)cos(X)The trigonometric functions require that X be bound toThe trigonometric functions require that X be bound tosin(X)sin(X)a value representing an angle in radians.a value representing an angle in radians.tan(X)tan(X)Returns the tangent of its argument.Returns the tangent of its argument...  

More Functions! More Functions! exp(X)exp(X)

e raised to the value to which X is bound.e raised to the value to which X is bound.ln(X)ln(X)

Logarithm of X, base e.Logarithm of X, base e.log(X)log(X)

Logarithm of X, base 10.Logarithm of X, base 10.sqrt(X)sqrt(X)

Square root of X.Square root of X.random(X)random(X)

Binds X to a random real; 0 <= X < 1.Binds X to a random real; 0 <= X < 1.random(X, Y)random(X, Y)

Binds Y to a random integer; 0 <= Y < X.Binds Y to a random integer; 0 <= Y < X.trunc(X)trunc(X)

Truncates X. The result still being a realTruncates X. The result still being a realval(domain,X)val(domain,X)

Explicit conversion between numeric domainsExplicit conversion between numeric domains

Assignment vs. Comparison Assignment vs. Comparison (=)(=)Ex:Ex:

X = Y+Z*20.X = Y+Z*20.

The variable X is assigned the value Y+Z*20 if X is uninstantiatedThe variable X is assigned the value Y+Z*20 if X is uninstantiatedX is compared to Y+Z*20 if X has been instantiated earlier on.X is compared to Y+Z*20 if X has been instantiated earlier on.(i.e. There is no == for comparison. Tricky. Compiler specific.)(i.e. There is no == for comparison. Tricky. Compiler specific.)Some dialects of prolog use ‘is’ for assignment and = for Some dialects of prolog use ‘is’ for assignment and = for

comparison.comparison.

Relational operations Relational operations return succeed or failreturn succeed or fail

SymbolSymbol RelationRelation<< Less thanLess than>> Greater thanGreater than>>== Greater or equalGreater or equal<=<= Less than or Less than or

equalequal<> Or ><<> Or >< Not equal Not equal

Types available for Types available for ComparisonComparison

• Prolog the previous operations for comparison on Prolog the previous operations for comparison on integers and reals (duh), strings, characters and integers and reals (duh), strings, characters and symbols.symbols.

• Characters are converted to ASCII values which are Characters are converted to ASCII values which are then compared. then compared.

• Strings are compared character by character until a pair Strings are compared character by character until a pair are not equal. Shorter strings are considered < larger are not equal. Shorter strings are considered < larger strings. strings.

• Symbols cannot be compared directly due to storage Symbols cannot be compared directly due to storage mechanism. They must first be bound to variables or mechanism. They must first be bound to variables or written as strings.written as strings.

I/O I/O • I/O can be performed on virtually any I/O can be performed on virtually any

device. Standard is keyboard/video.device. Standard is keyboard/video.• Prolog uses write, readln, readint, readch, Prolog uses write, readln, readint, readch,

readreal (some other readtypes as well – readreal (some other readtypes as well – all are covered – many compatible). all are covered – many compatible).

EX: EX: GOAL GOAL

write(“Enter an integer!”),write(“Enter an integer!”),readint(Int),readint(Int),

LoopsLoops

• Prolog provides no support for loops, though Prolog provides no support for loops, though it can be ‘tricked’ into looping. Ex: it can be ‘tricked’ into looping. Ex:

CLAUSESCLAUSES repeat.repeat. repeat:-repeat.repeat:-repeat.typewriter:-typewriter:- repeat,repeat, readchar(C),readchar(C),write(C),write(C),C = '\r',!.C = '\r',!.

RecursionRecursion

• Repetition is normally done through Repetition is normally done through recursion. The standard example is:recursion. The standard example is:factorial(1, 1) :- !.factorial(1, 1) :- !.

factorial(X, FactX) :-factorial(X, FactX) :-Y = X-1,Y = X-1,

factorial(Y, FactY),factorial(Y, FactY),FactX = X*FactY.FactX = X*FactY.

Part III: Data typesPart III: Data types

Description of Prolog’s built-in Description of Prolog’s built-in data types and which are data types and which are compatible.compatible.

Data TypesData Types•CharCharA character, implemented as an unsigned byte. Syntactically, it is written as a character surrounded by single quotation marks: 'a'.

•RealRealA floating-point number, implemented as 8 bytes in accordance with IEEE conventions; equivalent to C's double.

Data Types Data Types

• StringString A pointer to a null terminated sequence of

characters (as in C), defined by:1. a sequence of letters, numbers and

underscores, provided the first character is lower-case; or

2. a character sequence surrounded by a pair of double quotation marks.

Data TypesData Types• IntegerInteger A signed quantity, having the natural size for

the machine/platform architecture in question.

• SymbolSymbolA sequence of characters, implemented as a pointer to an entry in a hashed symbol-table, containing strings. The syntax is the same as for strings.

Data TypesData Types

• List List The Prolog equivalent to arrays.

Lists in prolog are, however, dynamic and similar to LISP in that you can only use equivalents to access elements. [Head|Tail]

Data TypesData Types

• Other built in Domains (probably compiler Other built in Domains (probably compiler specific!) specific!)

short, ushort, long, ulong, unsigned, byte, word, dword.

These are mostly similar to their C counterparts. Note: No operator overloading is permitted in Prolog! (see reason for =<)

Part IV: Crazy Things in Part IV: Crazy Things in PrologProlog

Backtracking, Cuts, Fails, Dynamic Backtracking, Cuts, Fails, Dynamic Facts!Facts!Lets get Crazy!Lets get Crazy!

BacktrackingBacktracking• The process used by Prolog to re-satisfy goalsThe process used by Prolog to re-satisfy goals• When a goal or subgoal fails, Prolog attempts When a goal or subgoal fails, Prolog attempts

to re-satisfy each of the subgoals in turn.to re-satisfy each of the subgoals in turn.• When no other subgoals can be satisfied, it When no other subgoals can be satisfied, it

attempts to find an alternative clause for the attempts to find an alternative clause for the goal. Variables are returned to their original goal. Variables are returned to their original values.values.

• Proceeds to satisfy any alternate clauses.Proceeds to satisfy any alternate clauses.

BacktrackingBacktracking• Example:Example:male(alan).male(alan).male(gary).male(gary).female(margaret).female(margaret).parent(alan, gary).parent(alan, gary).parent(alan, margaret).parent(alan, margaret).mother(X,Y) :- parent(X,Y), female(X).mother(X,Y) :- parent(X,Y), female(X).father(X,Y) :- parent(X,Y), male(X).father(X,Y) :- parent(X,Y), male(X).

Goal: Goal: ?- mother(alan,Z)?- mother(alan,Z)

The “Cut”The “Cut”• Syntactically described by !Syntactically described by !• Special mechanism which controls (prevents) Special mechanism which controls (prevents)

backtracking.backtracking.• As a goal, the “cut” always succeeds and cannot As a goal, the “cut” always succeeds and cannot

be re-satisfied be re-satisfied • Similar to GOTO – powerful but usually uglySimilar to GOTO – powerful but usually ugly• Once a “cut” is encountered, backtracking Once a “cut” is encountered, backtracking

cannot retreat past this pointcannot retreat past this point• Two types: Red cut and a Green cut.Two types: Red cut and a Green cut.

Green Cuts!Green Cuts!A ‘Green Cut’ is when:A ‘Green Cut’ is when:• You incorporate a cut when you know that You incorporate a cut when you know that

after a certain stage in the clauses, no new after a certain stage in the clauses, no new meaningful solutions will be generatedmeaningful solutions will be generated

• You can save time and memory by You can save time and memory by eliminating extraneous searching that the eliminating extraneous searching that the system would otherwise need to discover system would otherwise need to discover on its own, the hard way.on its own, the hard way.

• The program would run fine without the The program would run fine without the cut, it is merely an optimization.cut, it is merely an optimization.

Red Cut!Red Cut!

• Changes the logic of a programChanges the logic of a program• Correct solutions depend on using Correct solutions depend on using

the cut for omitting certain subgoals the cut for omitting certain subgoals from being considered.from being considered.

• Makes for much worse readability Makes for much worse readability and maintainability. and maintainability.

The “The “GreenGreen Cut” Example Cut” Example• Example: trapping the input.Example: trapping the input.

CLAUSESCLAUSES

r(X) :- X = 1 , !, write(“you entered 1.”).r(X) :- X = 1 , !, write(“you entered 1.”). r(X) :- X = 2 r(X) :- X = 2 , ! ,write(“you entered 2.”)., ! ,write(“you entered 2.”). r(X) :- X = r(X) :- X = 3 , ! ,write(“you entered 3.”).3 , ! ,write(“you entered 3.”). r(_) :- write("This r(_) :- write("This is a catchall clause.").is a catchall clause.").

GOALGOAL

r(1).r(1).

The “The “RedRed Cut” Example Cut” Example• Example: Library access! Example: Library access! (from Programming in Prolog 2(from Programming in Prolog 2ndnd Ed. P. Ed. P.

76.)76.)CLAUSESCLAUSES

facility(Pers, Fac):- book_overdue(Pers, facility(Pers, Fac):- book_overdue(Pers, Book),!,basic_facility(Fac).Book),!,basic_facility(Fac).

facility(Pers, Fac):-general_facility(Fac).facility(Pers, Fac):-general_facility(Fac).

basic_facility(reference).basic_facility(reference). basic_facility(enquiries).basic_facility(enquiries).

additional_facility(borrowing).additional_facility(borrowing). additional_facility(inter_library_loan).additional_facility(inter_library_loan).

general_facility(X):-basic_facility(X).general_facility(X):-basic_facility(X). general_facility(X):-general_facility(X):-additional_facility(X).additional_facility(X).

book_overdue(‘A. Webb’, book69).book_overdue(‘A. Webb’, book69).

GOALGOAL

facility(A. Webb,Y).facility(A. Webb,Y).

FailFail• Another built in predicate used for controlling Another built in predicate used for controlling

the backtracking process. the backtracking process. • Can be used in the GOAL or CLAUSES sectionsCan be used in the GOAL or CLAUSES sections• Essentially the opposite of the cut.Essentially the opposite of the cut.• Causes a forced failure in a chain of goalsCauses a forced failure in a chain of goals• Equivalent to adding an impossible goal. Equivalent to adding an impossible goal. (Ex. (Ex.

2=3)2=3)• Encourages backtracking to continue.Encourages backtracking to continue.

Fail Example:Fail Example:• Nicer output:Nicer output:CLAUSESCLAUSES

father(leonard,katherine).father(leonard,katherine). father(jack, christine).father(jack, christine).father(leonard, jane).father(leonard, jane).

list_dads:-father(X,Y),list_dads:-father(X,Y), write(X," is ",Y,"'s father\write(X," is ",Y,"'s father\n"),n"),

fail.fail.

list_dads.list_dads.

GOALGOAL

list_dads. list_dads.

That’s all.That’s all.