Hacker News Reader

This was (is?) what the semantic web dream was all about, and I find it funny that it took a corporation (FB) developing a clone before others discovered the concept. Semantic web data would be published as RDF data and clients would consume this data using a SPARQL query engine to get whichever shape of data that they desired.

To clarify: I mean that Prolog was under consideration to be used for what SPARQL was then developed, as a more readable and simpler query and also modeling language.

Several researchers working in this area considered the development of SPARQL to be a missed opportunity for better formalisms, since Prolog could have been used instead.

And, yes, to many who have worked with RDF, SPARQL and the various notations that have been developed for semantic web technologies, Prolog seems like a dream that shows what these technologies could have been, and can become in the future, i.e., easily processable, with a uniform and simple syntax that already has an ISO standard, and amenable to formal reasoning based on well-known logical rules.

> easily processable

> formal reasoning based on well known logical rules

Oof, I do not know any serious researcher of logic who would support that claim.

Prolog is, due to its age and heritage, inherently side/effectful and undecidable/turing-complete.

SPARQL has big fat warts, for sure, design by committee, bulky syntax, way too long spec, way too many capabilities, and questionable decidability (looking at you MAYBE clause), BUT at its heart it's non recursive conjunctive queries over regular path expressions.

CJ over PathRegex are a really elegant way to describe arbitrarily nested datastructures with flat queries, and are a lot more intuitive and concise than the corresponding datalog query.

Edit: Not saying that prolog doesn't have its place btw, it's a neat language with awesome capabilities, but is NOT a query language.

That's right- Prolog is not a query language.

But the claim I believe is that _Datalog_ is a subset of Prolog that is a query language. That claim is true by design.

Also, given bottom-up evaluation, Datalog programs are guaranteed to terminate and, restricted to definite clauses with no function symbols (of arity more than 0) they are also amenable to formal proofs of correctness, perhaps more so than Prolog itself.

EDIT: Oh. I assume that by "formal reasoning" you and triska are discussing formal proofs of correctness- otherwise I don't understand the disagreement. Resolution is a well-known logical rule (an inference rule) and it's amenable to formal reasoning, for sure.

Sure Datalog is a query language, but Prolog isn't.

I object to datalog being viewed as a subset of prolog, other than for historical reasons. It's just not useful as both languages differ significantly in philosophy, properties and implemenentation.

Datalog program equality is undecidable btw so while it's certainly more amenable to correctness proofs than prolog (which isn't at all with it's undecidability and implementation definedness everywhere), you'd still want more restricted logics for that.

Which isn't to say that's a bad thing, often times you want that power, and you don't need the correctness proof.

Fun fact, DLLite can tell you that the shin bone is a bone, and it can do so 10 billion times a second, and verifiably correctly so ;)

Edit: Some systems that arguably implement a superset of Datalog, but for which their Datalog subset is not a subset of Prolog are LogicBlox, Datomic, Datascript and TriQ-Lite.

>> Edit: Some systems that arguably implement a superset of Datalog, but for which their Datalog subset is not a subset of Prolog are LogicBlox, Datomic, Datascript and TriQ-Lite.

That's interesting, I didn't know about that. I might have a look now that you mention it.

Regarding correctnes proofs, I think triska knows this subject better than me but my understanding has always been that if you stay within the pure subset of Prolog (i.e. no destructive update of terms, no reads and writes to the database and basically nothing with side-effects) then you can actually fully reason about your programs at least in principle.

