perm filename TUTORI.LPT[PRO,LOG] blob sn#620882 filedate 1981-10-28 generic text, type T, neo UTF8
```
This file is <f.prolog>tutorial.*

A PROLOG TUTORIAL
A PROLOG TUTORIAL
A PROLOG TUTORIAL
BASED ON
BASED ON
BASED ON
USER'S GUIDE TO DECSYSTEM-10 PROLOG  [3]
USER'S GUIDE TO DECSYSTEM-10 PROLOG  [3]
USER'S GUIDE TO DECSYSTEM-10 PROLOG  [3]

Prepared by

Ernie Davis   and   Udi Shapiro

December 1980

1. Introduction.
1. Introduction.
1. Introduction.

Prolog   is  a  simple  but  powerful  programming  language

←←←←←←←←← ←←←←
developed at the University of Marseille  [5] as a practical tool

for programming in logic  [2, 6, 1].  From a user's point of view

the major attraction of the  language  is  ease  of  programming.

Clear, readable, concise programs can be written quickly with few

errors.

Our  implementation  was  developed  in  Edinburgh  by  Luis

M. Pereira, Fernando C. N. Pereira and David  H. D.  Warren,  and

comprises of an interpreter and a compiler.

2. The Language.
2. The Language.
2. The Language.

A  Prolog  program  is  a  collection  of  first-order logic
1
←←←← ←←←←
sentences (procedures) in what is called Horn-form :

P :- Q , Q ,... , Q .  for n >= 0
1   2        n

←←←←←←←←←←←←←←←
1
Our Prolog implementors used ":-" instead of the  more  common
implication signs.
1

Where  P and the Q 's are terms.  for example, the following is a
i
program for computing reachability in a graph:

reachable(X,X).
reachable(X,Z) :- edge(X,Y), reachable(Y,Z).

edge(a,b).
edge(b,c).
edge(b,d).
edge(d,b).

The semantic interpretation of such a Horn sentence is:   "P

is implied by the conjunction of Q ,..., Q ".
1       n

Its  procedural  interpretation  is:  "To satisfy the goal P

satisfy goals Q ,..., Q ".
1       n

When n=0 these interpretations read "P is  true"  or  "P  is

satisfied" respectively.

Note  that  the  main  functor  of  a  term  (e.g.  edge  in

edge(a,b)) should be adjacent to  the  parethesis,  unlike  LISP.

with "←") and constant  names  with  lower  case.    For  further

syntactic details see the manual  [3].

3. Declarative and Procedural Semantics of Prolog.
3. Declarative and Procedural Semantics of Prolog.
3. Declarative and Procedural Semantics of Prolog.

One  of  the  nice  properties  of  Prolog  is that is has a

relatively clean semantics.

To invoke a Logic program, one gives it a goal. A goal is  a

sentence of the form :- P. For example
2

:- edge(a,X).   or

:- reachable(a,d).

The  declarative  semantics of a logic program is defined as

follows:

←←←←
A goal is true if it is  the  head  of  some  clause
instance  and  each  of the goals (if any) in the body of
that clause instance is true.

When a goal is given to the Prolog interpreter, it tries  to

satisfy   it,   in  the  following  way,  which  constitutes  the

procedural semantics of Prolog:

←←←←←←←
To execute a goal, the interpreter searches for  the
←←←←←←←    ←←←←←←←
first clause whose head matches or unifies with the goal.
The  unification  process   [4]  finds  the  most general
common instance of the two terms, which is unique  if  it
exists.    If  a  match  is  found,  the  matching clause
instance is then activated by  executing  in  turn,  from
left  to  right,  each of the goals (if any) in its body.
If at any time the system fails to find  a  match  for  a
goal,  it  backtracks,  ie.  it rejects the most recently
activated clause, undoing any substitutions made  by  the
match  with  the head of the clause.  Next it reconsiders
the original goal which activated  the  rejected  clause,
and  tries to find a subsequent clause which also matches
the goal.

execute(true) :- !.
execute((P,Q)) :- !, execute(P), execute(Q).
execute(P) :- clause(P,Q), execute(Q).

To understand how this mini-interpreter works, note  that  a

unit  clause  P.  is  implemented  internally  as  P :- true, and

clause(P,Q) succeeds with a clause in the  data-base  whose  head
3

matches P and body matches Q.

4. List Processing.
4. List Processing.
4. List Processing.

Lists  are  implemented  in  a  very  clean  way  in Prolog.

[a, b, c, d] is a list whose elements are a, b, c and d.  [a | X]

is a list whose CAR is a and its CDR is X. Note that the CDR of a

list  can  only be a list.  The term [a, b, c | X] is also legal,

and it corresponds to the list whose CAR is a, CADR is  b,  CADDR

is c, and CDDDR is X (clean, isn`t it?).

