Ulrich Neumerkel, Stefan Kral
2016 · arXiv
Many Prolog programs are unnecessarily impure because of inadequate means to express syntactic inequality. While the frequently provided built-in `dif/2` is able to correctly describe expected answers, its direct use in programs often leads to overly complex and inefficient definitions --- mainly due to the lack of adequate indexing mechanisms. We propose to overcome these problems by using a new predicate that subsumes both equality and inequality via reification. Code complexity is reduced with a monotonic, higher-order if-then-else construct based on `call/N`. For comparable correct uses of impure definitions, our approach is as determinate and similarly efficient as its impure counterparts.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
Have you been exposed to more recent research on Prolog language constructs? In particular, I recommend the following publication: https://arxiv.org/abs/1607.01590 if_/3 and other declarative predicates like dif/2 are more general alternatives and likely good solutions in the cases you mention. They are still quite recent, at least if we ignore the fact that dif/2 was even available in the very first Prolog system, sometimes called Prolog 0.
These are valid concerns, arising mostly from inadequate implementations and a lack of modern features in early Prolog systems. In the past 20 years, many new language constructs and implementation advances were introduced and have become widely available in newer Prolog implementations to address precisely these problems among others. For example, inspired by pioneering systems such as XSB Prolog, modern Prolog systems such as Scryer Prolog support alternative execution strategies, internally implemented via delimited continuations as described by Desouter et al., and thus prevent many infinite loops that arise with the default execution…
strategy: https://www.ijcai.org/Proceedings/16/Papers/619.pdf As another example, in 2016, Neumerkel and Kral introduced if_/3 and related predicates, which are now available as library(reif) in Scryer Prolog: https://arxiv.org/abs/1607.01590 As yet another example, better indexing techniques such as JIT indexing help to improve determinism and efficiency automatically. As long as you keep to the pure monotonic core of Prolog, conjunction and disjunction are indeed semantically commutative, and different execution strategies are applicable. Of course, using !/0 and other constructs that rely on specific execution strategies forfeits this advantage.
That's super cool. I'm definitely not an expert on the subject but this paper about dif/2 intrigues me: https://arxiv.org/abs/1607.01590 And perhaps Ciao's paper could offer some hints? http://cliplab.org/papers/hermenegildo11:ciao-design-tplp.pd... You're probably already aware of it but Scryer Prolog seems like an interesting place to borrow ideas from. Both Scryer and Trealla have efficient string (list of characters) representations.
In general, using any of the mentioned predicates (->)/2, (\+)/1 or !/0 in Prolog code destroys essential properties we expect from classical logic, and therefore complicates declarative reasoning about the code to such an extent that it can be said to prevent it entirely. For example, both versions of foo/2 that are shown above suffer from the same core deficiency: If some_condition/1 has multiple solutions, then they are cut away and not generated at all. Therefore, for the most general query, ?- foo(X, Y). only a single answer, or a proper subset of all answers one would expect when reading (->)/2 as "implies", may be shown where, under a declarative reading based…
on first-order logic, there ought to be more. This is problematic because if any concrete solution S is cut off due to this deficiency, we can still force the Prolog system to yield it with: ?- X = S, foo(X, Y). So, we are in the situation that adding a constraint (X = S) yields a solution that is not shown when the constraint is removed. In other words, a specialized version of the predicate is more general than the original definition. This violates monotonicity, which is an essential property of classical first-order logic, and the basis for declarative debugging approaches that let us reason about the location of mistakes in Prolog predicates. To write good declarative Prolog code that is also efficient, we first need to find and implement the mechanisms that let us express predicates like foo/2 in such a way that they are efficient while retaining their generality as logical relations. One important building block pertaining to this concrete example was recently found with the new language construct if_/3, described in Indexing dif/2 by Ulrich Neumerkel and Stefan Kral: https://arxiv.org/abs/1607.01590 With if_/3, we can write foo/2 as: foo(X, Y) :- if_(some_condition(X), bar(Y, X) baz(X, Y)). The only requirement for this to work is to have a reified version of some_condition/1, in such a way that we can tell, from the implicit second argument, whether the condition holds or not, while still generating all answers for the most general query. Some predicates are already reified in the library, so we can write for example: ?- X = a, if_(X = a, Y = b, Y = c). X = a, Y = b. which succeeds without leaving choice-points, and that is good for performance. At the same time, we get both answers (X = a and also dif(X, a), i.e., X is not equal to a) on backtracking if we omit the first goal: ?- if_(X = a, Y = b, Y = c). X = a, Y = b ; Y = c, dif(X, a). Hence, the predicate retains important logical properties we expect from first-order logic, and this allows declarative reading and debugging based on these properties. To benefit from the true power of Prolog, such constructs must become available in Prolog implementations. For example, currently, the only Prolog system that ships with if_/3 as a built-in feature is Mark Thom's Scryer Prolog, where if_/3 and related predicates are available in library(reif): https://github.com/mthom/scryer-prolog https://github.com/mthom/scryer-prolog/blob/master/src/prolo... Other features that are necessary to make Prolog programs more declarative include CLP(ℤ) constraints, pure I/O, efficient implementation of partial strings as lists of characters etc., all of which are currently work in progress and as of yet only partially available in some Prolog systems. Over time, such features will become more widely available, and then they can be more easily taught and used to obtain Prolog programs that are pure and efficient.
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.