Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> 17 [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Tue May 25 15:44:48 PDT 2004

Contents


    CSci620 Programing Languages -- 17 -- Hello, Prolog!

      Previous

      [ 16.html ]

      Preparation

      Pages 195..211 + the special Prolog Handout.

      Topics

        Note

        The book does not explain how to load facts into Prolog's data base. The Handout does this better. Notice that our system uses ".plg" for Prolog and ".pl" is for Perl! The book is using the Windows version of SWI Prolog that I have on my laptops.

        Book

          Handout

          [ Prolog.html ]

          Logic

          Programming in Logic

          The first three lines of page 199 are a data base. They should be put in a file "array.plg" and compiled into Prolog before the queries on pages 199..201 are tested. I will demo this in class.

          In the middle of page 202 is another collection of facts and rules that need to be placed in a file [ greater.plg ] and put in the data base. I will use this to demonstrate two common mistakes made when starting Prolog.

          The code on page 203 uses a predicate name close that is already part of our version of Prolog. Here [ p203.plg ] is the fixed code.

          Data structures

          On page 207 the definitions of push and pop should be put in a file stack.plg before Prolog runs.

          On page 209 the definition of the queue should be in a file: queue.plg

          On page 210: push_pop should be defined in a file and loaded into the Prolog form a file.

        . . . . . . . . . ( end of section Book) <<Contents | Index>>

      . . . . . . . . . ( end of section Topics) <<Contents | Index>>

      Questions

        What is my experience with Prolog

        I have a lot of fun with Prolog: solving puzzles, and trying out prototype algorithms. I've used it (once) for trying out a large number of options for a terminal to see if any of them gave the behavior I needed. Prolog said "No".

        What is the difference between Propositional and first order calculus?

        These are both logics. The first-order or lower-predicate calculus (LPC) has a universe of discourse plus predicates and quantifiers (all, some) over objects in the universe. Propositional calculus has a finite number of propositions. Each proposition can be either true or false.

        Why do we separate finite from infinite domains of discourse?

        In finite domains we have a simple procedure (but expensive) for testing the truth or falsity of a theorem. In infinite ones we usually don't.

        In an infinite domain, like the integers you can search for solutions for ever, and miss it anyway.

        What is Godel's Incompleteness Theorem?

        First Kurt Goedel proved that the lower predicate (first order) calculus anything that was true could be proved true and vice versa. Then he proved that in more complex logics -- any logic capable of expression integer arithmetic -- there are well formed formula that can not be proved (but are obviously true), or there are formula that can be both proved and disproved! This is the incompleteness theorem. For an entertaining but long study of this find "Goedel, Escher, Bach" [ search?cat=web&cs=utf8&q=Goedel+Escher+Bach ] by Douglas Hofstadter.

        Prolog is not quite powerful enough for Goedel's incompleteneess theorem to apply directly but instead we have many true theorems that Prolog can not prove.

        Worse any domain that includes integers there is a strong chance of Prolog going on an infinite search for a solution in the wrong direction. For example, looking for a solution of a predicate p(I,J,K) where I, J, and K are any positive integer needs great care to avoid searching I=1,2,3,4,... for ever with J=K=1, when the solution is p(1,2,2)!

        What does meta mean?

        2000 years ago it was used to mean "after" by Aristotle. After the book on "Physics" he wrote "MetaPhysics".

        The prefix 'meta' is used when one language talks about languages.

        A meta symbol is a symbol that represents something in a language. In English we have words like: <verb>, <noun>, <pronoun>, etc. that name families of words. These are metasymbols in English.

        What is a Propositional Variable?

        We call them Boolean Variables.

        Is the book wrong in the parsing of the formula at the bottom of page 197?

        It depends on the priority and grammar of the formulas. On web pages and email I use notations that force me to avoid ambiguity:
         		for all n( if arity(n) then n is Integers and n >=0 )
        or
         		for all n( if arity(n)) then n is Integers and n >=0
        However the second reading implies a global n and a local one. A peculiar formula that I would believe. Hence The first reading is correct.

        What is the difference between SWI and Gnu Prolog?

        It is (I guess) a matter of taste, and not important for CSci620.

        Why does the input of "X." give the output that it does?

        This is a request for the Prolog system to find the solution of all questions. The programmers have decided to give you the answer produced in "The Hitchhiker's Guide to the Galaxy": [ hhgg.html ] when asked what the answer to the ultimate question of life, death and the universe was.

        In Page 4 of the handout X and Y are shown in Reverse order!

        Output from a Prolog query is a list of variable values. The order doesn't matter and sometimes they appear in an unexpected order.

        Explaining traces

        A trace is a series of steps as Prolog searches for a solution to a query. Each step is when we Call a predicate for the first time, Redo it after a failure, Failing to find something, or Exiting with a successful value. Variables are replaced by numbered General variables. This become atoms because of calls but may revert to variables on Failure.

        The "creep" is output at each step when you tap the Enter key. The "a" key aborts a run.

        What is Prolog's No?

        When all the possible solutions have been found and you ask for another one, Prolog outputs "No.". It uses "No" is there is no solution at found and you ask for another one, Prolog outputs "No.". It uses "No" is there is no solution at all.

        Prolog's data structure

        Different Prolog's use different data structures. I think SWI Prolog has a hash table of predicates but I'm not sure and doesn't matter two much because we think of the data a s long list of facts and rules.

        assert, asserta, and assertz add new rules and facts. retract removes them. Abolish wipes out all the rules for a particular atom/functor.

        An assertional data base works by recording facts. These are rather like the entities or rows in a normal data base.

        Is the data base like an array or some other data structure?

        No. Prolog databases are a rule unto themselves. But they do a good job of simulating any data you could want (but slowly).

        Explain Figures 8.5 and 8.6

        These are visual representations of traces. Start at the top and follow the arrows down and two the left.... when you get to a leaf follow and arrow up and take the next branch to the right...

        How does X=Y+2 and X is Y+2 differ?

        We tried this in class
         		Y=1, X=Y+2.
        and got:
         		X=1+2.
        The Y+2 is not evaluated. We then tried
         		Y=1, X is Y+2.
        and got:
         		X=3.

        Further

         		Z=X+Y, Y=1, Y=2, W is Z.
        Gave us X=1+2 and W=3.

        "is" evaluates its argument, "=" does not.

        On page 205 why does ac and af appear twice?

        Because there are two paths joining a to c, and two joining a to f in the graph being studied.

        It is common for complex Prolog definitions to lead to multiple occurrences of the same solution.

      . . . . . . . . . ( end of section Questions) <<Contents | Index>>

      Next

      More Prolog: pages 211-222 [ 18.html ]

      Laboratory

      [ lab17.html ]

    . . . . . . . . . ( end of section CSci620 Programing Languages -- 17 -- Hello, Prolog!) <<Contents | Index>>

    Glossary

  1. BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
  2. EBNF::="Extended " BNF.
  3. HTML::= "HyperText Markup Language", used on the WWW.
  4. HTML_page::syntax= "<HTML>" head body.
  5. Java::="An " OO " Language from Sun".
  6. LISP::= "LISt Processing Language".
  7. LRM::="Language Reference Manual".
  8. OO::="Object-Oriented".
  9. Prolog::="Programming in Logic".
  10. TBA::="To Be Announced".
  11. UML::="Unified Modeling Language".
  12. URL::=Universal_Resource_Locator,
  13. Universal_Resource_Locator::syntax= protocol ":" location, where
    Net
    1. protocol::= "http" | "ftp" | "mailto" | ... ,
    2. location::= O( "//" host) O(pathname).

    (End of Net)
  14. WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
  15. XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of syntax, semantics, and other formal specifications.


Formulae and Definitions in Alphabetical Order