[dcre]

This paper was very influential on me when I first started programming professionally around 2012. I don't plan on reading it again, but my vague memory of what I got out of it is pretty simple and I think has become pretty standard practice at this point: avoid mutable state and use pure functions where possible.

The framing of accidental and essential complexity is of course very useful and not really unique to this paper. The difficulty is there is nothing but experience-informed judgment that can tell you which complexity is accidental and which is essential. There is always a framing of the problem that can justify some bit of complexity as essential. You have to judge.

[feoren]

Plenty of state -- even mutable state -- is essential complexity. Think of an IDE where a user is typing out code: the state is changing all the time. Pure functional programming has a hard time walking the line between "avoiding" mutable state, and "ignoring" mutable state. If you insist on functional purity, you're already admitting defeat in the face of essential mutable state. The walls of functional (and especially reactive) programming are too high -- they currently don't play very well with their Turing and von Neumann neighbors.

Functional programming is only "mathematically pure" because we already have math for it. You can make mutating state "mathematically pure" too, if you just invent new math for it. For example, you can pair state with a "generation" variable and define mutating functions as returning the new state with generation + 1; now all your functions are pure again. That's not all it takes, and it's not easy! But it shows how narrow-minded the current idea of "purity" is.

[mrkeen]

> Think of an IDE where a user is typing out code: the state is changing all the time.

That's easy mode. Mutability is often justifiable when one person is doing one thing to a computer at a time. Now extrapolate to multiple people editing the same document at once. Suddenly you're discussing CRDTs and other approaches. And now implement undo on top of that!

Likewise with git, or blockchain, or kafka. They're persistent logs so you can keep your head straight while figuring out what the current state(s) of the system can be. Even with git, when you do an in-place mutation (force-push) there's still an extra log (reflog) behind the scenes trying to keep the changes sane.

[feoren]

I think this is a good example of why "simple CRUD systems" are actually much more complex than people usually give them credit for. Anything seems easy if you do it badly. But multiple people editing a document at once with CRDTs and undo is still even easier than a basic CRUD application done properly: now you have multiple people editing multiple different data types at once! In such cases we should be thinking about building CRDTs over all the various operations users may be doing with the data, which means thinking about associativity and commutativity of generic data operations. Git only has to deal with merging text files line by line; CRUD applications have to deal with merging lots of different data types!

[kccqzy]

