5 ms·

Asking this earnestly and not as a rhetorical question: what do I get from Prolog that I can't get from using SQL? Is it speed, is it ergonomics, is it the abil

Asking this earnestly and not as a rhetorical question: what do I get from Prolog that I can't get from using SQL? Is it speed, is it ergonomics, is it the ability to do computations that are otherwise intractable? And if there are any such advantages, at what level of complexity of abstraction do they come up, and at which level would I not see the value of using prolog?

4ad 3y ago
I am not sure how you could meaningfully compare Prolog and SQL. Both are declarative languages, but that's where the similarities end. SQL is for interacting with databases, whereas Prolog is, more or less, a language that you can write regular programs in. Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.
- ngruhn 3y ago
  Both languages are relational, which is fairly unique among programming languages. For example you can define a graph in Prolog like this: edge(1, 2). edge(2, 3). edge(3, 4). These edges are naturally undirected. Similarly, in SQL you can have a table "Edges": +——-+——-+ | 1 | 2 | | 2 | 3 | | 3 | 4 | +——-+——-+ which also imposes no strict direction. In non-relational languages you have to define maps for both directions. However, in Prolog you can easily define something like reachability using recursion: reachable(V, V). reachable(V, W) :- edge(V, U), reachable(U, W). In SQL you would have to join the "Edges" table with itself an unknown number of times. I suspect this is possible somehow but definitely less natural.
  - Epa095 3y ago
    The reachable predicate on your 'naturally undirected edges' treat them as directed;-) I would rather say that your edges are naturally directed, and then you can add a clause to make them undirected.
  - j-pb 3y ago
    I get what you're trying to say, that in Prolog you are able to lookup structures by their shape, and not by some pre-defined path, as in other languages, so you can do both `edge(1, A)` and `edge(A, 1)`. But the graph in your example is still directed, simply by the virtue of predicate arguments being ordered. So your example misses two rules to be correct. reachable(V, W) :- edge(V, W). reachable(V, W) :- edge(W, V). reachable(V, W) :- reachable(V, U), reachable(U, W). Alternatively you could introduce edge(V, W) :- edge(W, V).
  - cmrdporcupine 3y ago
    > In SQL you would have to join the "Edges" table with itself an unknown number of times. In fact fore recent SQL standards have added extensions for these kinds of recursive joins. (And some databases like Oracle, DB2 have had recurse or tclose operators for a long time.) I don't think they're particularly elegant -- they're awkward like most things in SQL because SQL's syntax sucks -- but the ability is in fact there these days.
- yowlingcat 3y ago
  How are the two any different? Can you come up with any differences in expressive power between the first-order logic/Horn clauses that underpin Prolog and the relational algebra that underpins SQL? I wonder whether you're accurately portraying the structural foundations of either Prolog or SQL.
  - nevertoolate 3y ago
    You want to learn or to debate :)
    - yowlingcat 3y ago
      I get where you're coming from but your point seems flippant. My answer is "debate" -- and looking at the rest of my subthread, some commenters have raised some great concrete areas around Prolog's unique strengths, which I've found helpful!
  - hyperpape 3y ago
    Relational algebra is not Turing complete. SQL gets Turing completeness by means of various additions/alterations (sometimes pretty weird ones about that). So the foundations are pretty different, and I think this is obvious if you tried to start writing typical programs in SQL/Prolog. Now, some people argue you might want a less expressive logic programming language, especially datalog, so this isn’t a knock-down argument, but it’s a pretty big difference.
    - _a_a_a_ 3y ago
      > Relational algebra is not Turing complete. yes it is > SQL gets Turing completeness by means of various additions/alterations. Sigh. No. SQL was a subset of relational until recursive CTEs were included to round it off properly.
      - hyperpape 3y ago
        > yes it is Can you double check and/or give references? Because I specifically doubted my memory here, and everything I found online before posting matches what I thought—-standard relational algebra is not Turing-complete (hence relational queries are guaranteed to terminate).
