3 ms·

What you describe sounds like the difference between Relational Algebra (steps) and Relational Calculus (no steps), as formulated by E. F. Codd. He called the a

What you describe sounds like the difference between Relational Algebra (steps) and Relational Calculus (no steps), as formulated by E. F. Codd. He called the algebra "procedural", for that reason, and by that definition functional programming languages would also be called procedural. SQL is a bit of both, but more to the calculus/non-procedural side. Prolog is trying to be both (you can think in steps when you want to, but mostly you shouldn't have to). Answer Set Programming has no notion of steps or ordering at all.

hyperthesis 3y ago
Wow, I've never heard of "relational calculus" (maybe I assumed it a synonym for the algebra?), though I've only read Codd's first relational paper. Sounds perfect! I'll google - though would you recommend a particular reference? BTW A possible term is programming-by-example (or "exemplary programming", to parallel fp's pun), where you give an example of what you want. I suppose you end up with a specification language to specify what you want, which might well be very complex, and use composition. Yeah, I think in prolog you can destructure and structure (construct) in the same expression, but in practice, recursion always seemed involved (IIRC a uni class). XSLT feels kinda similar (though uses paths instead of destructuring). Answer Set Programming (also new to me) sounds like specifying the set you want. The difficulty is then describing what you want - sometimes it's easier to state how to make it. Reminds me of AI in golden-era science fiction, where computers would do exactly what you asked (repackaging genie's three wishes).
- felixyz 3y ago
  I think the most relevant papers would be: "Relational completeness of data base sublanguages" "A data base sublanguage founded on the Relational Calculus" SQL is most similar to the calculus "sublanguage", so that would be the main point of reference. ISBL was an early implementation of relational calculus[1]. The The Datalog Educational System (DES)[2] is the only available implementation of relational calculus (in both its forms), and it also implements relational algebra, Datalog, and SQL! I agree, in general it's more convenient to state "what the solution should look like", but in some cases we find it easier to give instructions to follow instead. This is true in everyday conversation between humans as well. Cooking recipes are a good example - we generally want to know the steps required, but sometimes it's helpful to add a description of what the end result should be like. [1]: https://en.wikipedia.org/wiki/ISBL https://en.wikipedia.org/wiki/ISBL [2]: https://des.sourceforge.io/ https://des.sourceforge.io/
  - hyperthesis 3y ago
    Just so you know your guidance wasn't wasted: I looked into all these references, and Codd's calculus is based on predicate calculus (like Answer Set Programming), so it all seems inspired by set builder notation, all x such that ... { x : property(x) } Is encryption another example of having the result (the encrypted message) but not knowing how to make it?
  - hyperthesis 3y ago
    Thanks very much! I had heard of Codd's first two languages as not being "usable by mortals" (non-mathematicians). ALPHA seems to be the first one. Re: functional programming is a subset of relational programming. I read them as brand names, so it was revealing when you pointed out that they are literally true - formal properties. I wonder, what are their consequences? For relations, each input can have a set of outputs. So this is like a tree at each call level, ever-expanding. (in general a call graph, not a tree) For functions, I think it's only that one input always gives the same output, including nested functions. So, only immutability? For injections, it's just reversibility. A cute idea, implemented by only having injective functions to compose, but hasn't taken off. I expect it's too restrictive, except when reversibility is the purpose.

hyperthesis 3y ago

Wow, I've never heard of "relational calculus" (maybe I assumed it a synonym for the algebra?), though I've only read Codd's first relational paper. Sounds perfect! I'll google - though would you recommend a particular reference? BTW A possible term is programming-by-example (or "exemplary programming", to parallel fp's pun), where you give an example of what you want. I suppose you end up with a specification language to specify what you want, which might well be very complex, and use composition. Yeah, I think in prolog you can destructure and structure (construct) in the same expression, but in practice, recursion always seemed involved (IIRC a uni class). XSLT feels kinda similar (though uses paths instead of destructuring). Answer Set Programming (also new to me) sounds like specifying the set you want. The difficulty is then describing what you want - sometimes it's easier to state how to make it. Reminds me of AI in golden-era science fiction, where computers would do exactly what you asked (repackaging genie's three wishes).

felixyz 3y ago
I think the most relevant papers would be: "Relational completeness of data base sublanguages" "A data base sublanguage founded on the Relational Calculus" SQL is most similar to the calculus "sublanguage", so that would be the main point of reference. ISBL was an early implementation of relational calculus[1]. The The Datalog Educational System (DES)[2] is the only available implementation of relational calculus (in both its forms), and it also implements relational algebra, Datalog, and SQL! I agree, in general it's more convenient to state "what the solution should look like", but in some cases we find it easier to give instructions to follow instead. This is true in everyday conversation between humans as well. Cooking recipes are a good example - we generally want to know the steps required, but sometimes it's helpful to add a description of what the end result should be like. [1]: https://en.wikipedia.org/wiki/ISBL https://en.wikipedia.org/wiki/ISBL [2]: https://des.sourceforge.io/ https://des.sourceforge.io/
- hyperthesis 3y ago
  Just so you know your guidance wasn't wasted: I looked into all these references, and Codd's calculus is based on predicate calculus (like Answer Set Programming), so it all seems inspired by set builder notation, all x such that ... { x : property(x) } Is encryption another example of having the result (the encrypted message) but not knowing how to make it?
- hyperthesis 3y ago
  Thanks very much! I had heard of Codd's first two languages as not being "usable by mortals" (non-mathematicians). ALPHA seems to be the first one. Re: functional programming is a subset of relational programming. I read them as brand names, so it was revealing when you pointed out that they are literally true - formal properties. I wonder, what are their consequences? For relations, each input can have a set of outputs. So this is like a tree at each call level, ever-expanding. (in general a call graph, not a tree) For functions, I think it's only that one input always gives the same output, including nested functions. So, only immutability? For injections, it's just reversibility. A cute idea, implemented by only having injective functions to compose, but hasn't taken off. I expect it's too restrictive, except when reversibility is the purpose.