Prolog Execution
Call: Call a predicate(invocation)
Exit: Return an answer to the caller
Fail: Return to caller with no answer
Redo: Try next path to find an answer
Use of XSB
- Put your ruleset and data in a file with extension .P (or .pl)
1 | p(X) :- q(X, _). |
Don’t forget: all rules and facts end with a period (.)
Comments: / / or % …
Loading your program, myprog.P
1
?- [myprog].
XSB will compile myprog.P (if necessary) and load it. Now you can type further queries, e.g.
1
2?- p(X).
?- p(1).Some Useful Built-ins:
- write(X) - write whatever X is bound to
- writeln(X) - write then put newline
- nl - output newline
- Equality: =
- Inequality: \=
Some Useful Tricks:
XSB returns only the first answer to the query. To get the next, type ‘;
‘ Usually, typing the ;’s is tedious. To do this programmatically, use this idiom:
1
?- (q(_X), write('X='), writeln(_X), fail; true).
_X here tells XSB to not print its own answers, since we are printing them by ourselves. (XSB won’t print answers for variables that are prefixed with a _.)
Syntax of Prolog Programs
A Prolog program is a sequence of clauses.
Each clause (
sometimes called a rule or Horn rule) is of the form:Head :- Body.
Head is one term.
Body is a comma-separated list of terms.
A clause with an empty body is called a fact.
A clause is also sometimes called a rule.
- Most statements can be written many ways
- That’s great for people but a nuisance for computers
- It turns out that if you make certain restrictions on the format of statements you can prove theorems mechanically
- Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.
- That’s what logic programming systems do
Logic Programming Concepts
- The Prolog interpreter has a colleciton of facts and rules in its DATABASE
- Prolog provides an automatic way to deduce true results from facts and rules
- Query or goal(i.e., a clause with an empty head)
- So, rules are theorems that allow the interpreter to infer things
- The scope of a variable is the clause in which it appears:
- Variables whose first appearance is on the
left hand side of the clause (i.e., in the head) have implicit universal quantifiers
- Variables whose first appearance is on the
Operators
- conjunction
- disjunction
- negation
- implication
Universal and existential quantifiers
Statements
- sometimes true, sometimes false, sometimes unknown
- Axioms - assumed true
- theorems - provably true
- Goals - things we’d like to prove true
Recursion
Transitive closure
Example: a graph declared with facts (true statements)
edge(1,2).
edge(2,3).
edge(2,4).
if there is an edge from X to Y, we can reach Y from X:
reach(X, Y):- edge(X, Y)/
if there is an edge from X to Z, and we can reach Y from Z, then we can reach Y from X:
reach(X, Y):-
edge(X, Z),
reach(Z, Y).
Prolog Programs
- Syntax of Prolog Programs
- A program is a sequence of clauses (Horn rules).
- Each clause is of the form
head:- body.- Head is one
term.- Body is a
comma-separated list of terms.- A clause with an empty body is called a
fact.- A clause is also sometimes called a
rule.
Terms
Atomic data
- Numeric constants: integers, floating point numbers
- Atoms:
- Identifiers: sequence of letters, digits, underscore, beginning with a lower case letter (e.g. paul, r2d2, one_element).
- Strings of characters enclosed n single quotes (e.g. ‘Stony Brook’).
Variables
Variables are denoted by identifiers beginning with an Uppercase letter or underscore (e.g. X, Index, _param).
These are Single-Assignment Logical variables:
- Variables can be assigned only once, but that value can be further refined
- Different occurrences of the same variable in a clause denote the same data.
Variables are implicitly declared upon first use.
- Variables are not typed
- All types are discovered implicitly (no declarations in LP)
- If the variable does not start with underscore, it is assumed that it appears multiple times in the rule.
- If it does not appear multiple times, then a warning is produced: “Singleton variable”
- You can use variables proceded with underscore to eliminate this warning.
Anonymous variables (also called Don’t care variables):
variables beginning with “_”
- Underscore, by itself (i.e., _), represents a variable
- Each occurrence of _ corresponds to a different variable; even within a clause, _ does not stand for one and the same object.
- A variable with a name beginning with “_”, but has more characters. e.g.: _radius, _size
- We want to give it a descriptive name
- sometimes it is used to create relationships within a clause (and must therefore be used more than once): a warning is produced: “Singleton-marked variable appears more than once”
Warnings are used to identify bugs (most because of copy-paste errors)
- Instead of declarations and type checking
- Fix all the warnings in a program, so you know that you don’t miss any logical error
Structures
Logic Programming Queries
To run a Prolog program, one asks the interpreter a question
- This is done by asking a query which the interpreter tries to prove:
- If it can, it says yes
- If it can’t, it says no
- If your query contained variables, the interpreter prints the values it had to give them to make the query true.
Meaning of Logic Programs (Semantics)
Declarative Meaning
What are the logical consequences of a program?
- Logical consequence of a program L is the smallest set such that
- All facts of the program are in L
- If H:- B1, B2, …, Bn is an instance of a clause in the program such that B1, B2, …, Bn are all in L, then H is also in L.
Procedural Meaning
For what values of the variables in the query can I prove the query?
- The user gives the system a goal:
- The system attempts to find axioms + inference steps to prove goal.
- If goal contains variables, then also gives the values for those variables.
- A query is, in general, a conjunction of goals: G1, G2, …, Gn
- To prove G1, G2, …, Gn:
- Find a clause H:- B1, B2, …, Bk such that G1 and H match.
- Uder the substitution for variables, prove B1, B2, …, Bk, G2, …, Gn
- If nothing is left to prove then the proof succeeds
- If there are no more clauses to match, the proof fails
- The Prolog interpreter works by what is called BACKWARD CHAINING (also called top-down, goal directed)
- It begins with the thing it is trying to prove and works backwards looking for things that would imply it, until it gets to facts.
- It is also possible to work forward from the facts trying to see if any of the things you can prove from them are what you were looking for
- This methodology is called bottom-up resolution
- It can be very time-consuming
- When it attempts resolution, the Prolog interpreter pushes the current goal onto a stack, makes the first term in the body the current goal, and goes back to the beginning of the database and starts looking again
- If it gets through the first goal of a body successfully, the interpreter continues with the next one
- If it gets all the way through the body, the goal is satisfied and it backs up a level and proceeds
- The Prolog interpreter starts at the beginning of your database (this ordering is part of Prolog, NOT of logic programming in general) and looks for something with which to unify the current goal
- If it finds a fact; it succeeds,
- If it finds a rule, it attempts to satisfy the terms in the body of the rule depth first
- If it fails to satisfy the terms in the body of a rule, the interpreter undoes the unification of the left hand side (BACKTRACKING) (this includes un-instantiating any variables that were given values as a result of the unification) and keeps looking through the database for something else with which to unify
- If the interpreter gets to the end of database without succeeding, it backs out a level (that’s how it might fail to satisfy something in a body) and continues from there