CS320 Notes on Logic Programming

	http://www.csci.csusb.edu/cs320/sebesta/16.html

Logic Programming

16.2 The Predicate Calculus

      Books introduction is OK but does not define a predicate.
	A proposition is some true/false statement.
	A predicate is a proposition that contains variables
		and constants of some type or other.
	In class we will list some example predicates(semantics).

	In logic programming predicates have the familiar syntax
	of conditions or boolean expressions but a totally different
	semantics.

16.2.1 Propositions.

	Definition of atomic propositions, terms and functor comes
	from Prolog.  The word 'functor' is used because they look
	like 'functions' but DON'T return a value when 'invoked'.

	The book uses a rather strange notation for propositions
	that is neither standard nor ASCII.
	I recommend you use the notation in 
		http://www.csci.csusb.edu/dick/maths/intro_logic.html
	Examples (Page 608, 4th edn., page 537, 3rd edn):
		for all X (if woman(X) then human(X))
		for some X( mother(mary,X) and male(X))

16.2.2 Clausal Form

	The book introduces this because these clauses explain what
	Prolog does.  Therefore use Prolog's symbol in place of the 
	REVERSED HOOK
	used in the book:
		B1 or B2 or ... or Bn :- A1 and A2 and... and An

		P:-Q::=if Q then P.
	Page 609
		likes(bob, trout):- likes(bob,fish) and fish(trout).
		father(louis, al) and father(louis, violet) :- father(al,bob) and mother(violet, bob) and grandfather(louis,bob).

	Page 538, old edition.
	like(bob, mary):- like(bob,redhead) and redhead(mary).

16.3 Resolution.

	This is a beautiful improvement over the way that computers normally work!

	Instead of following instructions that calculate a unique state
	from a previous one,
		we look for a state that fits all the current constraints,
	and
		if its not good enough we look for another one.

	Notice the words
		unification
		instantiation
	Nothing makes much sense without them.

	RESOLUTION is a generic way of combining two statements
	into a single conclusion.  I think of it as being like
	multiplying two factions and seeing what cancels out.
			(123/234)*(234/567) ====> (123/567)
			(P:-Q) and (Q:-R)   ====> (P:-R)
	But it only works with statements in a particular form.
	They are called Horn Clauses.  They have form: P if Q.

	UNIFICATION is a way to handle variables and constants. 
	It is used to handle arguments in Prolog.
	The idea is a simple comparing and matching two structures.
	When we match up a variable with a constant we know the value.

	Algorithm to UNIFY to structures or formula
	Case 1: Two atoms(constants).
		If they are equal then they unify
		else unification fails.
	Case 2: Two variables,
		Take note of the fact that they are ACTUALLY the same
			variable
	Case 3: A variable and a non-variable.  Take note
		that this variable(and those equal to it) must
			all match the non-variable.
	Case 3: Two structures (recursive)
		F1(X1,X2,X3,....)
	vs
		F2(Y1,Y2,.......)
		Then F1 and F2 must be the same atom
		and they must have the same number of arguments(arities),
		and X1 must unify with Y1
		and X2 must unify with Y2
		and so on.

	Sample: 
	How can a(X,1,Y)=a(2, Z, c(X))?
	Unify a(X,1,Y) with a(2, Z, c(X))
		this is case 3 above, F1=F2=a, and there are 3 things two compare.
		Unify   X=2
			1=Z
			Y=c(X)
		So X is 2, Z is 1 and so Y is c(2)...
	a(1,1,c(2)) = a(2,1,c(2)).

	Notice.  The meaning of a and c is not used.  Prolog/unifications
		aims to solve the equality for ALL POSSIBLE MEANINGS.

	The Prolog experiments in the labs and the homework
	have lots of examples of unification.


	Instanciation.
	Prolog variables are NOT normal.  They are more like
	mathematical variables.  They start out without any
	values (prolog numbers them _0, _1, _2, _3, ...).
	Unification can bind a variable to a a structure
		(which can have variable in it!)
	Once bound the value stays the same and the variable
	starts to behave like a constant (almost).
	However, if a step fails the prolog system
	back-tracks and systematically turns these
	pseudo-constants back into undefined variables again.
	Only then can they be given a new value.

	When a command or query finishes, it has removed
	all variables....

	This is different enough for us to not talk about
		assignment
	but to talk about a variable having different
		instances
	and the process of
		instantiation
	is that of binding a variable to a temporary instance.

16.4

	The idea is that 

		THE SPECIFICATION AUTOMATICALLY DETERMINES THE PROGRAM.

	It is not quite that simple, however.

	But it IS an EXCELLENT idea to note down the requirements for a
	program, in logic, prior to writing the program.
			(for a BIG, undefined problem that is).
	You'll find lots of bugs this way before you waste time programming them!

	Do not make the mistake of going straight into Prolog
	without sorting out the logic first.  
	You end up fighting on two fronts.  On one side you fight your
	lack of understanding and on the other you fight with Prolog
	itself.

	In http://www.csci.csusb.edu/cs320/ are two sample solutions to
	a problem:
	$CS320/prolog/compsci.plg  is such a failed attempt.
	$CS320/prolog/compsci2.plg was done after analyzing the problem better.

	

16.5 History

	Know the names and dates

16.6 Basic Elements

	Our prolog is like the one Sebesta describes.
		SWI-prolog.
	It is compiled from Source and is available fro UNIX, DOS,
		Windows1 through to 95

	To store input - finish with a full-stop.
	Beware of tapping enter without typing a ".", "!" or "?".

	atoms can be a string enclosed in single quotes.
	This is useful for naming files:
		consult('metro.plg')!

16.6.4 Goal statements.

16.6.5 Process

16.6.6 Arithmetic --- the pernicious 'is'

	The book is NOT joking....

16.6.7 List structures -- rip off from LISP???

16.7 Deficiencies

	The Cut
	The Closed World assumption
	The Negation Problem
	Intrinsic Limitation
	The Negation Problem

16.8 Applications

	Relational DBs - most don't use prolog (pity!)
	Expert Systems - the only successful every day use of AI.
	Natural Language
	Education - We have discussed using it here...

16.9 Conclusions.

ALSO - A little logic never hurt anyone
		as long as they can use it creatively.

	I've had more fun and frustration with 'prolog' than with any
	language I've learned for the last 10 years....

Problems 3,4,5,6,7 Are good portfolio material.