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

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.

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.

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.

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

Ask for the address of all perfect beings.

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

(and (perfect ?x)
     (address ?x ?y))
results:
nothing

So is it Mount Olympus, or nothing? How do we know that Zeus is not mortal, and not fallible? This is not defined anywhere.

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.

If you start building up real reasoning programs based on this, think how dangerous that is. You're saying: "I know I'm in a position to deduce everything true that's relevant to this problem. I'm reasoning, and built into my reasoning mechanism is the assumption that anything that I don't know can't possible be relevant to this problem, right?" There are a lot of big organisations that work like that. Most corporate marketing divisions work like that.