oldsecondhand 3y ago
SQL doesn't have homoiconic structure like Prolog or Lisp, which would facilitate metaprogramming. Prolog and Lisp were derived from first principles, SQL was designed to be a language that reads similar to English (i.e. easy to learn for non-programmers). Prolog and Lisp also has the concept of "atom" which can represent many things, but in parsing it's used for terminal symbols. Prolog has the advantage over Lisp that you can define custom operators and their precedence, so you can create easy to read domain specific languages without excessive amounts of parentheses. The built-in backtracking can also be useful for parsing. Definite Clause Grammer rules are also a standard feature, which is very similar to the Backus-Naur form. https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar
- yowlingcat 3y ago
  You're talking about the "how" but I'm asking about the "what" -- and I'm not really sure I agree with much of what you mentioned. SQL "reading similar to english" doesn't really mean much. Homoiconicity is syntax sugar and in practice, you can do the same thing in any vanilla programming language you'd use with SQL anyways (query builder flavored ORMs). It's not really a killer app. BNF and DCGs get a bit closer to what I'm asking, but even then I'm not sure it really adds anything novel -- what, if any advantages do you get from that over the relational algebra whose set theoretic underpinnings serve as the foundation for SQL? How is backtracking functionally different or more powerful than joining? Let me give an example by way of another formalism, which is the Church-Turing correspondence that establishes a correspondence between the lambda calculus and Turing machines. Is there any theoretically stronger expressive power one gets from Prolog over SQL, or is it an ergonomics question, similar to using say, Ruby over Java?
  - MichaelBurge 3y ago
    SQL with recursive CTEs is Turing-complete. So nothing stops you from writing compilers, rendering Mandelbrot fractals, parsing text, and training neural networks in SQL.
    - 3y ago
crabbone 3y ago
Unification. This is the central point of Prolog, it's the mechanism behind matching structured data, while in SQL you would have to implement unification for each individual query, afresh, every time. Unification allows you to "not know" a lot of things about the shape of the data you want to match, whereas with SQL in order to be able to match something you need to know precisely how the data is organized. Another, unrelated aspect: I/O, system calls, all that stuff that would require from you in SQL database to go outside and implement functions that are loaded into your database in some database-specific way. Parsing. SQL doesn't offer much in terms of working with strings. Writing as much as a parser for arithmetic expressions with just integers would be a huge undertaking. No sane person would write such a parser unless for some bizarre code-golf challenge. It's trivial to do that in Prolog. CLFD. This isn't part of standard Prolog, but it comes with most implementations. This allows you easily to write queries about numerical facts (eg. find all factors of a given integer). To continue in the similar spirit as above: modern Prologs come with a bunch of libraries. You can have an HTTP server in Prolog, or an image processing tool etc. Something that in SQL you'd have to implement outside of it, and load as an external function. Modules. Prolog code is more amenable to reuse and can be better organized because you can put it in boxes, hide things you want to keep private in those boxes etc. This is while SQL operates entirely in some sort of a global namespace. The list isn't exhaustive, these are just the things I could think in a short time.
- yowlingcat 3y ago
  Thank you for the thoughtful comment! Comparing these specific features to using, say, a vanilla general purpose PL such as Python with an ORM and a SQL database, it looks to me like the integration of primitives such as parsing, constraint programming and unification are far stronger. In particular, unification seems to be a material one that you mentioned -- to do this in SQL, you'd have to do contortions around an EAV model which could probably get you to the same area you would with prolog unification, but probably much less efficiently. It does seem like the answer to my question is "ergonomics and efficiency" which is a useful thing to know.
