Comment by lliwta | Hacker News Reader

Comment by lliwta | Hacker News Reader

Parent Full thread

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.

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.

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

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.

Reply on news.ycombinator.com