For example, a procedure for testing/finding membership in a

list:

member(X,[X|←]).
member(X,[←|L]) :- member(X,L).

And a procedure for finding duplicate members in lists. This

procedure  illustrates how backtracking simulates two nested "for

loops".

duplicate(X,L1,L2) :- member(X,L1), member(X,L2).

And the famous append:

append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

5. Implementing a data-base in Prolog.
5. Implementing a data-base in Prolog.
5. Implementing a data-base in Prolog.

The following example almost speaks for itself.   Note  that

the  query-user  can  not  tell which relations are primitive and
4

which are computed.

father(abraham,isaac).
father(isaac,jacob).
father(isaac,esau).

mother(sarah,isaac).

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

brother(X,Y) :- parent(Z,X), parent(Z,Y), X\==Y.

grandmother(X,Y) :- mother(X,Z), parent(Z,Y).

6. Programming with side effects.
6. Programming with side effects.
6. Programming with side effects.

So  far  the examples we showed were of "pure" prolog. Every

LISP user knows that the "pure" part of the language is  cleaner,

but  many  times  more cumbersome to use.  The following examples

show how by using  the  build-in  procedures  for  asserting  and

retracting  assertions from the data base one can get the effects

of global variables:

set(Name,Value) :-  retractall(variable(Name,←)),
assert(variable(Name,Value)).

NewValue is Value + 1,
assert(variable(Name,NewValue)),

Using this technique and the build-in  list  structures  one

can easily implement global stacks:
5

stack←init(Name) :- retractall(stack(Name,←)),
assert(stack(Name,[])).

push(Name,Element) :- retract(stack(Name,List)),
assert(stack(Name,[Element|List])).

pop(Name,Element) :- retract(stack(Name,[Element|List])),
assert(stack(Name,List)), !.

7. Data Entry in Prolog.
7. Data Entry in Prolog.
7. Data Entry in Prolog.

Communication  with  the  user in Prolog is simple and easy.

For example, a procedure for asking the user  a  question.    The

procedure  succeeds  if  the  user  answer yes, fails if the user

answers no, and bothers the user forever otherwise:

display(Question),
display(' (yes/no)?'), ttynl,

8. Implementing environment for Prolog.
8. Implementing environment for Prolog.
8. Implementing environment for Prolog.

The Prolog environment is good, but yet inferior to the LISP

environments.  For example, the tracing utility is global and can

be  invoked  either  from  top  level  interpreter  by  executing

"trace",  or  by  calling  "trace" from an interpreted procedure.

This seems very inflexible, since if you want to stop  tracing  a

procedure  you  have  to delete somehow the "trace" call from its

body.  However the following shows how easy it  is  to  implement

trace(P) :- asserta((P :- trace, fail)).
6

Executing trace(member(←,←)) will insert

member(←,←) :- trace, fail.

as   the  first  clause  of  the  member  procedure.    Executing

member(←,←)  will  invoke  trace  and  fail,  and  the   (traced)

execution   of   member   will   proceed   normally.    Executing

trace(member(←,[])) will cause tracing of calls to member with an

empty list only.  Implementing notrace(P) is similarly easy.

9. AI programming in Prolog.
9. AI programming in Prolog.
9. AI programming in Prolog.

All the above examples should have convinced the  reader  by

now  that  Prolog  is the ideal language for AI programming.  But

only to illustrate that, we show how McSam, a micro version of  a

Script  Applyer  Mechanism  can  be implemented easily in Prolog.

Recall that the LISP implementation of McSam  is  nine  pages  of

code long.

A  parsed  story  is  a list of its Conceptual-Dependencies,

with some slots filled in,  as  (supposedly)  were  generated  by

McEli.  The  following  is  the CD`s for the story: "John went to

leones.  He ordered a Hamburger.  He left."

story([[ptrans, john, john, ←, leones],
[mtrans, ←, ←, hamburger],
[ptrans, Actor, Actor, ←, ←]  ]).

A script is a list of CD`s, not instantiated yet, and a  list  of

