20 ms·

All examples shown in the article can be ran with Datalog too (with stratified negation and arithmetic comparison), which has a clearer execution model and look

All examples shown in the article can be ran with Datalog too (with stratified negation and arithmetic comparison), which has a clearer execution model and looks almost identical to Prolog. Prolog underneath is doing backtracking, while Datalog is finding a least fixed point of derived relations where iterating on data won't produce more relations, and is akind to SQL (but usually stronger because of recursion).

ModernMech 5mo ago
Importantly, Datalog is not Turing-complete though.
- gobdovan 5mo ago
  Exactly :) It is terminating due to the LFP semantics I was pointing out, it's more akin to SQL than to Prolog. The article doesn't even show the usage of the Prolog cut (`!`). And yet Prolog can express all examples in the article. For these kinds of problems, giving up TC is mostly a feature. And if you need more expressiveness, there's a lot of practical Datalog-ish systems that can recover Turing completeness (Flix, Formulog, parts of Souffle), while still being saner than SWI Prolog and co. for this type of work, as you generally don't have to care about atom order or search order in the same way. They act so much more predictably.
- AlotOfReading 5mo ago
  You can get Turing completeness by wrapping your datalog query in a while loop, so that's not particularly restrictive.
  - ModernMech 5mo ago
    In the case of Datalog, it not being Turing-complete is usually seen as a feature rather than restrictive.
  - Dylan16807 5mo ago
    You can get Turing completeness by wrapping basically any math or logic system in a while loop, even arithmetic. So that doesn't tell us much about the restrictiveness of the overall system since I'd call "you can only use arithmetic" pretty damn restrictive.
  - baq 5mo ago
    It’s surprisingly hard to design a useful language which isn’t Turing-complete, so it should be seen as a compliment, not a problem to fix
YeGoblynQueenne 5mo ago
Ahem. "Prolog underneath" is doing SLD-Resolution implemented as a Depth-First Search with backtracking. Saying it's "doing backtracking" is really fudging quite a bit. Datalog, instead, is "underneath" implementing a TP-Operator, a procedure that finds the fix-point of a Datalog program which happens to be the same as its Least Herbrand Model, which is what SLD-Resolution also finds, except that SLD-Resolution allows functions and does not guarantee termination, like Datalog does. The big advantage of a TP Operator is the termination guarantees and it can be implemented so that it's efficient, but it's still limited, and the fact that there are many different flavours of Datalog (with or without stratified negation, arithmetic, lists etc) is testament to the difficulty of improving on Prolog's efficiency without breaking its soundness or completeness. Or, like I always say, "sound, complete, efficient: choose two".
- gobdovan 5mo ago
  By the same logic, would you say that the fact that there's only one mainstream Rust is testament to the simplicity of implementing a macro-heavy, borrow checked language without breaking safety, performance and expressiveness?
  - YeGoblynQueenne 5mo ago
    I... don't really have an opinion on Rust. I have no idea, honest. Mostly what I mean above is that Prolog is a hard balancing act, specifically balancing efficient execution with the practicalities of programming (e.g. lists, database asserts/retracts, I/O etc) and the theoretical underpinnings of Horn logic and SLD-Resolution. There's a lot of stuff that went into Prolog and its development process is quite distinct to any other language I'm aware of, where there wasn't like a central committee or an enlightened dictator, or a small band of hard-headed academics (...Haskell...) and so on, but instead there was a decades-long academic research process of going from First-Order Logic to Herbrand semantics, to definite logic, to Resolution, to Linear Resolution, to Linear Resolution with a Selection Rule, to Linear Resolution with a Selection Rule restricted to Definite clauses, to Negation-As-Failure under a Closed World Assumption, and finally to a language with an automated theorem prover as an interpreter and a clunky mockery of FOL syntax and terminology that isn't even complete (despite Resolution being complete); a process with no centralised structure instead split across multiple acadmics in several universities in the UK, in France, and in Japan. Another way to see Prolog is that it's the result of a very peculiar academic process that is hard to replicate and that yielded a result that is difficult to outdo, with all its compromises; because of its compromises. Because its particular compromises were made to solve hard problems and were arrived at after a long, collaborative process that won't be easily outdone. Not that attempts haven't been made. For example, in logic programming circles Prolog is now considered a little bit quaint, even outdated. Most of the activity has shifted to Answer Set Programming (ASP). And that makes sense, Prolog is old news. ASP is the new kid on the block, it's only 30 years old! And like normal programming languages it was designed by a couple of people before being adopted by a wider community. I just really don't know how any of that maps to Rust.