I see this in practice everytime I write an extensive piece of Prolog code (for the record, I do that a lot, for my PhD) and I end up using the assert/1-retract/1 mechanism to update the program database as the program runs. The problem with that is that it kicks you right out of the cozy world of immutability, right back to the world of programmig with mutable states. Once your program reaches a certain degree of complexity it becomes impossible to predict its state at any given point in time. [Edit: the reason is that if something goes wrong and your program fails unexpectedly, the program database is left in an unpredictable state - and you have to understand each such state with great precision or it all goes to hell in a handcart. You're back to doing memory allocation by hand basically].

The hurt I feel everytime I use the assert/retract mechanism, or rather, the difference between the level of pain using assert/retract compared to not using them, is, for me, a great measure of the extent to which pure Prolog code is predictable. I'd even say amenable to formal proofs of correcntess but I've never actually tried that, to be fair.

As to decidability, my understanding is that you can either have Turing completeness, or decidability, but not both. So to slightly correct my comment from above, Datalog itself is decidable only given a finite constant and predicate signature (the set of constants and predicate symbols). But finiteness means incompleteness.

Out of the examples I would take a look at the LogicBlox Stuff, they gave join algorithm research a big push with their Leapfrog-Triejoin.

The following papers ascend in difficulty, and are based on each other, but offer a fascinating glimpse into the connection of DPLL SAT solving and Conjunctive Query evaluation.

https://openproceedings.org/2014/conf/icdt/Veldhuizen14.pdf

https://arxiv.org/abs/1310.3314

https://arxiv.org/abs/1404.0703

As for reasoning and decidability, I think we need to clarify the decidability we're talking about. Decision problems are decidable or undecidable, and when one talks about decidability for a logic one usually means the decision problem wether a given formula of the logic is valid or not.

Everything finite is always decidable, because you can just enumerate all possibilities. And logics without negation (like Datalog without stratified negation) are generally (?) decidable because you can just construct a Herbrand interpretation accordingly.

However when we talk about correctness and formal reasoning there are other decision problems which are relevant, most of them revolve around stuff like "does this program implement this specification?", "does this program terminate?", "is this program keeping these invariants?", "are these two programs equal?"

Note that even if these problems are undecidable, it doesn't mean that they're always undecidable, just that they're not decidable in general, e.g. the halting problem is undecidable, but I can give you infinitely many turing-machines which always halt.

The pure side effect free fragment you describe is still at least as (?) powerful as FOL, even HOL if you include the meta predicates like call, thanks to the build-in predicates like forall. Heck I guess the build-in arithmetic alone will cost you decidability (of validity).

Datalog is even more restricted than what you describe and equality of two Datalog programs is not decidable according to https://core.ac.uk/download/pdf/82609701.pdf

So the question is, how much reasoning a.k.a. how many decision problems can you actually do/solve on Datalog and Prolog. For Datalog, I'd say quite a bit, but not everything, and for Prolog I'd argue very little. But both give you a lot of power in return and that's the price you have to pay.

Edit: And yeah, I don't envy you, on having to work with side-effectful prolog code. At some point it's just writing C with extra steps, ground through the Warren Abstract Sausage Machine. ^^'

Thanks for the papers you suggest! I'll try and have a quick look. I'm actually interested in the subject because my research does touch on Datalog (exactly because of the decidability guarantees).

Agreed about the definitions of decidability and formal correctness. Agreed also about the expressivity of the pure subset of Prolog. Oh, I remember now about Datalog and deciding equality. Yes. Well. You hit these kinds of walls anytime you try to do anything intersting with logic above the propositional level. The history of logic programming is a history of one negative result after the other and the compromises that must be made to avoid them. C'est la vie.

But we persist because there is a pot of gold at the end of the rainbow and what best way is there to spend your life than chasing rainbows? :0

>> So the question is, how much reasoning a.k.a. how many decision problems can you actually do/solve on Datalog and Prolog. For Datalog, I'd say quite a bit, but not everything, and for Prolog I'd argue very little. But both give you a lot of power in return and that's the price you have to pay.

Yes, I agree absolutely about that.

For example, my code doesn't _need_ the impure constructs. But it's a lot more efficient with them. So it's a trade-off. And a trade-off very common in Prolog which, to my opinion makes many pragmatic choices that sacrifice purity for the benefit of having a useable language.

That goes for reasoning about correctnes, also. The fact that you can sometimes reason about program correctness, given you can accept some restrictions to what kind of programs you can reason about is already miles ahead from what is possible with anything that isn't a logic programming language. That has to count for something.

>> Edit: And yeah, I don't envy you, on having to work with side-effectful prolog code. At some point it's just writing C with extra steps, ground through the Warren Abstract Sausage Machine. ^^'

Aw, I enjoy writing Prolog. So much so that I left my lucrative career in the industry to do research that would let me write a lot of it :)

> notations which are no longer a subset of ISO Prolog and therefore also not Datalog.

This is false. Datalog is not (or no longer) about prolog like syntax, Datalog as used nowadays in research, describes the semantics for a logic which includes conjunctive queries and recursion, often denoted as an abstract syntax consisting of rules with a body and head, no ascii syntax attached.

