In imperative programming you tell the computer how to do something, step by step. In declarative programming you state what result you want or what is true, and the language works out how. SQL is a familiar declarative language: you describe the rows you want, not how to find them.

Facts, rules and queries

Logic programming languages such as Prolog use a knowledge base made of:

  • Facts: statements that are true.
  • Rules: logical relationships that let new facts be inferred.
  • Queries (goals): questions asked of the knowledge base.
parent(tom, ann).
parent(tom, bob).
parent(ann, cy).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
sibling(X, Y) :- parent(P, X), parent(P, Y), X = Y.

Names starting with a lowercase letter are constants (atoms), and names starting with a capital letter are variables. :- reads “if” and the comma reads “and”. Every fact and rule ends with a full stop.

Queries:

?- parent(tom, ann).        % true
?- parent(tom, X).          % X = ann ; X = bob
?- grandparent(tom, Who).   % Who = cy

How the engine works

Prolog answers a query by searching the facts and rules from top to bottom. It tries to unify (match) the query with a fact or rule head, replacing variables with values. If a step fails it uses backtracking: it goes back to the last choice point and tries the next option. This depth-first search produces every answer to the question.

Example: for grandparent(tom, Who) it must prove parent(tom, Y), so it tries Y = ann, then parent(ann, Who) gives Who = cy. Backtracking would later try Y = bob, which has no children, and fail.

Where it is used

Declarative and logic approaches suit problems about relationships and constraints: expert systems, medical diagnosis, natural language processing, scheduling, puzzle solving and database queries. Compare the approaches:

Paradigm You describe Example
Imperative / procedural Steps to follow Pseudocode, Python
Object-oriented Interacting objects Java
Functional Functions and composition Haskell
Declarative / logic Facts, rules and goals Prolog, SQL

A drawback is less control over performance, and some tasks such as detailed input and output are awkward. Choosing a paradigm means matching it to the problem.

Check your understanding

What does declarative programming focus on?

  • What the result should be, not the steps
  • Exact step-by-step instructions
  • Hardware details
  • Memory addresses

Answer: What the result should be, not the steps. The language works out how.

In Prolog, how is a variable written?

  • Starting with a capital letter
  • Starting with a lowercase letter
  • In quotation marks
  • With a # sign

Answer: Starting with a capital letter. Lowercase names are constants.

What is backtracking?

  • Returning to an earlier choice point to try another option after failure
  • Deleting facts
  • Running code backwards in time
  • Compiling twice

Answer: Returning to an earlier choice point to try another option after failure. It lets Prolog find every solution.

Which statement is a rule?

  • parent(tom, ann).
  • grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
  • ?- parent(tom, X).
  • X = ann

Answer: grandparent(X, Z) :- parent(X, Y), parent(Y, Z). A rule has a head, :- and a body of conditions.

PreviousNext