What Is Declarative Programming (2013) | Hacker News Reader

What Is Declarative Programming (2013)

michaelrbernste.in

53 pointssigna1143 comments

"We say the operation is declarative if, whenever called with the same arguments, it returns the same results independent of any other computation state."

That's the use of the term 'declarative programming' by the functional programming community. There are some other uses of it.

Usually in computer science 'declarative programming' means: the problem is described and way to the solution is determined from the problem description. A declarative program describes 'what' and not 'how'. The detailed control flow is not described.

• specify static properties of problems

* solutions are computed

* no explicit dynamic behaviour

I've seen "declarative" languages that included if statements (explicit dynamic behavior!) still passed off as declarative. Some even add sequencing, and what not. However, its ok because they aren't part of the language core, just escape hatches on expressiveness :)

"Declarative" always exists in a spectrum: one's specification is another's implementation. It used to be that Fortran was "declarative" because you no longer had to write machine code and schedule instructions by hand! In truth, it is about how many, not just the kind, details can be omitted. E.g. the list order element is probably important, and if HTML couldn't guarantee that this order would be preserved at run-time, there would be some big problems.

> "Declarative" always exists in a spectrum: one's specification is another's implementation.

I'll go further: statelessness and applicativity obviously have an intimate and important relationship with declarativity ("what rather than how") (just as non-Turing-equivalence does), but they're not the same, and trying to simply define the latter as the former is an annoying PR wheeze that spreads obfuscation.

> It used to be that Fortran was "declarative" because you no longer had to write machine code and schedule instructions by hand!

Maybe, but even at that time, pure mathematics was still more declarative than Fortran, so it's not a relative term.

> In truth, it is about how many, not just the kind, details can be omitted.

I think it's about the kind of details that can be omitted. If I can omit implementation details (how to execute my code on a given machine) from my function declaration, then that is a declarative function.

Again, an implementation is just a more detailed specification. I can say "make me a cake", or I could provide a high level theory on cake baking so my cake gets made, or a detailed recipe, or I can describe all the movements needed exactly. Which one is declarative?

There are many levels in describing what one wants, that there is somehow a magical sharp line where it becomes "how" is not reasonable.

Indeed, that's the definition I am familiar with. To give an example, consider Prolog:

  parent(john,mark).
  parent(steve,john).

  ancestor(A,D) :-
    parent(A,D).
  ancestor(A,D) :-
    parent(P,D),
    ancestor(A,P).

This is a declarative program - it describes being an ancestor means (the parent of a person or an ancestor of the parent of a person). The program does not specify the steps to find a ancestor given a descendant or a descendant given an ancestor. Yet we can do such queries thanks to Prolog's resolution procedure:

  ?- ancestor(steve,mark).
  true
  findall(A,ancestor(A,mark),L).
  L = [john, steve].
  ?- findall(D,ancestor(steve,D),L).
  L = [john, mark].

Of course, as the sibling poster points out, it's a spectrum. Even Prolog has procedural aspects: the ordering of clauses has an effect on execution, as well as the use of cuts, etc. But the definition cited is more a definition for pure functional programming.

Isn't it fairer to say that any non-trivial Prolog program has significant procedural aspects? Yes, you can construct small examples that are purely declarative, and therefore map nicely to predicate calculus, but I found that eventually as programs grew in complexity you ended up using Prolog as yet another procedural language with a few isolated bits of interesting behaviour.

I suspect that's why there was a brief phase where people were keen on embedding Prolog engines into more conventional platforms as specialized "inference engines" rather than trying to do everything in Prolog.

Only if you get lazy. It is certainly possible to write in a mostly declarative fashion, though loading of initial conditions and saving results don't map well. I write non-trivial declarative stuff (I hesitate to use the word programs) in CNF‡, and that pseudo-language simply lacks every sort of traditional control structure. (I've done Conway's GoL so I guess turing-level computation could be implemented.)

Prolog does make it very easy to fall off the declarative wagon, but the imperative parts should only be used sparingly as glue code.

‡Okay, I cheat and render to CNF.