> Thus, they also do not immediately benefit from recent advances in Prolog systems in that they cannot directly be parsed and interpreted by them.

This is like saying, that Javascript can benefit from updates to the Java virtual machine. Prolog and Datalog require radically different evaluation strategies and implementations.

My last and only experience with Datalog (or a variation thereof) was (I believe) Logicblox, which (at least at the time) had zero support for pagination. In spite of all the supposed benefits of the system, that makes it fundamentally unsuitable imho.

What's the best example of modern Datalog?

Datomic. Also interesting:

https://github.com/sixthnormal/clj-3df

Datomic provides a fantastic range of query features, but the underlying Datalog engine does have drawbacks in how it evaluates results eagerly and requires intermediate result sets to fit in memory [0].

For comparison, I work on https://opencrux.com which uses lazy Datalog evaluation and can spill to disk when necessary. Naturally there are downsides to this approach also, including a dependence on seek-heavy use of local KV indexes.

clj-3df is definitely interesting although not strictly comparable :)

[0] https://docs.datomic.com/on-prem/query.html#memory-usage

Oh hello! I hadn't realised JUXT had their own products now, will definitely check this out.

A good way to try Datalog is to use a state-of-the-art Prolog system that supports SLG resolution (tabling).

SLG resolution is an evaluation strategy of Prolog programs that provides favourable termination properties compared to SLDNF resolution which is Prolog's default execution strategy.

A great example for this is XSB Prolog, since it has pioneered and refined many of these techniques and serves as an example and benchmark for many other Prolog systems in this area:

https://xsb.com/xsb-prolog

The nice thing is that this approach allows you to use Datalog, and at the same time gives you a Turing-complete programming language that is comparatively easy to grasp once you understand Datalog, while sharing many of the same advantages and being syntactically only a slight extension of it.

A turning complete query language sounds like a recipe for DoS attacks.

It is only Turing complete if you allow new rules. Usually a client would only be allowed to formulate query goals.

In that sense, GraphQL is Turing complete as well, as the underlying implementation could just simulate a Turing machine.

What I read from your post here is that GraphQL is safe by default and would require effort to make it dangerous while Datalog is dangerous by default and would require configuration to make it safe. I know which one I'd rather put on a server.

You have read that incorrectly. A Datalog/Prolog query does not define new rules. That's like calling arbitrary code on remote machines. You would never allow that.

But IF you were allowed to define new rules, THEN you could simulate a turing machine or create infinite reductions.

> A great example for this is XSB Prolog,

I'm really sorry but it honestly cannot be. I was curious because Datalog/Prolog based technologies are intriguing so I clicked on that link.

https://xsb.com/xsb-prolog seems to have no download but links to

http://xsb.sourceforge.net/ which claims version 3.8 (October 2017) is current and links to

http://xsb.sourceforge.net/downloads/downloads.html which does not specify a version but offers a tar.gz that contains version 3.7 from July 2016.

Going back to sourceforge and heading to the SVN https://sourceforge.net/p/xsb/src/HEAD/tree/trunk/XSB/ states version 3.9, November 2019 and looks pretty active commit-wise.

Okay, let's do that. Checking out trunk, I see perl and C scrolling by. While I have no problem with Perl, I know quite a few developers - especially in the web context - that find it rather off-putting. I get a README that tells me to read the manual in order to install. Fair enough. Opening that ( http://xsb.sourceforge.net/manual1/manual1.pdf ) gives me a 622 page PDF from October 2017. Chapter 2:

"Make sure that after you have obtained XSB, you have uncompressed it by following the instructions found in the file README." There were no such instructions. But well, configure and make are in build, that's fine and the rest of the instructions are clear.

I was confused why configure looked for mysql and make did something with Java but whatever, both worked great out of the box. Let me check the binary. I get a REPL, claiming to be version 3.8 from October 2017 and despite having 7 lines of output I have no idea how to quit out of that process, so I turn to Google which gives me http://xsb.sourceforge.net/shadow_site/manual1/node14.html

Neither ctrl^c, nor ctrl^d work, and halt + return is ignored. I go ahead, kill the process and delete the directory.

Alternatives to the above? That original site tells me to contact some organisation, "xsb prolog" on Google turns up ancient results.

Now compare that with https://graphql.org/graphql-js/

