[CSUSB] >> [CompSci] >> /u/faculty/dick/cs320/prolog/intro.prolog

How to run SWI Prolog

For a quick experiment just type `pl` at the UNIX prompt:
    $ pl
To compile Prolog files type:
    $ pl -c file1 -c file2 ...
where file1, file2, ... contain Prolog programs which are to be compiled. 
The result is put in a.out  If a syntax error occurs in a file, the error
message will include the name of the file and the number of the line in
which it occurred. Or type:
    $ pl -o program -c file ...
to output the compiled program into program.  If the Prolog program is in
a single file and the file's suffix is .pl then Q/quickie can compile and
run  it.
 
When the program is running it responds with a 
	?- 
prompt.  The user then enters queries.   Each query must terminate with a
period.  A query can be any valid statement.  Type a CTRL/D to exit (hold
down CTRL and tap the D).

Try it:
(type underlined parts)
	....$ pl
	      ==

	?- write('hello, world').
	   ====================== (don't forget the .)
	?- CTRL/D
	   ======
or input the query:
	?- halt.
	   ======
 

Useful Commands

Try these useful commands out to gat a feel of the system....
Start up Prolog and the input the following (without the `?-` prompt!)

To look at the program/database:
	?- listing.
 
To look at a definition use `listing`:
	?- listing(member).
	?- listing(member).
	?- listing(listing).
	?- listing(help).
 
To ask for help use `help`:
	?- help.
 
To ask for help on a predicate etc:
	?- help(print).
	?- help(listing).
 
To look for help on a topic:
	?- apropos(file).
	?- apropos(addition).
	?- apropos(list).

To load a program from a file inside Prolog, give the query:
	?- consult(Name).
which will instruct the system to find and read the file 'Name.pl'. The
search starts in the standard library and then the local directory etc.
 
To edit a definition:
	?- ed(Name).
 
To add to the program/database:
	?- assert(Clause).
 

Constants or Variables?

A variable starts with a capital letter. A constant with a
lower case letter.  So x = 2 is false because little 'x' is a constant not a variable.  X=2 may bee troue or false depending on what (if any) value is
already bound to X.


Responses to Commands and Queries

Prolog has already got a `predicate` "member" that matches
an item against a list:
	member( Item, List ).
A List in Prolog is written like this:
	[ Item1, Item2, Item3, ...]
You can also have:
	[ Item1 | TheRestOfTheList ]

The command:
?- member(3,[1,2,3]), write(ok).
makes Prolog check whether 3 belongs to the list [1, 2, 3], and to output
"ok" if so.  So 'member' can be used to test for membership.  The program
then waits for ';' (Prolog for "or"), and will then search for another
solution.  If no solution  can  be found,  the system simply returns "No"
and a '?-' prompt.
 
If a variable is included it is displayed:
?- member(X, [tom, dick, harry]).
X = tom <Return>
?-
Notice above that we can use 'member' above as a condition
that can be true or false, and a command that does something.
This is a general rule:  When you write a procedure it is
more as useful in Prolog than in many languages because it also
a condition.
 
Prolog will generate a series of values:  
?- member(X, [tom, dick, harry]).
X = tom ;
X = dick ;
X = harry ;
No

Prolog backtracks and will redo a predicate if a later predicate fails:
?- member(X,[1,2,3,4,5,6,7,8,9]),  member(Y,[1,2,3]), X is Y*Y.
Y = 1
X = 1 ;
Y = 4
X = 2 ;
Y = 9
X = 3 ;
No.
?-
 

Execution And Interruption

Execution of a predicate starts when you input it as a query.  Only when 
execution  is  complete  does the program  become  ready  for  another 
directive. However, one may interrupt the normal execution of a directive
by typing CTRL/C. This interrupt signal has the  effect  of terminating
the execution of the command.  Prolog will then respond with a prompt.
 
Execution may also be terminated if the program runs out of stack space. 
Warning: make sure that the reason the program ran out of stack space was
not due to an error in your program before increasing the size.
 

Tracing

Prolog interpreter provides a tracing facility.  This turned on by input:
?- trace, query. 
and stays on for that one query only.  Predicates may be individually
traced enabling each event involving the predicate to be displayed on the
terminal with the  current values  of  its  arguments.
 
The events traced 
      Call      Exit      Fail      Redo
 
 `Call' indicates that a predicate is being called for the first time.  A
line beginning with `Exit' shows the interpreter exiting a clause after
all the goals have been satisfied. `Fail' indicates an exit from a clause
due to a failure in satisfying a goal.  After a failure, Prolog will
attempt to redo an earlier predicate if there are alternative clauses left
in the predicate definition.  This is shown by a `Redo'.
 
After reporting the program waits for one of a number of actions by the
user - 'h' gives a list of possibilities, 'a' aborts execution and tapping
return lets the program continue An example of tracing output is shown
below:
	?- trace. member(X, [1,2]).
 

Programs

A  program  is  made  up  of  a sequence  of  clauses, directives, and
comments.  The text of a program is normally created separately in a file
(or files), using an editor.
 
Any characters following the `%' character on any line are treated as part
of a comment and are ignored.
 
Directives are ways of directing the compiler to execute some goal or
goals during the compilation process. Typically like this:
	:-op( =>, xfx, 9000).
 
 

Syntax

A program is a set of definitions, the data is a set of definitions, and
even the queries are input using the same notation!  In  Prolog: data and
program are stored using the same notation and in the same structure.  
The basic notation is a predicate  in "functorial form":
	functor ( part, part, part, ... ).
It is stored like a record structure.  Its meaning varies depending on the
context - it can be a data structure, program, or an axiom.  A form like
this
	has('Jim', 'red hair')
is a tree with `has` at the top and `'Jim''`, and `'red hair'` at the
bottom.  Normally Prolog treats an expression as a a tree with as well. 
So `1+B` has a `+` at the top and `1` and `B` as leaves.  Prolog lists a
shown like this:
	[element,element,....]
 
A definition is made of `clauses`:
	predicate:-predicate, predicate,.... .
and each predicate is as above above.  The clauses of a predicate do not
have to be immediately consecutive, but their  relative  order  may be 
important.  
 

Operators and precedences

Prolog already understands mathematical style operators.  Prefix, infix
and postfix operators can be defined:
fx	prefix	( - X, good X))
xfx,...	infix   	(P:-Q, X + Y, X has Y)
xf	postfix	( X!,  X?)
 