My recollections (they are a bit vague as it was ~20 years ago) was that you could write the "core" of your solution (I was looking at simulations of things like power stations) in nice declarative Prolog - but then, inevitably, your glue/interface code grows in complexity faster than your "core" so that you end up with that dominating and I didn't think Prolog was great for that at all.

I think I eventually gave up on it entirely and ended up writing something in Lisp that took systems of ODEs and wrote standalone C++ models.

It isn't just about being lazy. I'd argue that the foreach that exists in a couple of Prologs is not declarative (despite being called logical loops etc.) but I still use it because I prefer that over repeating myself.

Repeated clauses as OR gets pretty cumbersome once you work with bigger codebases because it sort of violates DRY. If you change/refactor something...suddenly you have to wade through a bunch of clauses. I've rewritten quite a few of these by falling back on imperative code.

That's the definition of "referentially transparent", not declarative. I don't think the FP community has or attempts a shared definition of "declarative". It's just sort of a feeling and, as such, has all the associated woo woo properties.

For a counterpoint from a (contentious) expert, try http://existentialtype.wordpress.com/2013/07/18/what-if-anyt.... Here, Harper lays out 8 definitions of "declarative" which might have force. You don't have to agree that this list is comprehensive, but I know that I've personally heard arguments using most of those "definitions".

In http://existentialtype.wordpress.com/2013/07/22/there-is-suc... Harper argues a particular definition of "declarative" near to his heart. The critical could argue that his earlier list was aimed at nothing more than exposing this definition. Harper's idea is that declarative languages are ones with "mathematical variables" instead of just "computer science-y assignables or slots".

I don't care whether or not that's your definition of declarative as well, but I think variable v. assignable is a very nice, hard distinction between languages.

The difference to me is maybe not as formal, though if I had to pick one I'd pick your definition: declarative is when variables are like mathematical variables, and not like turing-machine memory cells.

To me the difference is in the level of abstraction.

