Logic programming

Logic programming is a very general paradigm, but the essential idea is similar to the constraint-satisfaction idea in non-deterministic computing combined with a powerful pattern-matching algorithm called unification. The difference is that we now expect all possible solutions to be returned, and, more importantly, support for logical bidirectional computation. For instance, we would expect to be able to answer questions like "What number adds to 1 to give 2?" as well as "What do 1 and 1 add up to?" using a single add function definition.

Features

The constraints in a logic program are typically defined using primitive and compound logical rules. The data units can be varied, but in a query language, these would be just the data entries in a relational database. For example, these would be entered into a Lisp-based implementation as the assertions:

(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)

Simple queries along with the means of combining them that carry logical meaning (eg. and,or,not) are the primitive operations of such a query language. Abstractions or rules can then be formed out of these primitives similar to how functions are defined. To retrieve information, the database could be queried with simple/compound queries like:

;simple query
(job ?x (computer programmer))

;compound query
(and (job ?person (computer programmer))
	 (address ?person ?where))

;rule definition
(rule (lives-near ?person-1 ?person-2)
      (and (address ?person-1 (?town . ?rest-1))
           (address ?person-2 (?town . ?rest-2))
           (not (same ?person-1 ?person-2))))

;rule query
(and (job ?x (computer programmer))
	 (lives-near ?x (Bitdiddle Ben)))

The system responds by finding all possible assignments to the pattern variables identified with ? that match the pattern provided and returning the results in some convenient form. Implementing this requires search strategies which can be based on the amb evaluator used in non-deterministic computing, stream operations, or other supportive frameworks.

Stream-based implementation

Logic program interpreters are structured similar to any old interpreter, with a eval-apply loop, internal evaluation procedures to simplify rules into language primitives, and environments consisting of frames of variable bindings. The particular operations expected by our query language can be conveniently implemented with streams.

A stream-based implementation can be built around streams of frames and pattern-matching algorithms that return streams of frames satisfying patterns in queries. Pattern-matching algorithms include

1. Simple pattern-matching: Iterating over the database, testing all possible variable bindings to see if the pattern is satisfied and returning a stream of frames containing the valid bindings. This is enough to implement even compound queries, which, interestingly, can be viewed as filters on the streams of frames applied in series (and) or in parallel (or).
2. Unification: This is basically a generalization of the pattern-matcher required for implementing rules. It allows variables to be present in both the "pattern" (query) and the "datum" (function signature / rule conclusion) can contain variables. For eg., one might need to unify (?x a ?y) with (?y ?z a) to obtain a frame containing the bindings ?x = ?y = ?z = a.

The difference between the two is akin to the difference between straightforward variable definitions like x=1,y=2 vs solving a system of equations x=y-1,y=2x, explaining why unification is generally much more complex to implement.

Caveats worth mentioning:

1. This is a procedural implementation of a subset of logic, not full-blown logical inference. Some operations like not behave differently from their logical equivalents.
2. Infinite loops pop up pretty often if programs are not well-written.
3. Serious inefficiency issues pop up too. Order of computation matters often, and should be optimized whenever possible.