ModernMech 5mo ago

Importantly, Datalog is not Turing-complete though.

gobdovan 5mo ago
Exactly :) It is terminating due to the LFP semantics I was pointing out, it's more akin to SQL than to Prolog. The article doesn't even show the usage of the Prolog cut (`!`). And yet Prolog can express all examples in the article. For these kinds of problems, giving up TC is mostly a feature. And if you need more expressiveness, there's a lot of practical Datalog-ish systems that can recover Turing completeness (Flix, Formulog, parts of Souffle), while still being saner than SWI Prolog and co. for this type of work, as you generally don't have to care about atom order or search order in the same way. They act so much more predictably.
AlotOfReading 5mo ago
You can get Turing completeness by wrapping your datalog query in a while loop, so that's not particularly restrictive.
- ModernMech 5mo ago
  In the case of Datalog, it not being Turing-complete is usually seen as a feature rather than restrictive.
- Dylan16807 5mo ago
  You can get Turing completeness by wrapping basically any math or logic system in a while loop, even arithmetic. So that doesn't tell us much about the restrictiveness of the overall system since I'd call "you can only use arithmetic" pretty damn restrictive.
- baq 5mo ago
  It’s surprisingly hard to design a useful language which isn’t Turing-complete, so it should be seen as a compliment, not a problem to fix

YeGoblynQueenne 5mo ago

Ahem. "Prolog underneath" is doing SLD-Resolution implemented as a Depth-First Search with backtracking. Saying it's "doing backtracking" is really fudging quite a bit. Datalog, instead, is "underneath" implementing a TP-Operator, a procedure that finds the fix-point of a Datalog program which happens to be the same as its Least Herbrand Model, which is what SLD-Resolution also finds, except that SLD-Resolution allows functions and does not guarantee termination, like Datalog does. The big advantage of a TP Operator is the termination guarantees and it can be implemented so that it's efficient, but it's still limited, and the fact that there are many different flavours of Datalog (with or without stratified negation, arithmetic, lists etc) is testament to the difficulty of improving on Prolog's efficiency without breaking its soundness or completeness. Or, like I always say, "sound, complete, efficient: choose two".

gobdovan 5mo ago
By the same logic, would you say that the fact that there's only one mainstream Rust is testament to the simplicity of implementing a macro-heavy, borrow checked language without breaking safety, performance and expressiveness?
- YeGoblynQueenne 5mo ago
  I... don't really have an opinion on Rust. I have no idea, honest. Mostly what I mean above is that Prolog is a hard balancing act, specifically balancing efficient execution with the practicalities of programming (e.g. lists, database asserts/retracts, I/O etc) and the theoretical underpinnings of Horn logic and SLD-Resolution. There's a lot of stuff that went into Prolog and its development process is quite distinct to any other language I'm aware of, where there wasn't like a central committee or an enlightened dictator, or a small band of hard-headed academics (...Haskell...) and so on, but instead there was a decades-long academic research process of going from First-Order Logic to Herbrand semantics, to definite logic, to Resolution, to Linear Resolution, to Linear Resolution with a Selection Rule, to Linear Resolution with a Selection Rule restricted to Definite clauses, to Negation-As-Failure under a Closed World Assumption, and finally to a language with an automated theorem prover as an interpreter and a clunky mockery of FOL syntax and terminology that isn't even complete (despite Resolution being complete); a process with no centralised structure instead split across multiple acadmics in several universities in the UK, in France, and in Japan. Another way to see Prolog is that it's the result of a very peculiar academic process that is hard to replicate and that yielded a result that is difficult to outdo, with all its compromises; because of its compromises. Because its particular compromises were made to solve hard problems and were arrived at after a long, collaborative process that won't be easily outdone. Not that attempts haven't been made. For example, in logic programming circles Prolog is now considered a little bit quaint, even outdated. Most of the activity has shifted to Answer Set Programming (ASP). And that makes sense, Prolog is old news. ASP is the new kid on the block, it's only 30 years old! And like normal programming languages it was designed by a couple of people before being adopted by a wider community. I just really don't know how any of that maps to Rust.