Just like many of these rather research centric languages, it does not matter how cool their tech is if that's the first experience people get. In my view experiences like the above are why they fail to gain adoption in today's world, not some technical aspect or technique. At least unlike much of the linked data and SPARQL world this thing compiled out of the box and I would have been up and running in about 10 minutes if I had any intention to continue.

That sucks. XSB is old code and I believe it was meant mostly as a proof of concept even at the time it was written. I doubt many people use it, even in research, nowadays.

I believe what triska meant about XSB is that it demonstrated the benefits of SLG resolution, by being a proof of concept like I say. So yes, XSB would be more of academic interest.

If you want a modern Prolog to play around with you should try Swi-Prolog. From the conclusion of your comment I'm assuming you haven't tried it because you wouldn't have trouble "getting up and running" in 10 minutes. Or 5 or so. Seriously, Swi's maintainers (triska is a contributor) have gone out of their way to make it useable.

Anyway, if you put in all this work to get XSB working I think you should definitely give Swi-Prolog a try. Sunk cost fallacy, innit.

Here's the link:

https://www.swi-prolog.org/Download.html

On windows, there's an installer. On Linux you can yum-install or apt-get etc an earlier version and try it out, then if you like it you can follow the Download page's links to figure out how to install a newer version (that does take a bit more work).

If you're stuck with Prolog, there's a discourse group, here:

https://swi-prolog.discourse.group/

People there are always happy to help newcomers (and will never send you to RTFM).

But be warned that learning Prolog is not easy. I help with markings and labs for Prolog courses at my university and students always have a hard time with it, until some things start to click.

EDIT: "halt." should work at any Prolog prompt. The "." is a statement terminator. You probably didn't get anything after "halt return" because you missed the dot.

EDIT II: Oh, I forget. You can try Swi-Prolog on Swish (Prolog notebooks):

https://swish.swi-prolog.org

So no need to install anything but keep in mind that some stuff is limited for security reasons (you can do a lot of damage with a language that lets you rewrite it on the fly).

Much appreciated, I kind of got what triska meant (didn't realize they were a contributor to that project), I just wanted to highlight that this is a real barrier for adoption of these alternative stacks. I find this interesting enough to spend more than those 10 minutes when I have time, sure. It's just that a random dev on the search for some component to solve something in their stack likely wont.

Just gave the SWI implementation a try and that was honestly a much better experience and I could immediately jump on their getting started guides to get a feel. Thanks for the pointers as well, I've got a few colleagues that actively use prolog but good to see that there's an active community out there.

> EDIT: "halt." should work at any Prolog prompt. The "." is a statement terminator. You probably didn't get anything after "halt return" because you missed the dot.

Whoops. Yup, I think I might have, I was under the impression that dot in the documentation was the sentence delimiter.

(And btw, my bad about the Perl comment, I just realized when setting up the SWI one that they seem to share a file extension with Perl.)

I agree, it's very bad to have to go through so much hassle when you just want to have a quick look to evaluate a possible tool for a problem you have right now. This is a difficult situation to resolve: usabiity won't improve until there's more users and until usability improves there won't be more users.

I'm glad you like Swi. It's not the fastest implementation but it's certainly the one with the largest community and the most quality-of-life features, documentation server, unit tests library, package manager etc. I love it :)

>> (And btw, my bad about the Perl comment, I just realized when setting up the SWI one that they seem to share a file extension with Perl.)

Oh yes, I totally forgot about that (can't say I use much perl!). It can look funny if you don't expect it :)

Anyway I hope you have time to look into the language more in the future. Like I say, it's hard to learn but it's worth the pain.

>Just like many of these rather research centric languages, it does not matter how cool their tech is if that's the first experience people get. In my view experiences like the above are why they fail to gain adoption in today's world, not some technical aspect or technique. At least unlike much of the linked data and SPARQL world this thing compiled out of the box and I would have been up and running in about 10 minutes if I had any intention to continue.

Just what I was thinking as I read the parent. This is the real answer to the OP's question.

You might want to check out Grakn (https://github.com/graknlabs/grakn/) - its query language is an implementation of recursive datalog with negation and comes with lazy execution. I am one of its developers.

Certainly not the best, but worth mentioning the Python implementation pydatalog.

https://sites.google.com/site/pydatalog/home