5 ms·

Parallel Logic Programming: A Sequel

73 points by matt_d 5y ago

JadeNB 5y ago
From the abstract: > The comprehensive survey of the first twenty years of research in parallel logic programming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. … This survey provides a review of the research in parallel logic programming covering the period since 2001, thus providing a natural continuation of the previous survey. The goal of the survey is to serve not only as a reference for researchers and developers of logic programming systems, but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logic programming.
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 ago
  A 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 ago
    Yikes! 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...
nemoniac 5y ago
That's going to be a long read. Looking forward to it. I'm old enough to remember the Japanese Fifth Generation Computer Project that went all in on parallel logic programming. Now, as the abstract of this article points out, we have "ubiquitous multi-core and highly-connected architectures", has its time finally come? I would be very interested to read the opinions of some knowledgeable people here (triska?) about how well placed some existing software is, e.g swipl, mercury, and friends, to take advantage of it.
kristjansson 5y ago
The referenced paper from 2001: https://dl.acm.org/doi/abs/10.1145/504083.504085 https://dl.acm.org/doi/abs/10.1145/504083.504085
galaxyLogic 5y ago
Interesting. Are there already some practical Prolog or Datalog implementations which can take advantage of multiple cores?
- refset 5y ago
  RDFox [0] is a commercial system with "Parallel Datalog Materialisation" [1] [0] https://www.oxfordsemantic.tech/product https://www.oxfordsemantic.tech/product [1] http://www.cs.ox.ac.uk/dan.olteanu/papers/mnpho-aaai14.pdf http://www.cs.ox.ac.uk/dan.olteanu/papers/mnpho-aaai14.pdf
infogulch 5y ago
A recent submission seems related: The joy of concurrent logic programming https://news.ycombinator.com/item?id=29139437 https://news.ycombinator.com/item?id=29139437 http://www.call-with-current-continuation.org/articles/the-joy-of-concurrent-logic-programming.txt http://www.call-with-current-continuation.org/articles/the-j...

73 points by matt_d 5y ago

From the abstract: > The comprehensive survey of the first twenty years of research in parallel logic programming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. … This survey provides a review of the research in parallel logic programming covering the period since 2001, thus providing a natural continuation of the previous survey. The goal of the survey is to serve not only as a reference for researchers and developers of logic programming systems, but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logic programming.

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 ago
A 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 ago
  Yikes! 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...

nemoniac 5y ago

That's going to be a long read. Looking forward to it. I'm old enough to remember the Japanese Fifth Generation Computer Project that went all in on parallel logic programming. Now, as the abstract of this article points out, we have "ubiquitous multi-core and highly-connected architectures", has its time finally come? I would be very interested to read the opinions of some knowledgeable people here (triska?) about how well placed some existing software is, e.g swipl, mercury, and friends, to take advantage of it.

kristjansson 5y ago

The referenced paper from 2001: https://dl.acm.org/doi/abs/10.1145/504083.504085 https://dl.acm.org/doi/abs/10.1145/504083.504085

galaxyLogic 5y ago

Interesting. Are there already some practical Prolog or Datalog implementations which can take advantage of multiple cores?

refset 5y ago
RDFox [0] is a commercial system with "Parallel Datalog Materialisation" [1] [0] https://www.oxfordsemantic.tech/product https://www.oxfordsemantic.tech/product [1] http://www.cs.ox.ac.uk/dan.olteanu/papers/mnpho-aaai14.pdf http://www.cs.ox.ac.uk/dan.olteanu/papers/mnpho-aaai14.pdf

infogulch 5y ago

A recent submission seems related: The joy of concurrent logic programming https://news.ycombinator.com/item?id=29139437 https://news.ycombinator.com/item?id=29139437 http://www.call-with-current-continuation.org/articles/the-joy-of-concurrent-logic-programming.txt http://www.call-with-current-continuation.org/articles/the-j...