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