SICP - Logic Programming Part 2

In this lecture we took a high level view at implementation, though we didn't actually write the pattern matching or any other LISP code, which I'll admit was dissappointing.  I guess if I want to try this out I'll have to read the appropriate section in the book.




Note Dump:

Logic Programming Part 2

Implimenting the logic language

We have literals and variables - need pattern matching

(MATCH pat data dictionary)
  Is there any way to match this pattern against the data subject to the bindings
  already in the dictionary.

  (?x ?y ?y ?x) (a b b a) [x = a] => [x = a, y = b] the match is found, the
  dictionary is extended
  (?x ?y ?y ?x) (a b b a) [y = a] => fail, no match found

A primative query is two input streams and one output stream. One stream is the database.
The database holds all of our facts. The other stream is a stream of dictionaries.
When if finds a match, it outputs the extended dictionary.

What gets printed to terminal is the query with the variables instantiated for each
output dictionary.

The shape of a query is:

-input dicts--->[Query]---output dicts-->
                   |
  |
  |
  db

And P Q looks like
-input dicts---->[P]---[Q]---output dicts-->
                  |     /
 |    /
 |----
 |
 db
And, overall, has the same overall shape as a primative query.

Or P Q looks like this
-input dicts--------->[P]--\
             \         |    |--[Merge]--- output dicts-->
              \--->[Q]-----/
   |  |
   | /
   |/
   db

Not P looks like this
              /--[Filter]--\
-input dicts----->[P]--------output dicts-->
                   |
  |
  |
  db
Any matches found by the query are thrown away by the filter. Non-matches flow
through.

And is a series combination
Or is a parallel combination
Not is a filter

The things that we build have the same overall structure as the primatives... "Closure"
Combinations can be reconbined because they all have the same structure.

Question about where the dictionary comes from. Initially the dictionary is empty. As
streams are combined, the dictionaries flow down the stream.

One question asks about redundancy in AND, Abelson notes that there are other ways to
implement AND that are more efficient.

Abstraction:
Draw a box around our whole query and make it a query
We match the conclusion of a rule to the query, which gives us a dictionary. That
dictionary is then processed by the body of the rule.

If we want to generalize the pattern, we need a Unifier.
Unify (?x ?x)
with ((a ?y c)(a b z?))
x?: (a b c)
y?: b
z?: c

Unify (?x ?x)
with ((?y a ?w)(b ?v ?z))
?y: b
?v: a
?w: ?z
?x: (b a ?w)

A unifier is a very simple modification to a pattern matcher. Two or three lines for the
symetric case.  The "deduction" is just the recursive unwinding of the pattern.

Sometimes the unifier will have to be clever...
Unify (?x ?x)
with (?y (?y . a))
?x: ?y
?y: (a a a ...)

This would require the use of a fixed point calculation, which can't be done without
going into an infinite loop, so the interpreter just recognizes this and punts.

To apply a rule
Evaluate the rule body relative to an
environment formed by unifynig the rule
conclusions with the given query.

To apply a procedure
Evaluate the procedure body relative to
an environment formed by binding the
procedure parameters to the arguments.

Even though logic rules and procedures are very different, the eval-apply process is
nearly identical.

We need local variables to ensure that we don't have variable conflicts.

Question about time sequence (well more like an observation). Because there is no order,
you can't really do time-sequense or side effects.

In the logic language, if we want to check if something is true, we enter the exact thing
we are checking and if we get a result it's true.

The result of the unifier is basically a dictionary with variables defined as variables.

Asked about the unifier evaluating fixed point:
Unifty ( ?x ?x )
with ((a ?y b) ?y)
?y would have to contain ?y ... OMG ITS A FIXED POINT I'M GIVING UP...

Now we know logic language and rules work, what does it mean?

It's not what it seems to be ... AND, NOT, OR are not actual logic

Should be AND P Q and AND Q P should be the same thing...

(rule (outranked-by ?s ?b)
  (or (supervisor ?s ?b)
      (and (supervisor ?s ?m)
           (outranked-by ?m ?b))))

(rule (outranked-by ?s ?b)
  (or (supervisor ?s ?b)
      (and (outranked-by ?m ?b)
           (supervisor ?s ?m))))

Same definition, just reversed the last two clauses...
If this were true logic, they would both work.
The second version will go into an infinite loop, because it is will call itself again
with ?m with no restriction set to ?m. The first version will have a constraint on ?m set
by the query on supervisor.

In logic program, if you start changing the order of evaluation, you can see different
efficency. Some orderings will result in infinite loops. We don't know a priori which
rules need to run first.

Deeper problem with comparing logic language to classical logic language.

ALL HUMANS ARE MORTAL
ALL GREEKS ARE HUMAN
SOCRATES IS A GREEK
THEREFORE SOCRATES IS MORTAL

Compare this to our logic language:
(Greek Socrates) (Greek Plato)
(Greek Zeus)     (god Zeus)

(rule (mortal ?x) (human ?x))
(rule (fallible ?x) (human ?x))

(rule (human ?x)
   (and (Greek ?x) (not (god ?x))))
 
(rule (address ?x Olympus)
   (and (Greek ?x) (god ?x)))
 
All humans are mortal and fallible
All non-god greeks are human
Address of any god is Mount Olympus

(RULE (PERFECT ?X)
   (AND (NOT (MORTAL ?X))
   (AND (NOT (FALLIBLE ?X)))))

(AND (ADDRESS ?X ?Y)
     (PERFECT ?X))   -----> this will give us Olympus

(AND (PERFECT ?X)
     (ADDRESS ?X ?Y)) ------> this will give us nothing

NOT is a filter...
The NOTs in PERFECT have nothing to filter if it is called first, so they return nothing

Zeus should satisfy (NOT (FALLIBLE ZEUS))

NOT is not the NOT of logic. It means "not deducible from what is in the database", it
does not mean "not true"

Closed world assumption. If I don't know anything about ?x, then it isn't true. This is
dangerous. NOT ?x is false, but NOT NOT ?x is also false.

Logic programming has great power, bridging imperitive and declarative, but it has
a way to go (as of 1986)

Oh Christ, Mullet strikes again... thinking you can just through the opposite in the
database. He totally misses the point. You don't want a bunch of explicit NOTs necessarily.