Relational Programming
From the programmer’s point of view, relational programming extends declarative programming with a new kind of statement called a "choice". Conceptually, the choice statement nondeterministically picks one among a set of alternatives. During execution, the choice is implemented with search, which enumerates the possible answers.
The Relational Computation Model
The choice and fail Statements
The relational computation model extends the declarative model with two new statements,
choiceandfail:
- The
choicestatement groups together a set of alternative statements. Executing a choice statement provisionally picks one of these alternatives. If the alternative is found to be wrong later on, then another one is picked.- The
failstatement indicates that the current alternative is wrong. Afailis executed implicitly when trying to bind two incompatible values
Search Tree
- Relational programs run sequentially.
- Choices are tried left to right. On failure, execution backtracks to the last choice point.
- Execution forms a search tree, with nodes as choices and subtrees as alternatives.
Encapsulated Search
- A relational program can execute in many ways, depending on the choices made. The search strategy can be controlled (e.g., depth-first, breadth-first) and so can the number of solutions (one, all, or on demand).
Encapsulated search provides this control by running the program in a controlled environment, an environment decides which choices are made (and when), it also isolates the program’s variable bindings from the rest of the application.
This allows the following properties to emerge:
- Modularity
- Multiple relational programs can run concurrently without interference.
- Compositionality
- One encapsulated search can safely run inside another
The Solve Function
We provide encapsulated search by adding one function,
Solve, to the computation model. The call{Solve F}is given a zero-argument functionF(or equivalently, a one-argument procedure) that returns a solution to a relational program. The call returns a lazy list of all solutions, ordered according to a depth-first search strategy.(…)
Solve is compositional, i.e., it can be nested: the function
Fcan contain calls toSolve. UsingSolveas a basic operation, we can define both one solution and all-solutions search.
Relation to Logic Programming
The advantage of logic programming is that programs have two semantics, a logical and an operational semantics, which can be studied separately. If the underlying logic is chosen well, then the logical semantics is much simpler than the operational. However, logic programming cannot be used for all computation models. For example, there is no good way to design a logic for the stateful model.
Logic and Logic Programming
A logic program is a statement of logic that is given an operational semantics, i.e., it can be executed on a computer. If the operational semantics is well designed, then the execution has two properties: it is correct, i.e., it respects the logical semantics (all consequences of the execution are valid logical consequences of the program considered as a set of logical axioms) and it is efficient, i.e., it allows writing programs that execute with the expected time and space complexity.
Propositional Logic
Propositional formulas consist of expressions combining symbols such as p, q, r, and so forth together with the connectors ∧ ("and"), ∨ ("or"), ↔ ("if and only if"), → ("implies"), and ¬ ("not").
First-Order Predicate Calculus
Propositional Logic is rather weak as a base for logic programming, principally because it does not allow expressing data structures. First-order predicate calculus is much better suited for this. The Predicate Calculus generalizes propositional logic with variables, terms, and quantifiers A logical formula in the predicate calculus has the following grammar, where \(\left< a \right>\) is an atom and \(\left< f \right>\) is a formula: