Logic Programming

A ProgrammingParadigm based on logic (more accurately, the PredicateCalculus?). A program is represented by a set of facts (statements/relationships which are held to be true), and a set of axioms (i.e. if A is true, then B is true). The axioms and clauses may have arguments.

For example, one could define the relation child(A,B), meaning that A is a child of B. One then could establish a set of facts (stored in a database--see below):

 child(Pebbles,Fred)
 child(Pebbles,Wilma)
 child(Wilma,Freds-mother-in-law) (what's her name?)
 child(Bam-bam,Barney)
 child(Bam-bam,Betty)

One can query the database:

 child? (Pebbles,Fred) -> True
 child? (Pebbles,Barney) -> False (at least Fred hopes not!)

One then can define define a descendent relationship, the transitive closure of the child relationship (this is pseudocode, obviously)

 descendent(A,B) := child(A,B)
 descendent(A,B) := exists(x : child(A,x) && descendent(x,B))

One can query these relationships as well.

 descendent? (Pebbles,Fred) -> True
 descendent? (Pebbles,Freds-mother-in-law)? True
 descendent? (Pebbles,Barney) -> False

A TheoremProvingSystem is used to search the database of facts and to determine what is true and what isn't.

There's a lot more to this than this simple example shows. The above example (and virtually all logic programming languages) use the ClosedWorldAssumption--meaning if it isn't explicitly stated as true (either as a fact, or inferrable from the facts and axioms), then it's false.

The PrologLanguage is perhaps the most widely known example of a LogicProgrammingLanguage, and, while it's certainly useful, it falls short of being a logic programming language in the theoretical sense. You can imagine Prolog as being like a theorem-prover, and you tell it rules like If A and B are true, then C is true. But, as with most other programming languages, it turns out that Prolog can be quite sensitive to the order of statements. For instance, in Prolog, the rule If A and B are true, then C is true might not be the same as the logically equivalent If B and A are true, then C is true. Furthermore, Prolog has a number of important but theoretically messy constructs that are used for flow control, internal database manipulation, etc. These sorts of things don't fit into the logic programming paradigm.

DataLog is a very clean, simple LogicProgramming language - it would be a very fine 'exemplar' of LogicProgramming, similar to how LambdaCalculus is the exemplar of FunctionalProgramming.

The MercuryLanguage is a more modern attempt at creating a logic programming language.

TemporalLogic has been used to introduce SideEffects in a pure way (seen in languages Dedalus, Bloom, others). Every fact has a 'timestamp' (fact@time), at least logically, and there must be explicit rules that propagate a fact over time (fact@(t+1) :- fact@t). By controlling the rules to propagate facts, you can also use rules to 'delete' facts by blocking their propagation. The implementation must be smart about propagation rules so that it doesn't burn CPU computing them, so special syntax is sometimes used. In most implementations (as in traditional TemporalLogic) a discrete, linear model of time is used. Facts are allowed to depend on facts only from the same instant or the previous instant. While the total set of facts grows monotonically, 'old' facts can be garbage-collected, and it is possible to model state and changes in the fact set over slices in time. IO is integrated statefully and eventfully. For example, one might compute the desired position of a robotic arm at any given instant, and incoming events (such as a mouse-click, or an incoming message) are generally just queued up and spread across a few instants. FFI calls are expressed as facts that are true for an instant in time. Integration of the discrete time model with real-time has been done, in Bloom at least, by giving easy access to a 'periodic' event (e.g. request a signal at 10 Hz).

Dedalus adds TemporalLogic to DataLog. It is worth noting that, even though DataLog is not TuringComplete (since it can compute only a finite set of facts for a given instant in time), the addition of TemporalLogic makes it complete (since one can compute an infinite number of instants). One can express arbitrary loops, queues, et cetera in TemporalLogic. Bloom is basically a more modular Dedalus with built-in support for RelationalModel and CollectionOrientedProgramming.

Without TemporalLogic, LogicProgramming languages (such as PrologLanguage) have typically been 'impure' - having SideEffects just for evaluating the logic or querying a fact. Impure LogicProgramming makes analysis, refactoring, and reuse quite difficult, and defeats the DeclarativeProgramming properties (since the order-of-expression and duplicate expression have a significant effect on program behavior).

I was telling a programmer about logic programming the other day, and they thought it sounded like a terribly boring way to write programs. What they like about programming is that you can specify the steps for things, and logic programming gets rid of that and wants to turn programming into mathematics. Maybe that's useful, he said, but it doesn't sound like much fun. And who wants to learn all that logic?

Surprisingly (to most people), the Make language implemented by a MakeTool like GnuMake is a logic programming language. Attempts to use it as if it were some other sort of language account for many frustrations with it.

Not really. The 'product : dependencies' aspect might be LogicProgramming-like, but is not an inference rule... and not even used as one.
Make is DeclarativeProgramming, like regexps, SQL, etc. In this sense, it states the "what," not "how." -- TobyThain

A "follow-on" paradigm to LogicProgramming is ConstraintLogicProgramming.

Paradigms with similar characteristics: ConcurrentConstraintProgramming, TermRewriting, ReactiveProgramming.

One interesting area of research in ComputerScience is the unifcation of LogicProgramming with RelationalDatabases. There is a very strong correspondence between the relations in a LogicProgramming language (and the facts contained therein), and relational tables (and the records contained therein).

LogicProgramming:

One of the 5 known programming paradigms (procedural, object-oriented, logic, functional, and ... wasn't there another one ?) [cf. ThereAreExactlyThreeParadigms]

The idea of using logic to write computer programs by specifying what the programs should do, and not how they should do it. In logic programming, you write the specification for a program, and the computer executes it. Also see DeclarativeProgramming.

Would you consider NUnit/MSUnit testing to be incorporating logic programming concepts in to OOP (albeit in a very limited area)?

See LogicProgrammingInCpp for an implementation in CeePlusPlus.

Related Paradigms: TemporalLogicProgramming

ConstraintProgramming, ConstrantLogicProgramming?, ConcurrentConstraintProgramming, ,

ProgrammingParadigm