SICP - Logic Programming Part 1

In this lecture we start looking at a Logical Programming language that differs quite a lot from the way we have been programming thus far. This lecture is about looking at the language and seeing how it is used, the next lecture will actually implement the language.




Note dump:

SICP - 8A Logic Programming Part 1

Evaluator for list has two elements:
EVAL takes in an expression and an environment and turn into procedure and arguments
which are then passed off to ...
APPLY, which creates an expression and an environment which it passes to EVAL

About unwinding the expression to primatives.

You can gain control of complexity by inventing new language (Metalinguistic Abstraction)

We're going to build a language that doesn't care about proceedures

Going to look at the language from a high level and simultaniously look at implementation

Doesn't use procedures or functions
Use streams to avoid backtracking

Declarative knowledge: what is true
Computer Science worried about How-to knowledge

Want to think about a programming language where we deal with declarative knowledge
We specifiy facts and the program operates with rules of logic.

SON-OF ADAM ABEL
SON-OF ADAM CAIN
SON-OF CAIN ENOCH
SON-OF ENOCH IRAD

These are our facts, now we can ask questions, like who is the son of Adam? Should
give us Cain and Abel
Who is Cain the son of? Should give us Adam
What is the relationship of Cain and Enoch? should give us "Son of"

One peice of declarative knowledge can be the basis of a great deal of how-to knowledge

We can give it rules of inference:

IF (SON-OF ?X ?Y) AND
(SON-F ?Y ?Z)
THEN (GRANDSON ?X ?Z)

Procedure to merge two sorted lists:
(define (merge x y)
  (cond
    ((null? x) y)
((null? y) x)
(else
 (let ((a (car x)) (b (car y)))
   (if (< a b)
 (cons a
       (merge (cdr x) y))
 (cons b
       (merge x (cdr y))))))))

Takes an X and a Y and spits out an answer

We can look at it logically too:

(let ((a (car x)) (b (car y)))
    (if (< a b)
(cons a
     (merge (cdr x) y))

This is the clause the chops up x
The underlying logic that makes the recursion work:

IF
(CDR-X and Y merge-to-form Z)
AND
A < (car y)
THEN
((cons A CDR-X) and Y
merge-to-form (cons A Z)

IF
(X and CDR-Y merge-to-form Z)
AND
B < (car x)
THEN
(X and (cons B CDR-Y)
merge-to-form (cons B Z))

For all X, (X and () merge-to-form X)
For all Y, (() and Y merge-to-form Y)

The LISP procedure has a box called MERGE and in comes an X and Y and out
comes an answer. Answer is a function of X and Y.

The logic describes a relation between three things, X, Y, and Z.
We can use these rules of logic to ask many things:

(1, 3, 7) and (2, 4, 8) merge-to-form what?
(1, 3, 7) and what? merge-to-form (1, 2, 3, 4, 7, 8)
?X and ?Y merge-to-form (1, 2, 3, 4, 7, 8) ... gives 2^6 answers.

We won't be computing functions, we'll be talking about relations. They don't have
directionality.

Relations don't necessary have only one answer. Style of programming is called
Logic Programming

The point of LP is that you use Logic to express what is true, check what is true, and
find out what is true.  Prolog is one type of Logic Programming language.

This is the sample "database" we'll use:

(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 40000)
(supervisor (Bitdiddle Ben) (Warbucks Oliver))
(address (Bitdiddle Ben) (Slumberville (Ridge Road) 10))

(job (Hacker Alyssa P) (computer programmer))
(salary (Hacker Alyssa P) 35000)
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))

(job (Tweakit Lem E) (computer technician))
(salary (Tweakit Lem E) 15000)
(supervisor (Tweakit Lem E) (Bitdiddle Ben))
(address (Tweakit Lem E) (Boston (Bay State Road) 22))

(job (Reasoner Louis) (computer programmer trainee))
(salary (Reasoner Louis) 20000)
(supervisor (Reasoner Louis) (Hacker Alyssa P))
(address (Reasoner Louis) (Slumberville (Pine Tree Road) 80))

(job (Warbucks Oliver) (administration big wheel))
(salary (Warbucks Oliver) 100000)
(address (Warbucks Oliver) (Swellesley (The Manor)))

When learning about a language:
What are the primatives?
What are the means of combination?
What are the means of abstraction?

What are the primatives above? In this language, it's a query.


(job ?x (computer programmer))
matches
           \/
           \/
(job (Hacker Alyssa P) (computer programmer))

Can match more than one variable

(job ?x (computer ?type))
matches
           \/                     /
           \/                    \/
(job (Bitdiddle Ben) (computer [wizard]))
(job (Hacker Alyssa P) (computer [programmer]))
(job (Tweakit Lem E) (computer [technician]))

Doesn't match Louis Reasoner, because query is looking for two symbols,
and (computer programmer trainee) has three symbols. Using a dot would fix...
(computer . ?type) - a list with computer followed by everything else, which
we call "?type"

(SUPERVISOR ?X ?Y) will give us all the supervisor relationships

(ADDRESS ?X (CAMBRIDGE . ?T) will give us everyone that lives in Cambridge

MEANS OF COMBINATION

How to combine queries

This will give us everyone in the computer division and their boss
(and (job x? (computer . ?y))
     (supervisor ?x ?z))

This will find everyone with a salary greater than 30000
(and (salary ?p ?a)
     (lisp-value > ?a 30000))

lisp-value is an interface to list that allows us to use the > symbol.

List all the people in the computer division who have a supervisor outside the computer
division
(and
   (job ?x (computer . ?y))
   (not (and (supervisor ?x ?z)
             (job ?z (computer . ?w)))))

Means of combination are logical operations:
AND, OR, NOT... lisp-value is a hack to give us access to LISP

MEANS OF ABSTRACTION

Rules as a means of abstraction:

(rule                                       <- call it a rule
   (bigshot ?x ?dept                        <- rule conclusion
   (and                                     \
   (job ?x (computer . ?y))                  |- rule body
   (not (and (supervisor ?x ?z)              |
             (job ?z (computer . ?w)))))    /

(rule (merge-to-form () ?y ?y)) - rules with no body
(rule (merge-to-form ?y () ?y))


(rule
   (merge-to-form
      (?a . ?x) (?b . ?y) (?b . ?z))          b comes first in merge
   (and (merge-to-form (?a . ?x) ?y ?z)        if
      (lisp-value > ?a ?b)))                  a is greater than b

(rule
   (merge-to-form
      (?a . ?x) (?b . ?y) (?a . ?z))          a comes first in merge
   (and (merge-to-form ?x (?b . ?y) ?z)        if
      (lisp-value > ?b ?a)))              b is greater than a

(MERGE-TO-FORM (2 ?A) ?X (1 2 3 4)
Responses to query:
(MERGE-TO-FORM (2 3) (1 4) (1 2 3 4)
(MERGE-TO-FORM (2 4) (1 3) (1 2 3 4)

It takes a little while to process because it has to check all possible answers.

(MERGE-TO-FORM ?X ?Y (1 2 3 4 5)
Responses to query:
going to take forever to find all the answers (2^5 or 32 possible answers)
This implementation is interpreted twice (once by our language to get it to LISP and
then interpreting the underlying LISP.

Question about if using lisp-value affects the non-directional nature of logic programming
and the answer is yes. Apparently anything except AND can make things not work right...