Hacker News Reader

Comment by discarded1023 | Hacker News Reader

What do you mean by "misappropriated"?

You can try running with what wikipedia says [1] or stack overflow [2]. You could say it's PL marketing terminology from the 1980s and 1990s (FP + Prolog v the world). Roughly these languages aren't based on the idea of changing state, but of course that idea eventually ends up in there somewhere (e.g. monads and laziness in Haskell, DCGs in Prolog).

On the positive side, I'd be comfortable saying that SQL is declarative.

I'd be wary about bringing Turing completeness in here. It seems irrelevant.

[1] https://en.wikipedia.org/wiki/Declarative_programming

[2] https://stackoverflow.com/questions/129628/what-is-declarati...

View on HN

To answer the first question: "Wrongly taken".

fp is declarative in the shallow sense of being immutable. But you can't just state what you want (e.g. what constraint programming languages enable); you must write a program. If fp is also declarative, what word is left for describing what I mean? Thus: misappropriation.

Not "Turing completeness", "Turing equivalence". Many very simple systems are turing equivalent, so they can exhibit arbitrary complexity. A mapping, from what you have to what you want, is an example of declarative programming. WYSIWYG is declarative. [But arguably this makes "declarative programming" an oxymoron... or we must call html a "programming" language]

Yes, SQL is a lot more declarative; the underlying relational algebra perhaps also is. Something that I'd personally like is a term for systems that enable you to specify the outcome as-is, rather than a composition of steps to achieve it. Perhaps I just want a word for this. I'll give an example:

  (a+b)(x+y) -> ax+bx+ay+by
  (declarative: "fully expanded form")

  (a+b)(x+y) -> a(x+y)+b(x+y) -> ax+ay+b(x+y) -> ax+bx+ay+by
  (steps: "distribute (x+y), distribute a, distribute b")

[1] I agree with wikipedia here: programs describe their desired results without explicitly listing commands or steps that must be performed.

but not in the next sentence: Functional and logical programming languages are characterized by a declarative programming style.

because functional programs specify steps to be performed e.g. g(f(x)) rather than a state of affairs to be attained.

[2] Unfortunately I don't have time to fully read the SO question right now, but I note it's closed and there seems much contention in the comments.

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.

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).

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 [2]: https://des.sourceforge.io/

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.

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?

Reply on news.ycombinator.com