home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / hugs101.zip / hugs101o.zip / Progs / HUGS / Demos / Prolog / Readme < prev    next >
Text File  |  1995-02-14  |  11KB  |  282 lines
  1. ______________________________________________________________________________
  2. Mini Prolog Version 1.5g                          Mark P. Jones 23rd July 1991
  3.  
  4.              A simple Prolog interpreter, for Gofer 2.28
  5.  
  6. ______________________________________________________________________________
  7.  
  8.  
  9. This document gives a brief introduction to Mini Prolog Version 1.5g, a simple
  10. Prolog interpreter that can be used with Gofer 2.28.   The original version of
  11. this program was written nearly two years ago as an Orwell program, running on
  12. the interpreter used here in Oxford for teaching functional programming.  More
  13. recently I rewrote the interpreter for the Haskell B. compiler produced by the
  14. people at Chalmers in Sweden, and took the opportunity to experiment with some
  15. of the new features of Haskell, including  type classes  and I/O.   Only a few
  16. small changes to the Haskell B version have been necessary to make Mini Prolog
  17. run under my own  Haskell-like  interpreter,  Gofer, with most  of these being
  18. required to take account of changes in the definition of  Haskell from version
  19. 1.0 to the latest version 1.1, due at the end of the month.
  20.  
  21. This document isn't going to explain a  lot  about  how  Prolog  programs  are
  22. written and work.  But there are plenty of other references for that.   Please
  23. feel free to contact me with any questions or suggestions.  I'd very much like
  24. to receive any comments.
  25.  
  26. jones-mark@cs.yale.edu
  27. ______________________________________________________________________________
  28.  
  29.                            GETTING STARTED
  30.  
  31. The  Mini Prolog interpreter  takes the form of a small  collection  of  Gofer
  32. scripts.  The most important part of  any  implementation  of  Prolog  is  the
  33. inference engine  which  controls  the  search  for  goals  to  user  supplied
  34. queries.  Mini Prolog comes with a choice of two different inference  engines,
  35. the `pure' engine uses lazy evaluation to construct and  traverse  potentially
  36. infinite proof trees.  The `stack' engine uses an explicit stack  (implemented
  37. using a list) to provide a more concrete  description  of  backtracking.   The
  38. stack engine also implements  the  Prolog  cut  `!'  predicate,  used  in  the
  39. examples below.  Assuming that you've got everything set up  properly  to  use
  40. the Gofer interpreter, and that all of the Mini Prolog script files are in the
  41. current working directory, you should start Gofer with the command `gofer':
  42.  
  43.   machine% gofer
  44.   Gofer Version 2.20
  45.  
  46.   Reading script file "/users/mpj/research/Gofer/prelude":
  47.   Parsing...................................................................
  48.   Dependency analysis.......................................................
  49.   Type checking.............................................................
  50.   Compiling.................................................................
  51.  
  52.   Gofer session for:
  53.   /users/mpj/research/Gofer/prelude
  54.   Type :? for help
  55.  
  56. and then specify the appropriate set of script to be loaded:
  57.  
  58.   ? :l Parse Interact PrologData Subst PureEngine Main
  59.  
  60. for the `pure' version of the inference engine, or:
  61.  
  62.   ? :l Parse Interact PrologData Subst StackEngine Main
  63.  
  64. for the stack version, which is the one needed for the rest of this document.
  65. Once the script files have been loaded,  start the Mini prolog interpreter by
  66. typing the expression `main' and pressing return.
  67.  
  68.   ? main
  69.   Mini Prolog Version 1.5g (stack based)
  70.  
  71.   Reading stdlib........done
  72.   > 
  73.  
  74. The `>' prompt indicates that the interpreter is running and waiting for  user
  75. input.
  76.  
  77.                         STANDARD PREDICATES
  78.  
  79. Before the `>' prompt appears, Mini Prolog reads a set of  standard  predicate
  80. definitions from the file `stdlib' in the current directory.  You are free  to
  81. modify this file to suit your own needs.  The only predicate that is built  in
  82. to Mini Prolog is the cut, written `!' whose use is demonstrated below.  There
  83. are no other  extralogical  predicates,  no  input/output  predicates  and  no
  84. arithmetic as found in full implementations of Prolog.  Some of these features
  85. could be added to the interpreter without too much  difficulty,  others  would
  86. require rather more work.
  87.  
  88. At any time, you can ask the interpreter to display the list of rules that are
  89. being held in the database by typing "??" and pressing the  return  key.   Try
  90. this after you've started the  interpreter  and  you'll  get  a  list  of  the
  91. predicates defined in the file `stdlib'.  For example:
  92.  
  93.   > ??
  94.   append(nil,X,X).
  95.   append(cons(X,Y),Z,cons(X,W)):-append(Y,Z,W).
  96.  
  97.   equals(X,X).
  98.  
  99.   not(X):-X,!,false.
  100.   not(X).
  101.  
  102.   or(X,Y):-X.
  103.   or(X,Y):-Y.
  104.  
  105.   true.
  106.   >
  107.  
  108.                           THE APPEND PREDICATE
  109.  
  110. The Mini Prolog interpreter does not support the standard  Prolog  syntax  for
  111. lists.    Instead,   you   have    to    write    the    list    [1,2,3]    as
  112. "cons(1,cons(2,cons(3,nil)))".  One of the first things I tried was  appending
  113. two simple lists:
  114.  
  115.   > ?- append(cons(1,nil),cons(2,nil),X)
  116.   X = cons(1,cons(2,nil)) ;
  117.   no.
  118.   >
  119.  
  120. Given a query, Mini Prolog attempts to find values for each of  the  variables
  121. (beginning with a capital letter) in the query.  Here Mini  Prolog  has  found
  122. that X = cons(1,cons(2,nil)) is a solution to the query.   When  I  press  the
  123. semicolon key, ";", it tries to find another solution, but fails and  displays
  124. the message "no.".
  125.  
  126. What amazed me when I first started experimenting with Prolog was that I could
  127. actually ask Mini Prolog to work through the problem in reverse, asking  which
  128. lists could be appended to get the list cons(1,cons(2,nil)):
  129.  
  130.   > ?- append(X,Y,cons(1,cons(2,nil)))
  131.   X = nil
  132.   Y = cons(1,cons(2,nil)) ;
  133.   X = cons(1,nil)
  134.   Y = cons(2,nil) ;
  135.   X = cons(1,cons(2,nil))
  136.   Y = nil ;
  137.   no.
  138.   >
  139.  
  140. Note that the interpreter pauses after displaying each solution and waits  for
  141. a key to be  pressed.  Pressing `;' tells Mini Prolog  to continue looking for
  142. another solution, displaying `no' if no more solutions can be found.  Pressing
  143. any other key stops the execution of the query.  If there are no variables  in
  144. the original query, then the interpreter simply outputs `yes' if the query can
  145. be proved and otherwise prints `no':
  146.  
  147.   > ?- append(cons(1,nil),cons(2,nil),cons(1,cons(2,nil)))
  148.   yes.
  149.   > ?- append(cons(1,nil),cons(2,nil),cons(1,cons(3,nil)))
  150.   no.
  151.   >
  152.  
  153. Unfortunately, typing a control C to interrupt a query with an  infinite  loop
  154. will exit the Prolog interpreter completely -- sorry, but I don't know  a  way
  155. around this at the moment.
  156.  
  157.  
  158.                        RUNNING IN THE FAMILY
  159.  
  160. You don't have to stick with the standard predicates that are already included
  161. in Mini Prolog.  Additional rules can be typed in at the ">" prompt.  Here are
  162. a couple of examples based around the idea of family trees:
  163.  
  164.   > parent(Child,Parent):-father(Child,Parent).
  165.   > parent(Child,Parent):-mother(Child,Parent).
  166.   > grandparent(GChild,Gparent):-parent(GChild,Parent),parent(Parent,Gparent).
  167.   >
  168.  
  169. Note that  Mini Prolog  expects  a maximum of one rule per line,  and will not
  170. allow predicate definitions to be spread out over a number of lines.
  171.  
  172. All you have to do now is enter some details about your family  and  then  you
  173. can ask who your grandparents are ... let's take a typical family:
  174.  
  175.   > father(charles,princePhilip).
  176.   > mother(charles,theQueen).
  177.   > father(anne,princePhilip).
  178.   > mother(anne,theQueen).
  179.   > father(andrew,princePhilip).
  180.   > mother(andrew,theQueen).
  181.   > father(edward,princePhilip).
  182.   > mother(edward,theQueen).
  183.   > mother(theQueen,theQueenMother).
  184.   > father(william,charles).
  185.   > mother(william,diana).
  186.   > father(harry,charles).
  187.   > mother(harry,diana).
  188.   >
  189.  
  190. And  now  we  can  ask  some  questions;  like  who  are  the  Queen  mother's
  191. grandchildren ?
  192.  
  193.   > ?- grandparent(X,theQueenMother)
  194.   X = charles ;
  195.   X = anne ;
  196.   X = andrew ;
  197.   X = edward ;
  198.   no.
  199.   >
  200.  
  201. or, who are Harry's grandparents ?
  202.  
  203.   > ?- grandparent(harry,Who)
  204.   Who = princePhilip ;
  205.   Who = theQueen ;
  206.   no.
  207.   >
  208.  
  209. Note that Mini Prolog can only use the facts it has been  given.   Tell  it  a
  210. little more about Diana's parents and you'll find it knows more about  Harry's
  211. grandparents.
  212.  
  213. Now suppose we define a sibling relation:
  214.  
  215.   > sibling(One,Tother) :- parent(One,X),parent(Tother,X).
  216.   >
  217.  
  218. Fine.  It all looks quite correct.  But when you try to find Harry's siblings,
  219. you get:
  220.  
  221.   > ?- sibling(harry,Who)
  222.   Who = william ;
  223.   Who = harry ;
  224.   Who = william ;
  225.   Who = harry ;
  226.   no.
  227.   >
  228.  
  229. Each of William and Harry  appears  twice  in  the  above.   Once  by  putting
  230. X=charles and once using X=diana in the definition of sibling above.   We  can
  231. use the cut predicate to make sure that we look for at most one parent:
  232.  
  233.   > newsib(One,Tother) :- parent(One,X),!,parent(Tother,X).
  234.   >
  235.   > ?- newsib(harry,Who)
  236.   Who = william ;
  237.   Who = harry ;
  238.   no.
  239.   >
  240.  
  241. Thats better, but we don't really want to list Harry as his  own  sibling,  so
  242. we'll add a further restriction:
  243.  
  244.   > newsib1(O,T):-parent(O,X),!,parent(T,X),not(equals(O,T)).
  245.   >
  246.   > ?- newsib1(harry,Who)
  247.   Who = william ;
  248.   no.
  249.   >
  250.  
  251. Thats just about perfect.  You might like to play with  some  other  examples,
  252. enlarge the family tree, work out suitable predicates for other relations (who
  253. are Harry's aunts ?) etc.  Initially, the answers that Mini Prolog gives  will
  254. all be pretty obvious to you.  Try getting involved in a  larger  family  tree
  255. and more complicated relations and you'll find it's not so easy.
  256.  
  257.                                   GOODBYES
  258.  
  259. I could go on with more examples, but I guess you've got the  picture  by  now
  260. ... at least I hope so !  I suppose I should just tell you how to get  out  of
  261. Mini Prolog (ok. ^C works but its not exactly elegant).  Just type  "bye"  (or
  262. "quit") and you're out.  Be warned though: when you leave Mini Prolog, it will
  263. not retain any new rules that you've entered, so  you'll  have  to  find  some
  264. other way to save them (I usually type  "??"  to  list  the  rules  that  I've
  265. entered and use the mouse to paste them into an editor in another window,  but
  266. that obviously requires you to be using a workstation at the time).
  267.  
  268.   > bye
  269.   Thank you and goodbye
  270.  
  271.   (12749 reductions, 1256 cells)
  272.   ?
  273.  
  274. The `?' prompt  tells you that you are now back in Gofer,  and you can restart
  275. Mini Prolog as before,  carry on with some other work in Gofer,  or use the :q
  276. command to exit Gofer and return to the operating system.
  277.  
  278. I hope you have fun with Mini Prolog;  please tell me if you have any comments
  279. you'd like to make.
  280.  
  281. ______________________________________________________________________________
  282.