Variables vs constants

In Prolog a variable has an uppercase letter or an underscore(_) as its
first character.  All other identifiers, operators,  and numbers are
atomic constants.  An identifier (starting with a lower case letter) is
called an atom.  Strings are also constants.  Single quoted strings 'A123'
are treated like an atom - even if they begin a capital letter.  Double
quoted strings indicate an array of integers for the ASCII  numbers of the
contents of the string.  
 
 

Semantics of Variables

All variables are temporary and local.   Prolog works by searching for
values for its variables.  Each value is called an instance.  Prolog links
the instance to a variable.  It can also link equal variables to each
other.  But these links are temporary and will be undone.  It keeps adding
facts and deducing values until it has got all the facts(success) or until
it can not find a value that fits a variable, or it would have to change a
value of a variable!
 
Once an instance has been found it is fixed until Prolog is forced to go
back and undo the command that found it.  At the end of a search(backtrack
or success) all variables loose their values.   The only permanent storage
is for facts and definitions in the database.  'Assert' and 'retract'
manipulate these. 
 

Unification

Variables get temporary values by a process called unification. 
Alternative definitions can uncover new temporary values.  Each is an 
instance and the variable is then said to be instanciated.
 
Unification forces two expressions to match by (1) instanciating variables
as constants, and (2) linking variable together.  This is done, piece by
piece, throughout the two expressions, in parallel.  For example `X+Y*3`
matches `1+X*Z` when `X=Y=1` and`Z=3`.  Unification does NOT evaluate
expressions.
 
Prolog uses unification whenever it calls a predicate. The name of the
predicate is found in the data base and the arguments in the data base are
unified with the arguments in the call.   So if 
	a(1). a(2).
is in the data base
the query:
	?- a(X).
will generate
	X=1
Tapping ';' (or) gives
	X=2
in turn.
 

Equality

It as if the fact
	X=X
is the only fact on file. The query 
	?- A=1+B, B=3.
first invokes X=X with X unified to A and 1+B.  So,  A=1+B.  Then B
unified with X, and X with 3.  So A=1+3  and B=3.  The `1+3` is not
evaluated, So,
	B=3
	A=1+3
is output.  
 

Evaluating Expressions

Normally Prolog treats an expression like `1+B` as a data structure and
does not evaluate it.  However, the operator `is` does evaluate its right-
hand expression:
	?- B=3, A is 1+B.
A is instanciated to 4 rather than 1+3. The same thing happens here:
	?- C = 1+B, B=3, A is C.
Evaluation only occurs in certain predicates:
	is,<,>,<=,=\=,=:=, >,=<,...
In `X is E` the E is evaluated and X becomes the value or else X's value
tested vs. result.  Evaluation is on the RHS of 'is' only.  In these
E1<E2, E1<=E2, E1 =:= E2, E1=\=E2,   E1>E2, and   E1>=E2,  E1 and E2 are
evaluated and compared. 
 

Semantics of Clauses

In other languages you define new functions and procedures.  In Prolog
you use "clause" to describe ideas that can be used as either
data or procedures.  They have two forms:
	name(arguments).
and
	name(arguments):-body.
They are put into Prolog's database by the "assert" command.

Prolog treats a clause in the database like this
	e(0).
as a fact that matches a query like e(0) and e(X) but not e(1) or e(x). 
It matches e(0) to e(X) by instanciating X to 0.
(This will be run through in lab1)
 
A clause like this
	e(N):- N>1, M is N-2, e(M).
can be read `e(N) is true if N >0 and M is N-1 and e(M) is true`. Prolog
executes it like procedure call.  First Prolog matches arguments, then it
executes each item in the list in turn.  The whole clause fails if any item
fails.

The query:
	?- e(4).
matches it with N=4, and so executes in turn:
		4>0
		M=2
and then calls e(2).
 

Semantics of Definitions

A definition is a series of clauses stored in the data base.  These
declare alternative possibilities.  Prolog searches them for a clause that
matches the current goal.  For example, if
	e(0).
	e(N):- N>1, M is N-2, e(M).
	e(N):- N<0, write('error'), fail.
is in the data base, and you ask
	?- e(1).
Prolog first finds `e(0)` which does not match `e(1)`.  It then finds e(N)
and matches with N=1.  But 1 is not > 1,  then it tries the next clause
but finds the 1<0 is false.  And so concludes the e(1) is false.

If you test e(3) then Prolog finds that it matches the second clause with
N=3, and tries out: 3>1, M is 3-1, e(M). This means Prolog tries out
e(1).  But we know that this will fail.
 
The call e(-1) fails to match e(0), then matches e(N), but N>0 fails.  So 
the last clause is executed, and an error message is produced before the
whole definition fails.

Condition or Action?

Most Prolog statements are both a condition and an action depending on how
they are invoked.  For example:
	1 = 2	is false
and	X = 2	is false if X is 1 already.
But 	X = 2   is true and sets X to 2 if X has no value yet.