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


          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
                                              ←←←← ←←←←  
     sentences (procedures) in what is called Horn-form :

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

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

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

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


          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.

     Also  note  that variable names start with Upper case letters (or

     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

         :- edge(a,X).   or

         :- reachable(a,d).

          The  declarative  semantics of a logic program is defined as


              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.

          Written in Prolog, a Prolog interpreter looks like this:

         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

     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


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

          And a procedure for finding duplicate members in lists. This

     procedure  illustrates how backtracking simulates two nested "for


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

          And the famous append:

         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

     which are computed.



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

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

         had←sex(X,Y) :- father(X,Z), mother(Y,Z).

         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,←)),

         add1(Name,NewValue) :-  retract(variable(Name,Value)),
                                 NewValue is Value + 1,

          Using this technique and the build-in  list  structures  one

     can easily implement global stacks:

         stack←init(Name) :- retractall(stack(Name,←)),

         push(Name,Element) :- retract(stack(Name,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:

         ask(Question) :- repeat,
                            display(' (yes/no)?'), ttynl,
                            (Answer=yes, !;
                             Answer=no, !, fail).

     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

     your own traceing facility:

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

          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

     nice  mnemonic  names for script variables are lost when a script

     is read in).

                [ [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),

         find(Story,Script,Defaults) :- filler(Slot,Story),

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

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

         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

     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').

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

                               Have fun !!!


     [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.

                             Table of Contents
                             Table of Contents
                             Table of Contents

     1. Introduction.                                                0
     2. The Language.                                                0
     3. Declarative and Procedural Semantics of Prolog.              1
     4. List Processing.                                             3
     5. Implementing a data-base in Prolog.                          3
     6. Programming with side effects.                               4
     7. Data Entry in Prolog.                                        5
     8. Implementing environment for Prolog.                         5
     9. AI programming in Prolog.                                    6
     10. Some Practical Hints for Using Prolog.                      8