[HN Gopher] Parallel Logic Programming: A Sequel
___________________________________________________________________
Parallel Logic Programming: A Sequel
Author : matt_d
Score : 52 points
Date : 2021-12-09 16:08 UTC (6 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| nemoniac wrote:
| 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 wrote:
| The referenced paper from 2001:
|
| https://dl.acm.org/doi/abs/10.1145/504083.504085
| dragontamer wrote:
| 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]
| YeGoblynQueenne wrote:
| 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.
| JadeNB wrote:
| 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.
___________________________________________________________________
(page generated 2021-12-09 23:01 UTC)