# SICP 8b Logic Programming II

By now, pattern-matching syntax should be second nature to us.

```(a ?x c)
(job ?x (computer ?y))
(job ?x (computer . ?y))
(a ?x ?x)
(?x ?y ?y ?x)
(a . ?x)
```

`match` asks the question: is there any way to match a pattern with data, subject to bindings already in a dictionary?

```(match pat data dictionary)
```

The matcher was already covered in the lecture on systems with rule-based control, so we'll skip it here.

## 1 Implementation of means of combination

We have closure. The means of combination have the same overall structure as the primitive things that we're combining.

## 2 Implementation of means of abstraction

How do we implement a rule? Here's a quick recap of a rule.

```(rule (boss ?z ?d)
(and (job ?x (?d . ?y))
(supervisor ?x?z)))
```

We match the conclusion of the rule against something we want to check is true. That match gives us a dictionary, and with respect to the dictionary, we process the body of the rule.

Actually, this is not quite true.

```(boss ?who computer)
```

Here we aren't matching a pattern against data, we are matching two patterns and asking if they are consistent. A pattern matcher does not suffice; we require a unifier, a slight generalisation of a pattern matcher. A unifier takes two patterns and finds the most general thing that can be substituted for the variables in those two patterns to satisfy both simultaneously.

```unify (?x ?x)
with ((a ?y z) (a b ?z))
results:
?x : (a b c)
?y : b
?z : c
```

A more complicated example.

```unify (?x ?x)
with ((?y a ?w) (b ?v ?z))
results:
?y : b
?v : a
?w : ?z
?x : (b a ?w)
```

Nothing clever is happening here. Just recursion.

```unify (?x ?x)
with (?y (a . ?y))
should result in:
?x : ?y
?y : (a a a ...)
```

`y` must be an infinite list of `a`'s. The logic program can't handle this.

## 3 Apply

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

Compare this to applying a procedure.

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

We see the eval apply loop yet again.

## 4 Naming conflicts

To avoid name conflicts, we use the environment model. A more brutal (and inefficient) method is also possible: every time a rule is applied, rename all of the variables in the rule to some new unique names that won't conflict with anything else.

## 5 Not

`and`, `or`, `not`, and the logical implication of rules are not quite as they seem.

In logic `(and p q)` and `(and q p)` are equivalent statements. This is not the case in our language.

```(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))))
```

The first statement functions as expected; the second leads to an infinite loop. Changing `and`​s and `or`​s in logic programming can drastically change the speed of the queries.

All humans are mortal.
All Greeks are humans.
Socrates is a Greek.
∴ Socrates is a Greek.

```(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))))
(and (Greek ?x) (god ?x)))
(rule (perfect ?x)
(and (not (mortal ?x))
(not (fallible ?x))))
```

```(and (address ?x ?y)
(perfect ?x))
results:
Olympus

(and (perfect ?x)
`not` does not mean the logical not. `not` means not deducible: there no such thing in the database, as opposed to not true. This is called the closed world assumption. Under this assumption, all kinds of issues turn up, such as `not not x` not being equal to `x`. Closed world assumption is dangerous for real reasoning problems, marking a chasm between declarative and imperative knowledge.