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(Wilma,Freds-mother-in-law) (what's her name?)
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
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.
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.
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
is a more modern attempt at creating a logic programming language.
has been used to introduce SideEffect
s 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
. 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
languages (such as PrologLanguage
) have typically been 'impure' - having SideEffect
s 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
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
Paradigms with similar characteristics: ConcurrentConstraintProgramming
One interesting area of research in ComputerScience
is the unifcation of LogicProgramming
s. 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).
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)?
for an implementation in CeePlusPlus
Related Paradigms: TemporalLogic