12.0  Prologue

SQL, Prolog, and Datalog are purely declarative: you describe what you want, not how to find it. The runtime - a query planner, a resolution engine, or a constraint solver - discovers the how. This is declarative programming at its most extreme: the language has no loops, no assignments, and no control flow. The same principles appear in functional languages as list comprehensions, pattern guards, and term rewriting.

12.1  Relational Queries

SQL expresses queries in terms of relations (tables), projections (SELECT), selections (WHERE), and joins. The query optimizer translates the declarative intent into an efficient execution plan without exposing that plan to the user. -- SQL: find employees earning above department average SELECT e.name, e.salary, e.dept FROM employees e WHERE e.salary > ( SELECT AVG(salary) FROM employees WHERE dept = e.dept ); -- Window function: running total per department (no GROUP BY needed) SELECT name, dept, salary, SUM(salary) OVER (PARTITION BY dept ORDER BY salary) AS running_total FROM employees; -- Haskell list comprehension (same relational model) -- Find pairs (a, b) where a + b == target pairs target xs = [ (a, b) | a <- xs, b <- xs, a + b == target, a <= b ] -- Python list comprehension (equivalent) pairs = [(a, b) for a in xs for b in xs if a + b == target and a <= b] List comprehensions in Haskell and Python are direct transliterations of SQL SELECT-FROM-WHERE: generators correspond to FROM, guards to WHERE, and the head expression to SELECT. All three are declarative specifications over a relation.

12.2  Logic Rules and Unification

Logic programming (Prolog, Datalog) defines facts and rules; a query asks what can be proved. The engine searches for variable bindings that satisfy the query using unification - matching a query term against a rule head by finding a consistent substitution. % Prolog: facts and rules define a knowledge base parent(tom, bob). parent(bob, ann). parent(bob, pat). ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). % Query: who are ann's ancestors? ?- ancestor(X, ann). % X = bob ; X = tom % Datalog (subset of Prolog - no function symbols, always terminates) % Used in database query engines (Souffle, Datomic) .decl edge(a: symbol, b: symbol) edge("a", "b"). edge("b", "c"). edge("c", "d"). .decl reachable(a: symbol, b: symbol) reachable(X, Y) :- edge(X, Y). reachable(X, Y) :- edge(X, Z), reachable(Z, Y). .output reachable -- a reaches b, c, d; b reaches c, d; etc. Datalog is decidable and always terminates, unlike general Prolog, which makes it safe for use as a query language inside databases and program analysis tools. Datomic uses Datalog as its query language; Souffle uses it for static analysis.

12.3  Constraint Satisfaction

Constraint programming defines a set of variables, their domains, and constraints that must hold. The solver searches the combined space, pruning branches that violate constraints. Problems like scheduling, map coloring, and Sudoku are natural fits. -- Python (python-constraint): map coloring from constraint import Problem, AllDifferentConstraint problem = Problem() regions = ["WA", "NT", "SA", "Q", "NSW", "V", "T"] colors = ["red", "green", "blue"] problem.addVariables(regions, colors) # Adjacent regions must have different colors adjacencies = [ ("WA", "NT"), ("WA", "SA"), ("NT", "SA"), ("NT", "Q"), ("SA", "Q"), ("SA", "NSW"), ("SA", "V"), ("Q", "NSW"),("NSW", "V"), ] for (a, b) in adjacencies: problem.addConstraint(lambda x, y: x != y, (a, b)) solution = problem.getSolution() # e.g. {"WA": "red", "NT": "green", "SA": "blue", ...} -- Haskell (Logic monad): constraint-like search import Control.Monad (guard) pythagorean :: Int -> [(Int,Int,Int)] pythagorean n = do c <- [1..n]; b <- [1..c]; a <- [1..b] guard (a^2 + b^2 == c^2) return (a, b, c) The guard function in Haskell’s list monad prunes the search space exactly as a constraint does: if the predicate fails, the branch produces no results. This is the same mechanism Prolog uses when a goal fails.

12.4  Pattern-Based Rewriting

Term rewriting defines a set of rules of the form pattern → replacement. The engine repeatedly applies rules to an expression until no rule matches (normal form). This is the computation model behind algebraic simplification, compiler optimizations, and the lambda calculus itself. -- Haskell: pattern matching is local term rewriting simplify :: Expr -> Expr simplify (Add (Lit 0) e) = simplify e -- 0 + e = e simplify (Add e (Lit 0)) = simplify e -- e + 0 = e simplify (Mul (Lit 1) e) = simplify e -- 1 * e = e simplify (Mul (Lit 0) _) = Lit 0 -- 0 * e = 0 simplify (Add e1 e2) = Add (simplify e1) (simplify e2) simplify (Mul e1 e2) = Mul (simplify e1) (simplify e2) simplify e = e -- Rascal / Stratego (dedicated term rewriting languages) -- rule simplify: -- Add(Lit(0), e) => e -- Mul(Lit(1), e) => e -- SQL query rewriting (done internally by the query optimizer) -- SELECT * FROM t WHERE 1=1 => SELECT * FROM t -- SELECT * FROM t WHERE a AND a => SELECT * FROM t WHERE a Haskell’s pattern matching clauses are term-rewriting rules evaluated top-to-bottom. Compiler backends use rewriting to simplify IR expressions; query planners use it to eliminate redundant conditions and push predicates closer to the data source.

12.5  Epilogue

Queries, logic rules, constraints, and term rewriting represent the most purely declarative end of the programming spectrum. In each case the programmer states relationships rather than procedures, and an engine - optimizer, resolver, solver, or rewriter - decides the execution strategy. Declarative programming is not one technique but a continuum of approaches unified by the goal of expressing what over how. The final chapter collects ten project ideas that put these techniques into practice.

12.6  References

Datalog - Wikipedia
Souffle Datalog - Docs
PostgreSQL SELECT - Docs
Term Rewriting - Wikipedia