3 ms·
Oooph. That's a bit larger than I was expecting. But good, this stuff probably needs more discussion. So I think the best way to understand logic-programming,
by dragontamer 5y ago
Oooph. That's a bit larger than I was expecting. But good, this stuff probably needs more discussion.
So I think the best way to understand logic-programming, is that a particular class of logic is chosen as the baseline. In the case of Prolog, "horn clause" logic is your baseline, and all of your "code" is a glorified horn clause.
The system then explores the horn-clause space, and this depth-first-search is happening behind the scenes by the compiler / runtime system. It combines clauses together (the "database") to find knowledge, and reports back solutions.
---------
Although horn clauses are limited, they're also relatively simple to search. So its a good location for a programming language to use as a baseline. You can search higher-orders of logic by thinking about the depth-first-search and building out new knowledge automatically (ie: writing more and more Prolog code).
---------
I feel like the idea of search is easily parallelized. Depth-first-search not so much so, but almost all searches can be conducted in both depth-first manner (sequentially) and breadth-first manner (parallel). A combination of depth + breadth would generalize into a large number of cores, such as GPUs or supercomputers.
- deleted 5y ago[deleted]
- YeGoblynQueenne 5y agoA couple terminological nits: Logic programs are sets of clauses so in Prolog, all your code is a set of clauses, not "a glorified horn clause", as you say. Horn clauses are the components of a logic program. Horn clauses can be interpreted as implications, "A IF B AND C AND D..." or "A IF (empty)" or "(empty) IF A". The first two are known as definite clauses and the last as a goal, or, in more database-y terminology, as "rules", "facts" and "queries". A logic program is written as a set of "facts" and "rules" and executed by running a "query" over it. Now all this is to say that Horn clauses aren't "limited". There are First-Order Logic (FOL) expressions that can't be encoded in Horn logic (e.g. "A OR B" where neither A nor B are negated), but definite clauses are sound and refutation-complete for SLD-resolution, a deductive procedure. Soundess means that any statement found true, is true; and completeness means that any true statement can be found true. In plain English, the restriction to Horn clauses is only syntactic and you can express anything, in a logic programming language, that can be expressed in any language in which you can encode a Universal Turing Machine. With apologies for the nitpicking :) Edit: As to the use of depth-first search (DFS), it's not that the space of Horn clauses is searched. That is what is done in Inductive Logic Programming where the goal is to find new programs. In the garden variety Logic Programming, which is deductive, DFS is used to find _resolvents_, which are literals (elements of clauses) with opposite signs (positive or negative) that are elminated to eventually reduce a query down to the empty-clause. If this can be done, then the query is refuted. Since a query is basically a set of negated literals, a successful refutation proves it (well, actually, it proves its _complement_; but this is what we usually want to prove). Searching for resolents is actually pretty efficient because the set of possible resolvents keeps getting smaller as one goes. Unless one gets stuck in an infinite loop, of course, which is a limitation of DFS. But, as the paper hints, there are other execution strategies, such as SLG-resolution, which can avoid some of that. Edit 2: Regarding higher-order logics, Prolog is normally described as a FOL language but in truth it cheats and allows higher-order variables. In particular, it allows variables quantified over _logic programs_. Which is definitely very much above the first-order. But that's a super big secret that should never be revealed to anyone outside logic programming circles. Ever.
- YeGoblynQueenne 5y agoYikes! O.o What I call "resolvents" above are not. Resolvents are the clauses that result from the elimination of complementary literals found by DFS. Haha. Good thing I sometimes go back and re-read my old comments...