Computer Science › Section G · Programming languages › Topic G.7
Declarative programming
What if you could describe a problem precisely and let the computer work out how to solve it? Declarative programming does exactly that, and its logic-based form shows how a machine can draw conclusions from facts by pure reasoning.
Saying what, not how
In the imperative paradigm, the programmer designs an algorithm and writes it as commands. In the declarative paradigm, the programmer describes the problem, and the system applies one general-purpose problem-solving method, built in once and for all, to find the answer. The programmer's job shifts from inventing steps to stating facts and requirements accurately. This only works when a single general method can cope with every problem written in the language, so the art of designing a declarative language lies in choosing that method well.
Declarative languages you may already know
SQL is one of the most widely used declarative languages. The query SELECT name FROM members WHERE age >= 18; states which rows are wanted and never says how to find them; the database chooses whether to scan the table or use an index. HTML describes a page's structure, headings, paragraphs and links, and leaves the drawing to the browser. Compare an imperative version of the SQL query: create an empty list, loop over every member, test the age, and append matching names. Both give the same result, but the declarative version leaves the method to the system. The topic "Querying with SQL" treats SQL in depth.
Logic and the resolution rule
Logic programming builds on formal logic. Statements are written in clause form: simple statements, possibly negated with ¬ (not), joined by OR. The rule "if it rains, the pitch is wet" becomes ¬rain OR wet, which is true exactly when the original is. The inference rule called resolution combines two clauses in which one contains a statement and the other contains its negation. From A OR ¬B and B OR C, resolution derives A OR C, called the resolvent: if B is false the first clause forces A, and if B is true the second forces C. The resolvent is a logical consequence, true whenever both originals are.
Proof by finding a contradiction
A set of statements is inconsistent if they cannot all be true at once, such as P together with ¬P. Resolving P with ¬P leaves nothing at all, the empty clause, which signals a contradiction. Repeated resolution will always reach the empty clause from an inconsistent set of clauses. This gives a general method of proof: to show that a statement follows from some facts, add its negation to the facts and resolve repeatedly. If the empty clause appears, the negation cannot be true, so the statement itself must be. Because the method never changes, it can serve as a declarative language's built-in problem solver.
Worked example: a proof by resolution
Facts: if the alarm sounds, the guard comes; if the guard comes, the door opens; the alarm sounds. Show that the door opens. Steps: (1) Write the facts as clauses: ¬alarm OR guard, ¬guard OR door, and alarm. (2) Add the negation of the goal: ¬door. (3) Resolve ¬guard OR door with ¬door to get ¬guard. (4) Resolve ¬alarm OR guard with ¬guard to get ¬alarm. (5) Resolve ¬alarm with alarm to get the empty clause. (6) The four clauses are inconsistent, so ¬door cannot hold alongside the facts, and the door opens. No algorithm specific to doors or alarms was written; resolution did all the work.
Unification
Real facts involve variables. The rule "anyone who has passed calculus may take mechanics" applies to every person, while a fact names one person, say Ravi. Resolution needs exactly opposite statements, so the system first finds values for the variables that make the two sides match. Here it substitutes Ravi for the variable, turning the general rule into one about Ravi, which can then be resolved with the fact. Finding such substitutions is called unification. Unification lets one general rule be applied to many specific cases, and it is also how a logic system produces answers: the values it substitutes are the results reported to the user.
Prolog: facts and rules
Prolog, short for programming in logic, was created in Marseille in the early 1970s by Alain Colmerauer and Philippe Roussel, and its built-in method is repeated resolution with unification. A program is a list of facts and rules, each ending with a full stop. Constants start with a lowercase letter and variables with a capital. The facts prereq(arithmetic, algebra). prereq(algebra, calculus). prereq(calculus, mechanics). record which course comes directly before which. A rule reads "this holds if these hold", with :- meaning "if" and a comma meaning "and": before(X, Z) :- prereq(X, Z). and before(X, Z) :- prereq(X, Y), before(Y, Z). This second rule is recursive.
Asking Prolog questions
A program runs when a user poses a goal, a query. The query ?- prereq(algebra, calculus). matches a fact, so Prolog answers true; older systems print yes. A query with a variable asks for values: ?- prereq(X, calculus). gives X = algebra. Prolog tries clauses from top to bottom and the conditions of a rule from left to right, and when a path fails it backtracks to try the next possibility. For ?- before(X, calculus). it first finds X = algebra from the first rule, then, when asked for more, X = arithmetic through the recursive rule. Anything it cannot prove is reported as false, which is called the closed-world assumption.
Worked example: tracing a recursive query
Query: ?- before(arithmetic, mechanics). Steps: (1) First rule: is there a fact prereq(arithmetic, mechanics)? No, so Prolog backtracks to the second rule. (2) Second rule: find prereq(arithmetic, Y). Unification gives Y = algebra. The new goal is before(algebra, mechanics). (3) For that goal, the first rule needs prereq(algebra, mechanics), which fails. The second rule finds prereq(algebra, Y) with Y = calculus, leaving before(calculus, mechanics). (4) The first rule needs prereq(calculus, mechanics), which is a fact. (5) Every goal is satisfied, so Prolog answers true. The chain arithmetic, algebra, calculus, mechanics was discovered, not programmed step by step.
Functional programming: a close relative
Functional programming is sometimes grouped with the declarative style, because programs are built from expressions rather than sequences of commands. A pure function always gives the same output for the same inputs and changes nothing outside itself, and data is usually immutable, never updated in place. Functions can be passed as values: in Python, list(map(lambda n: n * 2, [1, 2, 3])) gives [2, 4, 6] without altering the original list. Haskell is purely functional, while LISP, Scheme and Python support the style alongside others. Logic programming remains the clearest case of declarative programming, because its solving method is entirely built in.
Common mistakes to avoid
Thinking declarative means "no algorithm": there is always one, built into the system rather than written by the programmer. Reversing Prolog's capitalisation, so Ravi becomes a variable and x a constant. Forgetting the full stop at the end of each clause. Assuming clause order never matters: writing the recursive rule as before(X, Z) :- before(X, Y), prereq(Y, Z). puts the recursive goal first, so Prolog can recurse endlessly without making progress. Reading Prolog's false as "proven untrue" when it means "cannot be proved from these facts".
Key takeaways
Declarative programs describe the problem and rely on a general built-in method to solve it; SQL and HTML are everyday examples. Logic programming uses clauses and resolution: resolving complementary statements yields a resolvent, and reaching the empty clause after adding a goal's negation proves the goal. Unification substitutes values for variables so rules apply to specific cases. Prolog programs are facts and rules, run by queries that are answered through top-to-bottom, left-to-right search with backtracking, under a closed-world assumption.
Flashcards
Flashcard
Describe the problem; a built-in method solves it
Test your understanding
Question 1 of 5
What does resolution derive from the clauses P OR ¬Q and Q OR ¬R?
Question 2 of 5
To prove a goal G from some facts by resolution, what does a logic system do?
Question 3 of 5
With the facts prereq(arithmetic, algebra). prereq(algebra, calculus). prereq(calculus, mechanics). what does ?- prereq(algebra, Y). return?
Question 4 of 5
Which statement about Prolog's names is correct?
Question 5 of 5
Prolog answers false to ?- prereq(mechanics, calculus). with the course facts above. What does this mean?