_a_a_a_ 3y ago
> what do I get from Prolog that I can't get from using SQL? 1. Nothing, theoretically (but see 2, 3, 4) 2. They are for different domains/problems 3. Both are based on the same formal background (1st order predicate calculus IIRC) 4. Learn both. It's not hard and they're both useful and it won't be a waste of your time.
tannhaeuser 3y ago
SQL excels at data processing. It's not only a query DSL but also has INSERT, UPDATE, etc., making up a practical batch processing language with natural lock semantics, rollback, etc. SQL also pretty much enshrines a strict DDL/DML separation, has privileges and roles, and so on. Prolog, OTOH, excels at planning, optimization, constraint solving, etc. Given Prolog was originally designed for old-school grammar/logic-based NLP, it also has excellent built-in support for custom DSLs and recursive-descent parsing using definite clause grammars making use of Prolog's logical variables (with indeterminism / backtracking and retry) and unification (pattern matching on steroids). Check out Prolog in-browser demos for robotic planning/container logistics and machine learning/bioinformatics (not based on LLMs) at [1]. These aren't problems you'd tackle with SQL ;) but beyond SQL's inappropriateness also require actual language support for debugging, packages, testing, integration, etc. [1]: https://quantumprolog.sgml.io https://quantumprolog.sgml.io
trealira 3y ago
I haven't used it, but based on this, it seems good for declaratively solving problems given facts and constraints: https://xmonader.github.io/prolog/2018/12/21/solving-murder-prolog.html https://xmonader.github.io/prolog/2018/12/21/solving-murder-...
yowlingcat 3y ago
First of all -- I want to thank you all for robust discussion on this subthread. I've learned a lot about the experience of other folks using Prolog and where they've gotten mileage out of its unique strengths. It's been eye opening to see for sure! Part of the reason I wanted to ask this question because I had a suspicion that there may not necessarily be as large of a gap between SQL and Prolog as there may initially appear. Said another way, I wondered if there was a Prolog (or Datalog) to SQL compiler used in production. I recently stumbled upon Logica [1], which appears to based on a predecessor (Yeladog) built at Google. I don't have experience using it, so I'm not sure how complete the implementation is nor how efficient it is. I'm curious if anyone has used it before and if so, what their experience was. At first blush, it appears to bring the best of both worlds: the expressive power of Prolog/Datalog, combined with the standard operational tooling of SQL which is a common core dependency in many if not most production software systems. Two questions: 1) How does Datalog compare to Prolog for common problems you might use Prolog for? Any things you can do in Prolog differentially that wouldn't be as easy in Datalog and vice versa? 2) What issues might come up in system that uses a Datalog to SQL transpiler? Given that some of the answers in this thread about the efficiency of using Prolog to do constraint solving, it seems like such an approach might lose some of the efficiency that makes it so powerful in the first place. On the other hand, if it doesn't, it seems like it'd bring a killer app to SQL, which is the ability to do constraint solving in a nearly native fashion inside SQL. [1] https://github.com/EvgSkv/logica https://github.com/EvgSkv/logica

4ad 3y ago

I am not sure how you could meaningfully compare Prolog and SQL. Both are declarative languages, but that's where the similarities end. SQL is for interacting with databases, whereas Prolog is, more or less, a language that you can write regular programs in. Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.

ngruhn 3y ago
Both languages are relational, which is fairly unique among programming languages. For example you can define a graph in Prolog like this: edge(1, 2). edge(2, 3). edge(3, 4). These edges are naturally undirected. Similarly, in SQL you can have a table "Edges": +——-+——-+ | 1 | 2 | | 2 | 3 | | 3 | 4 | +——-+——-+ which also imposes no strict direction. In non-relational languages you have to define maps for both directions. However, in Prolog you can easily define something like reachability using recursion: reachable(V, V). reachable(V, W) :- edge(V, U), reachable(U, W). In SQL you would have to join the "Edges" table with itself an unknown number of times. I suspect this is possible somehow but definitely less natural.
- Epa095 3y ago
  The reachable predicate on your 'naturally undirected edges' treat them as directed;-) I would rather say that your edges are naturally directed, and then you can add a clause to make them undirected.
- j-pb 3y ago
  I get what you're trying to say, that in Prolog you are able to lookup structures by their shape, and not by some pre-defined path, as in other languages, so you can do both `edge(1, A)` and `edge(A, 1)`. But the graph in your example is still directed, simply by the virtue of predicate arguments being ordered. So your example misses two rules to be correct. reachable(V, W) :- edge(V, W). reachable(V, W) :- edge(W, V). reachable(V, W) :- reachable(V, U), reachable(U, W). Alternatively you could introduce edge(V, W) :- edge(W, V).