In a non-declarative language, one way to reverse a list is to traverse it, remembering the last item, and change the pointer of the current item to point to the remembered item (if there's no remembered item, the current item is the head of the list, and we make it point to the list terminator). So we have to say exactly how to build the value we're interested in, the reversed list.

Whereas in a declarative language, I simply give a definition of what a reversed list is, without saying how to go about doing it. In fact the computer is free to come up with any way it wants to do this, and I can define a reversed list as being the fold of construction over that list.

Prelude> foldl (flip (:)) [] [1,2,3,4]

[4,3,2,1]

Which does not force me, the programmer, to use any mutable memory cells; in other words this operation is loosely defined enough that it could be "run" both destructively and immutably. The fact that the function declaration does not specify the implementation is what I usually mean by "declarative".

To be clear, this is Robert Harper's definition. I just like it :)

I think there's generally a UI/UX notion of "declarative", the "declarative feel". There's also that whole list of technical definitions. The mismatch is one of category as much as of definition.

For instance, I would analyze your foldl example as being driven by the fact that foldl has a denotation above its implementation. But, as Harper notes, all languages have a denotational semantics if we choose to recognize them and it's difficult to say what it means for a denotational semantics ti be "better" than another in any technical sense.

So what is declarative?

In my mind, it should really only be a UX term. I think technical definitions are debated because of the category mismatch alluded to earlier. I think notions like "equational semantics", "denotational semantics", "referentially transparent", and "variable" are the right technical terminology.

> That's the use of the term 'declarative programming' by the functional programming community. There are some other uses of it.

I came here just to say this. This article repeats an annoyingly religious argument about "declarative programming". It's so dogmatic and skewed a definition that it seems to have excluded the canonical example of declarative programming, prolog. Which, for any serious program, relies heavily on cuts and non-referentially transparent I/O.

XAML is a perfect example:

"When used in Windows Workflow Foundation contexts, XAML is used to describe potentially long-running declarative logic, such as those created by process modeling tools and rules systems."

http://en.wikipedia.org/wiki/Extensible_Application_Markup_L...

PS: it is of course also used for modern GUI mark-up.

This blog post points out problems with the three criteria given in the article for what "declarative" means: http://existentialtype.wordpress.com/2013/07/18/what-if-anyt...

edit: addresses -> points out problems with.

edit2: the blog post also addresses the "referential transparency" characterization.

Spreadsheet is a declarative programming system with a simple programming model and an amazingly intuitive UI, that has enabled a generation of non-programmers to do very complex computation and analysis.

Spreadsheets meet none of the three criteria given in the article:

* Independence: Spreadsheets explicitly rely upon mutable state for <strike>all</strike> some commonly-used operations (i.e., the value of cells).

* Statelessness: Non-independence implies non-statelessness.

* Deterministic: Non-independence implies non-determinism.

The reasoning for the last two point to an underlying problem with the criteria (removing the word "computation" from independence makes the three inter-reducible in any real-world machine). but yeah.

edit: all functions->some commonly-used operations

edit wrt downvotes: perhaps reserve judgement unless you've maintained a very large spreadsheet-based application written by non-programmers. Spreadsheets -- as most commonly used in practice -- do not meet the criteria above, except for the smallest/most trivial of applications. Period.

Now, perhaps the problem is the definition. Or perhaps the problem is that spreadsheets are awful at-scale (even assembly can be quite elegant for small problems or when usage is well-constrained). Or maybe both.

> Spreadsheets explicitly rely upon mutable state for all functions (i.e., the value of cells)

How so? The values in the cells don't change as a spreadsheet "runs". You put the formulae in and the output is there, conceptually instantaneously. Some spreadsheets have some cells that are seen as "input" and expected to be edited, but that corresponds rather well to monadic I/O.

To name a few:

1. Macros. And you don't get to weasel, because any non-trivial spreadsheet application contains at least a few.

2. relative references, which are basically heap pointers.

3. simulating for loops/iteration is a fairly common thing in spread-sheet programming.

But also see my edit to the original comment.

As an aside, it's absolutely astounding to me that my original reply is down-voted.

edit: most obvious -> a few

edit2: Could someone please explain what's so offensive about these posts? Is there that much love for spreadsheet programming (last I checked everyone understood the downsides of at-scale spreadsheets and how these problems arise from subtle non-declarative features)? Am I being unintentionally abrasive? Should I post example files and links to empirical studies demonstrating how people commonly program spreadsheets in non-declarative ways?

I think the problem is (at least that's my problem with your posts, although I didn't downvote you) that you're, and from the look of it for your disdain for spreadsheets, arguing spreadsheet != declarative programming because <i>tenuous definition of declarative programming</>, and the whole argument just smells like cognitive dissonance - declarative programming good, Excel bad, hence Excel not declarative programming.

Not trying to be an asshole, but since you were asking, I'm just saying what I suspect to be a possible reason...

> tenuous definition of declarative programming

> declarative programming good, Excel bad, hence Excel not declarative programming.

I didn't choose the definition of declarative programming. I'm taking the article's definition as given.

Spreadsheets are a great example of a declarative ethos. You're nitpicking on details which equally applies to prolog too. The underlying theme of spreadsheets is definitely declarative. Spreadsheets are older than excel.

> Spreadsheets are a great example of a declarative ethos.

I kind-of agree. The primitives do have many nice properties.

> You're nitpicking on details which equally applies to prolog too.

I strongly disagree.

When escape hatches exist, I think you have to look at how a language/system is commonly used in order to assess whether it has some of these properties or not. Otherwise everything in which a pure function is definable becomes declarative and the phrase becomes rather useless.

Prolog and spreadsheets differ in a rather fundamental, albeit empirical, way: spreadsheet users tend to make pervasive use of the these imperative features.

So there are two alternatives -- spreadsheet programmers are all completely inexperienced and have no idea what's good for them, or there are fundamental limits to the declarative features of the spreadsheet model, beyond which they become imperative.

I think the answer is a bit of both. Spreadsheet users tend to not be trained software engineers, but they aren't idiots and basic programming is not rocket science. None-the-less, lots of spreadsheets end up with pervasive use of imperative features (which causes real problems in terms of maintainability)

So assuming a huge population of users are at least kind-of competent/intelligent, there appear to be fundamental limitations to the basic model, beyond which it can't be used to solve common problems effectively in a declarative way.

Which of course should be interpreted by those who really like spreadsheet programming as a call to arms (education and/or refinements to the model) rather than a categorical criticism...

The "underlying theme" of spreadsheets may be declarative, but declarative has very little relation to how real non-trivial spreadsheet-based apps are constructed.

Spreadsheets are a tool in which one motivated in that direction can do fairly pure, fairly complex, dataflow oriented programming -- but that's not generally what they are used for.

There is nothing wrong with your posts. It's just that recently the understanding of what downvotes mean changed drastically in the community.

I've no idea why and when it happened, but downvotes now seem to mean "I disagree, but am too lazy to write a comment", instead of "your comment is not fit for this site and/or it damages the quality of current discussion" as it was understood before.

Macro is not part of the spreadsheet computation model. It's like saying a FFI library written in C for Haskell somehow makes Haskell a stateful language.

Relative reference declares a dependence relationship. That's part of what declarative programming is.

Macros are used pervasively.

To use your analogy, it's like writing a lambda calculus interpreter with an FFI, doing everything via the FFI, and calling it declarative.

But macros are only part of the problem.

> That's part of what declarative programming is.

Sorry, I was constraining myself to the definition from the article.

I think your point is broader. It applies to spreadsheets, Prolog, SQL. A declarative system needs to be "contaminated" by non-declarative pragmas for real-world use. (I think OP made this point.) To do something faster, or to do it at all.

SQL is a good example. You can get the desired output from a variety of queries... some of which might complete an order of magnitude slower than others. At some point you will need to peel back the "what" abstraction and consider the "how" -- what execution plan will the engine make for a given query.

Regardless, it's still a win. Even if it is no longer purely declarative, you still have leverage. i.e. You're expressing the solution concisely and with satisfactory performance, both.

I think you've confused what mutable state is. The cell values entered by a user are input values. The derived value of a cell bases on the computation of other cells, which is not changed once computed. When a user changes an input value in a cell, a new round of computation of the whole spreadsheet is started. The input value are not mutable state during computation. The modal of computation of a spreadsheet is pretty much stateless.

The computation between cells are done by the declaring formulas and cell dependency. The order of computation or how the computation is carried out is not specified, which is what declarative programming is.

The input cells and derived cells are pretty much like the tables and computed views in a RDBMS, where SQL is a declarative language to define the view.

> I think you've confused what mutable state is.

Absolutely not.

Macros provide shared mutable state. Macros are used pervasively in spreadsheet programming. You cannot carte blanc ignore macros without some serious explanation.

> The modal of computation of a spreadsheet is pretty much stateless.

Relative references means semantics depend on code layout, which in most hygenic circumstances is an old-school GOTO. In truly awful uses, relative references recover the sort of code layout dependencies which even C avoids. This can definitely be even worse than shared mutable state.

Even if macros and for loops "contaminate" the declarativeness and are unavoidable at scale, it's very easy to analyze the core of spreadsheet logic from the referentially transparent point of view of dataflow programming. The problem is that the direct view of a spreadsheet does not show this layer, even if it is what people program.

Spreadsheets are a small, mostly applicative language with references. We can ignore the "grid" presentation as it's just an easy way to examine the values of each of these references. Instead, we just say that a spreadsheet program is a collection of named formulae in this language where the references each refer to the names of one of the formulae. A program is well-formed if all references have a target.

Evaluation of a spreadsheet language involves seeking a fixed-point of this collection of formulae. If the formulae are not well-formed then their evaluation may become "stuck". If all references are targeted then the spreadsheet may diverge. Generally, both of those cases are uninteresting and we seek convergent programs.

Spreadsheet programs are finally displayed by iterating their formulae to convergence and displaying the result of every formula at once in a grid.

---

If you think about spreadsheets as having the denotation I just described then they are referentially transparent, have a well-defined notion of "variable" as opposed to "assignable", have (restricted) beta equivalence, have a denotational semantics, talk about "what, not how", and, if you do some analysis to find the connected components of your dataflow graph, are implicitly parallelizable.

I'm familiar with this characterization. I just don't think it's representative of realistic spreadsheet programming (edit: or many existing implementations).

Here's an excellent quote from the conclusion of a paper on the topic stating exactly this viewpoint (and they aren't even referring to macros afaict) [1]:

Current spreadsheet implementations do not strictly follow any of the established conceptual models. They rather follow a teleological approach of “what the user probably intends to do”. But phrases containing the word “probably” are problematic as they do not hold for all situations. This poses a challenge for education. If limits and “critical factors” remain unnoticed or misconceived, spreadsheet quality is seriously impacted.

[1] http://arxiv.org/pdf/0801.4274.pdf

I'm not claiming that this is a complete characterization, but instead the core conceit. I don't think it would be hard to extend the core model to include things like macros or for loops.

Mostly "declarative" by whatever definition you choose is still an interesting characterization.

> Declarativeness is a property of code which subsumes what professional developers typically refer to as functional and purely functional code. While real world applications don't allow us to solely rely on declarative code to solve all of our problems, we can embrace its positive qualities and learn to overcome its shortcomings by following two basic approaches: embedding and extending.

I like the balanced conclusion. So as I understand it,languages like Haskell(which I dont know) wrap states into a type that can be passed to pure functions right?is that what monads are about? A bit like promises in javascript where the developpers wraps an eventual outcome into an object and can reason about his code without worrying about what the value will be or even if the value will be at all?

More generally,how one does remove side-effects from OO code?since objects are statefull,or is the solution not using OO at all?

A more paradigm-neutral notion of declarativity is that you separate intent (the function or relation that your program is to compute) from execution (the shoveling of bits that goes on in the actual execution of the program).