default   names   for   the  slots  (recall  that  variables  are

implemented internally as numbers preceded by  "←",  so  all  the
7

nice  mnemonic  names for script variables are lost when a script

script(restaurant,
[ [ptrans, Actor, Actor, Earlier←place, Restaurant
[ptrans, Actor, Actor, Door, Seat],
[mtrans, Actor, Waiter, Food],
[ingest, Actor, Food, [mouth, Actor] ],
[atrans, Actor, Money, Actor, Waiter],
[ptrans, Actor, Actor, Restaurant, Gone] ],
[ [Actor, customer], [Earlier←place, place1],
[Restaurant, restaurant], [Door, door],
[Seat, seat], [Food, meal], [Waiter, waiter],
[Money, check], [Gone, place2]  ] ).

For every script, there are  some  slot-fillers  that  might

trigger it:

trigger(leones, restaurant).
trigger(waiter, restaurant).

And....  here is mcsam !!!!

mcsam(Story,Script) :-  find(Story,Script,Defaults),
process(Script,Story),
name←defaults(Defaults),!.

find(Story,Script,Defaults) :- filler(Slot,Story),
trigger(Slot,Name),
script(Name,Script,Default

process(Script,[]).
process([Line|Script],[Line|Story]) :- process(Script,Sto
process([Line|Script],Story) :- process(Script,Story).

filler(Slot,Story) :- member([←|Args],Story),
member(Slot,Args),
nonvar(Slot).

name←defaults([]).
name←defaults([[N,N]|L]) :-  name←defaults(L).
name←defaults([[←,←]|L]) :-  name←defaults(L).

This  example  is sort of a "low blow" to LISP, since all it
8

does  is  drive  two unifies, the one that unifies the story with

the script, and the one that unifies  the  variables  with  their

default  names.  All  the rest Prolog does for you. But still, we

expect McEli also to be relatively easier to  program  in  Prolog

than in LISP.  Would you like to try?

10. Some Practical Hints for Using Prolog.
10. Some Practical Hints for Using Prolog.
10. Some Practical Hints for Using Prolog.

All Prolog files are in <f.prolog>.  All you need to know is

in  prolog.doc .  The interpreter is prolog.exe, and the compiler

is plc.exe (you might want to talk to someone who broke his teeth

using it before trying to do it yourself).

Executing the directive :-P at  top  level  will  result  in

nothing  (excluding  side-effects)  if  P succeeds, and "?" if it

fails.  The question directive ?-P is more useful, since it  will

give you also the bindings in case of a successful termination.

In top level interpreter you can omit the "?-" and "P." will

mean  a question directive.  In a file you can omit the ":-" in a

unit clause, and "P." will mean "P :- true".

The correct way of using Prolog is like using UCILISP.   You

write  and  edit  procedures  using  a text editor, and load them

using     consult('filename')     the     first     time,     and

reconsult('filename') in all other times.

A convenient alternative to the directive

consult('file1'), consult('file2'), reconsult('file3').
9

given at top level interpreter is ['file1','file2',-'file3'].

Have fun !!!
10

REFERENCES
REFERENCES
REFERENCES

[1]   A. Colmerauer.
←←← ←←←←←←←←←← ←← ←←←←←←←←←←←←
Les Grammaires de Metamorphose.
Technical Report, Groupe d`Intelligence Artificielle,
Marseille-Luminy, November, 1975.

[2]   Robert A. Kowalski.
←←←←← ←←← ←←←←←←← ←←←←←←←
Logic for Problem Solving.
Elsevier North Holland Inc., 1979.

[3]   L. Pereira, F. Pereira and D. Warren.
←←←← ← ←←←←← ←← ←←←←←←←←← ←← ←←←←←←
User's Guide to DECsystem-10 PROLOG.
Technical Report 03/13/5570, Labortorio Nacional De
Engenharia Civil, Lisbon, September, 1978.
Provisional version.

[4]   J. A. Robinson.
A Machine Oriented Logic Based on the Resolution Principle.
←←←←
JACM 12, January, 1965.

[5]   P. Roussel.
←←←←←←  ←←←←←← ←←←←←←←←← ←← ← ←←←←←←←←←←←
Prolog: Manuel Reference et d`Utilisation.
Technical Report, Groupe d`Intelligence Artificielle,
Marseille-Luminy, September, 1975.

[6]   M. H. van-Emden.
←←←←←←←←←←← ←←←← ←←←←←←←←←← ←←←←←
Programming with Resolution Logic.
Technical Report Report CS-75-30, Dept. of Computer
Science, University of Waterloo, November, 1975.