Logic and Rule-Based Programming
Logic programming describes facts and rules.
7.1 Core idea
Logic programming describes facts and rules. The runtime answers queries by searching for assignments that satisfy the logical relationships. Prolog is a well-known logic programming language.
7.2 Facts, rules, and queries
_Not run — no Prolog system on the build machine; the queries below follow standard Prolog semantics._
Expected result (standard Prolog semantics — not run here; see the step-by-step model in 7.4):
The facts state parent relationships. The rule says X is a grandparent of Z when X is a parent of Y and Y is a parent of Z.
parent(ana, boris).
parent(boris, chika).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).?- grandparent(ana, chika).7.3 Variables and unification
In Prolog, names beginning with uppercase letters or _ are variables. Lowercase names are generally atoms. Unification finds substitutions that make terms structurally equal, subject to the language's rules.
_Not run (no Prolog system); the bindings follow the unification rules and are reproduced by the model in 7.4._
The terms unify with A = 1 and B = 2.
?- pair(A, 2) = pair(1, B).7.4 Backtracking
When a possible path fails, a Prolog runtime can backtrack and search for another matching rule or fact. Search order matters for performance and can matter for termination.
_Not run (no Prolog system); the step-by-step model in 7.4 shows this search._
The query can yield Drink = tea and, on requesting another solution, Drink = coffee.
Try it: unification and backtracking, step by step No Prolog system was available on the build machine, so the Prolog snippets in this module were not run. The explorer below is a small JavaScript model of Prolog's resolution (depth-first search with unification and backtracking) applied to this module's own facts and rules; it shows each step the search takes. It is a teaching model, not a full Prolog implementation.
likes(lee, tea).
likes(lee, coffee).
likes(sam, tea).
?- likes(lee, Drink).7.5 Recursion in logic programs
_Not run (no Prolog system)._ The first rule is the base case; the second expresses a recursive relationship. In a larger knowledge base, cycles and rule ordering can affect termination and repeated answers.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).7.6 Negation and the closed-world assumption
Some logic programming systems use negation as failure: a goal is treated as false when the system cannot prove it. This is not identical to proving a classical logical negation. Understand the database's completeness assumptions before using this model for important decisions.
7.7 Uses and limitations
Logic and rules are useful for:
Scheduling and configuration Eligibility and policy rules Complex search can be expensive; rule conflicts, incomplete facts, nontermination, and explainability require attention.
Exercise
Represent a small family tree or course prerequisite graph as facts and rules. Query ancestors or all valid learning paths.
Quiz
? Given `parent(ana, boris).`, `parent(boris, chika).` and the `grandparent` rule, what does `?- grandparent(ana, chika).` answer?
+ true :: X = ana, Y = boris, Z = chika satisfies both `parent` goals.
- false :: Both required facts exist.
- boris :: The query is a yes/no question; it does not return Y.
- An error :: The rule and facts are well-formed.
? What does unification of `pair(A, 2)` with `pair(1, B)` produce?
+ A = 1, B = 2 :: Matching arguments position by position gives these bindings.
- A = 2, B = 1 :: Arguments are matched by position.
- Failure :: The functors and arities match, so unification succeeds.
- A = B :: Each variable is bound to a constant.
? What does negation as failure mean? (select all that apply)
+ A goal is treated as false when it cannot be proven. :: That is the definition.
+ It relies on the closed-world assumption that all relevant facts are present. :: Missing facts become "false".
- It proves the classical logical negation. :: It is not identical to classical negation.
- It always terminates. :: Search can still fail to terminate.