For example, SQL or LinQ are declarative fragments embedded in an otherwise imperative/OO language, since you specify the intent, and behind the scenes, the database's query optimizer or the LinQ API can do all the optimizations they like because you've specified your intent and not a concrete plan for execution.

In Haskell, treating state as data to be passed around has the advantage that you can also fork the state if you want to try out alternatives (i.e., search).

Which means, you don't remove side-effects from OO code. You institute a contract between some provider of a declarative framework (that allows you to specify intents) and the consumer of said framework (who is supposed not to poke around in any state that the framework works on).

I.e. state is seen in functional programming as undocumented API calls in imperative programming. In rare cases you need them, but you want to only use them where you actually get an advantage out of it, because it's bound to get in your way at some point if you're not careful.

> So as I understand it,languages like Haskell(which I dont know) wrap states into a type that can be passed to pure functions right?

I would restate this as: "In Haskell you write a description of a stateful computation." The "State Monad" is really just the illusion of mutable state, provided by passing the underlying state to each described computation. Actually-mutable state is possible with things like IORef, but these are impure.

You could also say it's just an implementation of mutable state. The "State" type and its operations are just a few lines of simple Haskell code. The implementation uses parameters and return values to thread state between functions. It's just a simple abstraction of a simple pattern of programming. It uses a monadic interface, which is convenient and gives you some syntactic sugar, but there's nothing magical about it.

From the Haskell point of view, so called "actually-mutable" state is on the other hand deeply magical, because it lets you do exotic things like having one thread modify a value in another thread. And that's possible through things like IORefs. But it should be avoided as much as possible.

Really I just wanted to point out that the State Monad is not actually hiding any "real" mutation anywhere, nor is it related to the IO Monad- I was confused on this point for some time when learning Haskell.

Haskell actually lacks named state (in its safe world), meaning state is just a value to be passed around and returned. You can then index off of this state, but these names are then qualified.

OOP is all about naming: objects encapsulate state, have identities if they are aliased, are thought of by humans in terms of nouns, have ontological is-a and has-a relationships, and so on. If it is just referential transparency you are after...then there are solutions for OOP (that also don't involve monads), but it requires a different programming model:

http://research.microsoft.com/apps/pubs/default.aspx?id=2112...

CSS should be a very good example...

CSS is a markup though and not a Turing complete language.

EDIT: Turns out that HTML5 + CSS3 are in fact accidentally Turing complete http://beza1e1.tuxen.de/articles/accidentally_turing_complet.... Regardless, it's still only accidentally Turing complete.

Reply on news.ycombinator.com