4 ms·

SQL doesn't have homoiconic structure like Prolog or Lisp, which would facilitate metaprogramming. Prolog and Lisp were derived from first principles, SQL was

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.
  - e12e 3y ago
    > nothing stops you But ergonomics of the syntax certainly hinders you ...
- Skinney 3y ago
  > Is there any theoretically stronger expressive power one gets from Prolog over SQL, I guess this is best illustrated by examples. In prolog, you can define how people are related using "facts" or data: person_parent(alfred, benny). person_parent(benny, carl). This then forms relationships. In SQL you could write: CREATE TABLE persons ( name TEXT NOT NULL, parent TEXT NOT NULL); The difference lies in how you query said data. Let's say I want to know if "carl" is the grandparent of "alfred", in Prolog I would first write a rule to define what a grandparent is: grandparent(X, Y):- person_parent(X, Z), person_parent(Z, Y). Then query if "carl" is the grandparent of "alfred": grandparent(alfred, carl). --> true Now, the interesting thing is that I can use the same rule to ask how many grandkids carl has: grandparent(X, carl). --> X = alfred (and any other kid) Or, I could ask how many grandparents alfred has grandparent(alfred, Y). --> Y = carl (and any other grandparent) Or I could ask for any combinations of kids and their grandparents grandparent(X, Y). --> X = alfred, Y = carl (and any other combination). In SQL, on the other hand, you'd have to write each of these queries by hand. A more powerful example, is defining the rules of suduko and then asking prolog to finish solving a board for you. I will not even begin to suggest how that would be done in SQL (partly because you simply would not use SQL for that).
  - ginko 3y ago
    I have to admit I never really got into SQL, and maybe learning Prolog in university ruined me for it, but can someone explain why SQL is considered "relational" when you still have to explicitly do queries for basic stuff like this? If it's just that you can define relations in the database scheme, then pretty any programming language would be considered relational.
    - tracnar 3y ago
      SQL is called relational because it's based on relational algebra [1]. Although in practice it only loosely follows that theory. [1] https://en.m.wikipedia.org/wiki/Relational_algebra https://en.m.wikipedia.org/wiki/Relational_algebra
    - cmrdporcupine 3y ago
- oldsecondhand 3y ago
  Their theoretical expressive power are the same, they're both turing complete languages. However their practical expressive power is different that comes from language ergonomics, standard libraries and different default optimizations.
yodsanklai 3y ago
SQL has formal foundations too, relational algebra
- cmrdporcupine 3y ago
  But it violates the relational algebra all over the place in ways that blunt its usefulness and hides its elegance. Example: Adds nulls (weird trivalue logic, and breaks reordering of some relational algebraic expressions), has duplicate tuples (relations stop being sets of sets). Unfortunately SQL has done more recently to put people off the relational model than it has to bring them around. Though the majority of people who use it don't actually understand the relational model, so. Datalog is also built on the relational algebra. Or at least, Datalog works on relations and any Datalog programme can effectively "compiled down" to a relational algebraic expression.

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.
- e12e 3y ago
  > nothing stops you But ergonomics of the syntax certainly hinders you ...
Skinney 3y ago
> Is there any theoretically stronger expressive power one gets from Prolog over SQL, I guess this is best illustrated by examples. In prolog, you can define how people are related using "facts" or data: person_parent(alfred, benny). person_parent(benny, carl). This then forms relationships. In SQL you could write: CREATE TABLE persons ( name TEXT NOT NULL, parent TEXT NOT NULL); The difference lies in how you query said data. Let's say I want to know if "carl" is the grandparent of "alfred", in Prolog I would first write a rule to define what a grandparent is: grandparent(X, Y):- person_parent(X, Z), person_parent(Z, Y). Then query if "carl" is the grandparent of "alfred": grandparent(alfred, carl). --> true Now, the interesting thing is that I can use the same rule to ask how many grandkids carl has: grandparent(X, carl). --> X = alfred (and any other kid) Or, I could ask how many grandparents alfred has grandparent(alfred, Y). --> Y = carl (and any other grandparent) Or I could ask for any combinations of kids and their grandparents grandparent(X, Y). --> X = alfred, Y = carl (and any other combination). In SQL, on the other hand, you'd have to write each of these queries by hand. A more powerful example, is defining the rules of suduko and then asking prolog to finish solving a board for you. I will not even begin to suggest how that would be done in SQL (partly because you simply would not use SQL for that).
- ginko 3y ago
  I have to admit I never really got into SQL, and maybe learning Prolog in university ruined me for it, but can someone explain why SQL is considered "relational" when you still have to explicitly do queries for basic stuff like this? If it's just that you can define relations in the database scheme, then pretty any programming language would be considered relational.
  - tracnar 3y ago
    SQL is called relational because it's based on relational algebra [1]. Although in practice it only loosely follows that theory. [1] https://en.m.wikipedia.org/wiki/Relational_algebra https://en.m.wikipedia.org/wiki/Relational_algebra
  - cmrdporcupine 3y ago
oldsecondhand 3y ago
Their theoretical expressive power are the same, they're both turing complete languages. However their practical expressive power is different that comes from language ergonomics, standard libraries and different default optimizations.

yodsanklai 3y ago

SQL has formal foundations too, relational algebra

cmrdporcupine 3y ago
But it violates the relational algebra all over the place in ways that blunt its usefulness and hides its elegance. Example: Adds nulls (weird trivalue logic, and breaks reordering of some relational algebraic expressions), has duplicate tuples (relations stop being sets of sets). Unfortunately SQL has done more recently to put people off the relational model than it has to bring them around. Though the majority of people who use it don't actually understand the relational model, so. Datalog is also built on the relational algebra. Or at least, Datalog works on relations and any Datalog programme can effectively "compiled down" to a relational algebraic expression.