There is no essential mutable state in computer science. All essential mutable state can be modeled away to use no mutable state, as you have shown in the generation number idea which is one valid way. (I'm strictly talking about computer science problems not computer engineering problems such as drivers.)

The generation number idea you have shown is an excellent idea. It immediately enables several new capabilities compared with just mutation:

* You are now able to determine which data is older and which is newer without resorting to an external clock.

* If your mutation takes a long time, there is no longer a need to use a long-held mutex to ensure thread safety which would prevent concurrent reads; you can create a new generation separately and then atomically CAS it. Writers don't block readers.

* If you suddenly need undo/redo functionality, it's suddenly trivial. Or diff'ing between versions. Or understanding the reason for changes (basics of auditing).

[layer8]

> All essential mutable state can be modeled away to use no mutable state

However, that modeling introduces complexity of its own that not everyone agrees is entirely essential.

[feoren]

Engineering is about tradeoffs. There is no One Model To Rule Them All. Your post is a great thing to keep in mind, but it's not a prescription. Engineers need to be able to look at a problem from many points of views at once, and try to find the right path for their current problem. This is why it's so important that models play nicely with one another, something that functional programming is getting better at, but reactive programming still really struggles with.

All of your asterisked points are well-taken, but: do you need that capability? Sometimes; sometimes not.

[enlyth]

> There is no essential mutable state in computer science.

Yes, theoretically. Now imagine your mutable state is 2GB in size, have fun creating a copy of it on every change.

[kccqzy]

You are not getting the point of my comment or the original article. It's clear to me that the kind of complexity being talked about in the article is cognitive complexity not computational complexity. It's not about choosing between an O(n) copying of data and O(1) in-place mutation; it's about choosing code that's easy to comprehend and maintain.

[deathanatos]

Their point is that you can't choose the cognitively simpler choice because of real world design constraints, such as not consuming all available RAM — i.e., because of essential complexity.

[kragen]

that's complexity introduced by your approach to the solution (using an inadequately large computer) rather than essential to the problem you're trying to solve

[raatuter]

Immutable data structures are often implemented as persistant data structures, which have the traits of immutability but does not "copy everything on every change" https://en.wikipedia.org/wiki/Persistent_data_structure

[pletnes]

Btrfs does stuff like instantaneous snapshots for a multi terabyte size filesystem. I have no idea how they do it, but apparently it’s 100% possible.

[waynesonfire]

Well since it's claiming to not mutate state, it must be simple! Go read the code and tell us what you learn.

In the event you find the source code TLDR, indeed it seems implementing an immutable api is complex.

[akimball]

The optimizer removes that.

[kilgnad]

To see immutability on huge state in action see git.

That is essentially what must be going on under the hood to model mutable state. Every mutation made to a variable is a commit. The only commits that are saved are the ones that have existing references.

Now you're thinking it could be a big memory leak. But you pair this with reference counting you can eliminate the leak.

Essentially when the reference of the earliest commit goes out of scope, the next earliest commit is checked out as the initial root commit and the current commit is freed.

The memory model is then like a moving git window/linked list. Mutations are committed at the tail end while memory is freed at the head.

[kilgnad]

Lambda calculus machines can't exist in reality though. Only the von Neumann machine can be actualized.

Thus from a practical perspective the foundations of actual computing must be built on mutable state.

You are wrong about the generations idea. It's a side effect. Functions themselves cannot actually do anything with a generation number. It's completely useless other then for letting you know how many times a value has changed.

A generation number also doesn't negate the need for mutexes. The system is still operating on shared state, a generation number doesn't change this.

[kccqzy]

You are not getting the point of either my comment or the original article. You are thinking from an engineering point of view, where if you look through all the layers of abstraction you see mutexes and shared mutable memory. That's not my point; my point is about building up those abstractions so they are sufficiently hidden. Functional programmers routinely operate on a higher level of abstraction, and they have shorter, more maintainable code. In such code, it would be a code smell if you continue to use mutexes, because that should've been an implementation detail. It should've been clear from the outset that the kind of complexity the article is talking about is cognitive complexity.

[kilgnad]

I am getting it. I am simply saying that you can't completely hide those details. They leak through.

[cubefox]

I always thought the problem with a "purely" functional view is much more practical: From my limited Haskell experience, I gather that you have to use recursion instead of loops, since loops (and GOTOs) work by iteratively modifying some state, unlike recursion. But humans think in loops. If you look in a cookbook for a recipe, it will almost certainly contain loops and rarely any recursions.

Recursion programs are provably Turing equivalent to WHILE or GOTO programs, but that doesn't mean they are equally natural for our brain to think about. (Not to mention things like tail recursion, which is even less intuitive.)

[dannyobrien]

I definitely don't think in terms of recursion (and I don't think I've seen it explicitly in a recipe!), but I'm not sure loops and interation are necessarily that intuitive, either. I learned programming at an early age and I still distinctly remember the period when loop constructs "made sense".

I can believe that recursion is even less easy to teach than iteration, but it may be that this is a pedagological issue, or that we have yet to work out the best way to convey or document computation.

[cubefox]

Many recipes contain WHILE loops. E.g. while the pan is not full, layer meat sauce, lasagna noodles, and bechamel sauce. FOR loops (do the x process 10 times, or once for everything in a list) are also prefectly natural. Examples for recursion are not as easy to find. This points to recursion itself being harder for us than loops. Understanding loops in recipes doesn't require pedagogical attention.

[mpweiher]

> Plenty of state -- even mutable state -- is essential complexity.

Arguably most of it!

After all, computer don't compute.

https://www.youtube.com/watch?v=EKWGGDXe5MA&t=297s

One of the miseries of life is that everyone names everything a litte bit wrong, and so it makes everything a little harder to understand in the world than it would be if it were named differently. A computer does not primarily compute in the sense of doing arithmetic. Strange. Although they call them computers, that's not what they primarily do. They primarily are filing systems. People in the computer business say they're not really computers, they are "data handlers". All right. That's nice. Data handlers would have been a better name because it gives a better idea of the idea of a filing system.

[dagss]

Related: The Norwegian word for "computer" is "datamaskin". Or, "data machine".

[SilasX]

And in the Romance languages, some variant of “ordinator”, meaning someone who orders, regulates, or arranges, closer to the tasks we actually expect of computers.

[ergeysay]

Not to mention that pure FP completely handwaves away implicit global state such as heap.

[kilgnad]

That's the point. This hand waving allows the user to build more complex systems.

The cost is efficiency but make no mistake not thinking about the heap allows people to build much more complex programs. It's a trade off between complexity and efficiency.

[cubefox]

Then could it reversely be argued that not worrying about the stack (tail recursion) allows people to build more complex programs? Probably depends on which is more worrisome on average, heap or stack.

[akimball]

Au contraire. It is a tradeoff between application programmer effort and compiler writer effort. Amortization infers it is better to have an extremely advanced IR optimizer.

[kilgnad]

Then why do zero cost abstractions exist? Languages like rust and C++ make the trade off on the application side rather then the compiler side.

[bitwize]

Ah, but if you model the mutable state as a function taking prior state to new state (and no cheating and modeling it as World -> World), you can constrain and control it into something you can reason about. You're one step closer to taming the dragon of chaos, bucko!

[lucasdicioccio]

IMHO in the context of the Tar-Pit Paper (programming for services and applications rather than electronics) mutation merely is a mean to an end. The end being: some piece of memory holds the value I expect (e.g., to transmit, store, show information). Thus I disagree that mutable state is essential complexity. For the rest of the post I don't understand what you mean with "walking the line between avoiding/ignoring mutable state" and I wish you ad elaborated about what you mean by "play very well with Turing neighbors" because I cannot really connect with that.

Regarding, functional programming and mutation. In a typed "pure-FP" language like Haskell: - you need to explicitly declare what constitutes a valid value - which drives what valid values are observable between program steps - which informs how corrupted a data-structure can be in your program

For instance, using a tree-shaped structure like `Tree1 = Leaf Int32 | Node Int32 Tree1 Tree1` and you have some `MutableRef (Tree1)`. You know exactly that from the ref you can read a whole Tree1, you can change the content of the MutableRef but you need to give a whole new Tree1. In particular, you are sure to never read "an half-initialized tree" or "a tree that was changed while I was reading it" because these things just do not exist in the realm of valid Tree1s. Such simple guarantees are really important to many programs but are not guaranteed in most programming languages.

Of course, if for some reason (e.g., for performance) you need something more flexible and are willing to pay the extra complexity, you can do it. As an illustration, you can augment your Tree1 with some MutableRef as well. `Tree2 = Leaf Int32 | Node Int32 Tree2 Tree2 | Cell (MutableRef Tree1)`. Here Tree2 contains mutable references to a valid Tree1 so Tree2 is not fractally complicated but you could do that too. With Tree2, you can interleave reads, writes, and other operations while working on a Tree2. These extra effects could be required (for performance reasons for instance) at the expense of inviting surprising behaviors (bugs). In pure-FP it is clear that with Tree2 we lost the possibility to "read/write a whole tree in a single program step". Thus, if the control flow of the code is not linear (e.g., multi-threaded, callback-heavy) you may have fun things occurring, like printing a half of the tree at a given time and the second half of the tree after a mutation, resulting in printing a tree that never existed. Enforcing global properties like the heap-invariant becomes inconvenient because it is actually hard if we let mutation in. I'd go as far as saying that the Tree2 doesn't exist as a tree: given a Tree2 we are merely capable of enumerating chunks with tree-shapes piecewise.

This reply is long already, so I won't go into how Haskell has various flavors of mutable refs in IO, ST, STM and recently even got linear-types to allow some fine-grained composition-of-atomic-mutations/interleaving/prevention of effects. But overall I find pure-FP takes mutability much more seriously than other more mainstream languages. Here, pure-FP just keeps us honest about where non-determinism bites. The collective failure to realize is one of the key reason why we are in The Tar-Pit: violated in-memory-invariants can compound even outside programs by forcing outside/future users to deal with things like misleading information being shown to users, urgently upgrading your fleet of servers, days of one-off data-cleanup and so on and so forth.

[kilgnad]

No. Pure functions are more modular. It allows you to treat your logic like bricks and building blocks. Pure functions are composable purely off of types. Combinators are actually the proper term here.

Mutable state does not do this. Your idea of generations doesn't make sense, because that means every function must take a generation as the input parameter too. Given a different generation number the function must deterministically create the same output.

It is not a complete system. Your equations produce this useless generation number that aren't reused as part of the system, it's just there for you and meta analysis.

That is not to say your first paragraph is completely wrong though. There is a trade off between modularity and efficiency. Mutating a variable is less resource intensive then generating a new variable.

[feoren]

> Pure functions are more modular. It allows you to treat your logic like bricks and building blocks.

Mathematical purity is indeed what allows you to treat your logic like bricks and building blocks. My point is that "a monad is a monoid in the category of endofunctors" is not the only "pure math" out there, and also that your domain model is likely the most impure part of your whole program. Functional programming is awesome! But mostly ignores the existence of essential mutable state, and embracing functional programming is only a small part of the "mathematical purity" struggle that is indeed the only way to build truly reusable building blocks. If you're spending lots of time building clean, pure, mathematical data manipulation logic, but the data you're manipulating is "Dog : Animal" and "Cat : Animal", you're in a garbage in/garbage out situation. Worry about the mathematical purity of your data model itself. It will marry and dance and harmonize with the purity of your functional logic!

> Mutating a variable is less resource intensive then generating a new variable.

Not always.

[jameshart]

For anyone who is not aware, 'accidental and essential complexity' were coined in Fred Brooks' 1986 paper No Silver Bullet.

[hcrisp]

Chapter 1 of The Mythical Man Month by the same author is called "The Tar Pit" and has this memorable opening paragraph:

> No scene from prehistory is quite so vivid as that of the mortal struggles of great beasts in the tar pits. In the mind's eye one sees dinosaurs, mammoths, and sabertoothed tigers struggling against the grip of the tar. The fiercer the struggle, the more entangling the tar, and no beast is so strong or so skillful but that he ultimately sinks.

> Large-system programming has over the past decade been such a tar pit, and many great and powerful beasts have thrashed violently in it...

[dcre]

I was very curious about this claim and it seems that's not quite right. Of course the phrase "essential complexity" was applied to non-software topics before Brooks (Wikipedia correctly notes that the distinction between essence and accident goes back to Aristotle), but it seems Brooks was not the first to apply it to software either. I would not deny that he popularized it.

Book search results for "accidental complexity" between 1920 and 1985: https://www.google.com/search?q=%22accidental+complexity%22&...

Book search results for "essential complexity" between 1920 and 1985 (a lot more results): https://www.google.com/search?q=%22essential+complexity%22&l...

Here's a publication from 1981 defining "essential complexity" specifically with reference to computer programs. https://www.google.com/books/edition/Validation_Verification...

Note that there's another result that claims to be from 1968 but the text of the book says it's from 1996.

Interestingly "essential complexity" was used earlier and more often than "accidental complexity", probably because the former sufficiently implies the existence of the latter.

https://books.google.com/ngrams/graph?content=essential+comp...

[eternityforest]

My experience has shown almost all of it to be essential except the stuff that is very obvious "Programmers playing with stuff that seems cool".

Once you account for hardware errors, human errors, respecting the user's time, compatibility with different file formats, multiplatform support, and the limited resources developers have, etc, most programs seem like they couldn't be any simpler while still being something I want to use.

Or, they potentially could, but nobody would pay enough to justify the extra time it would take.

Which is why I don't complain that Etcher is 99MB. It's like conceptual art, Yes, you could do it smaller, but you didn't, and I don't want to because I can just use the existing thing and move on, and I wouldn't pay for a lighter version when the heavier thing is free.

I just don't see all that much disappointing software in the commerical space at least.

[gatane]

While programming in FORTH, you have a similar advice: avoid stack mumbling (aka copy and store ops).

But sometimes all that stack changes could be avoided by using a temp register.