- cmrdporcupine 3y ago
  > In SQL you would have to join the "Edges" table with itself an unknown number of times. In fact fore recent SQL standards have added extensions for these kinds of recursive joins. (And some databases like Oracle, DB2 have had recurse or tclose operators for a long time.) I don't think they're particularly elegant -- they're awkward like most things in SQL because SQL's syntax sucks -- but the ability is in fact there these days.
yowlingcat 3y ago
How are the two any different? Can you come up with any differences in expressive power between the first-order logic/Horn clauses that underpin Prolog and the relational algebra that underpins SQL? I wonder whether you're accurately portraying the structural foundations of either Prolog or SQL.
- nevertoolate 3y ago
  You want to learn or to debate :)
  - yowlingcat 3y ago
    I get where you're coming from but your point seems flippant. My answer is "debate" -- and looking at the rest of my subthread, some commenters have raised some great concrete areas around Prolog's unique strengths, which I've found helpful!
- hyperpape 3y ago
  Relational algebra is not Turing complete. SQL gets Turing completeness by means of various additions/alterations (sometimes pretty weird ones about that). So the foundations are pretty different, and I think this is obvious if you tried to start writing typical programs in SQL/Prolog. Now, some people argue you might want a less expressive logic programming language, especially datalog, so this isn’t a knock-down argument, but it’s a pretty big difference.
  - _a_a_a_ 3y ago
    > Relational algebra is not Turing complete. yes it is > SQL gets Turing completeness by means of various additions/alterations. Sigh. No. SQL was a subset of relational until recursive CTEs were included to round it off properly.
    - hyperpape 3y ago
      > yes it is Can you double check and/or give references? Because I specifically doubted my memory here, and everything I found online before posting matches what I thought—-standard relational algebra is not Turing-complete (hence relational queries are guaranteed to terminate).

oldsecondhand 3y ago

SQL doesn't have homoiconic structure like Prolog or Lisp, which would facilitate metaprogramming. Prolog and Lisp were derived from first principles, SQL was designed to be a language that reads similar to English (i.e. easy to learn for non-programmers). Prolog and Lisp also has the concept of "atom" which can represent many things, but in parsing it's used for terminal symbols. Prolog has the advantage over Lisp that you can define custom operators and their precedence, so you can create easy to read domain specific languages without excessive amounts of parentheses. The built-in backtracking can also be useful for parsing. Definite Clause Grammer rules are also a standard feature, which is very similar to the Backus-Naur form. https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar

yowlingcat 3y ago
You're talking about the "how" but I'm asking about the "what" -- and I'm not really sure I agree with much of what you mentioned. SQL "reading similar to english" doesn't really mean much. Homoiconicity is syntax sugar and in practice, you can do the same thing in any vanilla programming language you'd use with SQL anyways (query builder flavored ORMs). It's not really a killer app. BNF and DCGs get a bit closer to what I'm asking, but even then I'm not sure it really adds anything novel -- what, if any advantages do you get from that over the relational algebra whose set theoretic underpinnings serve as the foundation for SQL? How is backtracking functionally different or more powerful than joining? Let me give an example by way of another formalism, which is the Church-Turing correspondence that establishes a correspondence between the lambda calculus and Turing machines. Is there any theoretically stronger expressive power one gets from Prolog over SQL, or is it an ergonomics question, similar to using say, Ruby over Java?
- MichaelBurge 3y ago
  SQL with recursive CTEs is Turing-complete. So nothing stops you from writing compilers, rendering Mandelbrot fractals, parsing text, and training neural networks in SQL.
  - 3y ago

crabbone 3y ago

Unification. This is the central point of Prolog, it's the mechanism behind matching structured data, while in SQL you would have to implement unification for each individual query, afresh, every time. Unification allows you to "not know" a lot of things about the shape of the data you want to match, whereas with SQL in order to be able to match something you need to know precisely how the data is organized. Another, unrelated aspect: I/O, system calls, all that stuff that would require from you in SQL database to go outside and implement functions that are loaded into your database in some database-specific way. Parsing. SQL doesn't offer much in terms of working with strings. Writing as much as a parser for arithmetic expressions with just integers would be a huge undertaking. No sane person would write such a parser unless for some bizarre code-golf challenge. It's trivial to do that in Prolog. CLFD. This isn't part of standard Prolog, but it comes with most implementations. This allows you easily to write queries about numerical facts (eg. find all factors of a given integer). To continue in the similar spirit as above: modern Prologs come with a bunch of libraries. You can have an HTTP server in Prolog, or an image processing tool etc. Something that in SQL you'd have to implement outside of it, and load as an external function. Modules. Prolog code is more amenable to reuse and can be better organized because you can put it in boxes, hide things you want to keep private in those boxes etc. This is while SQL operates entirely in some sort of a global namespace. The list isn't exhaustive, these are just the things I could think in a short time.

yowlingcat 3y ago
Thank you for the thoughtful comment! Comparing these specific features to using, say, a vanilla general purpose PL such as Python with an ORM and a SQL database, it looks to me like the integration of primitives such as parsing, constraint programming and unification are far stronger. In particular, unification seems to be a material one that you mentioned -- to do this in SQL, you'd have to do contortions around an EAV model which could probably get you to the same area you would with prolog unification, but probably much less efficiently. It does seem like the answer to my question is "ergonomics and efficiency" which is a useful thing to know.

_a_a_a_ 3y ago

> what do I get from Prolog that I can't get from using SQL? 1. Nothing, theoretically (but see 2, 3, 4) 2. They are for different domains/problems 3. Both are based on the same formal background (1st order predicate calculus IIRC) 4. Learn both. It's not hard and they're both useful and it won't be a waste of your time.

tannhaeuser 3y ago

SQL excels at data processing. It's not only a query DSL but also has INSERT, UPDATE, etc., making up a practical batch processing language with natural lock semantics, rollback, etc. SQL also pretty much enshrines a strict DDL/DML separation, has privileges and roles, and so on. Prolog, OTOH, excels at planning, optimization, constraint solving, etc. Given Prolog was originally designed for old-school grammar/logic-based NLP, it also has excellent built-in support for custom DSLs and recursive-descent parsing using definite clause grammars making use of Prolog's logical variables (with indeterminism / backtracking and retry) and unification (pattern matching on steroids). Check out Prolog in-browser demos for robotic planning/container logistics and machine learning/bioinformatics (not based on LLMs) at [1]. These aren't problems you'd tackle with SQL ;) but beyond SQL's inappropriateness also require actual language support for debugging, packages, testing, integration, etc. [1]: https://quantumprolog.sgml.io https://quantumprolog.sgml.io

trealira 3y ago

I haven't used it, but based on this, it seems good for declaratively solving problems given facts and constraints: https://xmonader.github.io/prolog/2018/12/21/solving-murder-prolog.html https://xmonader.github.io/prolog/2018/12/21/solving-murder-...

yowlingcat 3y ago

First of all -- I want to thank you all for robust discussion on this subthread. I've learned a lot about the experience of other folks using Prolog and where they've gotten mileage out of its unique strengths. It's been eye opening to see for sure! Part of the reason I wanted to ask this question because I had a suspicion that there may not necessarily be as large of a gap between SQL and Prolog as there may initially appear. Said another way, I wondered if there was a Prolog (or Datalog) to SQL compiler used in production. I recently stumbled upon Logica [1], which appears to based on a predecessor (Yeladog) built at Google. I don't have experience using it, so I'm not sure how complete the implementation is nor how efficient it is. I'm curious if anyone has used it before and if so, what their experience was. At first blush, it appears to bring the best of both worlds: the expressive power of Prolog/Datalog, combined with the standard operational tooling of SQL which is a common core dependency in many if not most production software systems. Two questions: 1) How does Datalog compare to Prolog for common problems you might use Prolog for? Any things you can do in Prolog differentially that wouldn't be as easy in Datalog and vice versa? 2) What issues might come up in system that uses a Datalog to SQL transpiler? Given that some of the answers in this thread about the efficiency of using Prolog to do constraint solving, it seems like such an approach might lose some of the efficiency that makes it so powerful in the first place. On the other hand, if it doesn't, it seems like it'd bring a killer app to SQL, which is the ability to do constraint solving in a nearly native fashion inside SQL. [1] https://github.com/EvgSkv/logica https://github.com/EvgSkv/logica